運(yùn)籌學(xué)第九章 網(wǎng)絡(luò)計(jì)劃課件

運(yùn)籌學(xué)趙明霞山西大學(xué)經(jīng)濟(jì)與管理學(xué)院運(yùn)籌學(xué)趙明霞第九章網(wǎng)絡(luò)計(jì)劃

網(wǎng)絡(luò)計(jì)劃圖時間參數(shù)的計(jì)算

網(wǎng)絡(luò)計(jì)劃優(yōu)化2第九章網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃圖2通過重組,打亂,優(yōu)化等手段改變原本的固有辦事格式,優(yōu)化辦事效率的一種辦事方法。一種安排工作進(jìn)程的數(shù)學(xué)方法。它的實(shí)用范圍極廣泛，在企業(yè)管理和基本建設(shè)中，以及關(guān)系復(fù)雜的科研項(xiàng)目的組織與管理中，都可以應(yīng)用。我國，是從20世紀(jì)60年代開始運(yùn)用網(wǎng)絡(luò)計(jì)劃的，著名數(shù)學(xué)家華羅庚教授結(jié)合我國實(shí)際，在吸收國外網(wǎng)絡(luò)計(jì)劃技術(shù)理論的基礎(chǔ)上，將CPM、PERT等方法統(tǒng)一定名為統(tǒng)籌法。統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)。統(tǒng)籌方法3通過重組,打亂,優(yōu)化等手段改變原本的固有辦事格式,優(yōu)化辦事效統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序（或稱為活動）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。例9.1某公司研制新產(chǎn)品的部分工序與所需時間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表如表所示，請畫出其網(wǎng)絡(luò)計(jì)劃圖。工序代號工序內(nèi)容所需時間（天)緊前工序abcde產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)外購配套零件外購生產(chǎn)原料自制主件主配可靠性試驗(yàn)601513388-aacb,d第一節(jié)網(wǎng)絡(luò)圖4統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表點(diǎn)表示一個事件,是一個或若干個工序的開始或結(jié)束,是相鄰工序在時間上的分界點(diǎn),點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號?；”硎疽粋€工序（或活動），弧的方向是從工序開始指向工序的結(jié)束，弧上是各工序的代號，下面標(biāo)以完成此工序所需的時間（或資源）等數(shù)據(jù)，即為對此弧所賦的權(quán)數(shù)．2022/11/175.--線性規(guī)劃--線性規(guī)劃解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表2022/11/125.--１２４５３abcde601383815圖16１２４５３abcde601383815圖16

例9.2

把例1的工序進(jìn)度表做一些擴(kuò)充，如表，請畫出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。工序代號所需時間（天）緊前工序工序代號所需時間（天）緊前工序abcd60151338－aacefgh810165b，ｄdde，ｆ，ｇ7例9.2把例1的工序進(jìn)度表做一些擴(kuò)充，如表，請畫出其統(tǒng)解：虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時間。152643a60b158e1013dc38f圖28解：虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來表示相鄰工序的銜在網(wǎng)絡(luò)圖上添加ｇ、ｈ工序得網(wǎng)絡(luò)圖3。

在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個點(diǎn)之間多于一條弧，因此增加了一個點(diǎn)和虛工序如圖4。b1256734a6015ec13d388h510fg16圖39在網(wǎng)絡(luò)圖上添加ｇ、ｈ工序得網(wǎng)絡(luò)圖3。b1256734a601在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時，要注意圖中不能有缺口和回路。161257834a6015bec13d388h510f6g圖4避免交叉節(jié)點(diǎn)標(biāo)號：j>iij10在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時，要注意圖中不能有缺口和回路。161第二節(jié)時間參數(shù)的計(jì)算在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出：1、完成此工程項(xiàng)目所需的最少時間。2、每個工序的開始時間與結(jié)束時間。3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。4、非關(guān)鍵工序在不影響工程的完成時間的前提下，其開始時間與結(jié)束時間可以推遲多久。11第二節(jié)時間參數(shù)的計(jì)算11一、工作時間t(i,j)確定型概率型缺乏統(tǒng)計(jì)來確定完成每個活動所需時間，但對所需時間做了三種估計(jì)：1.樂觀時間。指所需最少時間，用a表示。2.最可能時間。指正常時間，用m表示。3.悲觀時間。指不順利情況下，最多時間，用b表示。2022/11/1712一、工作時間t(i,j)確定型2022/11/121活動樂觀時間最可能時間悲觀時間abcdefghi1.52.01.01.50.51.03.03.01.52.02.52.02.01.02.03.54.02.02.56.03.02.51.53.07.05.02.5例9.3

