浙江大學最牛應用運籌學課件資料講解

1、浙江大學最牛應用運籌學課件第三章第三章 線性規(guī)劃模型線性規(guī)劃模型 目標函數(shù)： 約束條件：nnxcxcxcz 2211max(min)mnmn22m11m2nn22221211nn1212111b).(xaxaxab).(xaxaxab).(xaxaxa. t . sX 0 0 第三章第三章 線性規(guī)劃模型線性規(guī)劃模型 Max z = X1+3X2 s.t. X1+ X26 -X1+2X28 X1 , X20z=0z=3z=6z=9z=12z=15.30 1 2 3 4 5 6-8 -7 -6 -5 -4 -3 -2 -1654321x1x2目標函數(shù)等值線目標函數(shù)等值線Z = X1+3X2可行域可

2、行域(4/3,14/3)第三章第三章 線性規(guī)劃模型線性規(guī)劃模型n對偶問題與影子價格對偶問題與影子價格 定義：定義： 設以下線性規(guī)劃問題設以下線性規(guī)劃問題 MAX Z = CTX s.t. AXb X0 為原始問題，則稱以下問題為原始問題，則稱以下問題 MIN W = bTY s.t. ATYC Y0 為原始問題的為原始問題的對偶問題對偶問題，最優(yōu)值，最優(yōu)值Y為為影子價格影子價格 第三章第三章 線性規(guī)劃模型線性規(guī)劃模型n對偶問題與原始問題的關系對偶問題與原始問題的關系目標極大化問題極大化問題 Cj（max Z）極小化問題極小化問題bi（min W）目標變變量量nxj0 aTijyicj約約束束n

3、xj無約束無約束 aTijyi=cjxj0 aTijyicj約約束束m aijxjbiyi0變變量量m aijxj=biyi無約束無約束 aijxjbiyi0 對偶問題的對偶是原問題。對偶問題的對偶是原問題。若兩個互為對偶問題之一有最優(yōu)解，則另一個必有最優(yōu)解，若兩個互為對偶問題之一有最優(yōu)解，則另一個必有最優(yōu)解，且目標函數(shù)值相等且目標函數(shù)值相等(Z*=W*)，最優(yōu)解滿足，最優(yōu)解滿足CX*=Y*b。若若X*,Y*分別是原問題和對偶問題的可行解，則分別是原問題和對偶問題的可行解，則 X*,Y*為最為最優(yōu)解的充分必要條件是優(yōu)解的充分必要條件是Y*XL=0和和YSX*=0。第三章第三章 線性規(guī)劃模型線性

4、規(guī)劃模型原問題標準型：原問題標準型：Max Z= CXCXAX AX + X XL= b bX X, ,X XL0對偶問題標準型：對偶問題標準型：Min W= YbYbYA YA - Y YS= C CY Y, ,Y YS0第三章第三章 線性規(guī)劃模型線性規(guī)劃模型原問題和對偶問題的互補松松弛關系：原問題和對偶問題的互補松松弛關系：第三章第三章 線性規(guī)劃模型線性規(guī)劃模型 根據(jù)對偶問題的性質有：根據(jù)對偶問題的性質有： Z* = W* = bi yi* 兩邊對兩邊對bi求偏導數(shù)得到：求偏導數(shù)得到： Z* = yi* (i= 1,2, ,m) bi 即即 yi* 表示每增加一個單位表示每增加一個單位 b

5、i 后后 Z* 的增量的增量第三章第三章 線性規(guī)劃模型線性規(guī)劃模型第三章第三章 線性規(guī)劃模型線性規(guī)劃模型 對于每一根7.4米長的鋼材，可有若干種下料方式把它截取成我們所需要的軸，如可以截取2根2.9米和1根1.5米，合計用料7.3米，余料為0.1米?？梢粤谐鋈康南铝戏绞剑築1B2B3B4B5B6B7B8需要量需要量2.9m2.1m1.5m余料余料2010.110301200.31110.90220.20130.80301.10041.4100200100最少線性規(guī)劃模型配套問題n思考題：思考題： 某廠生產(chǎn)一種產(chǎn)品，由兩個某廠生產(chǎn)一種產(chǎn)品，由兩個B1零件和三個零件和三個B2零件零件配套組裝而成

6、。該廠有配套組裝而成。該廠有A1，A2，A3三種機床可加工上三種機床可加工上述兩種零件，每種機床的臺數(shù)以及每臺機床每個工作日述兩種零件，每種機床的臺數(shù)以及每臺機床每個工作日全部用于加工某一種零部件的最大產(chǎn)量（即生產(chǎn)率：件全部用于加工某一種零部件的最大產(chǎn)量（即生產(chǎn)率：件/日）如下表所示。試求該產(chǎn)品產(chǎn)量最大的生產(chǎn)方案。日）如下表所示。試求該產(chǎn)品產(chǎn)量最大的生產(chǎn)方案。 該題不是單純要求兩種零件產(chǎn)量越大越好，而是要求每個工作日按2:3的比例生產(chǎn)出來的B1和B2零件的套數(shù)達到最大。 決策變量：以Xij表示每臺Ai(i=1,2,3)機床每個工作日加工Bj(j=1,2)零件的時間。Z為B1,B2零件按2:3比

7、例配套的數(shù)量（套/日）。 約束條件：工時約束 X11+X12 = 1 (A1一天） X21+X22 = 1 (A2一天） X31+X32 = 1 (A3一天） 配套約束： Z = MIN(320X11+235X21+410X31)/2, (330X12+245X22+418X32)/3)Z = MIN(320X11+235X21+410X31)/2, (330X12+245X22+418X32)/3) 等價于 Z(320X11+235X21+410X31)/2 Z(330X12+245X22+418X32)/3 非負約束：Z,Xij0,Z為整數(shù)目標函數(shù)： MAX Y = Z求解結果： Y*=Z

8、*=44,X11=0.13,X12=0.87,X21=1,X22=0 X31=0.25,X32=0.75, A1B1:8,A1B2:78,A2B1:70,A2B2:0,A3B1:10,A3B2:54 B1:88件；B2:132件配料問題練習配料問題練習n某化工廠要用三種原料某化工廠要用三種原料D,P,H混合配置三種不同混合配置三種不同規(guī)格的產(chǎn)品規(guī)格的產(chǎn)品A,B,C。各產(chǎn)品的規(guī)格、單價如左表。各產(chǎn)品的規(guī)格、單價如左表所示，各原料的單價及每天的最大供應量如右表所示，各原料的單價及每天的最大供應量如右表所示，該廠應如何安排生產(chǎn)才能使利潤最大？所示，該廠應如何安排生產(chǎn)才能使利潤最大？ 配料問題練習答案

9、配料問題練習答案n變量：變量： 產(chǎn)品產(chǎn)品A中中D,P,H含量分別為含量分別為 X11,X12,X13 產(chǎn)品產(chǎn)品B中中D,P,H含量分別為含量分別為 X21,X22,X23 產(chǎn)品產(chǎn)品C中中D,P,H含量分別為含量分別為 X31,X32,X33 令：令：X11+X12+X13=X1 X21+X22+X23=X2 X31+X32+X33=X3 根據(jù)規(guī)格條件有：根據(jù)規(guī)格條件有：X110.5X1; X120.25X1 X210.25X2; X220.5X2 配料問題答案配料問題答案得到：得到： - X11+ X12+X130 - X11+3X12- X130 -3X21+ X22+X230 - X21+

10、 X22- X230原材料供應條件：原材料供應條件： X11+X21+X31100 X12+X22+X32100 X13+X23+X3360非負約束：非負約束：Xij0, i,j=1,2,3目標函數(shù)：目標函數(shù)：max z = -15X11+25X12+15X13- 30X21+10X22-40X31-10X33第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展(Integer Linear Programming, ILP) ： 決策變量是整數(shù)的線性規(guī)劃決策變量是整數(shù)的線性規(guī)劃 第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展 第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展 一些變量的取值被限定為0或1。是整數(shù)

11、規(guī)劃的特例。 0-1規(guī)劃的一般模型： s.t. Xj = 0,1 j=1,2,n （X=0,1 等價于 X1, X0 且取整數(shù)。） 0-1規(guī)劃問題求解：思路與LP、IP問題一致。 0-1變量的靈活運用（選與不選或只能選幾種等）。 jnjjXCz1maxmibXanjijij,.2 , 1,1例例4-2 廠址選擇問題廠址選擇問題 在在N個地點中選個地點中選r個（個（Nr）建廠，在第）建廠，在第i個地點建個地點建廠（廠（i=1，2，N）所需投資為）所需投資為 Ii 萬元，占地萬元，占地Li畝，建成以后的生產(chǎn)能力為畝，建成以后的生產(chǎn)能力為Pi 萬噸?，F(xiàn)在有總萬噸?，F(xiàn)在有總投資投資I萬元，土地萬元，土

12、地L畝，應如何選擇廠址，使建成畝，應如何選擇廠址，使建成后總生產(chǎn)能力最大。后總生產(chǎn)能力最大。第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展 設： 整數(shù)規(guī)劃（整數(shù)規(guī)劃（0-1規(guī)劃）模型為：規(guī)劃）模型為： 地建廠表示在地不建廠表示在i1i0 xi1 ,0 xrxLxLIxI. t .sxPzmaxiN1iiN1iiiN1iiiN1iii投資約束土地約束建廠約束第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展 例4.3 考慮固定成本的最小生產(chǎn)費用問題考慮固定成本的最小生產(chǎn)費用問題 某工廠有三種設備均可生產(chǎn)同一產(chǎn)品，某工廠有三種設備均可生產(chǎn)同一產(chǎn)品，第第j種設備運行的固定成本為種設備運行的固定成本為dj，運行的

13、單位，運行的單位變動成本為變動成本為cj，則生產(chǎn)成本與產(chǎn)量，則生產(chǎn)成本與產(chǎn)量xj的關系的關系為：為： j=1,2,3 如何使設備運行的總成本最??？如何使設備運行的總成本最??？ 0 xxcd0 x0)x(fjjjjjjj當當?shù)谒恼碌谒恼?線性規(guī)劃的擴展線性規(guī)劃的擴展引入引入01變量變量 yj ， 令令 建立以下模型：建立以下模型：這里這里M是一個很大的正數(shù)。是一個很大的正數(shù)。當當yj=0時，時，xj=0，即第，即第j種設備不運行，相應的運行成本種設備不運行，相應的運行成本 djyj+cjxj=0當當yj1時，時，0 xjM，實際上對，實際上對xj沒有限制，運行成本為沒有限制，運行成本為 dj+c

14、jxj 這是一個混合這是一個混合0-1規(guī)劃問題規(guī)劃問題 1 , 0, 03 , 2 , 1. .)(min31jjjjjjjjjyxjMyxtsxcydz0 x種設備時，即j當采用第10 x種設備時，即j當不采用第 0jjjy第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展練習題：建立線性規(guī)劃模型練習題：建立線性規(guī)劃模型練習題練習題 ：建立線性規(guī)劃模型：建立線性規(guī)劃模型n決策變量確定：（是否投資需要決策）決策變量確定：（是否投資需要決策） X11，X12，X21，X31 均為均為01變量變量n約束條件確定：約束條件確定：n第一種產(chǎn)品的方案一和方案二最多只能選一：第一種產(chǎn)品的方案一和方案二最多只能選一

15、： X11+X12 1n第二種產(chǎn)品、第三種產(chǎn)品可選也可不選：第二種產(chǎn)品、第三種產(chǎn)品可選也可不選： X21 1 ， X31 1n 全部投資額應不超過全部投資額應不超過550萬萬 300X11+280X12+260X21+240X31 550第一種產(chǎn)品第一種產(chǎn)品方案方案1 方案方案2X11 X12第二種產(chǎn)品第二種產(chǎn)品X21第三種產(chǎn)品第三種產(chǎn)品X31練習題：建立線性規(guī)劃模型練習題：建立線性規(guī)劃模型n目標函數(shù)確定：每年的收益和最大 每年的總收益包含兩部分：n第一部分：項目投資收益，利用投資回收系數(shù)n第二部分：剩余資金的普通投資收益1)26. 01 ()26. 01 (26. 03124010.28)(

16、10.28)0.28(1X212601)28. 01 ()28. 01 (28. 0122801)3 . 01 ()3 . 01 (3 . 01130055555555XXX1) 1 . 01 () 1 . 01 ( 1 . 0)31240212601228011300(55055XXXX第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展 n項任務（項任務（B1,B2,Bn)由由n個人個人 (A1,A2,An) 去完成，每項任務交給一人，每人只有一項任務。去完成，每項任務交給一人，每人只有一項任務。第第i個人個人Ai去做第去做第j項任務項任務Bj的工作效率（如工時、的工作效率（如工時、成本或價值等）為

