1、高等運籌第八講高等運籌第八講目錄第一篇 運籌學(xué)發(fā)展歷史 第二篇 運籌學(xué)中的數(shù)學(xué)規(guī)劃 第三篇 運籌學(xué)中的組合優(yōu)化第四篇 運籌學(xué)中的隨機優(yōu)化 第五篇 運籌學(xué)中的博弈論 第六篇 運籌學(xué)中管理科學(xué)第七篇 運籌學(xué)中智能計算第八篇 運籌學(xué)發(fā)展勢態(tài)目錄第一篇 運籌學(xué)發(fā)展歷史 第三篇 運籌學(xué)中的組合優(yōu)化第十章 圖論第十一章 組合數(shù)學(xué)及相關(guān)問題第三篇 運籌學(xué)中的組合優(yōu)化第十章 圖論組合優(yōu)化組合優(yōu)化是20世紀(jì)60年代逐漸發(fā)展起來的一個交叉學(xué)科分支，它的研究對象是有限集合上的極值問題。一個組合優(yōu)化間題由三部分構(gòu)成:已知條件的輸入、可行解的描述、目標(biāo)函數(shù)的定義.經(jīng)典的組合優(yōu)化問題包括網(wǎng)絡(luò)流、旅行商、排序、裝箱、著色、

2、覆蓋、最短網(wǎng)絡(luò)等等。組合優(yōu)化組合優(yōu)化是20世紀(jì)60年代逐漸發(fā)展起來的一個交叉學(xué)科組合優(yōu)化的一個理論基礎(chǔ)是計算復(fù)雜性理論，據(jù)此組合優(yōu)化的可以分為兩類:P一問題類和NP一難問題類;屬于前者的問題有多項式時間算法，屬于后者的問題一般認為不存在多項式時間算法，通常采用精確算法、啟發(fā)式算法和近似算法等方法求解。組合優(yōu)化的一個理論基礎(chǔ)是計算復(fù)雜性理論，據(jù)此組合優(yōu)化的可以分精確算法包括簡單枚舉法、分而治之法、分支定界法、動態(tài)規(guī)劃法等;啟發(fā)式算法包括貪婪策略、局部搜索、禁忌搜索、神經(jīng)網(wǎng)絡(luò)、模擬退火、遺傳算法等;近似算法包括貪婪策略法、局部搜索法、原始對偶法、劃分法、松弛法、內(nèi)點算法、半定規(guī)劃等;精確算法包括簡

3、單枚舉法、分而治之法、分支定界法、動態(tài)規(guī)劃法等這些算法并不是彼此無關(guān)的。特別是近十幾年，針對某個間題的特點，將多個已有算法結(jié)合起來設(shè)計一個高效的集成型算法得到了發(fā)展。組合優(yōu)化與圖論、組合學(xué)、數(shù)理邏輯等有密切關(guān)系，在計算機科學(xué)、信息科學(xué)、管理科學(xué)和生命科學(xué)等學(xué)科有廣泛的應(yīng)用。這些算法并不是彼此無關(guān)的。特別是近十幾年，針對某個間題的特點第十章 圖論從哥尼斯堡七橋問題談起第十章 圖論從哥尼斯堡七橋問題1736年歐拉解決了哥尼斯堡的七橋問題，這被公認為圖論的第一個結(jié)果。此后的200多年里，圖論并未被視為是數(shù)學(xué)的一個分支，圖論的問題通常被看作一類智力游戲。然而，自20世紀(jì)30年代開始，圖論通過其廣泛的應(yīng)

