【正文】 7。 圖 8 如圖 8 ,① ② ③ ⑦ ⑧ 就是一條關(guān)鍵路線，我們要干完所有的工序 就必須走完所有這樣的路線，由于很多工序可以同時(shí)進(jìn)行，所以網(wǎng)絡(luò)中最 長(zhǎng)的路線就決定了完成整個(gè)工程所需的最少時(shí)間，這條路線稱為關(guān)鍵路 線。 6 統(tǒng)籌方法 ? 下面我們給出找關(guān)鍵路線的辦法 首先，從網(wǎng)絡(luò)的發(fā)點(diǎn)開始，按順序計(jì)算出每個(gè)工序的最早開始時(shí)間 （ ES )和最早結(jié)束時(shí)間（ EF) ，設(shè)一個(gè)工序所需的時(shí)間為 t，這對(duì)于同一 個(gè)工序來說，有 EF=ES+t。 6 統(tǒng)籌方法 圖 10 其次 ,從網(wǎng)絡(luò)的收點(diǎn)開始計(jì)算出在不影響整個(gè)工程最早結(jié)束時(shí)間的情 況下各個(gè)工序的最晚開始時(shí)間 (縮寫為 LS)和最晚結(jié)束時(shí)間（縮寫為 LF), 顯然對(duì)同一工序有 LS=LFt 1 2 3 6 7 8 5 a[0,60] 60 b[60,105] 45 e[] c[60,70] h[100,115] j[135,170] 35 i[] g[80,110] 30 d[] 20 40 25 f[70,88] 18 4 10 15 管 理 運(yùn) 籌 學(xué) 71 167。 接著，可以計(jì)算出每一個(gè)工序的時(shí)差，把在不影響工程最早結(jié)束時(shí)間 的條件下，工序最早開始（或結(jié)束）的時(shí)間可以推遲的時(shí)間，成為該工序 的時(shí)差，對(duì)每個(gè)工序來說其時(shí)差記為 Ts有 Ts=LSES=LFEF 1 2 3 6 7 8 5 a[0,60] 60[0,60] b[60,105] 45[90,135] e[] c[60,70] h[100,115] j[135,170] 35[135,170] i[] g[80,110] 30[80,110] d[] 20[60,80] 40[80,120] 25[110,135] f[70,88] 18[117,135] 4 10[107,117] 15[120,135 管 理 運(yùn) 籌 學(xué) 72 167。 這樣就找到了一條由關(guān)鍵工序 a,d,g,i和 j依次連接成的從發(fā)點(diǎn)到收點(diǎn)的 關(guān)鍵路線。 解：由表，繪出統(tǒng)籌方法的網(wǎng)絡(luò)圖如圖 12所示。 6 統(tǒng)籌方法 管 理 運(yùn) 籌 學(xué) 74 167。 6 統(tǒng)籌方法 由于是第一次搞培訓(xùn)，缺乏統(tǒng)計(jì)來確定完成每個(gè)活動(dòng)所需時(shí)間， 但對(duì)所需時(shí)間做了三種估計(jì)： 。 。 。如表 13所示： 表 13 單位：周 活動(dòng) 樂觀時(shí)間 最可能時(shí)間 悲觀時(shí)間 a b c d e f g h i 管 理 運(yùn) 籌 學(xué) 計(jì)劃評(píng)審技術(shù)－－ PERT ? PERT的產(chǎn)生 關(guān)鍵路線法中，工序時(shí)間是確定值，而對(duì)研究性的工序來說， t（ i， j）是隨機(jī)的。 ? PERT的時(shí)間估計(jì) 采用三種時(shí)間估計(jì)法 a－最樂觀時(shí)間， b－最悲觀時(shí)間， m－最可能時(shí)間，則 工序期望時(shí)間 te＝ 方差 δe2＝（ ） 2 a+4m+b 6 b－ a 6 管 理 運(yùn) 籌 學(xué) 77 167。我們可以用如下公式計(jì) 算出完成活動(dòng)所需的平均時(shí)間： 以及方差 例如：完成工作 g所需平均時(shí)間： 同時(shí)求出方差為 ?64 bmaT ???262 )( ab ???46 ???????? bmaT g94管 理 運(yùn) 籌 學(xué) 78 167。 6 統(tǒng)籌方法 下面就用平均時(shí)間代替完成活動(dòng)所需時(shí)間，并在網(wǎng)絡(luò)圖上標(biāo)上每個(gè)活 動(dòng)最早開始時(shí)間和最早結(jié)束時(shí)間，如圖 1214所示。 a[0,2] g[5,9] b[2,5] e[5,6] d[2,4] f[6,8] c[0,2] i[13,15] h[9,13] 3 2 2 2 1 4 2 4 2 1 2 3 4 5 8 7 6 a[0,2] g[5,9] b[2,5] e[5,6] d[2,4] f[6,8] c[0,2] i[13,15] h[9,13] 2[1,3] 1[10,11] 4[5,9] 4[9,13] 2[3,5] 2[0,2] 3[2,5] 2[13,15] 2[11,13] 圖 1214 圖 1215 管 理 運(yùn) 籌 學(xué) 80 167。則完成培訓(xùn)工作所需的平均時(shí)間為各關(guān)鍵路線 的時(shí)間之和： =2+3+4+4+2=15（周） 同時(shí)完成時(shí)間近似服從一定的概率分布正態(tài)分布，則均值為關(guān)鍵路線 上各關(guān)鍵活動(dòng)之均值之和 15，方差也為關(guān)鍵路線上各關(guān)鍵活動(dòng)方差之和 。 為求此概率，可以先求 u值。查正態(tài)分布函數(shù)表可知概率為 。 6 統(tǒng)籌方法 其正態(tài)分布圖如圖 1216所示： 16 15)(??TE?圖 1216 管 理 運(yùn) 籌 學(xué) 82 167。根據(jù)計(jì) 劃目標(biāo)，綜合考慮資源和降低成本等目標(biāo)，進(jìn)行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的計(jì) 劃方案。 2）利用非關(guān)鍵工序的時(shí)差，錯(cuò)開各工序的開始時(shí)間。 下面列舉一個(gè)拉平資源需要量最高峰的實(shí)例。如表 16所示： 管 理 運(yùn) 籌 學(xué) 83 167。 管 理 運(yùn) 籌 學(xué) 84 167。圖的下半部表示從第 60天至 135天內(nèi)的 75天里，所需機(jī)械 加工工人數(shù)，這樣的圖稱為資源負(fù)荷圖。 6 統(tǒng)籌方法 同時(shí)我們應(yīng)優(yōu)先安排關(guān)鍵工序所需的工人，再利用非關(guān)鍵工序的時(shí) 差，錯(cuò)開各工序的開始時(shí)間，從而拉平工人需要量的高峰。找到了時(shí)間 資源 優(yōu)化的方案，如圖 1218所示，在不增加工人的情況下保證了工程按期完 成。 6 統(tǒng)籌方法 費(fèi)用優(yōu)化 需要考慮時(shí)間與費(fèi)用的問題：在既定的時(shí)間前工程完工的前提下，使 得所需的費(fèi)用最少，或者在不超工程預(yù)算的條件下使工程最早完工。 直接費(fèi)用：為了加快工程進(jìn)度，需要增加人力、設(shè)備和工作班次，這 需要增加一筆費(fèi)用，成為直接費(fèi)用。一般說工序越短，直接費(fèi)用越多，間接費(fèi)用越少。 6 統(tǒng)籌方法 工序的最快完成時(shí)間：指完成時(shí)間的最高限度。直接費(fèi)用為 cj。這樣我們可以計(jì)算出縮短工序 j的一天工期所增加的直接 費(fèi)用，用 kj表示，稱為直接費(fèi)用變動(dòng)率。 模型一，在既定的時(shí)間 T完工的前提下，問各工序的完成時(shí)間為多少才使因 縮短工期而增加的直接費(fèi)用最少。我們用 Cij,C`ij表示用正 常完工時(shí)間和最快完成時(shí)間完成工序所需要的費(fèi)用， Kij為工序（ i ,j)的直接費(fèi)用 變動(dòng)率。 jjjjjTTcck``????管 理 運(yùn) 籌 學(xué) 88 167。 表 1217 工序 Tij正常完工 Cij直接費(fèi)用 T`ij最快完工 C`ij直接費(fèi)用 直接費(fèi)用變動(dòng)率 a 60 10000 60 10000 b 45 4500 30 6300 120 c 10 2800 5 4300 300 d 20 7000 10 11000 400 e 40 10000 35 12500 500 f 18 3600 10 5440 230 g 30 9000 20 12500 350 h 15 3750 10 5750 400 i 25 6250 15 9150 290 j 35 12022 35 12022 管 理 運(yùn) 籌 學(xué) 89 167。如果工期要 求在 140天完工呢？ 1 2 3 4 5 6 7 8 a b f e c h g i j d 圖 1219 管 理 運(yùn) 籌 學(xué) 90 167。 設(shè)此網(wǎng)絡(luò)圖上第 i點(diǎn)發(fā)生的時(shí)間為 xi，工序提前完工的時(shí)間為 yij。 6 統(tǒng)籌方法 x1 =0, y12?0, y27?15, y23 ?5 y24 ?10 y25 ?5 y37 ?8 y46 ?10 y57 ?5 y78 ?0 x8 ?150 xi ?0， yij ?0.（對(duì)一切可能的 ij) 運(yùn)算得到結(jié)果： f=6400。 6 統(tǒng)籌方法 模型二，我們知道直接費(fèi)用是隨著完成時(shí)間的縮短而增加，而間接費(fèi)用卻會(huì)隨著完成時(shí)間的縮短而減少，設(shè)單位時(shí)間的間接費(fèi)用為 d,計(jì)劃期的間接費(fèi)用與總工期成正比，即為 d(xnx1),那么求使包括間接費(fèi)用與直接費(fèi)用在內(nèi)的總費(fèi)用最少的整個(gè)工程最優(yōu)完成時(shí)間 T和各個(gè)工序最優(yōu)完成時(shí)間的模型為： 目標(biāo)函數(shù) min f=d(xnx1)+ . xjxi ? Tijyij，對(duì)一切?。?i ,j) yij?TijT`ij ，對(duì)一切?。?i ,j) xi ?0， yij ?0。 6 統(tǒng)籌方法 例 8 如果在例 7中，每天的間接費(fèi)用為 330元，求使包括間接費(fèi)用與直接費(fèi) 用在內(nèi)的總費(fèi)用最少的整個(gè)工程最優(yōu)完成時(shí)間 T和各個(gè)工序最優(yōu)完成時(shí)間。 此數(shù)學(xué)模型的目標(biāo)函數(shù)為： min f=330(x8x1) +120y27+300 y23 +400y24+500y25+230y37+350y46+290y67 此模型的約束條件與例 7的約束條件基本相同，只要在例子的約束條件中去 掉 x8 ?150就得到了例 8模型的約束條件了。 6 統(tǒng)籌方法 x3 =125, y23 =0, x4 =107, y24 =0, x5 =110, y25 =0, x6 =110, y37 =0, x7 =125, y46 =0, x8 =160, y57 =0, 也就是說整個(gè)工程工期為 160天時(shí)總費(fèi)用最少為 55700元，各個(gè) 工序開始時(shí)間如解所示，工序 i 要提前 10天完工，其余的工序按正 常時(shí)