17、成本或價值等）為Cij。問如何安排人員使總工作。問如何安排人員使總工作效率最好？效率最好？ 設設Xij表示表示Ai完成完成Bj工作，并令工作，并令 1 當指派當指派Ai去完成去完成Bj工作工作 Xij = 0 當不指派當不指派Ai去完成去完成Bj工作工作第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展n指派問題數(shù)學模型的標準型 MIN Z = （Cij0) （i= 1,2,n) (j= 1,2,n) Xij 皆為 0 或 1 由 Cij 組成的方陣 C = ( Cij )nn 稱為效率矩陣 ninjCijXij11njXij11niXij11第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展n指派問題標準型

18、的求解匈牙利法指派問題標準型的求解匈牙利法n 指派問題有以下性質：指派問題有以下性質： 若從效率矩陣若從效率矩陣C C的任何一行（列）各元素中的任何一行（列）各元素中分別減去一個常數(shù)分別減去一個常數(shù)K K（K K可正可負）得到新矩可正可負）得到新矩陣陣D,D,則以則以D D為效率矩陣的指派問題與原問題為效率矩陣的指派問題與原問題有相同的解，但最優(yōu)值比原問題最優(yōu)值小有相同的解，但最優(yōu)值比原問題最優(yōu)值小K K。 用匈牙利法求解的條件：用匈牙利法求解的條件： MIN、i=j 、Cij0第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展n匈牙利法的主要步驟：匈牙利法的主要步驟： 第一步：變換效率矩陣，使在各行