2022/11/1713活動樂觀時間最可能時間悲觀時間a1.

顯然這三種完成活動所需時間都具有一定概率，由經(jīng)驗(yàn)，我們可以可以假定這些時間的概率分布近似服從分布。我們可以用如下公式計(jì)算出完成活動所需的：方差平均時間例如：完成工作g所需平均時間：同時求出方差為14顯然這三種完成活動所需時間都具有一定概率，由經(jīng)驗(yàn)，我

同樣可以求出每個活動的完成所需平均時間及方差活動T（平均時間）方差活動T方差a20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.02815同樣可以求出每個活動的完成所需平均時間及方差活動T（平均時1、最早時間從網(wǎng)絡(luò)的發(fā)點(diǎn)開始，按順序計(jì)算出每個工序的最早開始時間（ES)和最早結(jié)束時間（EF)工序a的最早開始時間工序a的最早完成時間ija[0，60]60二、時間參數(shù)161、最早時間工序a的最早工序a的最早ija[0，60]60二1236785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]1841015例9.42022/11[0,60]60b[60,105]45e[62、最晚時間從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算，在不影響整個工程最早結(jié)束時間的情況下，各個工序的最晚結(jié)束時間（LF)和最晚開始時間(LS)工序a的最晚開始時間工序a的最晚完成時間ij[0，60]a2022/11/17182、最晚時間從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算，在不影響整個工程最早結(jié)束時

1236785a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,135191236785a[0,60]60[0,60]b[60,101、總時差在不影響工程最早結(jié)束時間的條件下，工序最早開始（或結(jié)束）的時間可以推遲的時間，成為該工序的總時差R三、時差2022/11/17201、總時差三、時差2022/11/12202、單時差在不影響緊后工序最早開始時間的條件下，工序最早開始（或結(jié)束）的時間可以推遲的時間，成為該工序的單時差r2022/11/17212、單時差2022/11/1221四、關(guān)鍵工序，關(guān)鍵路線網(wǎng)絡(luò)中最長的路線就決定了完成整個工程所需的最少時間，這條路線稱為關(guān)鍵路線?？倳r差為0的工序?yàn)殛P(guān)鍵工序。2022/11/1722.--線性規(guī)劃--線性規(guī)劃四、關(guān)鍵工序，關(guān)鍵路線網(wǎng)絡(luò)中最長的路線就決定了完成整個工程所例9-12022/11/1723例9-12022/11/12232022/11/1724.--線性規(guī)劃--線性規(guī)劃2022/11/1224.--線性規(guī)劃--線性規(guī)劃2022/11/1725.--線性規(guī)劃--線性規(guī)劃2022/11/1225.--線性規(guī)劃--線性規(guī)劃例9.4

某公司裝配一條新的生產(chǎn)線，具體過程如表1,求：完成此工程的最少時間，關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開始時間和非關(guān)鍵工序在不影響工程完成時間的前提下，其開始時間與結(jié)束時間可以推遲多久？26例9.4某公司裝配一條新的生產(chǎn)線，具體過程如表1,求：完工序代號工序內(nèi)容所需時間（天）緊前工序abcdefghij生產(chǎn)線設(shè)計(jì)外購零配件下料、鍛件工裝制造1木模、鑄件機(jī)械加工1工裝制造2機(jī)械加工2機(jī)械加工3裝配調(diào)試60451020401830152535/aaaacdd,egb,i,f,h27工序代號工序內(nèi)容所需時間（天）緊前工序a生產(chǎn)線設(shè)計(jì)60/2712346785a60b45echj35ig1030d204025f18152812346785a60b45echj35ig1030d204

