【正文】 公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。 管 理 運(yùn) 籌 學(xué) 這樣上述設(shè)備更新問題就變?yōu)椋涸谟邢蛸x權(quán)圖 G = (V, E, F )(圖解如下 )中求 v1到 v6的最短路問題 . 31)865(13)(30)865(11)(,59)1811865(11)(635261?????????????????vvvvvv???管 理 運(yùn) 籌 學(xué) 由實(shí)際問題可知 ,設(shè)備使用三年后應(yīng)當(dāng)更新 ,因此刪除該圖中 v1到 v5 ,v1到 v6 ,v2到 v6的連線；又設(shè)備使用一年后就更新則不劃算 ,因此再刪除該圖中 v1v2 ,v2v3 ,v3v4 ,v4v5 ,v5v6 五條連線后得到 從上圖中容易得到 v1到 v6只有兩條路： v1v3v6（費(fèi)用 22+31） 和 v1v4v6 （費(fèi)用 22+31） . 而這兩條路都是 v1到 v6的最短路 . 管 理 運(yùn) 籌 學(xué) 39 167。 “管理運(yùn)籌學(xué)軟件”有專門的子程序可以解決最小生成樹問題。 5 車間作業(yè)計(jì)劃模型 一、一臺(tái)機(jī)器、 n個(gè)零件的排序問題 例 ，常常出現(xiàn)很多零件同時(shí)要求這臺(tái) 磨床加工的情況，現(xiàn)有六個(gè)零件同時(shí)要求加工，這六個(gè)零件加工所需時(shí)間 如下表所示。如表 126中黃色線條所示。 表 3 工序代號(hào) 工序內(nèi)容 所需時(shí)間（天 ) 緊前工序 a b c d e 產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì) 外購配套零件 外購生產(chǎn)原料 自制主件 主配可靠性試驗(yàn) 60 15 13 38 8 a a c b,d 管 理 運(yùn) 籌 學(xué) 61 167。 關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。 解：由表，繪出統(tǒng)籌方法的網(wǎng)絡(luò)圖如圖 12所示。 6 統(tǒng)籌方法 下面就用平均時(shí)間代替完成活動(dòng)所需時(shí)間，并在網(wǎng)絡(luò)圖上標(biāo)上每個(gè)活 動(dòng)最早開始時(shí)間和最早結(jié)束時(shí)間，如圖 1214所示。 下面列舉一個(gè)拉平資源需要量最高峰的實(shí)例。一般說工序越短，直接費(fèi)用越多，間接費(fèi)用越少。如果工期要 求在 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。 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í)間完工。 jjjjjTTcck``????管 理 運(yùn) 籌 學(xué) 88 167。 6 統(tǒng)籌方法 費(fèi)用優(yōu)化 需要考慮時(shí)間與費(fèi)用的問題：在既定的時(shí)間前工程完工的前提下，使 得所需的費(fèi)用最少，或者在不超工程預(yù)算的條件下使工程最早完工。根據(jù)計(jì) 劃目標(biāo)，綜合考慮資源和降低成本等目標(biāo)，進(jìn)行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的計(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ì)算出每一個(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。 6 統(tǒng)籌方法 在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路 。 6 統(tǒng)籌方法 管 理 運(yùn) 籌 學(xué) 網(wǎng)絡(luò)規(guī)則 ? 避免循環(huán)、不留缺口 ? 一一對(duì)應(yīng)：一道工序用兩個(gè)事項(xiàng)表示 ? 3 、從左向右依次展開 例： 工 序 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)鍵路線法－－ CPM 時(shí)間參數(shù)運(yùn)算 什么是關(guā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） } 到齊上課，最后到者決定最早開課時(shí)間 事項(xiàng)最遲時(shí)間 TL(i)＝ min{TL(j) t（ i， j） } 保證 12點(diǎn)吃飯，路最遠(yuǎn)者決定最遲下課時(shí)間 工序最早可能開工時(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é) 工序最遲必須開工時(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í)差：在不影響其緊后工序 最遲必須 開工時(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í)差：在不影響其緊后工序 最早可能 開工時(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)。 1 2 3 4 5 1 車床 磨床 2 3 4 5 0 10 管 理 運(yùn) 籌 學(xué) 51 167。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流 {fij}稱之為可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點(diǎn)總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。 管 理 運(yùn) 籌 學(xué) 42 167。 2 最短路問題 管 理 運(yùn) 籌 學(xué) 35 167。 管 理 運(yùn) 籌 學(xué) 30 167。 管 理 運(yùn) 籌 學(xué) 26 167。 管 理 運(yùn) 籌 學(xué) 管 理 運(yùn) 籌 學(xué) 22 167。管 理 運(yùn) 籌 學(xué) 1 第五章 圖與網(wǎng)絡(luò)模型 167。 1 圖與網(wǎng)絡(luò)的基本概念 圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。 2 最短路問題 ? 最短路問題：對(duì)一個(gè)賦權(quán)的有向圖 D中的指定的兩個(gè)點(diǎn) Vs和 Vt找到一條從 Vs 到 Vt 的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從 Vs到 Vt的最短路。 2 最短路問題 例 1 求下圖中 v1到 v6的最短路 解：采用 Dijkstra算法，可解得最短路徑為 v1 v3 v4 v6 各點(diǎn)的標(biāo)號(hào)圖如下： v2 3 5 2 7 5 3 1 5 1 2 v1 v6 v5 v3 v4 (3,1) v2 3 5 2 7 5 3 1 5 1 2 V1 （ 0,s) v5 (8,4) v6 (2,1) v3 (3,3) v4 管 理 運(yùn) 籌 學(xué) 31 網(wǎng)絡(luò)最短路線問題： 尋找網(wǎng)絡(luò)中從起點(diǎn) v1 到終點(diǎn) vn 的最短路線。 2 最短路問題 例的解： 將問題轉(zhuǎn)化為最短路問題，如下圖： 用 vi表示“第 i年年初購進(jìn)一臺(tái)新設(shè)備” ,弧 （ vi,vj）表示第 i年年初購進(jìn)的設(shè)備一直使用到第 j年年初。 3 最小生成樹問題 例 用破圈算法求圖（ a）中的一個(gè)最小生成樹 v1 3 3 1 7 2 8 5 4 10 3 4 v7 v6 v5 v4 v2 v1 3 3 1 7 2 8 5 4 3 4 v7 v6 v5 v4 v2 v1 3 3 7 2 5 4 3 4 v7 v6 v5 v4 v2 v3 v3 v3 1 v1 3 3 7 2 4 3 4 v7 v6 v5 v4 v2 v3 1 v1 3 3 7 2 3 4 v7 v6 v5 v4 v2 v3 1 v1 3 3 7 2 3 v7 v6 v5 v4 v2 v3 1 (a) (b) (c) (d) (e) (f) 管 理 運(yùn) 籌 學(xué) 43 167。 我們把例 6的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運(yùn)籌學(xué)軟件”，馬上得到以下的結(jié)果： f12=5， f14=5， f23=2，f25=3， f43=2， f46=1， f47=2， f35=2， f36=2， f57=5， f67=3。 5 車間作業(yè)計(jì)劃模型 尋找例 2的最優(yōu)解：我們在表 125中找到所列出的最短加工時(shí)間是 ,它是第二道工序磨床 加工零件 2的所需時(shí)間，由于這個(gè)時(shí)間與磨床有關(guān)，故我們把零件 2放在加工順序的末尾，即第五位，并在表中劃去零件 2 所在行。 工作 A工作 A工作 A 的緊后工作 BES i jLS i jEF i jLF i jES j kEF j kLS i kLF j k工作a的 總時(shí)差工作 a 的自由時(shí)差工作A的 總時(shí)差最早開始最遲開始TF i j = L S i j E S i jTF i j = L F i j E F i jFF i j = E S j k E F i j工作持續(xù)時(shí)間 Di i j管 理 運(yùn) 籌 學(xué) 時(shí)間參數(shù)圖解 . 解上例： 計(jì)算事項(xiàng) ? ? ? 時(shí)間參數(shù) ? ? ? ? 解上例：計(jì)算事項(xiàng)時(shí)間參數(shù)TES TLS TEF TLF TES TLS TEF TLS r(i,j) R（ i,j） A4 B6 C6 G7 D7 E5