19、各列都出現(xiàn)零元素。第一步：變換效率矩陣，使在各行各列都出現(xiàn)零元素。 1、從矩陣、從矩陣C的每行元素減去該行的最小元素；的每行元素減去該行的最小元素； 2、再從所得矩陣的每列中減去該列最小元素。、再從所得矩陣的每列中減去該列最小元素。 第二步：以最少數(shù)目的水平線和垂直線劃去所有的零元第二步：以最少數(shù)目的水平線和垂直線劃去所有的零元素。如果所用的直線等于行或列數(shù)，則結束指派。否則素。如果所用的直線等于行或列數(shù)，則結束指派。否則繼續(xù)。繼續(xù)。 第三步：找到?jīng)]有被劃去的最小的元素，所有第三步：找到?jīng)]有被劃去的最小的元素，所有被劃被劃中的元素中的元素這一最小值。而被這一最小值。而被的元素（該元的元素（該元

20、素行列都被劃中）則要素行列都被劃中）則要這一最小值。再返回到第一這一最小值。再返回到第一步。步。 第四步：最后根據(jù)零元素的位置，確定最優(yōu)分配方案。第四步：最后根據(jù)零元素的位置，確定最優(yōu)分配方案。第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展 從產(chǎn)地到銷地之間運送貨物的最佳路徑。從產(chǎn)地到銷地之間運送貨物的最佳路徑。 多個產(chǎn)地和多個銷地；多個產(chǎn)地和多個銷地； 每個產(chǎn)地的產(chǎn)量不同，每個銷地的銷量也不同；每個產(chǎn)地的產(chǎn)量不同，每個銷地的銷量也不同； 各產(chǎn)銷兩地之間的運價不同。各產(chǎn)銷兩地之間的運價不同。 如何組織調(diào)運，才能既滿足各銷地的要求，如何組織調(diào)運，才能既滿足各銷地的要求，又使總的運輸費用（或里程、時間

21、等）最小。又使總的運輸費用（或里程、時間等）最小。第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展 設有同一種貨物從m個出發(fā)地1，2，m運往n個到達地1，2，n。第i個出發(fā)地的供應量（Supply）為si（si0）， 第j個到達地的需求量（Demand）為 dj（dj0）。 每單位貨物從產(chǎn)地 i 運到銷地 j 的運價為Cij。求一個使總運費最小的運輸方案。 1 2 3 n 供應供應 1 c11 c1n s1 2 c21 成本成本 c2n s2 cij m cm1 cmn sm 需求需求 d1 dn 出發(fā)地到達地第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展ninjCijXij11njiSXij1mijd

22、Xij1n產(chǎn)銷平衡的運輸問題模型產(chǎn)銷平衡的運輸問題模型 令令Xij為為 從從i i地運到地運到j j地的數(shù)量地的數(shù)量 MIN Z = （Cij0) ) （i= 1,2,m) i= 1,2,m) 供應約束供應約束 (j= 1,2,n) (j= 1,2,n) 需求約束需求約束 Xij0 由由 Cij、S Si、d dj 組成的組成的 (m+1)m+1)(n+1) (n+1) 矩陣矩陣稱為運輸矩陣稱為運輸矩陣第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展 實際決策值與目標值之間的差異實際決策值與目標值之間的差異決策值超過目標值的部分決策值超過目標值的部分決策值低于目標值的部分決策值低于目標值的部分 嚴格

23、滿足的等式或不等式約束嚴格滿足的等式或不等式約束把約束右端項看成是要追求的目標值，把約束右端項看成是要追求的目標值， 在達到此目標時允許有正負偏差，線性規(guī)劃問題在達到此目標時允許有正負偏差，線性規(guī)劃問題的目標函數(shù)，在給定目標值和加入正、負偏差后的目標函數(shù)，在給定目標值和加入正、負偏差后可變換為目標約束，也可將絕對約束變換為目標可變換為目標約束，也可將絕對約束變換為目標約束。約束。第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展要達到的多個目標之間有主次、輕重緩急要達到的多個目標之間有主次、輕重緩急之分，因此各目標之間有優(yōu)先等級。凡第一位要達到的目標賦予等級之分，因此各目標之間有優(yōu)先等級。凡第一位要達