1236785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]1841015291236785a[0,60]60b[60,105]45e[

1236785a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,135301236785a[0,60]60[0,60]b[60,10

最后將各工序的時差，以及其他信息構(gòu)成工序時間表如表所示。這樣就找到了一條由關(guān)鍵工序a,d,g,i和j依次連接成的從發(fā)點(diǎn)到收點(diǎn)的關(guān)鍵路線。31最后將各工序的時差，以及其他信息構(gòu)成工序時間表如表所示完成工序所需時間不確定例9-22022/11/1732完成工序所需時間不確定例9-22022/11/12322022/11/17332022/11/12332022/11/1734.--線性規(guī)劃--線性規(guī)劃2022/11/1234.--線性規(guī)劃--線性規(guī)劃關(guān)鍵線路2022/11/1735關(guān)鍵線路2022/11/1235第三節(jié)網(wǎng)絡(luò)計(jì)劃優(yōu)化把串聯(lián)工作改為平行工作或平行交叉工作2022/11/1736第三節(jié)網(wǎng)絡(luò)計(jì)劃優(yōu)化把串聯(lián)工作改為平行工作或平行交叉工作2利用時差

總時差不影響最短工期，但影響后續(xù)工序的自由時間。

單時差不影響后續(xù)工序。2022/11/1737利用時差2022/11/12373.時間-資源優(yōu)化做法：

1）優(yōu)先安排關(guān)鍵工序所需的資源。

2）利用非關(guān)鍵工序的時差，錯開各工序的開始時間。

3）適當(dāng)延長時差大的工序時間，或切斷非關(guān)鍵工序進(jìn)程。2022/11/17383.時間-資源優(yōu)化做法：2022/11/12382022/11/17392022/11/12392022/11/17402022/11/12402022/11/17412022/11/12414.工期—成本優(yōu)化直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、設(shè)備和工作班次，這需要增加一筆費(fèi)用，成為直接費(fèi)用。間接費(fèi)用：由于工程早日完工，減少了管理人員的工資辦公費(fèi)等費(fèi)用稱為間接費(fèi)用。一般說工序越短，直接費(fèi)用越多，間接費(fèi)用越少。2022/11/1742.--線性規(guī)劃--線性規(guī)劃4.工期—成本優(yōu)化直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、

工序的最快完成時間：指完成時間的最高限度。我們設(shè)完成工序j的正常所需時間為Tj;直接費(fèi)用為cj;完成工序j的最快完成時間為T`j,直接費(fèi)用為c`j。這樣我們可以計(jì)算出縮短工序j的一天工期所增加的直接費(fèi)用，用kj表示，稱為直接費(fèi)用變動率（成本斜率）。有43工序的最快完成時間：指完成時間的最高限度。43模型一，在既定的時間T完工的前提下，問各工序的完成時間為多少才使因縮短工期而增加的直接費(fèi)用最少。設(shè)工序（i,j)的提前完工時間為yij,我們用Tij,T`ij分別表示正常完工時間與最快完工的時間，則有工序（i,j)的實(shí)際完工時間為：Tij-yij

。我們用Cij,C`ij表示用正常完工時間和最快完成時間完成工序所需要的費(fèi)用，kij為工序（i,j)的直接費(fèi)用變動率（成本斜率）。44模型一，在既定的時間T完工的前提下，問各工序的完成時間為多少方法一：線性規(guī)劃法S.t.xj-xiTij-yij,對一切弧（i,j)yijTij-T`ij,對一切?。╥,j)xn-x1T,

xi0，yij0。45方法一：線性規(guī)劃法45例9.5例4所提供的信息都作為本例的信息，另外還給出了在裝配過程中各道工序所需正常完工時間與最快完工時間，以及對應(yīng)正常完工時間與最快完工時間的所需的直接費(fèi)用和每縮短一天工期所需增加的直接費(fèi)用，如表所示。46例9.5例4所提供的信息都作為本例的信息，另外還給出了在工序Tij正常完工Cij直接費(fèi)用T`ij最快完工C`ij直接費(fèi)用直接費(fèi)用變動率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-2022/11/1747.--線性規(guī)劃--線性規(guī)劃工序Tij正常完工Cij直接費(fèi)用T`ij最快完工C`ij直接該工程要求在150天內(nèi)完工，問每個工序應(yīng)比正常完工時間提前多少天完成，才能使整個工程因縮短工期而增加的直接費(fèi)用為最少。如果工期要求在140天完工呢？b12345678afechgijd48該工程要求在150天內(nèi)完工，問每個工序應(yīng)比正常完工時間提前多解：設(shè)此網(wǎng)絡(luò)圖上第i點(diǎn)發(fā)生的時間為xi，工序提前完工的時間為yij。minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t.x2-x160-y12,x7-x245-y27x3-x210-y23x4-x220-y24x5-x240-y25x7-x318-y37x6-x430-y46x5-x40

x7-x515-y57x7-x625-y67

x1=0

x8150

y120y2715y235y2410y255y378y4610y575y780xi0，yij0.（對一切可能的ij)運(yùn)算得到結(jié)果：f=6400。49解：設(shè)此網(wǎng)絡(luò)圖上第i點(diǎn)發(fā)生的時間為xi，工序提前完工的時間為方法二：統(tǒng)籌法從關(guān)鍵工序中找成本斜率最小的工序，壓縮工期；重新計(jì)算關(guān)鍵路線和關(guān)鍵工序；再重復(fù)循環(huán)1和2，直至達(dá)到壓縮工期要求；計(jì)算增加的總直接費(fèi)用50方法二：統(tǒng)籌法50模型二，我們知道直接費(fèi)用是隨著完成時間的縮短而增加，而間接費(fèi)用卻會隨著完成時間的縮短而減少，設(shè)單位時間的間接費(fèi)用為d,計(jì)劃期的間接費(fèi)用與總工期成正比，即為d(xn-x1)。那么求使包括間接費(fèi)用與直接費(fèi)用在內(nèi)的總費(fèi)用最少的整個工程最優(yōu)完成時間T和各個工序最優(yōu)完成時間的模型為：

s.t.xj-xiTij-yij，對一切?。╥,j)yijTij-T`ij，對一切?。╥,j)xi