4、用以及與數(shù)學(xué)其他分支的緊密聯(lián)系日顯其重要性。尤其是，圖論作為計算機科學(xué)的基礎(chǔ)之一，在運籌學(xué)中扮演著不可或缺的角色，很多非常難解的組合優(yōu)化問題都屬于NP一完全的圖論問題。1736年歐拉解決了哥尼斯堡的七橋問題，這被公認為圖論的第一10哥尼斯堡七橋問題(Bridges of Koenigsberg)能不能走過每一個橋剛好一次并且回到原來的地方？12哥尼斯堡七橋問題(Bridges of Koenigs11解決七橋問題的歐拉 尤拉（Leonard Euler; 1707 1783），瑞士人，出身于牧師家庭，13 歲考入大學(xué)，16 歲已經(jīng)獲得碩士學(xué)位。1727 年到俄國圣彼得科學(xué)院工作。1741 年轉(zhuǎn)

5、到德國，任柏林科學(xué)院物理數(shù)學(xué)所所長。1766 年回到俄國，直至去世。他在 1735 年，由于過度工作的關(guān)系，引至右眼失明。1771 年又因眼疾引致左眼失明。1783年逝世于俄國的圣彼得堡。 著作有無窮微量分析入門，無窮小分析引論（1748），微分學(xué)原理（1755），關(guān)于曲面上曲線的研究（1766），積分學(xué)原理（1768-1770），方程的積分法研究等。尤拉是數(shù)學(xué)史上最多產(chǎn)的數(shù)學(xué)家，我們現(xiàn)在習(xí)以為常的數(shù)學(xué)符號很多都是尤拉所發(fā)明介紹的，例如：函數(shù)符號f(x)、圓周率、自然對數(shù)的底 e、求和符號 、log x、sinx、cosx以及虛數(shù)單位 i 等，論著涉及的范圍非常之廣泛，他的成就對后世數(shù)學(xué)發(fā)展有

6、深遠的影響。13解決七橋問題的歐拉 尤拉（Leonard Euler; 12解決七橋問題的方法尤拉解決問題問題的第一步把問題抽象化。他想到：島的形狀、大小及橋的長短并不影響結(jié)果，位置才是重點。他把四大塊陸地縮成四個點，而把七座橋變成七條線，于是，就畫出了如此之圖形。14解決七橋問題的方法尤拉解決問題問題的第一步把問題抽象化13解決七橋問題的方法七橋問題就變成以下的問題：是否存在一個循環(huán)通過每一條邊，而且每邊只經(jīng)過一次？這樣的循環(huán)我們稱之為尤拉循環(huán)或者“一筆畫”問題。15解決七橋問題的方法14一筆畫定理終于，1736年，尤拉證實了自己的猜想七橋問題的走法根本不存在。并發(fā)表了他的一筆畫定理：一個圖

7、形要能一筆畫完成必須符合兩個狀況：圖形是封閉連通的。圖形中的奇點個數(shù)為0或2。 七橋問題中的四個點全部都是奇點，所以無法一次走完七座橋。16一筆畫定理終于，1736年，尤拉證實了自己的猜想七橋問15哈密頓（Hamilton）周遊世界問題哈密頓路徑至今尚無有效方法來解決！正十二面體有二十個頂點表示世界上20個城市各經(jīng)每個城市一次最后返回原地投影至平面17哈密頓（Hamilton）周遊世界問題哈密頓路徑至今尚無16實際生活中的圖論Graph Model18實際生活中的圖論Graph Model17電路模擬例：Pspice、Cadence、ADS.PspiceCadence19電路模擬例：Pspic

8、e、Cadence、ADS.18交通網(wǎng)絡(luò)航空網(wǎng)絡(luò)!捷運路線圖！20交通網(wǎng)絡(luò)航空網(wǎng)絡(luò)!捷運路線圖！19某學(xué)校網(wǎng)絡(luò)架構(gòu)圖計算機網(wǎng)絡(luò)21某學(xué)校網(wǎng)絡(luò)架構(gòu)圖計算機網(wǎng)絡(luò)20有向圖有單行道的街道！行程表！22有向圖有單行道的街道！行程表！21走迷宮與深度優(yōu)先搜索(Depth-First Search)老鼠走迷宮深度優(yōu)先搜索一直往前走碰壁就回頭換條路找沿途要記錄下走過的路線23走迷宮與深度優(yōu)先搜索(Depth-First Searc22 1圖的基本概念和術(shù)語24 1圖的基本概念和術(shù)語23什么是圖？一堆頂點和邊的組合！Set of vertices connected pairwise by edges. 例一

9、 例二 25什么是圖？一堆頂點和邊的組合！例一 24圖論的術(shù)語頂點 (Vertex)邊 (Edge)一個圖G = (V,E)V: 頂點的集合E: 邊的集合例：如右圖V= a,b,c,d,eE= (a,b),(a,c),(a,d),(b,e),(c,d),(c,e),(d,e)26圖論的術(shù)語頂點 (Vertex)25再來一些術(shù)語連通圖 (connected graph)子圖(subgraph)樹(tree)沒有回路的連通圖森林 (forest) 一堆樹的集合27再來一些術(shù)語連通圖 (connected graph)26樹的實例 行政組織圖28樹的實例 行政組織圖27有向圖(Digraph)有向圖

10、 (Digraph)有向且無簡單回路的圖(directed acyclic graph)29有向圖(Digraph)有向圖 (Digraph)有向且28加權(quán)圖(Weighted Graph)圖片來源：雷欽隆老師“資料結(jié)構(gòu)”課投影片30加權(quán)圖(Weighted Graph)圖片來源：雷欽隆老29生成樹(Spanning Tree)生成樹包括圖中所有的頂點，并且是一棵樹31生成樹(Spanning Tree)生成樹包括圖中所有的30一些特殊的圖32一些特殊的圖31完全圖 Complete graphs任意兩點之間都有一條邊與其相連的圖稱為完全圖，以Kn 來表示，n為頂點數(shù)33完全圖 Complet

11、e graphs任意兩點之間都有一32二分圖（偶圖） Bipartite graphsA graph that can be decomposed into two partite sets but not fewer is bipartiteIt is a complete bipartite if its vertices can be divided into two non-empty groups, A and B. Each vertex in A is connected to B, and vice-versa Complete bipartite graph K2,3The

12、graph is bipartite34二分圖（偶圖） Bipartite graphsA gr33平面圖 Planar graphsA planar graph is a graph that can be embedded in a plane so that no edges intersectPlanar:=NOT Planar:35平面圖 Planar graphsA planar gr34平面圖實例8個頂點(V=8)12條邊 (E=12)6個面 (F=6)8-12+6=236平面圖實例8個頂點(V=8)35更多平面圖實例 37更多平面圖實例 36樹 Trees 樹(tree):連通

13、無簡單回路無向圖若有n個頂點，則有n-1條邊任兩點之間僅有一條路徑生成樹 (spanning tree):包括圖中所有的頂點，并且是一棵樹A connected graph GSpanning trees of Gtree38樹 Trees 樹(tree):連通無簡單回路無向圖A 37 2最小生成樹問題樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。 圖11-11中，(a)就是一個樹，而(b)因為圖中有圈所以就不是樹， (c)因為不連通所以也不是樹。圖11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)39 2最

14、小生成樹問題樹是圖論中的重要概念，所謂樹就是一38最小生成樹問題 給了一個無向圖G=(V,E)，我們保留G的所有點，而刪掉部分G的邊或者說保留一部分G的邊，所獲得的圖G，稱之為G的生成子圖。在圖11-12中，(b)和(c)都是(a)的生成子圖。 如果圖G的一個生成子圖還是一個樹，則稱這個生成子圖為生成樹，在圖11-12中，(c)就是(a)的生成樹。 最小生成樹問題就是指在一個賦權(quán)的連通的無向圖G中找出一個生成樹，并使得這個生成樹的所有邊的權(quán)數(shù)之和為最小。圖11-12(a)(b)(c)40最小生成樹問題 給了一個無向圖G=(V,E)，39最小生成樹問題一、求解最小生成樹的破圈算法算法的步驟：1、

15、在給定的賦權(quán)的連通圖上任找一個圈。2、在所找的圈中去掉一個權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。3、如果所余下的圖已不包含圈，則計算結(jié)束，所余下的圖即為最小生成樹，否則返回第1步。41最小生成樹問題一、求解最小生成樹的破圈算法40最小生成樹問題例4 用破圈算法求圖（a）中的一個最小生成樹v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31

16、(a)(b)(c)(d)(e)(f)圖11-1342最小生成樹問題例4 用破圈算法求圖（a）中的一個最小41 3 最短路問題從旅游談起43 3 最短路問題從旅游談起42條條大路通廣州大連廣州44條條大路通廣州大連廣州43最短路問題最短路問題：對一個賦權(quán)的有向圖D中的指定的兩個點Vs和Vt找到一條從 Vs 到 Vt 的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從Vs到Vt的距離。45最短路問題最短路問題：對一個賦權(quán)的有向圖D中的指定的兩一、求解最短路的Dijkstra算法(雙標(biāo)號法）步驟：1.給出點V1以標(biāo)號(0,s)2.找出已標(biāo)

17、號的點的集合I，沒標(biāo)號的點的集合J以及弧的集 3. 如果上述弧的集合是空集，則計算結(jié)束。如果vt已標(biāo)號（lt,kt），則 vs到vt的距離為lt，而從 vs到vt的最短路徑，則可以從kt 反向追蹤到起點vs 而得到。如果vt 未標(biāo)號，則可以斷言不存在從 vs到vt的有向路。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。4. 對上述弧的集合中的每一條弧，計算 sij=li+cij 。在所有的 sij中，找到其值為最小的弧。不妨設(shè)此弧為（Vc,Vd），則給此弧的終點以雙標(biāo)號（scd,c）,返回步驟2。一、求解最短路的Dijkstra算法(雙標(biāo)號法）45最短路問題 例1 電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一

18、條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。 V1 （甲地）1517624441065v2V7 （乙地）v3v4v5v647最短路問題 例1 電信公司準(zhǔn)46最短路問題 例3 設(shè)備更新問題。某公司使用一臺設(shè)備，在每年年初，公司就要決定是購買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費，當(dāng)然新設(shè)備的維修費用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費，但維修費用就高了。請設(shè)計一個五年之內(nèi)的更新設(shè)備的計劃，使得五年內(nèi)購置費用和維修費用總的支付費用最小。 已知：設(shè)備每年年初的價格表 設(shè)備維修費如下表年份12345年初價格1

19、111121213使用年數(shù)0-11-22-33-44-5每年維修費用568111848最短路問題 例3 設(shè)備更新問47最短路問題例3的解： 將問題轉(zhuǎn)化為最短路問題，如下圖： 用vi表示“第i年年初購進一臺新設(shè)備”,?。╲i,vj）表示第i年年初購進的設(shè)備一直使用到第j年年初。把所有弧的權(quán)數(shù)計算如下表：v1v2v3v4v5v612345611622304159216223041317233141723518649最短路問題例3的解：v1v2v3v4v5v61234548最短路問題 (繼上頁) 把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。 最終得到下圖，可知，v1到v6的距離是53，最短路徑

20、有兩條： v1 v3 v6和 v1 v4 v6v1v2v3v4v5v6162230415916223041312317181723 V1（0,s）v3v4(41,1) v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)50最短路問題 (繼上頁) 把權(quán)數(shù)賦到圖中，再用Dijkst49 4 最大流問題最大流問題：給一個帶收發(fā)點的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點到收點的最大流量。一、最大流的數(shù)學(xué)模型 例6 某石油公司擁有一個管道網(wǎng)絡(luò)，使用這個網(wǎng)絡(luò)可以把石油從采地運送到一些銷售點，這

21、個網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（vi,vj）的流量cij（容量）也是不一樣的。cij的單位為萬加侖/小時。如果使用這個網(wǎng)絡(luò)系統(tǒng)從采地 v1向銷地 v7運送石油，問每小時能運送多少加侖石油？v563522241263v1v2v7v4v3v6圖11-2651 4 最大流問題最大流問題：給一個帶收發(fā)點的網(wǎng)50最大流問題 我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型： 設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上的總的流量為F，則有：52最大流問題 我們可以為此例題建立線性規(guī)51最大流問題 在這個線性規(guī)劃模型中，其約束條件中的前6個方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點的流出量

22、必須等于收點的總流入量；其余的點稱之為中間點，它的總流入量必須等于總流出量。其后面幾個約束條件表示對每一條弧(vi,vj)的流量fij要滿足流量的可行條件，應(yīng)小于等于弧(vi,vj)的容量cij，并大于等于零，即0fij cij。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流 fij稱之為可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點總流出量最大）的稱之為最大流（即線性規(guī)劃的最優(yōu)解）。 我們把例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

23、=5，f67=3。最優(yōu)值（最大流量）=10。53最大流問題 在這個線性規(guī)劃模型中，其約束條件中52最大流問題二、最大流問題網(wǎng)絡(luò)圖論的解法 對網(wǎng)絡(luò)上弧的容量的表示作改進。為省去弧的方向，如下圖: (a)和(b)、(c)和(d)的意義相同。 用以上方法對例6的圖的容量標(biāo)號作改進，得下圖vivjvivjcij0（a）（b） cijcijvivj（cji）（c）vivj cij cji（d）63522241263v1v2v5v7v4v3v60000000000054最大流問題二、最大流問題網(wǎng)絡(luò)圖論的解法 對網(wǎng)絡(luò)上53最大流問題 求最大流的基本算法（1）找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流

24、方向的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。（2）找出這條路上各條弧的最小的順流的容量pf，通過這條路增加網(wǎng)絡(luò)的流量pf。（3）在這條路上，減少每一條弧的順流容量pf ，同時增加這些弧的逆流容量pf，返回步驟（1）。 用此方法對例6求解： 第一次迭代：選擇路為v1 v4 v7 ?；。?v4 , v7 ）的順流容量為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如下圖：63522241263v1v2v5v7v4v3v600000000000420255最大流問題 求最大流的基本算法6352254最大流問題 第二次迭代：選擇路為v1 v2 v5 v7 ?；。?v2 , v5 ）的順流容量為3，

25、決定了pf=3，改進的網(wǎng)絡(luò)流量圖如下圖： 第三次迭代：選擇路為v1 v4 v6 v7 ?；。?v4 , v6 ）的順流容量為1，決定了pf=1，改進的網(wǎng)絡(luò)流量圖如下圖：635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v60000004202203333301356最大流問題 第二次迭代：選擇路為v1 55 第四次迭代：選擇路為v1 v4 v3 v6 v7 。?。?v3 , v6 ）的順流容量為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如下圖： 第五次迭代：選擇路為v1 v2 v3 v5 v7 ?；。?v2 , v3 ）的順流容量

26、為2，決定了pf=2，改進的網(wǎng)絡(luò)流量圖如下圖：22243v1v2v5v7v4v3v6100001203203335031200231322v1v2v5v7v4v3v61012020333501202313150020205最大流問題57 第四次迭代：選擇路為v1 v4 56 經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點到收點的一條路，路上的每一條弧順流容量都大于零，運算停止。得到最大流量為10。 最大流量圖如下圖：22v1v2v5v7v4v3v6123522355最大流問題58 經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點到57 5 最小費用最大流問題 最小費用最大流問題：給了一個帶收發(fā)點的網(wǎng)絡(luò)，對每一條

27、?。╲i,vj），除了給出容量cij外，還給出了這條弧的單位流量的費用bij，要求一個最大流F，并使得總運送費用最小。一、最小費用最大流的數(shù)學(xué)模型 例7 由于輸油管道的長短不一，所以在例6中每段管道（ vi,vj ）除了有不同的流量限制cij外，還有不同的單位流量的費用bij ，cij的單位為萬加侖/小時， bij的單位為百元/萬加侖。如圖。從采地 v1向銷地 v7運送石油，怎樣運送才能運送最多的石油并使得總的運送費用最??？求出最大流量和最小費用。(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)59 5

28、最小費用最大流問題 最小費用最大流58最小費用最大流問題 這個最小費用最大流問題也是一個線性規(guī)劃的問題。 解：我們用線性規(guī)劃來求解此題，可以分兩步走。 第一步，先求出此網(wǎng)絡(luò)圖中的最大流量F，這已在例6中建立了線性規(guī)劃的模型，通過管理運籌學(xué)軟件已經(jīng)獲得結(jié)果。 第二步，在最大流量F的所有解中，找出一個最小費用的解，我們來建立第二步中的線性規(guī)劃模型如下： 仍然設(shè)弧（vi,vj）上的流量為fij，這時已知網(wǎng)絡(luò)中最大流量為F，只要在例6的約束條件上，再加上總流量必須等于F的約束條件：f12=f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標(biāo)函數(shù)顯然是求其流量的最小費用 。 由此得到線性規(guī)劃模型如下：

29、60最小費用最大流問題 這個最小費用最大流59最小費用最大流問題 61最小費用最大流問題 60最小費用最大流問題 用管理運籌學(xué)軟件，可求得如下結(jié)果：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最優(yōu)值(最小費用)=145。對照前面例6的結(jié)果，可對最小費用最大流的概念有一個深刻的理解。 如果我們把例7的問題改為：每小時運送6萬加侖的石油從采地v1到銷地v7最小費用是多少？應(yīng)怎樣運送？這就變成了一個最小費用流的問題。一般來說，所謂最小費用流的問題就是：在給定了收點和發(fā)點并對每條弧(vi,vj)賦權(quán)以容量cij及

30、單位費用bij的網(wǎng)絡(luò)中，求一個給定值f的流量的最小費用，這個給定值f的流量應(yīng)小于等于最大流量F，否則無解。求最小費用流的問題的線性規(guī)劃的模型只要把最小費用最大流模型中的約束條件中的發(fā)點流量F改為f即可。在例6中只要把f12+f14=F改為f12+f14=f=6得到了最小費用流的線性規(guī)劃的模型了。62最小費用最大流問題 用管理運籌學(xué)軟件，可求得61最小費用最大流問題二、最小費用最大流的網(wǎng)絡(luò)圖論解法對網(wǎng)絡(luò)上?。╲i,vj）的（cij,bij）的表示作如下改動，用(b)來表示(a)。用上述方法對例7中的圖形進行改進，得圖如下頁：vivjvivj（cij,bij ）（0,-bij ）（a）（b）（ci

31、j,bij ）（cij,bij ）vivj（cji,bji ）（cij,bij ）vivj（cji,bji ）（0,-bji)（0,-bji)（c）（d）63最小費用最大流問題二、最小費用最大流的網(wǎng)絡(luò)圖論解法vi62最小費用最大流問題 求最小費用最大流的基本算法 在對弧的標(biāo)號作了改進的網(wǎng)絡(luò)圖上求最小費用最大流的基本算法與求最大流的基本算法完全一樣，不同的只是在步驟（1）中要選擇一條總的單位費用最小的路，而不是包含邊數(shù)最小的路。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,