24、到的目標賦予等級系數(shù)系數(shù)P1,次位的賦予等級系數(shù)次位的賦予等級系數(shù)P2，以此類推；并規(guī)定，以此類推；并規(guī)定PkPk+1, Pk比比Pk+1更大的優(yōu)先權。相同等級的以不同的權系數(shù)更大的優(yōu)先權。相同等級的以不同的權系數(shù)加以區(qū)別。加以區(qū)別。 目標規(guī)劃的目標函數(shù)是按各目標約束的目標規(guī)劃的目標函數(shù)是按各目標約束的正、負偏差變量和賦予相應的優(yōu)先因子而構造的。當每一目標值確定正、負偏差變量和賦予相應的優(yōu)先因子而構造的。當每一目標值確定后，決策者的要求是盡可能縮小偏離目標值，因此目標規(guī)劃的目標函后，決策者的要求是盡可能縮小偏離目標值，因此目標規(guī)劃的目標函數(shù)只能是數(shù)只能是 MIN Z = f f（d+,d- )

25、 )。 要求恰好達到目標值（正負偏差都要盡可能地?。?，這時要求恰好達到目標值（正負偏差都要盡可能地?。?，這時 MIN Z = f f（d+ d- ) ) 要求不超過目標值（允許達不到，正偏差要盡可能地?。┮蟛怀^目標值（允許達不到，正偏差要盡可能地?。?MIN Z = f f（d+ ) ) 要求不低于目標值：要求不低于目標值： MIN Z = f f（d- ) )運輸與目標規(guī)劃練習：運輸與目標規(guī)劃練習：有三個產(chǎn)地給四個銷地供應某產(chǎn)品，產(chǎn)銷地之間的供需量和單位運價（有三個產(chǎn)地給四個銷地供應某產(chǎn)品，產(chǎn)銷地之間的供需量和單位運價（C Cij）如下：）如下： 銷地銷地產(chǎn)地產(chǎn)地B1B1B2B2B3B3

26、B4B4產(chǎn)量產(chǎn)量(S(Si) )A1A1A2A2A3A35 53 34 42 25 55 56 64 42 27 76 63 3300300200200400400銷量銷量(D(Dj) )200200100100400400200200900900要求：要求：1 1）建立此運輸問題的線性規(guī)劃模型）建立此運輸問題的線性規(guī)劃模型( (用矩陣的形式簡化表示用矩陣的形式簡化表示) )； 2 2）由于市場情況的變化，）由于市場情況的變化，B3 B3 和和 B4 B4 的銷量各增加了的銷量各增加了5050單位（可求得此時最單位（可求得此時最 小運費為小運費為29502950元）。由于生產(chǎn)能力無法再提升，因

27、此有關部門在研究調(diào)運元）。由于生產(chǎn)能力無法再提升，因此有關部門在研究調(diào)運 方案時需依次考慮以下情況（已規(guī)定其優(yōu)先等級方案時需依次考慮以下情況（已規(guī)定其優(yōu)先等級 P1P1P3P3）：）： P1: A3P1: A3向向B1B1提供的產(chǎn)量不少于提供的產(chǎn)量不少于100100； P2: P2: 給給B1B1和和B3B3的供應需求率要相等；的供應需求率要相等； P3: P3: 總運費增加不超過最小調(diào)運方案費用的總運費增加不超過最小調(diào)運方案費用的1010。 試建立求解滿意調(diào)運方案的目標規(guī)劃模型（不需要化簡整理）。試建立求解滿意調(diào)運方案的目標規(guī)劃模型（不需要化簡整理）。 運輸與目標規(guī)劃練習：運輸與目標規(guī)劃練習