0，yij0。51模型二，我們知道直接費(fèi)用是隨著完成時間的縮短而增加，而間接費(fèi)

例9.6如果在例5中，每天的間接費(fèi)用為330元，求使包括間接費(fèi)用與直接費(fèi)用在內(nèi)的總費(fèi)用最少的整個工程最優(yōu)完成時間T和各個工序最優(yōu)完成時間。解：minf=330(x8-x1)+120y27+300y23+400y24+500y25+230y37+350y46+290y67

s.t.x2-x160-y12,x7-x245-y27x3-x210-y23x4-x220-y24x5-x240-y25x7-x318-y37x6-x430-y46x5-x40

x7-x515-y57x7-x625-y67

x1=0y120y2715y235y2410y255y378y4610y575y780xi0，yij0.（對一切可能的ij)52例9.6如果在例5中，每天的間接費(fèi)用為330元，求使包

f=55700.x1=0,y12=0,y67=10,

x2=60,y27=0,y78=0.x3=125,y23=0,

x4=107,y24=0,

x5=110,y25=0,

x6=110,y37=0,

x7=125,y46=0,

x8=160,y57=0,

也就是說整個工程工期為160天時總費(fèi)用最少為124600元，各個工序開始時間如解所示，工序i要提前10天完工，其余的工序按正常時間完工。53f=55700.53例9-354例9-35455552022/11/17562022/11/12562022/11/1757.--線性規(guī)劃--線性規(guī)劃2022/11/1257.--線性規(guī)劃--線性規(guī)劃習(xí)題9.4（1）9.59.79.858習(xí)題9.4（1）58運(yùn)籌學(xué)趙明霞山西大學(xué)經(jīng)濟(jì)與管理學(xué)院運(yùn)籌學(xué)趙明霞第九章網(wǎng)絡(luò)計(jì)劃

網(wǎng)絡(luò)計(jì)劃圖時間參數(shù)的計(jì)算

