1、運籌學趙明霞山西大學經濟與管理學院運籌學趙明霞第九章 網絡計劃 網絡計劃圖 時間參數的計算 網絡計劃優化2第九章 網絡計劃 網絡計劃圖2通過重組,打亂,優化等手段改變原本的固有辦事格式,優化辦事效率的一種辦事方法。 一種安排工作進程的數學方法。它的實用范圍極廣泛，在企業管理和基本建設中，以及關系復雜的科研項目的組織與管理中，都可以應用。我國，是從20世紀60年代開始運用網絡計劃的，著名數學家華羅庚教授結合我國實際，在吸收國外網絡計劃技術理論的基礎上，將CPM、PERT等方法統一定名為統籌法。統籌方法包括繪制計劃網絡圖、進度安排、網絡優化等環節。統籌方法3通過重組,打亂,優化等手段改變原本的固有

2、辦事格式,優化辦事效 統籌方法的第一步工作就是繪制計劃網絡圖，也就是將工序（或稱為活動）進度表轉換為統籌方法的網絡圖。例9.1 某公司研制新產品的部分工序與所需時間以及它們之間的相互關系都顯示在其工序進度表如表所示，請畫出其網絡計劃圖。工序代號工序內容所需時間（天)緊前工序abcde產品設計與工藝設計外購配套零件外購生產原料自制主件主配可靠性試驗601513388-aacb,d第一節 網絡圖4 統籌方法的第一步工作就是繪制計劃網絡圖，也就是將工序解:用網絡圖表示上述的工序進度表點表示一個事件,是一個或若干個工序的開始或結束,是相鄰工序在時間上的分界點,點用圓圈表示,圓圈里的數字表示點的編號。弧

3、表示一個工序（或活動），弧的方向是從工序開始指向工序的結束，弧上是各工序的代號，下面標以完成此工序所需的時間（或資源）等數據，即為對此弧所賦的權數2022/10/155-線性規劃-線性規劃解:用網絡圖表示上述的工序進度表2022/10/115-abcde601383815圖16abcde601383815圖16 例9.2 把例1的工序進度表做一些擴充，如表，請畫出其統籌方法的網絡圖。工序代號所需時間（天）緊前工序工序代號所需時間（天）緊前工序abcd60151338aacefgh810165b，dde，7 例9.2 把例1的工序進度表做一些擴充，如表，請畫出其統解：虛工序是實際上并不存在而虛設

4、的工序，用來表示相鄰工序的銜接關系，不需要人力、物力等資源與時間。152643a60b158e1013dc38f圖28解：虛工序是實際上并不存在而虛設的工序，用來表示相鄰工序的銜在網絡圖上添加、工序得網絡圖3。 在統籌方法的網絡圖中不允許兩個點之間多于一條弧，因此增加了一個點和虛工序如圖4。b1256734a6015ec13d388h510fg16圖39在網絡圖上添加、工序得網絡圖3。b1256734a601在繪制統籌方法的網絡圖時，要注意圖中不能有缺口和回路。161257834a6015bec13d388h510f6g圖4避免交叉節點標號：j iij10在繪制統籌方法的網絡圖時，要注意圖中不

5、能有缺口和回路。161第二節 時間參數的計算 在繪制出網絡圖之后，我們可以由網絡圖求出：1、完成此工程項目所需的最少時間。2、每個工序的開始時間與結束時間。3、關鍵路線及其應用的關鍵工序。4、非關鍵工序在不影響工程的完成時間的前提下，其開始時間與結束時間可以推遲多久。11第二節 時間參數的計算11一、工作時間 t (i, j )確定型概率型缺乏統計來確定完成每個活動所需時間，但對所需時間做了三種估計：1.樂觀時間。指所需最少時間，用a表示。2.最可能時間。指正常時間，用m表示。3.悲觀時間。指不順利情況下，最多時間，用b表示。2022/10/1512一、工作時間 t (i, j )確定型202

6、2/10/111活動 樂觀時間最可能時間悲觀時間 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/10/1513活動 樂觀時間最可能時間悲觀時間 a1. 顯然這三種完成活動所需時間都具有一定概率，由經驗，我們可以可以假定這些時間的概率分布近似服從 分布。我們可以用如下公式計算出完成活動所需的：方差平均時間例如：完成工作g所需平均時間：同時求出方差為14 顯然這三種完成活動所需時間都具有一定概率，由經驗，我 同樣可以求出每個活動的完成所需平均時間