32、-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）圖11-2864最小費用最大流問題(6,6)(3,4)(5,7)(2,63最小費用最大流問題用上述方法對例7求解： 第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后總流量為1，總費用10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖11-2965最小費用最大流問

33、題用上述方法對例7求解：v5(6,6)64最小費用最大流問題第二次迭代：找到最短路v1 v4 v7。第二次迭代后總流量為3，總費用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖11-3066最小費用最大流問題第二次迭代：找到最短路v1 65最小費用最大流問題第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后總流量為5，總費用56。(6,6)(3,4)

34、(5,7)(2,5)(0,-4)（0,3）(1,4)(0,3)(0,8)（1,2）v1v2v5v7v4v3v6(1,3)(5,-3)(2,-8)(1,-3)（2,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(3,-4)（2,-3）圖11-3167最小費用最大流問題第三次迭代：找到最短路v1 66最小費用最大流問題第四次迭代：找到最短路v1 v4 v3 v5 v7 。第四次迭代后總流量為6，總費用72。(6,6)(3,4)(4,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(1,3)(6,-3)(2,-8)(1,-3)

35、（3,-2）(0,-6)(0,-4)(0,-5)（1,4）(1,-7)(3,-4)（2,-3）圖11-3268最小費用最大流問題第四次迭代：找到最短路v1 67最小費用最大流問題 第五次迭代：找到最短路v1 v2 v5 v7 。第五次迭代后總流量為9，總費用123。(3,6)(0,4)(1,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(0,3)(6,-3)(2,-8)(1,-3)（3,-2）(3,-6)(3,-4)(0,-5)（1,4）(4,-7)(3,-4)（2,-3）圖11-3369最小費用最大流問題 第五次迭代：找到最短路v1

36、68最小費用最大流問題 第六次迭代：找到最短路v1 v2 v3 v5 v7 。第六次迭代后總流量為10，總費用145。已經(jīng)找不到從v1到v7的每條弧容量都大于零的路了，故已求得最小費用最大流了。(3,6)(0,4)(1,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(0,3)(6,-3)(2,-8)(1,-3)（3,-2）(3,-6)(3,-4)(0,-5)（1,4）(4,-7)(3,-4)（2,-3）圖11-3470最小費用最大流問題 第六次迭代：找到最短路v1 69最小費用最大流問題 如果對例7求一個最小費用流的問題：每小時運送6萬

37、加侖石油從v1到v7的最小費用是多少，或者每小時運送7萬加侖呢？我們可以從第四次迭代及圖11-32即可得到運送6萬加侖最小費用72百元，其運送方式通過比較圖11-28及圖11-32即得圖11-36所示。 至于每小時運送7萬加侖，我們可以在圖11-36的基礎(chǔ)上，再按第五次迭代所選的最短路運送1萬加侖即得最小費用：72+1*17=89百元，其運送方式如圖11-37所示。35123126v1v2v5v4v3v610342v710第六次迭代后總流量圖11-3571最小費用最大流問題 如果對例7求一個最70最小費用最大流問題 123126v1v2v5v4v3v6631v7圖11-3612123126v1

38、v2v5v4v3v6311v7圖11-37注：“管理運籌學(xué)軟件”有專門的子程序用于解決這類問題。72最小費用最大流問題 123126v1v2v5v4v3v71 6 網(wǎng)絡(luò)計劃技術(shù)用于工程項目的計劃 與控制的一項管理技術(shù)73 6 網(wǎng)絡(luò)計劃技術(shù)用于工程項目的計劃 72關(guān)鍵路徑法與計劃評審法1956年，美國杜邦公司在制定企業(yè)不同業(yè)務(wù)部門的系統(tǒng)規(guī)劃時，制定了第一套網(wǎng)絡(luò)計劃。這種計劃借助于網(wǎng)絡(luò)表示各項工作與所需要的時間，以及各項工作的相互關(guān)系。通過網(wǎng)絡(luò)分析研究工程費用與工期的相互關(guān)系，并找出在編制計劃及計劃執(zhí)行過程中的關(guān)鍵路線。這種方法稱為關(guān)鍵路線法（CPM)；1958年美國海軍武器部，在制定研制“北極星

39、”導(dǎo)彈計劃時，同樣地應(yīng)用了網(wǎng)絡(luò)分析方法與網(wǎng)絡(luò)計劃，但它注重于對各項工作安排的評價和審查，這種計劃稱計劃評審法（PERT） 74關(guān)鍵路徑法與計劃評審法1956年，美國杜邦公司在制定企業(yè)73網(wǎng)絡(luò)計劃技術(shù) 包括繪制計劃網(wǎng)絡(luò)圖、進度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)，下面進行分別討論：一、計劃網(wǎng)絡(luò)圖 統(tǒng)籌方法的第一步工作就是繪制計劃網(wǎng)絡(luò)圖，也就是將工序（或稱為活動）進度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。 例3、某公司研制新產(chǎn)品的部分工序與所需時間以及它們之間的相互關(guān)系都顯示在其工序進度表如表12-8所示，請畫出其統(tǒng)籌方法網(wǎng)絡(luò)圖。 表12-8工序代號工序內(nèi)容所需時間（天)緊前工序abcde產(chǎn)品設(shè)計與工藝設(shè)計外購配套零件外購生

40、產(chǎn)原料自制主件主配可靠性試驗601513388-aacb,d75網(wǎng)絡(luò)計劃技術(shù) 包括繪制計劃網(wǎng)絡(luò)圖、進度安74解:用網(wǎng)絡(luò)圖表示上述的工序進度表 網(wǎng)絡(luò)圖中的點表示一個事件,是一個或若干個工序的開始或結(jié)束,是相鄰工序在時間上的分界點,點用圓圈表示,圓圈里的數(shù)字表示點的編號?；”硎疽粋€工序（或活動），弧的方向是從工序開始指向工序的結(jié)束，弧上是各工序的代號，下面標(biāo)以完成此工序所需的時間（或資源）等數(shù)據(jù)，即為對此弧所賦的權(quán)數(shù) abcde601383815圖12-476解:用網(wǎng)絡(luò)圖表示上述的工序進度表abcde675 例、把例的工序進度表做一些擴充，如表12-9，請畫出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。 表12-9工序代

41、號所需時間（天）緊前工序工序代號所需時間（天）緊前工序abcd60151338aacefgh810165b，dde，77 例、把例的工序進度表做一些擴充，如表12-976 解：我們把工序擴充到圖12-4發(fā)生了問題，由于是的緊前工序，故的結(jié)束應(yīng)該是的開始，所以代表的弧的起點應(yīng)該是，由于工序的結(jié)束也是，所以工序也成了工序的緊前工序，與題意不符。 為此我們設(shè)立虛工序。虛工序是實際上并不存在而虛設(shè)的工序，用來表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時間。 152643a60b158e1013dc38f圖12-578 解：我們把工序擴充到圖12-4發(fā)生了77 在網(wǎng)絡(luò)圖上添加、工序得網(wǎng)絡(luò)圖12-6

42、。 在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個點之間多于一條弧，因此增加了一個點和虛工序如圖12-7。1256734a6015bec13d388h510fg16圖12-679 在網(wǎng)絡(luò)圖上添加、工序得網(wǎng)絡(luò)78 在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時，要注意圖中不能有缺口和回路。1257834a6015bec13d388h510f616g圖12-7801257834a6015bec13d388h510f679二、網(wǎng)絡(luò)時間與關(guān)鍵路線 在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出：1、完成此工程項目所需的最少時間。2、每個工序的開始時間與結(jié)束時間。3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。4、非關(guān)鍵工序在不影響工程的完成時間的前提下，其開始

43、時間與結(jié)束時間可以推遲多久。 例5、某公司裝配一條新的生產(chǎn)線，具體過程如表12-10,求：完成此工程的最少時間，關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開始時間和非關(guān)鍵工序在不影響工程完成時間的前提下，其開始時間與結(jié)束時間可以推遲多久。81二、網(wǎng)絡(luò)時間與關(guān)鍵路線80表12-10工序代號工序內(nèi)容所需時間（天）緊前工序abcdefghij生產(chǎn)線設(shè)計外購零配件下料、鍛件工裝制造1木模、鑄件機械加工1工裝制造2機械加工2機械加工3裝配調(diào)試60451020401830152535/aaaacdd,egb,i,f,h82表12-10工序代號工序內(nèi)容所需時間（天）緊前工序a生81解：據(jù)表12-10,繪制網(wǎng)絡(luò)圖

44、如圖12-8。 圖12-8 如圖12-8 ,-就是一條關(guān)鍵路線，我們要干完所有的工序就必須走完所有這樣的路線，由于很多工序可以同時進行，所以網(wǎng)絡(luò)中最長的路線就決定了完成整個工程所需的最少時間，這條路線稱為關(guān)鍵路線。12346785a60b45echj35ig1030d204025f181583解：據(jù)表12-10,繪制網(wǎng)絡(luò)圖如圖12-8。1234682下面我們給出找關(guān)鍵路線的辦法 首先，從網(wǎng)絡(luò)的發(fā)點開始，按順序計算出每個工序的最早開始時間（ES )和最早結(jié)束時間（EF) ，設(shè)一個工序所需的時間為t，這對于同一個工序來說，有 EF=ES+t。 工序a的最早開始時間工序a的最早完成時間11a0，60

