運(yùn)籌學(xué)第九章網(wǎng)絡(luò)計(jì)劃 胡運(yùn)權(quán)【高級(jí)課堂】

1、運(yùn)籌學(xué),趙明霞 山西大學(xué)經(jīng)濟(jì)與管理學(xué)院,1,高等課堂,第九章 網(wǎng)絡(luò)計(jì)劃,網(wǎng)絡(luò)計(jì)劃圖 時(shí)間參數(shù)的計(jì)算 網(wǎng)絡(luò)計(jì)劃優(yōu)化,2,高等課堂,通過(guò)重組,打亂,優(yōu)化等手段改變?cè)镜墓逃修k事格式,優(yōu)化辦事效率的一種辦事方法。 一種安排工作進(jìn)程的數(shù)學(xué)方法。 它的實(shí)用范圍極廣泛，在企業(yè)管理和基本建設(shè)中，以及關(guān)系復(fù)雜的科研項(xiàng)目的組織與管理中，都可以應(yīng)用。 我國(guó)，是從20世紀(jì)60年代開(kāi)始運(yùn)用網(wǎng)絡(luò)計(jì)劃的，著名數(shù)學(xué)家華羅庚教授結(jié)合我國(guó)實(shí)際，在吸收國(guó)外網(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,高等課堂,統(tǒng)籌方法的第一步工作就是繪制

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

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

4、時(shí)間的前提下，其開(kāi)始時(shí)間與結(jié)束時(shí)間可以推遲多久,11,高等課堂,一、工作時(shí)間 t (i, j,確定型 概率型 缺乏統(tǒng)計(jì)來(lái)確定完成每個(gè)活動(dòng)所需時(shí)間，但對(duì)所需時(shí)間做了三種估計(jì)： 1.樂(lè)觀時(shí)間。指所需最少時(shí)間，用a表示。 2.最可能時(shí)間。指正常時(shí)間，用m表示。 3.悲觀時(shí)間。指不順利情況下，最多時(shí)間，用b表示,12,高等課堂,例9.3,13,高等課堂,顯然這三種完成活動(dòng)所需時(shí)間都具有一定概率，由經(jīng)驗(yàn)，我們可以可以假定這些時(shí)間的概率分布近似服從 分布。我們可以用如下公式計(jì)算出完成活動(dòng)所需的,方差,平均時(shí)間,例如：完成工作g所需平均時(shí)間,同時(shí)求出方差為,14,高等課堂,同樣可以求出每個(gè)活動(dòng)的完成所需平均

5、時(shí)間及方差,15,高等課堂,1、最早時(shí)間 從網(wǎng)絡(luò)的發(fā)點(diǎn)開(kāi)始，按順序計(jì)算出每個(gè)工序的最早開(kāi)始時(shí)間 （ES )和最早結(jié)束時(shí)間（EF,二、時(shí)間參數(shù),16,高等課堂,例9.4,17,高等課堂,2、最晚時(shí)間,從網(wǎng)絡(luò)的收點(diǎn)開(kāi)始計(jì)算，在不影響整個(gè)工程最早結(jié)束時(shí)間的情 況下，各個(gè)工序的最晚結(jié)束時(shí)間（LF)和最晚開(kāi)始時(shí)間(LS,18,高等課堂,19,高等課堂,1、總時(shí)差 在不影響工程最早結(jié)束時(shí)間的條件下，工序最早開(kāi)始（或結(jié)束）的時(shí)間可以推遲的時(shí)間，成為該工序的總時(shí)差R,三、時(shí)差,20,高等課堂,2、單時(shí)差 在不影響緊后工序最早開(kāi)始時(shí)間的條件下，工序最早開(kāi)始（或結(jié)束）的時(shí)間可以推遲的時(shí)間，成為該工序的單時(shí)差r,2

6、1,高等課堂,四、關(guān)鍵工序，關(guān)鍵路線(xiàn),網(wǎng)絡(luò)中最長(zhǎng)的路線(xiàn)就決定了完成整個(gè)工程所需的最少時(shí)間，這條路線(xiàn)稱(chēng)為關(guān)鍵路線(xiàn)。 總時(shí)差為0的工序?yàn)殛P(guān)鍵工序,22,高等課堂,例9-1,23,高等課堂,24,高等課堂,25,高等課堂,例9.4 某公司裝配一條新的生產(chǎn)線(xiàn)，具體過(guò)程如表1,求：完成此工程的最少時(shí)間，關(guān)鍵路線(xiàn)及相應(yīng)的關(guān)鍵工序，各工序的最早開(kāi)始時(shí)間和非關(guān)鍵工序在不影響工程完成時(shí)間的前提下，其開(kāi)始時(shí)間與結(jié)束時(shí)間可以推遲多久,26,高等課堂,27,高等課堂,28,高等課堂,29,高等課堂,30,高等課堂,最后將各工序的時(shí)差，以及其他信息構(gòu)成工序時(shí)間表如表所示。 這樣就找到了一條由關(guān)鍵工序a,d,g,i和j依