28、：n產(chǎn)銷平衡，運輸問題模型 令Xij為 從i地運到j地的數(shù)量 目標函數(shù)： MIN Z = （Cij0) 約束條件： （i= 1,2,3) i= 1,2,3) 供應約束供應約束 (j= 1,2,3,4) (j= 1,2,3,4) 需求約束需求約束 Xij03141ijCijXij41jiSXij31ijDXij運輸與目標規(guī)劃練習：運輸與目標規(guī)劃練習：n供應絕對約束：供應絕對約束： i=1,2,3i=1,2,3n目標約束條件：目標約束條件： j=1,2,3,4 j=1,2,3,4 需求目標約需求目標約束束n目標函數(shù)：目標函數(shù)：41jiSXij31ijDdjdjXij0%)101 (2950:045

29、0200:100:773141366332313312111255311dXddXCPddXXXXXXPddXPijijij，非負約束：7366251)(mindPddPdPZ第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展決策決策1決策決策2決策決策3決策決策n1狀態(tài)狀態(tài)123n狀態(tài)狀態(tài)n狀態(tài)狀態(tài)4狀態(tài)狀態(tài)3狀態(tài)狀態(tài)2階段階段1階段階段2階段階段3階段階段n第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展表示決策順序的離散量，階段可按時間或空間劃分。表示決策順序的離散量，階段可按時間或空間劃分。能確定地表示決策過程當前特征的量。狀態(tài)可以是數(shù)能確定地表示決策過程當前特征的量。狀態(tài)可以是數(shù)量也可以是字符，數(shù)

30、量狀態(tài)可以是連續(xù)的也可以是離散的。量也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的也可以是離散的。表示每一狀態(tài)可以取不同值的變量。表示每一狀態(tài)可以取不同值的變量。：從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。決策是所：從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。決策是所在狀態(tài)變量的函數(shù)，記為在狀態(tài)變量的函數(shù)，記為d (X )。在狀態(tài)在狀態(tài)X 下，允許采取決策的全體。下，允許采取決策的全體。某一狀態(tài)以及該狀態(tài)下的決策，某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關系。與下一狀態(tài)之間的函數(shù)關系。第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展動態(tài)規(guī)劃作業(yè)動態(tài)規(guī)劃作業(yè)第四章第四章 線性規(guī)劃的擴展線性規(guī)劃的擴展S1=2S4=0

31、S3=2S3=1S3=0S2=2S2=1S2=00.060.480.300.160.300.500.800.300.500.800.200.400.600.600.400.600.150.200.40第一組第一組第三組第三組第二組第二組剩余人數(shù)剩余人數(shù)n時序順序時間時序順序時間n時序規(guī)劃時序規(guī)劃 多項任務等待同一人或物處理，每項多項任務等待同一人或物處理，每項任務的單獨完成的時間確定，且沒有先任務的單獨完成的時間確定，且沒有先后關系（緊前、緊后）。怎樣安排各項后關系（緊前、緊后）。怎樣安排各項任務的順序，使總效率最高？任務的順序，使總效率最高？n系統(tǒng)時間加工時間排隊時間系統(tǒng)時間加工時間排隊時間

32、n平均排隊（等待）時間最短問題平均排隊（等待）時間最短問題 加工時間最短者優(yōu)先加工時間最短者優(yōu)先 （相同時間的可任意安排）（相同時間的可任意安排）n平均延誤時間最短問題平均延誤時間最短問題 最先到期的工作優(yōu)先最先到期的工作優(yōu)先n時序規(guī)劃擴展（約翰遜原則）：時序規(guī)劃擴展（約翰遜原則）： 兩臺順序機器完成一批工作兩臺順序機器完成一批工作 每項工作在機器每項工作在機器1和機器和機器2上的加工時間不上的加工時間不一樣，如何使系統(tǒng)效率最高？一樣，如何使系統(tǒng)效率最高？ 3214機器機器1機器機器2工作工作n約翰遜原則約翰遜原則 找出各臺機器上加工時間最短的一項工作，找出各臺機器上加工時間最短的一項工作，

33、如果在機器如果在機器1上，這項工作最先做；上，這項工作最先做； 如果在機器如果在機器2上，這項工作最后做；上，這項工作最后做； 不斷重復，從兩端往內(nèi)排。相同時間可任選不斷重復，從兩端往內(nèi)排。相同時間可任選一一 個，一般先安排機器個，一般先安排機器1上工作。上工作。n最小樹最小樹 一個網(wǎng)絡中有很多樹，其中邊的長度一個網(wǎng)絡中有很多樹，其中邊的長度（權數(shù)）之和為最小的樹為最小樹。（權數(shù)）之和為最小的樹為最小樹。n最小樹的獲取破圈法最小樹的獲取破圈法 從圖中任取一個圈，去掉該圈的一條最從圖中任取一個圈，去掉該圈的一條最大邊，將此圈破去，然后重復破圈，直大邊，將此圈破去，然后重復破圈，直至無圈為止至無圈

34、為止。 n通過一個網(wǎng)絡的最短路徑通過一個網(wǎng)絡的最短路徑n問題問題 在一個網(wǎng)絡中，給定一個始點在一個網(wǎng)絡中，給定一個始點Vs，和一個，和一個終點終點Vt，求，求Vs 到到Vt的一條路，使路長最短。的一條路，使路長最短。n求解求解 能劃分階段的，可采用動態(tài)規(guī)劃方法。能劃分階段的，可采用動態(tài)規(guī)劃方法。 不能分階段的，采用不能分階段的，采用狄克斯屈狄克斯屈方法。方法。n狄克斯屈狄克斯屈方法方法n開始節(jié)點標永久標記開始節(jié)點標永久標記0,S,其余臨時其余臨時T,-n找出與開始節(jié)點相鄰的所有節(jié)點，為每一個設標記找出與開始節(jié)點相鄰的所有節(jié)點，為每一個設標記L,1，其中，其中L值最小的節(jié)點標記右上角標上值最小的

35、節(jié)點標記右上角標上*，使之成，使之成為永久標志。為永久標志。n從新的永久標志開始，找出從此節(jié)點出發(fā)可到達的所有從新的永久標志開始，找出從此節(jié)點出發(fā)可到達的所有節(jié)點，計算這些節(jié)點的最短距離（現(xiàn)有距離和經(jīng)新的永節(jié)點，計算這些節(jié)點的最短距離（現(xiàn)有距離和經(jīng)新的永久標志到達的距離的小的一個值），保持、新設或更改久標志到達的距離的小的一個值），保持、新設或更改這些節(jié)點的標志為這些節(jié)點的標志為 最短距離，最短路徑上前一節(jié)點標最短距離，最短路徑上前一節(jié)點標號號，比較圖中所有沒有，比較圖中所有沒有*的標記（臨時性標記），找出的標記（臨時性標記），找出距離最短的一個節(jié)點，使之成為永久性標記。重復這一距離最短的一個

36、節(jié)點，使之成為永久性標記。重復這一步，直到所有的節(jié)點都成為永久性標志為止。步，直到所有的節(jié)點都成為永久性標志為止。kijDi,mLijDj,k從從i-j時：時： 如果如果Di+LijDj,則不改變則不改變j的標記；的標記； 如果如果Di+LijDj，則改為，則改為Di+Lij,i狄克斯屈狄克斯屈方法方法最短路徑問題的應用n例56：設備更新問題 某廠使用一種設備，每年年初設備科需要對該設備的更新與否作出決策。若購置新設備，就要支付購置費；如果繼續(xù)使用則需要支付維修費，設備使用的年數(shù)越長，每年所需的維修費越多?，F(xiàn)若第一年年初購置了一臺新設備，問在5年內(nèi)如何制定設備更新計劃，以便使新設備購置費和維修

37、費的總費用最?。恳阎O備在5年內(nèi)各年年初的價格及設備使用不同年數(shù)的維修費如下：最短路徑問題的應用n例56：設備更新問題 把求總費用最小問題化為最短路徑問題。用點 i (i=1,2,3,4,5)表示第 i 年買進一臺新設備。增設一點 6 表示第五年末。從i點到i+1, 6 各畫一條弧，?。╥ , j）表示在第 i 年買進的設備一直使用到第 j 年年初（第 j 1年年末）。求1點到6點的最短路徑。路徑的權數(shù)為購買和維修費用。 ?。╥ , j）的權數(shù)為第i年的購置費ai從第i年使用至第j-1年末的維修費之和。 從第i年使用至第j-1年末的維修費：b1+bj-i （使用壽命為j-i年） 如：（24）權

38、數(shù)為：a2+b1+b2=1156=22 具體權數(shù)計算結果如下：通過一個網(wǎng)絡的最短路徑n例例56 設備更新問題設備更新問題 ：使用使用Dijstra算法，上述問題最短路為算法，上述問題最短路為1-3-6或或1-4-6 即：第即：第1、3年年初購買設備，或第年年初購買設備，或第1、4年年初購買設備年年初購買設備 五年最佳總費用為五年最佳總費用為53。132546162217182330594117301623413122通過一個網(wǎng)絡的最大流量通過一個網(wǎng)絡的最大流量n最大流量問題最大流量問題 在一定條件下，使網(wǎng)絡系統(tǒng)中從開始點在一定條件下，使網(wǎng)絡系統(tǒng)中從開始點到結束點之間的某種物資流的流量達到到結束

39、點之間的某種物資流的流量達到最大的問題。限制條件是每一條邊的最最大的問題。限制條件是每一條邊的最大通過能力（流量）不等。但有多條路大通過能力（流量）不等。但有多條路n最大流量求解最大流量求解n線性規(guī)劃方法線性規(guī)劃方法n福特富爾克遜標號法（福特富爾克遜標號法（“分步流動分步流動”） 最大流量的線性規(guī)劃模型最大流量的線性規(guī)劃模型n例例57：有下列石油運輸管道圖。某公司欲采用這個有下列石油運輸管道圖。某公司欲采用這個網(wǎng)絡圖從網(wǎng)絡圖從1地向銷地地向銷地7運送原油，弧的容量運送原油，弧的容量Cij（萬升（萬升/時）時）已給定（因管道直徑的變化，已給定（因管道直徑的變化，Cij不完全相同）。問如何不完全相

40、同）。問如何安排輸送，方能使每小時運送的原油最多？安排輸送，方能使每小時運送的原油最多？62321256432最大流量的線性規(guī)劃模型最大流量的線性規(guī)劃模型n設?。ㄔO?。╥,j）上的流量為）上的流量為Fij, 總流量為總流量為F.n目標函數(shù)：目標函數(shù)：MAX F=F12+F14n約束條件：約束條件： 流入流出流入流出; FijCij; Fij0 2點：點：F12=F23+F25; 4點：點：F14=F43+F46+F47 3點：點：F23+F43=F35+F36; 5點點 ：F25+F35F57 6點：點：F36+F46F67 ; 7點：點：F47+F57+F67=F12+F14n解：解：F12

41、=5;F14=5;F23=2;F25=3;F43=2;F46=1;F47=2;F35=2 F36=2;F57=5;F67=3 最大流量最大流量F1062321256432思考題：最小費用最大流思考題：最小費用最大流n如果?。ㄈ绻。╥,j）上的單位流量費用為）上的單位流量費用為Bij (百元百元/萬升）。萬升）。 圖中每一條弧的權數(shù)前一位為流量限制圖中每一條弧的權數(shù)前一位為流量限制Cij，后一位為單位費，后一位為單位費Bij。n怎樣運送才能使運送最多的石油并使總的費用最小？怎樣運送才能使運送最多的石油并使總的費用最小？n提示：先求得最大提示：先求得最大F值；再求總流量為值；再求總流量為F時使總

42、費用最小的方案。時使總費用最小的方案。n進一步思考：進一步思考： 1）求最小費用問題，如何求每小時運送）求最小費用問題，如何求每小時運送6萬升原油的最萬升原油的最 小費用？小費用？ 2）Cij為兩節(jié)點之間的距離時，求節(jié)點為兩節(jié)點之間的距離時，求節(jié)點1到節(jié)點到節(jié)點7的最短距離？的最短距離？ 6,32,53,22,31,32,85,76,64,43,42,4n標記：標記：流入節(jié)點的流量，該流量的來源節(jié)點流入節(jié)點的流量，該流量的來源節(jié)點，第一個節(jié)點標記第一個節(jié)點標記，S。n選取已有標記的一個節(jié)點，找出從此節(jié)點能直選取已有標記的一個節(jié)點，找出從此節(jié)點能直接到達的一個節(jié)點，確定到達節(jié)點的最大流量，接到達

43、的一個節(jié)點，確定到達節(jié)點的最大流量，相應地標上標記。重復這一步，盡快到達終點，相應地標上標記。重復這一步，盡快到達終點，得到一條從起點到終點的路徑，此路徑的最大得到一條從起點到終點的路徑，此路徑的最大流量為流入終點的流量。將此路徑上的每一邊流量為流入終點的流量。將此路徑上的每一邊的流動能力減去此流量。再從起始節(jié)點開始，的流動能力減去此流量。再從起始節(jié)點開始，按新的流動能力，重新進行標號，找出新的一按新的流動能力，重新進行標號，找出新的一條途徑和流量，重復進行下去，直到把所有可條途徑和流量，重復進行下去，直到把所有可能的路徑全部找到為止，全部路徑的流量和即能的路徑全部找到為止，全部路徑的流量和即

44、為通過該網(wǎng)絡的最大流量。為通過該網(wǎng)絡的最大流量。福特富爾克遜標號法：福特富爾克遜標號法：ijFi,KFj,imijFj=min(Fi,mij)福特富爾克遜標號法：福特富爾克遜標號法：第七章第七章 決策分析決策分析n風險決策風險決策n存在幾種自然狀態(tài)，哪一種狀態(tài)發(fā)生不確定，存在幾種自然狀態(tài)，哪一種狀態(tài)發(fā)生不確定，但每種自然狀態(tài)發(fā)生的可能性可以預計（主但每種自然狀態(tài)發(fā)生的可能性可以預計（主觀概率值）。觀概率值）。n決策依據(jù)：最大期望收益、最小期望損失標決策依據(jù)：最大期望收益、最小期望損失標準準n期望值：不同自然狀態(tài)下可能得到的值期望值：不同自然狀態(tài)下可能得到的值 期望值期望值（概率（概率結果值）結

45、果值）n決策方法：最大期望計算、條件概率、決策決策方法：最大期望計算、條件概率、決策樹、效用曲線分析樹、效用曲線分析第七章第七章 決策分析決策分析n最大期望收益值計算 i為備擇方案，i=1,2,n j為自然狀態(tài)，j=1,2,m 為為第i個備擇方案的期望收益值 pj為第j個自然狀態(tài)出現(xiàn)的概率 Oij為第i個備擇方案在第j個自然狀態(tài)下的收益 Vi0 為第i個備擇方案的初始投資值01)(iijmjjiVOpE iE第七章第七章 決策分析決策分析n風險的衡量 當備擇方案的期望收益值相等時，需計算風險值。風險應盡可能地小。 為第i個備擇方案的風險 mjjiijipEO12)( 第七章第七章 決策分析決策

46、分析n決策樹結構決策樹結構 狀態(tài)狀態(tài)節(jié)點節(jié)點狀態(tài)狀態(tài)節(jié)點節(jié)點收益收益收益收益收益收益收益收益概率枝概率枝方案枝方案枝概率值概率值概率值概率值概率值概率值概率值概率值第七章第七章 決策分析決策分析n利用決策樹決策利用決策樹決策 繪出決策樹繪出決策樹 預計各狀態(tài)概率預計各狀態(tài)概率 從右向左計算各個方案的收益期望從右向左計算各個方案的收益期望 根據(jù)期望值大小選擇方案根據(jù)期望值大小選擇方案n決策樹求解多階段決策問題決策樹求解多階段決策問題第七章第七章 決策分析決策分析n貝葉斯決策貝葉斯決策 自然狀態(tài)出現(xiàn)的概率估計的正確程度直自然狀態(tài)出現(xiàn)的概率估計的正確程度直接影響到?jīng)Q策中收益期望值。在條件許接影響到?jīng)Q