網(wǎng)絡(luò)計(jì)劃優(yōu)化60第九章網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃圖2通過重組,打亂,優(yōu)化等手段改變原本的固有辦事格式,優(yōu)化辦事效率的一種辦事方法。一種安排工作進(jìn)程的數(shù)學(xué)方法。它的實(shí)用范圍極廣泛，在企業(yè)管理和基本建設(shè)中，以及關(guān)系復(fù)雜的科研項(xiàng)目的組織與管理中，都可以應(yīng)用。我國，是從20世紀(jì)60年代開始運(yùn)用網(wǎng)絡(luò)計(jì)劃的，著名數(shù)學(xué)家華羅庚教授結(jié)合我國實(shí)際，在吸收國外網(wǎng)絡(luò)計(jì)劃技術(shù)理論的基礎(chǔ)上，將CPM、PERT等方法統(tǒng)一定名為統(tǒng)籌法。統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)。統(tǒng)籌方法61通過重組,打亂,優(yōu)化等手段改變原本的固有辦事格式,優(yōu)化辦事效統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序（或稱為活動）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。例9.1某公司研制新產(chǎn)品的部分工序與所需時間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表如表所示，請畫出其網(wǎng)絡(luò)計(jì)劃圖。工序代號工序內(nèi)容所需時間（天)緊前工序abcde產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)外購配套零件外購生產(chǎn)原料自制主件主配可靠性試驗(yàn)601513388-aacb,d第一節(jié)網(wǎng)絡(luò)圖62統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表點(diǎn)表示一個事件,是一個或若干個工序的開始或結(jié)束,是相鄰工序在時間上的分界點(diǎn),點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號?；”硎疽粋€工序（或活動），弧的方向是從工序開始指向工序的結(jié)束，弧上是各工序的代號，下面標(biāo)以完成此工序所需的時間（或資源）等數(shù)據(jù)，即為對此弧所賦的權(quán)數(shù)．2022/11/1763.--線性規(guī)劃--線性規(guī)劃解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表2022/11/125.--１２４５３abcde601383815圖164１２４５３abcde601383815圖16

例9.2

把例1的工序進(jìn)度表做一些擴(kuò)充，如表，請畫出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。工序代號所需時間（天）緊前工序工序代號所需時間（天）緊前工序abcd60151338－aacefgh810165b，ｄdde，ｆ，ｇ65例9.2把例1的工序進(jìn)度表做一些擴(kuò)充，如表，請畫出其統(tǒng)解：虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時間。152643a60b158e1013dc38f圖266解：虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來表示相鄰工序的銜在網(wǎng)絡(luò)圖上添加ｇ、ｈ工序得網(wǎng)絡(luò)圖3。

在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個點(diǎn)之間多于一條弧，因此增加了一個點(diǎn)和虛工序如圖4。b1256734a6015ec13d388h510fg16圖367在網(wǎng)絡(luò)圖上添加ｇ、ｈ工序得網(wǎng)絡(luò)圖3。b1256734a601在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時，要注意圖中不能有缺口和回路。161257834a6015bec13d388h510f6g圖4避免交叉節(jié)點(diǎn)標(biāo)號：j>iij68在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時，要注意圖中不能有缺口和回路。161第二節(jié)時間參數(shù)的計(jì)算在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出：1、完成此工程項(xiàng)目所需的最少時間。2、每個工序的開始時間與結(jié)束時間。3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。4、非關(guān)鍵工序在不影響工程的完成時間的前提下，其開始時間與結(jié)束時間可以推遲多久。69第二節(jié)時間參數(shù)的計(jì)算11一、工作時間t(i,j)確定型概率型缺乏統(tǒng)計(jì)來確定完成每個活動所需時間，但對所需時間做了三種估計(jì)：1.樂觀時間。指所需最少時間，用a表示。2.最可能時間。指正常時間，用m表示。3.悲觀時間。指不順利情況下，最多時間，用b表示。2022/11/1770一、工作時間t(i,j)確定型2022/11/121活動樂觀時間最可能時間悲觀時間abcdefghi1.52.01.01.50.51.03.03.01.52.02.52.02.01.02.03.54.02.02.56.03.02.51.53.07.05.02.5例9.3

2022/11/1771活動樂觀時間最可能時間悲觀時間a1.

顯然這三種完成活動所需時間都具有一定概率，由經(jīng)驗(yàn)，我們可以可以假定這些時間的概率分布近似服從分布。我們可以用如下公式計(jì)算出完成活動所需的：方差平均時間例如：完成工作g所需平均時間：同時求出方差為72顯然這三種完成活動所需時間都具有一定概率，由經(jīng)驗(yàn)，我