7、次連接成的從發(fā)點(diǎn)到收點(diǎn)的關(guān)鍵路線(xiàn),31,高等課堂,完成工序所需時(shí)間不確定,例9-2,32,高等課堂,33,高等課堂,34,高等課堂,關(guān)鍵線(xiàn)路,35,高等課堂,第三節(jié) 網(wǎng)絡(luò)計(jì)劃優(yōu)化,把串聯(lián)工作改為平行工作或平行交叉工作,36,高等課堂,利用時(shí)差 總時(shí)差不影響最短工期，但影響后續(xù)工序的自由時(shí)間。 單時(shí)差不影響后續(xù)工序,37,高等課堂,3.時(shí)間-資源優(yōu)化,做法： 1）優(yōu)先安排關(guān)鍵工序所需的資源。 2）利用非關(guān)鍵工序的時(shí)差，錯(cuò)開(kāi)各工序的開(kāi)始時(shí)間。 3）適當(dāng)延長(zhǎng)時(shí)差大的工序時(shí)間，或切斷非關(guān)鍵工序進(jìn)程,38,高等課堂,39,高等課堂,40,高等課堂,41,高等課堂,4.工期成本優(yōu)化,直接費(fèi)用：為了加快工程

8、進(jìn)度，需要增加人力、設(shè)備和工作班次，這需要增加一筆費(fèi)用，成為直接費(fèi)用。 間接費(fèi)用：由于工程早日完工，減少了管理人員的工資辦公費(fèi)等費(fèi)用稱(chēng)為間接費(fèi)用。一般說(shuō)工序越短，直接費(fèi)用越多，間接費(fèi)用越少,42,高等課堂,工序的最快完成時(shí)間：指完成時(shí)間的最高限度。 我們?cè)O(shè)完成工序j的正常所需時(shí)間為T(mén)j;直接費(fèi)用為cj;完成工序j的最快完成時(shí)間為T(mén)j,直接費(fèi)用為cj。這樣我們可以計(jì)算出縮短工序j的一天工期所增加的直接費(fèi)用，用kj表示，稱(chēng)為直接費(fèi)用變動(dòng)率（成本斜率）。有,43,高等課堂,模型一，在既定的時(shí)間T完工的前提下，問(wèn)各工序的完成時(shí)間為多少才使因縮短工期而增加的直接費(fèi)用最少。 設(shè)工序（i ,j)的提前完工時(shí)

9、間為yij,我們用Tij,Tij分別表示正常完工時(shí)間與最快完工的時(shí)間，則有工序（i ,j)的實(shí)際完工時(shí)間為：Tij- yij 。我們用Cij,Cij表示用正常完工時(shí)間和最快完成時(shí)間完成工序所需要的費(fèi)用，kij為工序（i ,j)的直接費(fèi)用變動(dòng)率（成本斜率,44,高等課堂,方法一：線(xiàn)性規(guī)劃法 S.t. xj-xi Tij-yij, 對(duì)一切?。╥, j) yij Tij-Tij, 對(duì)一切?。╥, j) xn-x1 T, xi 0， yij 0,45,高等課堂,例9.5 例4所提供的信息都作為本例的信息，另外還給出了在裝配過(guò)程中各道工序所需正常完工時(shí)間與最快完工時(shí)間，以及對(duì)應(yīng)正常完工時(shí)間與最快完工時(shí)間

10、的所需的直接費(fèi)用和每縮短一天工期所需增加的直接費(fèi)用，如表所示,46,高等課堂,47,高等課堂,該工程要求在150天內(nèi)完工，問(wèn)每個(gè)工序應(yīng)比正常完工時(shí)間提前多少天完成，才能使整個(gè)工程因縮短工期而增加的直接費(fèi)用為最少。 如果工期要求在140天完工呢,b,48,高等課堂,解：設(shè)此網(wǎng)絡(luò)圖上第i點(diǎn)發(fā)生的時(shí)間為xi，工序提前完工的時(shí)間為yij。 minf=120y27+300y23+400y24+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

11、-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.（對(duì)一切可能的ij) 運(yùn)算得到結(jié)果：f=6400,49,高等課堂,方法二：統(tǒng)籌法 從關(guān)鍵工序中找成本斜率最小的工序，壓縮工期； 重新計(jì)算關(guān)鍵路線(xiàn)和關(guān)鍵工序； 再重復(fù)循環(huán)1和2，直至達(dá)到壓縮工期要求； 計(jì)算增加的總直接費(fèi)用,50,高等課堂,模型二，我們知道直接費(fèi)用是隨著完成時(shí)間的縮短而增加，而間接費(fèi)用卻會(huì)隨著完成時(shí)間的縮短而減少，設(shè)單位

12、時(shí)間的間接費(fèi)用為d,計(jì)劃期的間接費(fèi)用與總工期成正比，即為d(xn-x1)。 那么求使包括間接費(fèi)用與直接費(fèi)用在內(nèi)的總費(fèi)用最少的整個(gè)工程最優(yōu)完成時(shí)間T和各個(gè)工序最優(yōu)完成時(shí)間的模型為： s. t. xj - xi Tij - yij，對(duì)一切弧（i ,j) yij Tij - Tij ，對(duì)一切?。╥ ,j) xi 0， yij 0,51,高等課堂,例9.6 如果在例5中，每天的間接費(fèi)用為330元，求使包括間接費(fèi)用與直接費(fèi)用在內(nèi)的總費(fèi)用最少的整個(gè)工程最優(yōu)完成時(shí)間T和各個(gè)工序最優(yōu)完成時(shí)間。 解： min f=330(x8-x1) +120y27+300 y23 +400y24+500y25+230y37+

13、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.（對(duì)一切可能的ij,52,高等課堂,f=55700. x1=0, y12=0, y67 =10, x2=60, y27 =0, y78=0. x3 =125, y23 =0, x4 =107, y24 =0, x5 =110