47、策中收益期望值。在條件許可的情況下，往往需要補充新信息。獲可的情況下，往往需要補充新信息。獲得補充信息需支付一定的費用。根據(jù)獲得補充信息需支付一定的費用。根據(jù)獲得的新信息修正原先對自然狀態(tài)出現(xiàn)的得的新信息修正原先對自然狀態(tài)出現(xiàn)的概率的估計值，并利用修正的概率重新概率的估計值，并利用修正的概率重新進行決策。修正概率主要利用貝葉斯定進行決策。修正概率主要利用貝葉斯定理。理。 第七章第七章 決策分析決策分析n貝葉斯決策過程貝葉斯決策過程 先驗分析先驗分析n根據(jù)資料及經(jīng)驗對各自然狀態(tài)出現(xiàn)的概率作出估根據(jù)資料及經(jīng)驗對各自然狀態(tài)出現(xiàn)的概率作出估 計，稱為先驗概率；計，稱為先驗概率；n根據(jù)先驗概率可作出決策

48、，得到最優(yōu)期望值，記根據(jù)先驗概率可作出決策，得到最優(yōu)期望值，記為為 EMV*。 預驗分析預驗分析n補充信息的成本收益分析補充信息的成本收益分析 后驗分析后驗分析n獲取條件概率，運用貝葉斯定理對先驗概率進行獲取條件概率，運用貝葉斯定理對先驗概率進行修正，得到后驗概率；修正，得到后驗概率；n根據(jù)后驗概率作出決策，計算補充信息的價值。根據(jù)后驗概率作出決策，計算補充信息的價值。第七章第七章 決策分析決策分析n預驗分析n信息的價值在于它能提高決策的最大期望值。但獲取信息的費用超過它所能提高的期望收益就不合算了。n所有信息中最好、最理想的信息自然是完全可靠、準確的信息，這種信息預報某自然狀態(tài)出現(xiàn)，則在實際