同樣可以求出每個活動的完成所需平均時間及方差活動T（平均時間）方差活動T方差a20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.02873同樣可以求出每個活動的完成所需平均時間及方差活動T（平均時1、最早時間從網(wǎng)絡(luò)的發(fā)點(diǎn)開始，按順序計(jì)算出每個工序的最早開始時間（ES)和最早結(jié)束時間（EF)工序a的最早開始時間工序a的最早完成時間ija[0，60]60二、時間參數(shù)741、最早時間工序a的最早工序a的最早ija[0，60]60二1236785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]1841015例9.42022/11[0,60]60b[60,105]45e[62、最晚時間從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算，在不影響整個工程最早結(jié)束時間的情況下，各個工序的最晚結(jié)束時間（LF)和最晚開始時間(LS)工序a的最晚開始時間工序a的最晚完成時間ij[0，60]a2022/11/17762、最晚時間從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算，在不影響整個工程最早結(jié)束時

1236785a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,135771236785a[0,60]60[0,60]b[60,101、總時差在不影響工程最早結(jié)束時間的條件下，工序最早開始（或結(jié)束）的時間可以推遲的時間，成為該工序的總時差R三、時差2022/11/17781、總時差三、時差2022/11/12202、單時差在不影響緊后工序最早開始時間的條件下，工序最早開始（或結(jié)束）的時間可以推遲的時間，成為該工序的單時差r2022/11/17792、單時差2022/11/1221四、關(guān)鍵工序，關(guān)鍵路線網(wǎng)絡(luò)中最長的路線就決定了完成整個工程所需的最少時間，這條路線稱為關(guān)鍵路線?？倳r差為0的工序?yàn)殛P(guān)鍵工序。2022/11/1780.--線性規(guī)劃--線性規(guī)劃四、關(guān)鍵工序，關(guān)鍵路線網(wǎng)絡(luò)中最長的路線就決定了完成整個工程所例9-12022/11/1781例9-12022/11/12232022/11/1782.--線性規(guī)劃--線性規(guī)劃2022/11/1224.--線性規(guī)劃--線性規(guī)劃2022/11/1783.--線性規(guī)劃--線性規(guī)劃2022/11/1225.--線性規(guī)劃--線性規(guī)劃例9.4

某公司裝配一條新的生產(chǎn)線，具體過程如表1,求：完成此工程的最少時間，關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開始時間和非關(guān)鍵工序在不影響工程完成時間的前提下，其開始時間與結(jié)束時間可以推遲多久？84例9.4某公司裝配一條新的生產(chǎn)線，具體過程如表1,求：完工序代號工序內(nèi)容所需時間（天）緊前工序abcdefghij生產(chǎn)線設(shè)計(jì)外購零配件下料、鍛件工裝制造1木模、鑄件機(jī)械加工1工裝制造2機(jī)械加工2機(jī)械加工3裝配調(diào)試60451020401830152535/aaaacdd,egb,i,f,h85工序代號工序內(nèi)容所需時間（天）緊前工序a生產(chǎn)線設(shè)計(jì)60/2712346785a60b45echj35ig1030d204025f18158612346785a60b45echj35ig1030d204