45、60圖12-984下面我們給出找關(guān)鍵路線的辦法工序a的最早工序a的最早183 圖12-10 其次,從網(wǎng)絡(luò)的收點開始計算出在不影響整個工程最早結(jié)束時間的情況下各個工序的最晚開始時間(縮寫為LS)和最晚結(jié)束時間（縮寫為LF),顯然對同一工序有 LS=LF-t1236785a0,6060b60,10545e60.100c60,70h100,115j135,17035i110.135g80,11030d60.80204025f70,88184101585 1236785a0,6060b60,105484 運用此法則，可以從首點開始計算出每個工序的LF與LS，如圖12-11所示。 接著，可以計算出每一個

46、工序的時差，把在不影響工程最早結(jié)束時間的條件下，工序最早開始（或結(jié)束）的時間可以推遲的時間，成為該工序的時差，對每個工序來說其時差記為Ts有 Ts=LS-ES=LF-EF1236785a0,60600,60b60,1054590,135e60.100c60,70h100,115j135,17035135,170i110.135g80,1103080,110d60.802060,804080,12025110,135f70,8818117,135410107,11715120,13586 運用此法則，可以從首點開始計算出每個工85 最后將各工序的時差，以及其他信息構(gòu)成工序時間表如表12-11所示

47、。 這樣就找到了一條由關(guān)鍵工序a,d,g,i和j依次連接成的從發(fā)點到收點的關(guān)鍵路線。87 最后將各工序的時差，以及其他信息構(gòu)成工序時86三、網(wǎng)絡(luò)優(yōu)化 得到初始的計劃方案，但通常要對初始方案進行調(diào)整與完善。根據(jù)計劃目標(biāo)，綜合考慮資源和降低成本等目標(biāo)，進行網(wǎng)絡(luò)優(yōu)化，確定最優(yōu)的計劃方案。 1.時間-資源優(yōu)化 做法： 1）優(yōu)先安排關(guān)鍵工序所需的資源。 2）利用非關(guān)鍵工序的時差，錯開各工序的開始時間。 3）統(tǒng)籌兼顧工程進度的要求和現(xiàn)有資源的限制，多次綜合平衡。 下面列舉一個拉平資源需要量最高峰的實例。在例5中，若加工工人為65人，并假定這些工人可完成這5個工序任一個，下面來尋求一個時間-資源最優(yōu)方案。如