49、中必定出現(xiàn)這自然狀態(tài)，這種信息稱為完備信息。n補充信息費用應遠小于完備信息的價值（上限）。n當完全信息預報出現(xiàn)第K個自然狀態(tài)出現(xiàn)時，最優(yōu)方案由 MAXUkjj 確定。n在完備信息下，決策所能獲得的最大期望收益值：n ERPI與EMV*之間的差額就是得到完全信息而使期望值增加的部分，即為完備信息價值EVPI。max1jijmiiuPERPI 第七章第七章 決策分析決策分析n后驗分析n補充新信息，通過對X1,X2,XS共S個狀態(tài)的調(diào)查，獲得實際出現(xiàn)自然狀態(tài)i而預報Xj的概率，即：P(Xj|i)。n在已知先驗概率P(j)(j=1,2,m)及條件概率P(Xj|i)(j=1,2,s;i=1,2,m)的基

50、礎上，利用貝葉斯定理計算修正概率，即后驗概率：n根據(jù)后驗概率，計算各方案的期望收益值，并依據(jù)期望收益值，重新作出決策(最大期望收益)。n計算獲得補充信息后，最大期望收益的實際增量。 mjjijjijijXPPXPPXP1)|()()|()()|( 第七章第七章 決策分析決策分析n后驗分析計算的表格形式I 先驗狀態(tài)概率先驗狀態(tài)概率 P(j j)II 條件概率條件概率 P(Xi|P(Xi|j)j)III P(j j) P( (Xi i| |j)j)X1, , Xi i, , XS SX1, , Xi i, , XS S1 : P(1 1) , P(Xi|P(Xi|1),.1),., P(1 1)

51、P(Xi|P(Xi|1), .1), .2 : P(2 2) , P(Xi|P(Xi|2), 2), , P(2 2) P(Xi|P(Xi|2), .2), . m : P(m m) , P(Xi| , P(Xi|m), m), , P(m m) P(Xi|P(Xi|m), .m), . 對第對第III部分的每一列求和部分的每一列求和P(X1), , P(Xi) , , P(Xm)后驗概率后驗概率: 1P(1 1|X1), , P(1 1|Xi), P(j j|Xi)= 2 P(j j) P( (Xi i| |j)/ j)/ P(Xi) mP(2 2|X1), , P(2 2|Xi),P(m

52、m|X1), , P(m m|Xi),風險型決策風險型決策貝葉斯決策作業(yè)：貝葉斯決策作業(yè)： 假定天氣是影響某工程項目能否按期完工的假定天氣是影響某工程項目能否按期完工的決定因素，如果天氣好，工程能按期完工，施決定因素，如果天氣好，工程能按期完工，施工單位能獲利工單位能獲利5萬元；如果天氣不好，不能按萬元；如果天氣不好，不能按期完工，則要罰款期完工，則要罰款1萬元；但如不施工則要損萬元；但如不施工則要損失人工費失人工費0.2萬元。根據(jù)過去的經(jīng)驗，在計劃萬元。根據(jù)過去的經(jīng)驗，在計劃期內(nèi)天氣好的可能性為期內(nèi)天氣好的可能性為30。為更好地掌握天。為更好地掌握天氣情況，可請氣象部門作進一步的預報，需支氣

53、情況，可請氣象部門作進一步的預報，需支付信息費付信息費0.08萬元。從所提供的預報信息可知，萬元。從所提供的預報信息可知，氣象部門對好天氣的預測準確性為氣象部門對好天氣的預測準確性為80，對壞，對壞天氣的預報準確性為天氣的預報準確性為90。問該如何進行決策？。問該如何進行決策？貝葉斯決策作業(yè)貝葉斯決策作業(yè)n先驗分析：先驗分析： 好天氣好天氣1 1（0.3) 0.3) 壞天氣壞天氣2 2（0.7) EMV0.7) EMV 施工施工 5 5 1 0.81 0.8 不施工不施工 0.2 0.2 0.2 0.2 0.20.2 EMV EMV* * = 0.8 = 0.8 施工有利，期望收益施工有利，期

