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

1、運(yùn)籌學(xué),2,第九章 網(wǎng)絡(luò)計劃,網(wǎng)絡(luò)計劃圖 時間參數(shù)的計算 網(wǎng)絡(luò)計劃優(yōu)化,3,通過重組,打亂,優(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ò)計劃的，著名數(shù)學(xué)家華羅庚教授結(jié)合我國實(shí)際，在吸收國外網(wǎng)絡(luò)計劃技術(shù)理論的基礎(chǔ)上，將CPM、PERT等方法統(tǒng)一定名為統(tǒng)籌法。 統(tǒng)籌方法包括繪制計劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)。,統(tǒng)籌方法,4,統(tǒng)籌方法的第一步工作就是繪制計劃網(wǎng)絡(luò)圖，也就是將工序（或稱為活動）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的

2、網(wǎng)絡(luò)圖。 例9.1 某公司研制新產(chǎn)品的部分工序與所需時間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表如表所示，請畫出其網(wǎng)絡(luò)計劃圖。,第一節(jié) 網(wǎng)絡(luò)圖,2021/4/2,運(yùn)籌學(xué)-線性規(guī)劃-線性規(guī)劃-線性規(guī)劃,5,解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表 點(diǎn)表示一個事件,是一個或若干個工序的開始或結(jié)束,是相鄰工序在時間上的分界點(diǎn),點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號。 弧表示一個工序（或活動），弧的方向是從工序開始指向工序的結(jié)束，弧上是各工序的代號，下面標(biāo)以完成此工序所需的時間（或資源）等數(shù)據(jù)，即為對此弧所賦的權(quán)數(shù),6,圖1,7,例9.2 把例1的工序進(jìn)度表做一些擴(kuò)充，如表，請畫出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。,8,

3、解：虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時間。,9,在網(wǎng)絡(luò)圖上添加、工序得網(wǎng)絡(luò)圖3。 在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個點(diǎn)之間多于一條弧，因此增加了一個點(diǎn)和虛工序如圖4。,b,10,在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時，要注意圖中不能有缺口和回路。,16,圖4,避免交叉 節(jié)點(diǎn)標(biāo)號：j i,11,第二節(jié) 時間參數(shù)的計算 在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出： 1、完成此工程項(xiàng)目所需的最少時間。 2、每個工序的開始時間與結(jié)束時間。 3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。 4、非關(guān)鍵工序在不影響工程的完成時間的前提下，其開始時間與結(jié)束時間可以推遲多久。,2021/4

4、/2,12,一、工作時間 t (i, j ),確定型 概率型 缺乏統(tǒng)計來確定完成每個活動所需時間，但對所需時間做了三種估計： 1.樂觀時間。指所需最少時間，用a表示。 2.最可能時間。指正常時間，用m表示。 3.悲觀時間。指不順利情況下，最多時間，用b表示。,2021/4/2,13,例9.3,14,顯然這三種完成活動所需時間都具有一定概率，由經(jīng)驗(yàn)，我們可以可以假定這些時間的概率分布近似服從 分布。我們可以用如下公式計算出完成活動所需的：,方差,平均時間,例如：完成工作g所需平均時間：,同時求出方差為,15,同樣可以求出每個活動的完成所需平均時間及方差,16,1、最早時間 從網(wǎng)絡(luò)的發(fā)點(diǎn)開始，按順

5、序計算出每個工序的最早開始時間 （ES )和最早結(jié)束時間（EF),二、時間參數(shù),2021/4/2,17,例9.4,2021/4/2,18,2、最晚時間,從網(wǎng)絡(luò)的收點(diǎn)開始計算，在不影響整個工程最早結(jié)束時間的情 況下，各個工序的最晚結(jié)束時間（LF)和最晚開始時間(LS),19,2021/4/2,20,1、總時差 在不影響工程最早結(jié)束時間的條件下，工序最早開始（或結(jié)束）的時間可以推遲的時間，成為該工序的總時差R,三、時差,2021/4/2,21,2、單時差 在不影響緊后工序最早開始時間的條件下，工序最早開始（或結(jié)束）的時間可以推遲的時間，成為該工序的單時差r,2021/4/2,運(yùn)籌學(xué)-線性規(guī)劃-線性

6、規(guī)劃-線性規(guī)劃,22,四、關(guān)鍵工序，關(guān)鍵路線,網(wǎng)絡(luò)中最長的路線就決定了完成整個工程所需的最少時間，這條路線稱為關(guān)鍵路線。 總時差為0的工序?yàn)殛P(guān)鍵工序。,2021/4/2,23,例9-1,2021/4/2,運(yùn)籌學(xué)-線性規(guī)劃-線性規(guī)劃-線性規(guī)劃,24,2021/4/2,運(yùn)籌學(xué)-線性規(guī)劃-線性規(guī)劃-線性規(guī)劃,25,26,例9.4 某公司裝配一條新的生產(chǎn)線，具體過程如表1,求：完成此工程的最少時間，關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開始時間和非關(guān)鍵工序在不影響工程完成時間的前提下，其開始時間與結(jié)束時間可以推遲多久？,27,28,29,30,31,最后將各工序的時差，以及其他信息構(gòu)成工序時間表如表所

