【正文】 用來表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時間。 每個工序的開始時間與結(jié)束時間。 1 2 3 4 6 7 8 5 a 60 b 45 e c h j 35 i g 10 30 d 20 40 25 f 18 15 管 理 運(yùn) 籌 學(xué) 69 167。 管 理 運(yùn) 籌 學(xué) 73 三、完成工序所需時間與關(guān)鍵路線 當(dāng)完成工序所需時間不確定的情況下如何求網(wǎng)絡(luò)時間和關(guān)鍵路線？ 例 6. 長征研究院培訓(xùn)中心負(fù)責(zé)明年春天的各干部的工商管理培訓(xùn)，培訓(xùn)中心列出有關(guān)培訓(xùn)組織的各項(xiàng)活動的信息，要求繪制出統(tǒng)籌方法的網(wǎng)絡(luò)圖，設(shè)法求出網(wǎng)絡(luò)時間和關(guān)鍵路線，并確定開始這個組織工作的時間以保證培訓(xùn)工作如期舉行。指正常時間，用 m表示。 6 統(tǒng)籌方法 同樣可以求出每個活動的完成所需平均時間及方差，如表 1214： 表 1214 活動 T（平均時間） 方差 活動 T 方差 a 2 f 2 b 3 g 4 c 2 h 4 d 2 i 2 e 1 管 理 運(yùn) 籌 學(xué) 79 167。 式中的 T為預(yù)定完工時間 16， E（ T） =15， 算得 u=。 3）統(tǒng)籌兼顧工程進(jìn)度的要求和現(xiàn)有資源的限制，多次綜合平衡。 2 7 4 6 3 5 f(22人） 18 h(39人 ) 15 58人 64人 80人 81人 42人 26人 65人 60 80 100 120 130 d(58人） i(26人） g(42人） 30 20 25 圖 1217 管 理 運(yùn) 籌 學(xué) 85 167。 間接費(fèi)用：由于工程早日完工，減少了管理人員的工資辦公費(fèi)等費(fèi)用 稱為間接費(fèi)用。有 時間 費(fèi)用優(yōu)化問題可建立兩個線性規(guī)劃模型。 6 統(tǒng)籌方法 該工程要求在 150天內(nèi)完工，問每個工序應(yīng)比正常完工時間提前多少天 完成，才能使整個工程因縮短工期而增加的直接費(fèi)用為最少。 ? ?j)(i, ijij )y(k管 理 運(yùn) 籌 學(xué) 93 167。 。 管 理 運(yùn) 籌 學(xué) 92 167。 6 統(tǒng)籌方法 例 7. 例 5所提供的信息都作為本例的信息，另外還給出了在裝配過程中各道工序所需正常完工時間與最快完工時間，以及對應(yīng)正常完工時間與最快完工時間的所需的直接費(fèi)用和每縮短一天工期所需增加的直接費(fèi)用，如表 1217所示。完成工序 j的最快完成時 間為 T`j,直接費(fèi)用為 c`j。這些 是時間 費(fèi)用優(yōu)化要研究和解決的問題。 6 統(tǒng)籌方法 在圖的上半部中，工序代號后的數(shù)字是人數(shù)，線下面的數(shù)字是非關(guān)鍵 工序時差長度。 資源優(yōu)化 做法： 1）優(yōu)先安排關(guān)鍵工序所需的資源。 由此我們可以計算出此項(xiàng)培訓(xùn)組織工作不同完工時間的概率，如 16周 內(nèi)完工的概率。 6 統(tǒng)籌方法 顯然這三種完成活動所需時間都具有一定概率，由經(jīng)驗(yàn)，我們可以 可以假定這些時間的概率分布近似服從 分布。指所需最少時間，用 a表示。 6 統(tǒng)籌方法 最后將各工序的時差，以及其他信息構(gòu)成工序時間表如表所示。 6 統(tǒng)籌方法 解：據(jù)表 10,繪制網(wǎng)絡(luò)圖如圖 8。 1 2 5 7 8 3 4 a 60 15 b e c 13 d 38 8 h 5 10 f 6 16 g 圖 127 管 理 運(yùn) 籌 學(xué) 66 167。 6 統(tǒng)籌方法 解：我們把工序 e 擴(kuò)充到圖 5發(fā)生了問題，由于ｄ是 e 的緊前工序，故ｄ的結(jié)束應(yīng)該是 e 的開始，所以代表 e 的弧的起點(diǎn)應(yīng)該是④，由于工序ｂ的結(jié)束也是④，所以工序ｂ也成了工序 e 的緊前工序，與題意不符。 工作 A工作 A工作 A 的緊后工作 BES i jLS i jEF i jLF i jES j kEF j kLS i kLF j k工作a的 總時差工作 a 的自由時差工作A的 總時差最早開始最遲開始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ù)時間 Di i j管 理 運(yùn) 籌 學(xué) 時間參數(shù)圖解 . 解上例： 計算事項(xiàng) ? ? ? 時間參數(shù) ? ? ? ? 解上例：計算事項(xiàng)時間參數(shù)TES TLS TEF TLF TES TLS TEF TLS r(i,j) R（ i,j） A4 B6 C6 G7 D7 E5 F9 H4 I 8 0 0 4 7 6 13 22 20 28 28 20 24 13 6 關(guān)鍵路線：由總時差為零的工序構(gòu)成 B D G I t（ i,j) t（ j,k) 管 理 運(yùn) 籌 學(xué) ? 解上例 計算工序時間參數(shù) 工序 i j t(i,j) ES EF LS LF R r A ? ? 4 0 4 3 7 3 0 B ? ? 6 0 6 0 6 0 0 C ? ? 6 4 10 7 13 3 3 D ? ? 7 6 13 6 13 0 0 E ? ? 5 6 11 19 24 13 11 F ? ? 9 13 22 15 24 2 0 G ? ? 7 13 20 13 20 0 0 H ? ? 4 22 26 24 28 2 2 I ? ? 8 20 28 20 28 0 0 管 理 運(yùn) 籌 學(xué) 60 167。 這樣就得到了最優(yōu)加工順序： 5， 3， 4， 1， 2。 5 車間作業(yè)計劃模型 尋找例 2的最優(yōu)解：我們在表 125中找到所列出的最短加工時間是 ,它是第二道工序磨床 加工零件 2的所需時間，由于這個時間與磨床有關(guān)，故我們把零件 2放在加工順序的末尾，即第五位，并在表中劃去零件 2 所在行。 5 車間作業(yè)計劃模型 二、兩臺機(jī)器、 n個零件 例 ，這些零件要求先在車床上車削，然后再在 磨床上加工，每臺機(jī)器上各零件加工時間如表 125所示。 我們把例 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。 cij的單位為萬加侖 /小時。 3 最小生成樹問題 例 用破圈算法求圖（ a）中的一個最小生成樹 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。在圖中， (b)和 (c)都是 (a)的生成子圖。 2 最短路問題 例的解： 將問題轉(zhuǎn)化為最短路問題，如下圖： 用 vi表示“第 i年年初購進(jìn)一臺新設(shè)備” ,弧 （ vi,vj）表示第 i年年初購進(jìn)的設(shè)備一直使用到第 j年年初。只要在算法中把從已標(biāo)號的點(diǎn)到未標(biāo)號的點(diǎn)的弧的集合改成已標(biāo)號的點(diǎn)到未標(biāo)號的點(diǎn)的邊的集合即可。 2 最短路問題 例 1 求下圖中 v1到 v6的最短路 解：采用 Dijkstra算法，可解得最短路徑為 v1 v3 v4 v6 各點(diǎn)的標(biā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 的最短路線。不妨設(shè)此弧為（ Vc,Vd），則給此弧的終點(diǎn)以雙標(biāo)號（ scd,c） ,返回步驟 2。 2 最短路問題 ? 最短路問題：對一個賦權(quán)的有向圖 D中的指定的兩個點(diǎn) Vs和 Vt找到一條從 Vs 到 Vt 的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從 Vs到 Vt的最短路。 管 理 運(yùn) 籌 學(xué) 25 167。 1 圖與網(wǎng)絡(luò)的基本概念 圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對象之間的關(guān)系。 管 理 運(yùn) 籌 學(xué) 例 101： 哥尼斯堡七橋問題 哥尼斯堡 （ 現(xiàn)名加里寧格勒 ）是歐洲一個城市 ， Pregei河把該城分成兩部分 ， 河中有兩個小島 ， 十八世紀(jì)時 ， 河兩邊及小島之間共有七座橋 ， 當(dāng)時人們提出這樣的問題：有沒有辦法從某處 （ 如 A） 出發(fā) ，經(jīng)過各橋一次且僅一次最后回到原地呢 ？ 管 理 運(yùn) 籌 學(xué) A B C D 管 理 運(yùn) 籌 學(xué) 最后 ， 數(shù)學(xué)家 Euler在 1736年巧妙地給出了這個問題的答案 ， 并因此奠定了圖論的基礎(chǔ) ， Euler把 A、B、 C、 D四塊陸地分別收縮成四個頂點(diǎn) ， 把橋表示成連接對應(yīng)頂點(diǎn)之間的邊 ， 問題轉(zhuǎn)化為從任意一點(diǎn)出發(fā) ， 能不能經(jīng)過各邊一次且僅一次 ，最后返回該點(diǎn) 。管 理 運(yùn) 籌 學(xué) 1 第五章 圖與網(wǎng)絡(luò)模型 167。 管 理 運(yùn) 籌 學(xué) 第二階段 是從十九世紀(jì)中葉到二十世紀(jì)中葉 ， 這時 ， 圖論問題大量出現(xiàn) ， 如 Hamilton問題 ， 地圖染色的四色問題以及可平面性問題等 ， 這時 ， 也出現(xiàn)用圖解決實(shí)際問題 ， 如 Cayley把樹應(yīng)用于化學(xué)領(lǐng)域 ， Kirchhoff用樹去研究電網(wǎng)絡(luò)等 . 管 理 運(yùn) 籌 學(xué) 第三階段 是二十世紀(jì)中葉以后 ， 由生產(chǎn)管理 、 軍事 、 交通 、 運(yùn)輸 、 計算機(jī)網(wǎng)絡(luò)等方面提出實(shí)際問題 ， 以及大型計算機(jī)使大規(guī)模問題的求解成 為 可 能 ， 特 別 是 以 Ford 和Fulkerson建立的網(wǎng)絡(luò)流理論 ， 與線性規(guī)劃 、 動態(tài)規(guī)劃等優(yōu)化理論和方法相互滲透 ， 促進(jìn)了圖論對實(shí)際問題的應(yīng)用 。 管 理 運(yùn) 籌 學(xué) 管 理 運(yùn) 籌 學(xué) 22 167。相互認(rèn)識用兩條反向的弧表示。 管 理 運(yùn) 籌 學(xué) 26 167。在所有的 sij中，找到其值為最小的弧。 管 理 運(yùn) 籌 學(xué) 30 167。也可直接在無向圖中用 Dijks