48、表12-16所示： 88三、網(wǎng)絡(luò)優(yōu)化87表12-16工序需要人數(shù)最早開始時間所需時間時差d5860200f22701847g428030h391001520i26110250 若上述工序都按最早開始時間安排，那么從第60天至第135天的75天里，所需的機械加工工人人數(shù)如圖12-17所示。89表12-16工序需要人數(shù)最早開始時間所需時間時差d5888 在圖的上半部中，工序代號后的數(shù)字是人數(shù)，線下面的數(shù)字是非關(guān)鍵工序時差長度。圖的下半部表示從第60天至135天內(nèi)的75天里，所需機械加工工人數(shù)，這樣的圖稱為資源負荷圖。 274635 f(22人）18h(39人)1558人64人80人81人42人26

49、人65人60 80 100 120 130 d(58人） i(26人） g(42人）302025圖12-1790 在圖的上半部中，工序代號后的數(shù)字是人數(shù)89 同時我們應(yīng)優(yōu)先安排關(guān)鍵工序所需的工人，再利用非關(guān)鍵工序的時差，錯開各工序的開始時間，從而拉平工人需要量的高峰。經(jīng)過調(diào)整，我們讓非關(guān)鍵工序f從第80天開始，工序h從第110天開始。找到了時間-資源優(yōu)化的方案，如圖12-18所示，在不增加工人的情況下保證了工程按期完成。246753 f(22人） h(39人） d(58人） i(26人） g(42人）工人數(shù)65人60 80 100 120 13058人42人64人26人65人圖12-1891 同時我們應(yīng)優(yōu)先安排關(guān)鍵工序所需的工人，902.時間-費用優(yōu)化 需要考慮時間與費用的問題：在既定的時間前工程完工的前提下，使得所需的費用最少，或者在不超工程預(yù)算的條件下使工程最早完工。這些是時間-費用優(yōu)化要研究和解決的問題。 直接費用：為了加快工程進度，需要增加人力、設(shè)備和工作班次，這需要增加一筆費用，成為直接費用。 間接費用：由于工程早日完工，減少了管理人員的工資辦公費等費用稱為間接費用。一般說工序越短，直接費用越多，間接費用越少。922.時間-費用優(yōu)化91