7、示。 這樣就找到了一條由關(guān)鍵工序a,d,g,i和j依次連接成的從發(fā)點(diǎn)到收點(diǎn)的關(guān)鍵路線。,2021/4/2,32,完成工序所需時間不確定,例9-2,2021/4/2,33,2021/4/2,運(yùn)籌學(xué)-線性規(guī)劃-線性規(guī)劃-線性規(guī)劃,34,2021/4/2,35,關(guān)鍵線路,2021/4/2,36,第三節(jié) 網(wǎng)絡(luò)計劃優(yōu)化,把串聯(lián)工作改為平行工作或平行交叉工作,2021/4/2,37,利用時差 總時差不影響最短工期，但影響后續(xù)工序的自由時間。 單時差不影響后續(xù)工序。,2021/4/2,38,3.時間-資源優(yōu)化,做法： 1）優(yōu)先安排關(guān)鍵工序所需的資源。 2）利用非關(guān)鍵工序的時差，錯開各工序的開始時間。 3）適

8、當(dāng)延長時差大的工序時間，或切斷非關(guān)鍵工序進(jìn)程。,2021/4/2,39,2021/4/2,40,2021/4/2,41,2021/4/2,運(yùn)籌學(xué)-線性規(guī)劃-線性規(guī)劃-線性規(guī)劃,42,4.工期成本優(yōu)化,直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、設(shè)備和工作班次，這需要增加一筆費(fèi)用，成為直接費(fèi)用。 間接費(fèi)用：由于工程早日完工，減少了管理人員的工資辦公費(fèi)等費(fèi)用稱為間接費(fèi)用。一般說工序越短，直接費(fèi)用越多，間接費(fèi)用越少。,43,工序的最快完成時間：指完成時間的最高限度。 我們設(shè)完成工序j的正常所需時間為Tj;直接費(fèi)用為cj;完成工序j的最快完成時間為Tj,直接費(fèi)用為cj。這樣我們可以計算出縮短工序j的一天

9、工期所增加的直接費(fèi)用，用kj表示，稱為直接費(fèi)用變動率（成本斜率）。有,44,模型一，在既定的時間T完工的前提下，問各工序的完成時間為多少才使因縮短工期而增加的直接費(fèi)用最少。 設(shè)工序（i ,j)的提前完工時間為yij,我們用Tij,Tij分別表示正常完工時間與最快完工的時間，則有工序（i ,j)的實(shí)際完工時間為：Tij- yij 。我們用Cij,Cij表示用正常完工時間和最快完成時間完成工序所需要的費(fèi)用，kij為工序（i ,j)的直接費(fèi)用變動率（成本斜率）。,45,方法一：線性規(guī)劃法 S.t. xj-xi Tij-yij, 對一切?。╥, j) yij Tij-Tij, 對一切?。╥, j) x

10、n-x1 T, xi 0， yij 0。,46,例9.5 例4所提供的信息都作為本例的信息，另外還給出了在裝配過程中各道工序所需正常完工時間與最快完工時間，以及對應(yīng)正常完工時間與最快完工時間的所需的直接費(fèi)用和每縮短一天工期所需增加的直接費(fèi)用，如表所示。,2021/4/2,運(yùn)籌學(xué)-線性規(guī)劃-線性規(guī)劃-線性規(guī)劃,47,48,該工程要求在150天內(nèi)完工，問每個工序應(yīng)比正常完工時間提前多少天完成，才能使整個工程因縮短工期而增加的直接費(fèi)用為最少。 如果工期要求在140天完工呢？,b,49,解：設(shè)此網(wǎng)絡(luò)圖上第i點(diǎn)發(fā)生的時間為xi，工序提前完工的時間為yij。 minf=120y27+300y23+400y

11、24+500y25+230y37+350y46+400y57+290y67. s.t. x2-x1 60-y12, x7- x2 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) 運(yùn)算得到結(jié)果：f=6400。,50,方法二：統(tǒng)籌法 從關(guān)鍵工序中找成本斜率最小的工序，壓縮工期

12、； 重新計算關(guān)鍵路線和關(guān)鍵工序； 再重復(fù)循環(huán)1和2，直至達(dá)到壓縮工期要求； 計算增加的總直接費(fèi)用,51,模型二，我們知道直接費(fèi)用是隨著完成時間的縮短而增加，而間接費(fèi)用卻會隨著完成時間的縮短而減少，設(shè)單位時間的間接費(fèi)用為d,計劃期的間接費(fèi)用與總工期成正比，即為d(xn-x1)。 那么求使包括間接費(fèi)用與直接費(fèi)用在內(nèi)的總費(fèi)用最少的整個工程最優(yōu)完成時間T和各個工序最優(yōu)完成時間的模型為： s. t. xj - xi Tij - yij，對一切?。╥ ,j) yij Tij - Tij ，對一切?。╥ ,j) xi 0， yij 0。,52,例9.6 如果在例5中，每天的間接費(fèi)用為330元，求使包括間接費(fèi)

13、用與直接費(fèi)用在內(nèi)的總費(fèi)用最少的整個工程最優(yōu)完成時間T和各個工序最優(yōu)完成時間。 解： min f=330(x8-x1) +120y27+300 y23 +400y24+500y25+230y37+350y46+290y67,s.t. x2-x1 60-y12, x7- x2 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,y120 y2715 y23 5 y24 10 y25 5 y37 8 y46 10 y57 5 y78 0 xi 0，yij 0.（對一切可能的ij),53,f=55700. x1=0, y12=0, y67 =10, x2=60, y27 =0, y78=0. x3 =125, y23 =0, x4 =107, y24 =0, x5 =110,