54、望收益0.80.8萬元萬元n預驗分析：預驗分析： 完備信息最大期望收益完備信息最大期望收益 ERPI=0.3ERPI=0.3* *5 50.70.7* *(-0.2)(-0.2) =1.36 ( =1.36 (萬元）萬元） 完備信息價值完備信息價值 EVPI=1.36 - 0.8 = 0.56 (EVPI=1.36 - 0.8 = 0.56 (萬元萬元) ) EVPI EVPI遠大于收集信息成本遠大于收集信息成本(0.08),(0.08),初步認為合算。初步認為合算。貝葉斯決策作業(yè)貝葉斯決策作業(yè)n后驗分析：后驗分析： 氣象中心提供預報兩種天氣狀態(tài)：好氣象中心提供預報兩種天氣狀態(tài)：好(X1),壞

55、壞(X2) (補充信息的自然狀態(tài)與原自然狀態(tài)一致補充信息的自然狀態(tài)與原自然狀態(tài)一致)n補充信息概率補充信息概率 好天氣預報準確性為好天氣預報準確性為80，壞天氣預報準確性為，壞天氣預報準確性為90 P(X1| 1)=0.8 實際是好天氣預報也是好天氣實際是好天氣預報也是好天氣 P(X2| 1)=0.2 實際是好天氣預報且是壞天氣實際是好天氣預報且是壞天氣 P(X1| 2)=0.1 實際是壞天氣預報且是好天氣實際是壞天氣預報且是好天氣 P(X2| 2)=0.9 實際是壞天氣預報也是壞天氣實際是壞天氣預報也是壞天氣貝葉斯決策作業(yè)貝葉斯決策作業(yè)n后驗分析概率計算的表格形式：n后驗決策： 預報天氣好（

56、X1），每個方案的最大期望收益EMV 好天氣1|X1（0.77) 壞天氣2|X1（0.23) EMV 施工 5 1 3.62* 不施工 0.2 0.2 0.2I 先驗狀態(tài)概率先驗狀態(tài)概率 P(j j) II 條件概率條件概率 P(Xi|P(Xi|j)j)III P(j j) P( (Xi i| |j)j)好天氣好天氣 X1, 壞天氣壞天氣 X2 X1, X2好天氣好天氣1 : 0.3 0.8 0.2 0.24 0.06 0.24 0.06壞天氣壞天氣2 : 0.7 0.1 0.9 0.07 0.63 0.07 0.63全概率全概率P(Xi):P(Xi): 對第對第III部分每一列求和部分每一列

57、求和 0.31 0.69后驗概率后驗概率P(j j|Xi) : 1 0.77 0.09 P(j j) P( (Xi i| |j)/ j)/ P(Xi) 2 0.23 0.91貝葉斯決策作業(yè)貝葉斯決策作業(yè)n后驗決策：后驗決策： 預報天氣壞（預報天氣壞（X2），每個方案的最大期望收益），每個方案的最大期望收益EMV 好天氣好天氣1|X21|X2（0.09) 0.09) 壞天氣壞天氣2|X22|X2（0.91) EMV0.91) EMV 施工施工 5 1 0.46 不施工不施工 0.2 0.2 0.2* n補充信息價值：補充信息價值： 后驗決策最大期望收益后驗決策最大期望收益EMV*=0.313.6

58、2+0.69(0.2)=0.9842 補充信息價值：補充信息帶來期望收益增量補充信息價值：補充信息帶來期望收益增量0.9842-0.80=0.1842 補充信息價值大于預報信息成本（補充信息價值大于預報信息成本（0.08)，因此的確是合算的。，因此的確是合算的。 n后驗決策結果：后驗決策結果： 預報好天氣時施工，預報壞天氣時不施工。預報好天氣時施工，預報壞天氣時不施工。貝葉斯決策的決策樹貝葉斯決策的決策樹126781110549不預報不預報預報預報預報好預報好0.31預報差預報差0.69施工施工施工施工不施工不施工不施工不施工施工施工不施工不施工天氣好天氣好 0.3天氣差天氣差 0.7天氣差天

59、氣差 0.91天氣好天氣好 0.09天氣差天氣差 0.23天氣好天氣好 0.77555-0.2-0.2-0.2-1-1-10.83.62-0.2-0.46-0.2-0.2-0.23.620.900.80.93成本成本0.08n繪制網(wǎng)絡圖的準備工作n確定目標：以時間要求還是資源費用要求為主n工程分解：列出全部分解后的工序及代號清單n工序關系：確定每一道工序的緊前工序是哪些n工序時間：確定每一道工序的完成所需的時間n一時估計法：僅估計一個完成工序的最大時間Dn三時估計法：樂觀時間 a、悲觀時間b、最可能時間m64bmaD 6ab n網(wǎng)絡圖繪制規(guī)則網(wǎng)絡圖繪制規(guī)則n方向、時序與結點編號方向、時序與結點

60、編號 網(wǎng)絡圖是有向圖，按流程的順序，規(guī)定工序從左向網(wǎng)絡圖是有向圖，按流程的順序，規(guī)定工序從左向右排列。網(wǎng)絡圖中的各個結點都有一個時間（某一右排列。網(wǎng)絡圖中的各個結點都有一個時間（某一個或若干個工序開始或結束時間），一般按結點的個或若干個工序開始或結束時間），一般按結點的時間順序編號（從左到右，從上到下），箭尾結點時間順序編號（從左到右，從上到下），箭尾結點編號應小于箭頭結點編號。始結點編號為編號應小于箭頭結點編號。始結點編號為1 1。n網(wǎng)絡圖中不能出現(xiàn)缺口和回路網(wǎng)絡圖中不能出現(xiàn)缺口和回路n二個結點之間只能有一個直接的工序二個結點之間只能有一個直接的工序 兩條箭線不能有同樣的始末結點，若二個事項