【正文】 tra算法來(lái)求解。 2 最短路問(wèn)題 管 理 運(yùn) 籌 學(xué) 35 167。 3 最小生成樹(shù)問(wèn)題 給了一個(gè)無(wú)向圖 G=(V,E)，我們保留 G的所有點(diǎn)，而刪掉部分 G的邊或者說(shuō)保留一部分 G的邊，所獲得的圖 G，稱(chēng)之為 G的生成子圖。 管 理 運(yùn) 籌 學(xué) 42 167。由于管道的直徑的變化，它的各段管道（ vi,vj）的流量 cij（容量）也是不一樣的。我們把滿(mǎn)足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流 {fij}稱(chēng)之為可行流，（即線(xiàn)性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點(diǎn)總流出量最大）的稱(chēng)之為最大流（即線(xiàn)性規(guī)劃的最優(yōu)解）。 管 理 運(yùn) 籌 學(xué) 49 167。 1 2 3 4 5 1 車(chē)床 磨床 2 3 4 5 0 10 管 理 運(yùn) 籌 學(xué) 51 167。如表 126中黑色線(xiàn)條 所示。 6 統(tǒng)籌方法 管 理 運(yùn) 籌 學(xué) 網(wǎng)絡(luò)規(guī)則 ? 避免循環(huán)、不留缺口 ? 一一對(duì)應(yīng)：一道工序用兩個(gè)事項(xiàng)表示 ? 3 、從左向右依次展開(kāi) 例： 工 序 A B C D E F G H I 緊前工序 A B B C、 D C、 D E、 F G 工序時(shí)間 4 6 6 7 5 9 7 4 8 ? ? ? ? ? ? A,4 B,6 D,7 E,5 F,9 H,4 I,8 C,6 G,7 管 理 運(yùn) 籌 學(xué) 關(guān)鍵路線(xiàn)法－－ CPM 時(shí)間參數(shù)運(yùn)算 什么是關(guān)鍵路線(xiàn)？ 作業(yè)時(shí)間 t（ i， j），經(jīng)驗(yàn)數(shù)據(jù)、統(tǒng)計(jì)數(shù)據(jù) 事項(xiàng)最早時(shí)間 TE(j)＝ max{TE(i)+ t（ i， j） } 到齊上課，最后到者決定最早開(kāi)課時(shí)間 事項(xiàng)最遲時(shí)間 TL(i)＝ min{TL(j) t（ i， j） } 保證 12點(diǎn)吃飯，路最遠(yuǎn)者決定最遲下課時(shí)間 工序最早可能開(kāi)工時(shí)間 TES(i,j)＝ TE(i) = max{TES(h,i)+ t（ h,i ） } 工序最早可能完工時(shí)間 TEF(i,j)＝ TES(i,j)+ t（ i， j） 管 理 運(yùn) 籌 學(xué) 工序最遲必須開(kāi)工時(shí)間 TLS（ i,j)＝ TL(j)－ t（ i,j)＝ min{TLs(j,k) t（ i， j） } 工序最遲必須完工時(shí)間 TLF（ i,j)＝ TL(j)＝ TLS（ i,j)+ t（ i,j) 工序總時(shí)差：在不影響其緊后工序 最遲必須 開(kāi)工時(shí)間的前提下，本工序可以推遲的時(shí)間 R（ i,j）＝ TLS(i,j)－ TES(i,j) ＝ TLF(i,j)－ TEF(i,j) ＝ min{TLS(j,k) } – TEF（ i,j） 工序單時(shí)差：在不影響其緊后工序 最早可能 開(kāi)工時(shí)間的前提下，本工序可以推遲的時(shí)間 r （ i,j）＝ min{TES(j,k) } – TEF（ i,j） 管 理 運(yùn) 籌 學(xué) 計(jì)算關(guān)系式 ? 這些時(shí)間參數(shù)的關(guān)系可以用下圖表示工作的關(guān)系狀態(tài)。 表 5 工序代號(hào) 所需時(shí)間（天） 緊前工序 工序代號(hào) 所需時(shí)間（天） 緊前工序 a b c d 60 15 13 38 － a a c e f g h 8 10 16 5 b，ｄ d d e，ｆ，ｇ 管 理 運(yùn) 籌 學(xué) 63 167。 6 統(tǒng)籌方法 在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路 。 6 統(tǒng)籌方法 表 10 工序代號(hào) 工序內(nèi)容 所需時(shí)間（天） 緊前工序 a b c d e f g h i j 生產(chǎn)線(xiàn)設(shè)計(jì) 外購(gòu)零配件 下料、鍛件 工裝制造 1 木模、鑄件 機(jī)械加工 1 工裝制造 2 機(jī)械加工 2 機(jī)械加工 3 裝配調(diào)試 60 45 10 20 40 18 30 15 25 35 / a a a a c d d,e g b,i,f,h 管 理 運(yùn) 籌 學(xué) 68 167。 接著，可以計(jì)算出每一個(gè)工序的時(shí)差，把在不影響工程最早結(jié)束時(shí)間 的條件下，工序最早開(kāi)始（或結(jié)束）的時(shí)間可以推遲的時(shí)間，成為該工序 的時(shí)差，對(duì)每個(gè)工序來(lái)說(shuō)其時(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。 6 統(tǒng)籌方法 由于是第一次搞培訓(xùn)，缺乏統(tǒng)計(jì)來(lái)確定完成每個(gè)活動(dòng)所需時(shí)間， 但對(duì)所需時(shí)間做了三種估計(jì)： 。 ? PERT的時(shí)間估計(jì) 采用三種時(shí)間估計(jì)法 a－最樂(lè)觀時(shí)間， b－最悲觀時(shí)間， m－最可能時(shí)間，則 工序期望時(shí)間 te＝ 方差 δe2＝（ ） 2 a+4m+b 6 b－ a 6 管 理 運(yùn) 籌 學(xué) 77 167。則完成培訓(xùn)工作所需的平均時(shí)間為各關(guān)鍵路線(xiàn) 的時(shí)間之和： =2+3+4+4+2=15（周） 同時(shí)完成時(shí)間近似服從一定的概率分布正態(tài)分布，則均值為關(guān)鍵路線(xiàn) 上各關(guān)鍵活動(dòng)之均值之和 15，方差也為關(guān)鍵路線(xiàn)上各關(guān)鍵活動(dòng)方差之和 。根據(jù)計(jì) 劃目標(biāo)，綜合考慮資源和降低成本等目標(biāo)，進(jìn)行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的計(jì) 劃方案。 管 理 運(yùn) 籌 學(xué) 84 167。 6 統(tǒng)籌方法 費(fèi)用優(yōu)化 需要考慮時(shí)間與費(fèi)用的問(wèn)題：在既定的時(shí)間前工程完工的前提下，使 得所需的費(fèi)用最少，或者在不超工程預(yù)算的條件下使工程最早完工。直接費(fèi)用為 cj。 jjjjjTTcck``????管 理 運(yùn) 籌 學(xué) 88 167。 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)籌方法 x3 =125, y23 =0, x4 =107, y24 =0, x5 =110, y25 =0, x6 =110, y37 =0, x7 =125, y46 =0, x8 =160, y57 =0, 也就是說(shuō)整個(gè)工程工期為 160天時(shí)總費(fèi)用最少為 55700元，各個(gè) 工序開(kāi)始時(shí)間如解所示，工序 i 要提前 10天完工，其余的工序按正 常時(shí)間完工。 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í)間。如果工期要 求在 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í)間 T完工的前提下，問(wèn)各工序的完成時(shí)間為多少才使因 縮短工期而增加的直接費(fèi)用最少。一般說(shuō)工序越短，直接費(fèi)用越多，間接費(fèi)用越少。 6 統(tǒng)籌方法 同時(shí)我們應(yīng)優(yōu)先安排關(guān)鍵工序所需的工人，再利用非關(guān)鍵工序的時(shí) 差，錯(cuò)開(kāi)各工序的開(kāi)始時(shí)間，從而拉平工人需要量的高峰。 下面列舉一個(gè)拉平資源需要量最高峰的實(shí)例。查正態(tài)分布函數(shù)表可知概率為 。 6 統(tǒng)籌方法 下面就用平均時(shí)間代替完成活動(dòng)所需時(shí)間，并在網(wǎng)絡(luò)圖上標(biāo)上每個(gè)活 動(dòng)最早開(kāi)始時(shí)間和最早結(jié)束時(shí)間，如圖 1214所示。 。 解：由表，繪出統(tǒng)籌方法的網(wǎng)絡(luò)圖如圖 12所示。 6 統(tǒng)籌方法 ? 下面我們給出找關(guān)鍵路線(xiàn)的辦法 首先，從網(wǎng)絡(luò)的發(fā)點(diǎn)開(kāi)始，按順序計(jì)算出每個(gè)工序的最早開(kāi)始時(shí)間 （ ES )和最早結(jié)束時(shí)間（ EF) ，設(shè)一個(gè)工序所需的時(shí)間為 t，這對(duì)于同一 個(gè)工序來(lái)說(shuō)，有 EF=ES+t。 關(guān)鍵路線(xiàn)及其應(yīng)用的關(guān)鍵工序。 1 5 2 6 4 3 a 60 b 15 8 e 10 13 d c 38 f 圖 5 管 理 運(yùn) 籌 學(xué) 64 167。 表 3 工序代號(hào) 工序內(nèi)容 所需時(shí)間（天 ) 緊前工序 a b c d e 產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì) 外購(gòu)配套零件 外購(gòu)生產(chǎn)原料 自制主件 主配可靠性試驗(yàn) 60 15 13 38 8 a a c b,d 管 理 運(yùn) 籌 學(xué) 61 167。 在加工所需時(shí)間表上選出最短加工時(shí)間 tij，這是第 i工序加工 j零件所需時(shí)間，當(dāng) i=1時(shí)，將零件 j的順序盡量靠前，若 i=2時(shí)，將零件 j的順序盡量 靠后。如表 126中黃色線(xiàn)條所示。我們用圖 121 中的線(xiàn)條圖來(lái)表示各零件加工的開(kāi)始時(shí)間與完成時(shí)間，這種圖是由一根時(shí)間軸和 車(chē)床、磨床在每個(gè)時(shí)間段的狀況的圖形所構(gòu)成。 5 車(chē)間作業(yè)計(jì)劃模型 一、一臺(tái)機(jī)器、 n個(gè)零件的排序問(wèn)題 例 ，常常出現(xiàn)很多零件同時(shí)要求這臺(tái) 磨床加工的情況，現(xiàn)有六個(gè)零件同時(shí)要求加工，這六個(gè)零件加工所需時(shí)間 如下表所示。 1 , 2 , 70 , 1 , 2 , , 6 。 “管理運(yùn)籌學(xué)軟件”有專(zhuān)門(mén)的子程序可以解決最小生成樹(shù)問(wèn)題。 (a) (b) (c) 管 理 運(yùn) 籌 學(xué) 41 167。 管 理 運(yùn) 籌 學(xué) 這樣上述設(shè)備更新問(wèn)題就變?yōu)椋涸谟邢蛸x權(quán)圖 G = (V, E, F )(圖解如下 )中求 v1到 v6的最短路問(wèn)題 . 31)865(13)(30)865(11)(,59)1811865(11)(635261?????????????????vvvvvv???管 理 運(yùn) 籌 學(xué) 由實(shí)際問(wèn)題可知 ,設(shè)備使用三年后應(yīng)當(dāng)更新