7、及方差活動T（平均時間）方差活動T方差a 20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.02815 同樣可以求出每個活動的完成所需平均時間及方差活動T（平均時1、最早時間從網絡的發點開始，按順序計算出每個工序的最早開始時間（ES )和最早結束時間（EF)工序a的最早開始時間工序a的最早完成時間ija0，6060二、時間參數161、最早時間工序a的最早工序a的最早ija0，6060二1236785a0,6060b60,10545e60.100c60,70h100,115j135,17035i110.135g80,11030d

8、60.80204025f70,881841015例9.42022/100,6060b60,10545e62、最晚時間從網絡的收點開始計算，在不影響整個工程最早結束時間的情況下，各個工序的最晚結束時間（LF)和最晚開始時間(LS)工序a的最晚開始時間工序a的最晚完成時間ij0，60a2022/10/15182、最晚時間從網絡的收點開始計算，在不影響整個工程最早結束時 1236785a0,60600,60b60,1054590,135e60.100c60,70h100,115j135,17035135,170i110.135g80,1103080,110d60.80206

9、0,804080,12025110,135f70,8818117,135410107,11715120,13519 1236785a0,60600,60b60,101、總時差在不影響工程最早結束時間的條件下，工序最早開始（或結束）的時間可以推遲的時間，成為該工序的總時差R三、時差2022/10/15201、總時差三、時差2022/10/11202、單時差在不影響緊后工序最早開始時間的條件下，工序最早開始（或結束）的時間可以推遲的時間，成為該工序的單時差r2022/10/15212、單時差2022/10/1121四、關鍵工序，關鍵路線網絡中最長的路線就決定了完成整個工程所需的最少時間，這條路線稱

10、為關鍵路線。總時差為0的工序為關鍵工序。2022/10/1522-線性規劃-線性規劃四、關鍵工序，關鍵路線網絡中最長的路線就決定了完成整個工程所例9-12022/10/1523例9-12022/10/11232022/10/1524-線性規劃-線性規劃2022/10/1124-線性規劃-線性規劃2022/10/1525-線性規劃-線性規劃2022/10/1125-線性規劃-線性規劃例9.4 某公司裝配一條新的生產線，具體過程如表1,求：完成此工程的最少時間，關鍵路線及相應的關鍵工序，各工序的最早開始時間和非關鍵工序在不影響工程完成時間的前提下，其開始時間與結束時間可以推遲多久？26例9.4 某

11、公司裝配一條新的生產線，具體過程如表1,求：完工序代號工序內容所需時間（天）緊前工序abcdefghij生產線設計外購零配件下料、鍛件工裝制造1木模、鑄件機械加工1工裝制造2機械加工2機械加工3裝配調試60451020401830152535/aaaacdd, egb, i, f, h27工序代號工序內容所需時間（天）緊前工序a生產線設計60/2712346785a60b45echj35ig1030d204025f18152812346785a60b45echj35ig1030d204 1236785a0,6060b60,10545e60.100c60,70h100,115j135,17035

12、i110.135g80,11030d60.80204025f70,88184101529 1236785a0,6060b60,10545e 1236785a0,60600,60b60,1054590,135e60.100c60,70h100,115j135,17035135,170i110.135g80,1103080,110d60.802060,804080,12025110,135f70,8818117,135410107,11715120,13530 1236785a0,60600,60b60,10 最后將各工序的時差，以及其他信息構成工序時間表如表所示。這樣就找到了一條由關鍵工序a,d

13、,g,i和j依次連接成的從發點到收點的關鍵路線。31 最后將各工序的時差，以及其他信息構成工序時間表如表所示完成工序所需時間不確定例9-22022/10/1532完成工序所需時間不確定例9-22022/10/11322022/10/15332022/10/11332022/10/1534-線性規劃-線性規劃2022/10/1134-線性規劃-線性規劃關鍵線路2022/10/1535關鍵線路2022/10/1135第三節 網絡計劃優化把串聯工作改為平行工作或平行交叉工作2022/10/1536第三節 網絡計劃優化把串聯工作改為平行工作或平行交叉工作2利用時差 總時差不影響最短工期，但影響后續工序

