【正文】 則不劃算 ,因此再刪除該圖中 v1v2 ,v2v3 ,v3v4 ,v4v5 ,v5v6 五條連線后得到 從上圖中容易得到 v1到 v6只有兩條路： v1v3v6（費用 22+31） 和 v1v4v6 （費用 22+31） . 而這兩條路都是 v1到 v6的最短路 . 管 理 運 籌 學(xué) 39 167。 2 最短路問題 管 理 運 籌 學(xué) 35 167。試確定一個 5年計劃，使總支出最小。也可直接在無向圖中用 Dijkstra算法來求解。 2 最短路問題 例 2 電信公司準備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。 管 理 運 籌 學(xué) 30 167。 ija ?? ?)(sv tvsv tv)(P? ???PvvijjiP),()( ??sv tv)(m i n*)( PP ?? ?tvsv管 理 運 籌 學(xué) 28 最短路問題 網(wǎng)絡(luò)： 規(guī)定起點、中間點和終點的賦權(quán)圖； 有向網(wǎng)絡(luò)： 網(wǎng)絡(luò)中每個邊都是有向邊； 無向網(wǎng)絡(luò)： 網(wǎng)絡(luò)中每個邊都是無向邊； 混合網(wǎng)絡(luò)： 網(wǎng)絡(luò)中既有有向邊，又有無向邊； 網(wǎng)絡(luò)最短路線問題： 尋找網(wǎng)絡(luò)中從起點 v1 到終點 vn 的最短路線。在所有的 sij中，找到其值為最小的弧。如果 vt已標號（ lt,kt），則 vs到 vt的距離為 lt，而從 vs到 vt的最短路徑，則可以從 kt 反向追蹤到起點vs 而得到。 管 理 運 籌 學(xué) 26 167。 ? 連通圖 ： 對無向圖 G，若任何兩個不同的點之間，至少存在一條鏈，則 G為連通圖。相互認識用兩條反向的弧表示。 1 圖與網(wǎng)絡(luò)的基本概念 當然圖論不僅僅是要描述對象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的，如對趙等七人的相互認識關(guān)系我們也可以表示如下，可見圖論中的圖與幾何圖、工程圖是不一樣的。 管 理 運 籌 學(xué) 管 理 運 籌 學(xué) 22 167。 管 理 運 籌 學(xué) 1 2 3 7 6 4 5 管 理 運 籌 學(xué) 假定第一次就座方案是 （ 1， 2， 3， 4， 5， 6， 7， 1） ，那么第二次就座方案就不允許這些頂點之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 。 管 理 運 籌 學(xué) 第二階段 是從十九世紀中葉到二十世紀中葉 ， 這時 ， 圖論問題大量出現(xiàn) ， 如 Hamilton問題 ， 地圖染色的四色問題以及可平面性問題等 ， 這時 ， 也出現(xiàn)用圖解決實際問題 ， 如 Cayley把樹應(yīng)用于化學(xué)領(lǐng)域 ， Kirchhoff用樹去研究電網(wǎng)絡(luò)等 . 管 理 運 籌 學(xué) 第三階段 是二十世紀中葉以后 ， 由生產(chǎn)管理 、 軍事 、 交通 、 運輸 、 計算機網(wǎng)絡(luò)等方面提出實際問題 ， 以及大型計算機使大規(guī)模問題的求解成 為 可 能 ， 特 別 是 以 Ford 和Fulkerson建立的網(wǎng)絡(luò)流理論 ， 與線性規(guī)劃 、 動態(tài)規(guī)劃等優(yōu)化理論和方法相互滲透 ， 促進了圖論對實際問題的應(yīng)用 。 3 最小生成樹問題 167。管 理 運 籌 學(xué) 1 第五章 圖與網(wǎng)絡(luò)模型 167。 4 最大流問題 167。 管 理 運 籌 學(xué) 例 101： 哥尼斯堡七橋問題 哥尼斯堡 （ 現(xiàn)名加里寧格勒 ）是歐洲一個城市 ， Pregei河把該城分成兩部分 ， 河中有兩個小島 ， 十八世紀時 ， 河兩邊及小島之間共有七座橋 ， 當時人們提出這樣的問題：有沒有辦法從某處 （ 如 A） 出發(fā) ，經(jīng)過各橋一次且僅一次最后回到原地呢 ？ 管 理 運 籌 學(xué) A B C D 管 理 運 籌 學(xué) 最后 ， 數(shù)學(xué)家 Euler在 1736年巧妙地給出了這個問題的答案 ， 并因此奠定了圖論的基礎(chǔ) ， Euler把 A、B、 C、 D四塊陸地分別收縮成四個頂點 ， 把橋表示成連接對應(yīng)頂點之間的邊 ， 問題轉(zhuǎn)化為從任意一點出發(fā) ， 能不能經(jīng)過各邊一次且僅一次 ，最后返回該點 。 管 理 運 籌 學(xué) 1 2 3 7 6 4 5 管 理 運 籌 學(xué) 1 2 3 7 6 4 5 管 理 運 籌 學(xué) 假定第二次就座方案是 （ 1， 3， 5， 7， 2， 4， 6， 1） ，那么第三次就座方案就不允許這些頂點之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 。 1 圖與網(wǎng)絡(luò)的基本概念 圖論中圖是由點和邊構(gòu)成，可以反映一些對象之間的關(guān)系。 (v1) 趙 (v2)錢 孫 (v3) 李 (v4) 周 (v5) 吳 (v6) 陳 (v7) e2 e1 e3 e4 e5 管 理 運 籌 學(xué) 24 167。 管 理 運 籌 學(xué) 25 167。 ? 回路： 若路的第一個點和最后一個點相同，則該路為回路。 2 最短路問題 ? 最短路問題：對一個賦權(quán)的有向圖 D中的指定的兩個點 Vs和 Vt找到一條從 Vs 到 Vt 的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從 Vs到 Vt的最短路。如果 vt 未標號，則可以斷言不存在從 vs到 vt的有向路。不妨設(shè)此弧為（ Vc,Vd），則給此弧的終點以雙標號（ scd,c） ,返回步驟 2。 Min L(?) = ? lij ?為從 v1 到 vn 的通路； lij?? 其中， lij為從 vi 到 vj 的一步距離。 2 最短路問題 例 1 求下圖中 v1到 v6的最短路 解：采用 Dijkstra算法，可解得最短路徑為 v1 v3 v4 v6 各點的標號圖如下： 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 管 理 運 籌 學(xué) 31 網(wǎng)絡(luò)最短路線問題： 尋找網(wǎng)絡(luò)中從起點 v1 到終點 vn 的最短路線。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。只要在算法中把從已標號的點到未標號的點的弧的集合改成已標號的點到未標號的點的邊的集合即可。若已知設(shè)備在各年的購買費，及不同機器役齡時的殘值與維修費。 2 最短路問題 例的解： 將問題轉(zhuǎn)化為最短路問題，如下圖： 用 vi表示“第 i年年初購進一臺新設(shè)備” ,弧 （ vi,vj）表示第 i年年初購進的設(shè)備一直使用到第 j年年初。 3 最小生成樹問題 ? 樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。在圖中， (b)和 (c)都是 (a)的生成子圖。 3 最小生成樹問題 求解最小生成樹的破圈算法 算法的步驟： 在給定的賦權(quán)的連通圖上任找一個圈。 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) 管 理 運 籌 學(xué) 43 167。 v1 3 3 1 7 2 8 5 4 10 3 4 v7 v6 v5 v4 v2 v3 管 理 運 籌 學(xué) 44 167。 cij的單位為萬加侖 /小時。 1 , 2 , 712ij ijijm ax F = f ff f ff f f ff f f ff f ff f ff f f f ff c i jf i j???? ? ?? ? ?????? ? ? ?? ? ?? ? ?目 標 函 數(shù) ：約 束 條 件 ：管 理 運 籌 學(xué) 46 167。 我們把例 6的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運籌學(xué)軟件”，馬上得到以下的結(jié)果： f12=5， f14=5， f23=2，f25=3， f43=2， f46=1， f47=2， f35=2， f36=2， f57=5， f67=3。 應(yīng)該按照什么樣的加工順序來加工這六個零件，才能使得這六個零 件在車間里停留的平均時間為最少？ 零件 加工時間（小時） 零件 加工時間（小時） 1 2 3 4 5 6 管 理 運 籌 學(xué) 48 167。 5 車間作業(yè)計劃模型 二、兩臺機器、 n個零件 例 ，這些零件要求先在車床上車削，然后再在 磨床上加工，每臺機器上各零件加工時間如表 125所示。 零件 車床 磨床 零件 車床 磨床 1 2 3 4 5 管 理 運 籌 學(xué) 50 167。 5 車間作業(yè)計劃模型 尋找例 2的最優(yōu)解：我們在表 125中找到所列出的最短加工時間是 ,它是第二道工序磨床 加工零件 2的所需時間，由于這個時間與磨床有關(guān)，故我們把零件 2放在加工順序的末尾，即第五位，并在表中劃去零件 2 所在行。 下一個最短加工時間為 ，這個加工時間是車床（第一工序）加工零件 5的所需時間，故 把零件 5排在加工順序的第一位上，同時把表中的零件 5所在的行劃去。 這樣就得到了最優(yōu)加工順序： 5， 3， 4， 1， 2。在表上劃去零件 j的所在行，回到步驟 1。 工作 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管 理 運 籌 學(xué) 時間參數(shù)圖解 . 解上例： 計算事項 ? ? ? 時間參數(shù) ? ? ? ? 解上例：計算事項時間參數(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