1236785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]1841015871236785a[0,60]60b[60,105]45e[

1236785a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,135881236785a[0,60]60[0,60]b[60,10

最后將各工序的時差，以及其他信息構(gòu)成工序時間表如表所示。這樣就找到了一條由關(guān)鍵工序a,d,g,i和j依次連接成的從發(fā)點(diǎn)到收點(diǎn)的關(guān)鍵路線。89最后將各工序的時差，以及其他信息構(gòu)成工序時間表如表所示完成工序所需時間不確定例9-22022/11/1790完成工序所需時間不確定例9-22022/11/12322022/11/17912022/11/12332022/11/1792.--線性規(guī)劃--線性規(guī)劃2022/11/1234.--線性規(guī)劃--線性規(guī)劃關(guān)鍵線路2022/11/1793關(guān)鍵線路2022/11/1235第三節(jié)網(wǎng)絡(luò)計(jì)劃優(yōu)化把串聯(lián)工作改為平行工作或平行交叉工作2022/11/1794第三節(jié)網(wǎng)絡(luò)計(jì)劃優(yōu)化把串聯(lián)工作改為平行工作或平行交叉工作2利用時差

總時差不影響最短工期，但影響后續(xù)工序的自由時間。

單時差不影響后續(xù)工序。2022/11/1795利用時差2022/11/12373.時間-資源優(yōu)化做法：

1）優(yōu)先安排關(guān)鍵工序所需的資源。

2）利用非關(guān)鍵工序的時差，錯開各工序的開始時間。

3）適當(dāng)延長時差大的工序時間，或切斷非關(guān)鍵工序進(jìn)程。2022/11/17963.時間-資源優(yōu)化做法：2022/11/12382022/11/17972022/11/12392022/11/17982022/11/12402022/11/17992022/11/12414.工期—成本優(yōu)化直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、設(shè)備和工作班次，這需要增加一筆費(fèi)用，成為直接費(fèi)用。間接費(fèi)用：由于工程早日完工，減少了管理人員的工資辦公費(fèi)等費(fèi)用稱為間接費(fèi)用。一般說工序越短，直接費(fèi)用越多，間接費(fèi)用越少。2022/11/17100.--線性規(guī)劃--線性規(guī)劃4.工期—成本優(yōu)化直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、

工序的最快完成時間：指完成時間的最高限度。我們設(shè)完成工序j的正常所需時間為Tj;直接費(fèi)用為cj;完成工序j的最快完成時間為T`j,直接費(fèi)用為c`j。這樣我們可以計(jì)算出縮短工序j的一天工期所增加的直接費(fèi)用，用kj表示，稱為直接費(fèi)用變動率（成本斜率）。有101工序的最快完成時間：指完成時間的最高限度。43模型一，在既定的時間T完工的前提下，問各工序的完成時間為多少才使因縮短工期而增加的直接費(fèi)用最少。設(shè)工序（i,j)的提前完工時間為yij,我們用Tij,T`ij分別表示正常完工時間與最快完工的時間，則有工序（i,j)的實(shí)際完工時間為：Tij-yij

。我們用Cij,C`ij表示用正常完工時間和最快完成時間完成工序所需要的費(fèi)用，kij為工序（i,j)的直接費(fèi)用變動率（成本斜率）。102模型一，在既定的時間T完工的前提下，問各工序的完成時間為多少方法一：線性規(guī)劃法S.t.xj-xiTij-yij,對一切?。╥,j)yijTij-T`ij,對一切弧（i,j)xn-x1T,

xi0，yij0。103方法一：線性規(guī)劃法45例9.5例4所提供的信息都作為本例的信息，另外還給出了在裝配過程中各道工序所需正常完工時間與最快完工時間，以及對應(yīng)正常完工時間與最快完工時間的所需的直接費(fèi)用和每縮短一天工期所需增加的直接費(fèi)用，如表所示。104例9.5例4所提供的信息都作為本例的信息，另外還給出了在工序Tij正常完工Cij直接費(fèi)用T`ij最快完工C`ij直接費(fèi)用直接費(fèi)用變動率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-2022/11/17105.--線性規(guī)劃--線性規(guī)劃工序Tij正常完工Cij直接費(fèi)用T`ij最快完工C`ij直接該工程要求在150天內(nèi)完工，問每個工序應(yīng)比正常完工時間提前多少天完成，才能使整個工程因縮短工期而增加的直接費(fèi)用為最少。如果工期要求在140天完工呢？b12345678afechgijd106該工程要求在150天內(nèi)完工，問每個工序應(yīng)比正常完工時間提前多解：設(shè)此網(wǎng)絡(luò)圖上第i點(diǎn)發(fā)生的時間為xi，工序提前完工的時間為yij。minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t.x2-x160-y12,x7-x245-y27x3-x210-y23x4-x220-y24x5-x240-y25x7-x318-y37x6-x430-y46x5-x40

x7-x515-y57x7-x625-y67

x1=0

x8150

y120y2715y235y2410y255y378y4610y575y780xi0，yij0.（對一切可能的ij)運(yùn)算得到結(jié)果：f=6400。107解：設(shè)此網(wǎng)絡(luò)圖上第i點(diǎn)發(fā)生的時間為xi，工序提前完工的時間為方法二：統(tǒng)籌法從關(guān)鍵工序中找成本斜率最小的工序，壓縮工期；重新計(jì)算關(guān)鍵路線和關(guān)鍵工序；再重復(fù)循環(huán)1和2，直至達(dá)到壓縮工期要求；計(jì)算增加的總直接費(fèi)用108方法二：統(tǒng)籌法50模型二，我們知道直接費(fèi)用是隨著完成時間的縮短而增加，而間接費(fèi)用卻會