14、的自由時間。 單時差不影響后續工序。2022/10/1537利用時差2022/10/11373.時間-資源優化做法： 1）優先安排關鍵工序所需的資源。 2）利用非關鍵工序的時差，錯開各工序的開始時間。 3）適當延長時差大的工序時間，或切斷非關鍵工序進程。2022/10/15383.時間-資源優化做法：2022/10/11382022/10/15392022/10/11392022/10/15402022/10/11402022/10/15412022/10/11414.工期成本優化直接費用：為了加快工程進度，需要增加人力、設備和工作班次，這需要增加一筆費用，成為直接費用。間接費用：由于工程早日

15、完工，減少了管理人員的工資辦公費等費用稱為間接費用。一般說工序越短，直接費用越多，間接費用越少。2022/10/1542-線性規劃-線性規劃4.工期成本優化直接費用：為了加快工程進度，需要增加人力、 工序的最快完成時間：指完成時間的最高限度。 我們設完成工序j的正常所需時間為Tj;直接費用為cj;完成工序j的最快完成時間為Tj,直接費用為cj。這樣我們可以計算出縮短工序j的一天工期所增加的直接費用，用kj表示，稱為直接費用變動率（成本斜率）。有43 工序的最快完成時間：指完成時間的最高限度。43模型一，在既定的時間T完工的前提下，問各工序的完成時間為多少才使因縮短工期而增加的直接費用最少。 設

16、工序（i ,j)的提前完工時間為yij,我們用Tij,Tij分別表示正常完工時間與最快完工的時間，則有工序（i ,j)的實際完工時間為：Tij- yij 。我們用Cij,Cij表示用正常完工時間和最快完成時間完成工序所需要的費用，kij為工序（i ,j)的直接費用變動率（成本斜率）。44模型一，在既定的時間T完工的前提下，問各工序的完成時間為多少方法一：線性規劃法S.t. xj-xi Tij-yij, 對一切弧（i, j) yij Tij-Tij, 對一切弧（i, j) xn-x1 T, xi 0， yij 0。45方法一：線性規劃法45例9.5 例4所提供的信息都作為本例的信息，另外還給出了

17、在裝配過程中各道工序所需正常完工時間與最快完工時間，以及對應正常完工時間與最快完工時間的所需的直接費用和每縮短一天工期所需增加的直接費用，如表所示。46例9.5 例4所提供的信息都作為本例的信息，另外還給出了在工序Tij正常完工Cij直接費用Tij最快完工Cij直接費用直接費用變動率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j3512000351

18、2000-2022/10/1547-線性規劃-線性規劃工序Tij正常完工Cij直接費用Tij最快完工Cij直接該工程要求在150天內完工，問每個工序應比正常完工時間提前多少天完成，才能使整個工程因縮短工期而增加的直接費用為最少。如果工期要求在140天完工呢？b12345678afechgijd48該工程要求在150天內完工，問每個工序應比正常完工時間提前多解：設此網絡圖上第i點發生的時間為xi，工序提前完工的時間為yij。minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t. x2-x1 60-y12, x7- x2

19、45-y27 x3-x210-y23 x4-x220-y24 x5-x240-y25 x7-x318-y37 x6-x430-y46 x5-x40 x7-x515-y57 x7-x625-y67 x1 =0 x8 150 y120 y2715 y23 5 y24 10 y25 5 y37 8 y46 10 y57 5 y78 0 xi 0，yij 0.（對一切可能的ij)運算得到結果：f=6400。49解：設此網絡圖上第i點發生的時間為xi，工序提前完工的時間為方法二：統籌法從關鍵工序中找成本斜率最小的工序，壓縮工期；重新計算關鍵路線和關鍵工序；再重復循環1和2，直至達到壓縮工期要求；計算增加

20、的總直接費用50方法二：統籌法50模型二，我們知道直接費用是隨著完成時間的縮短而增加，而間接費用卻會隨著完成時間的縮短而減少，設單位時間的間接費用為d,計劃期的間接費用與總工期成正比，即為d(xn-x1)。 那么求使包括間接費用與直接費用在內的總費用最少的整個工程最優完成時間T和各個工序最優完成時間的模型為： s. t. xj - xi Tij - yij，對一切弧（i ,j) yij Tij - Tij ，對一切弧（i ,j) xi 0， yij 0。51模型二，我們知道直接費用是隨著完成時間的縮短而增加，而間接費 例9.6 如果在例5中，每天的間接費用為330元，求使包括間接費用與直接費用在內的總費用最少的整個工程最優完成時間T和各個工序