《系統(tǒng)工程》課件第08章 圖與網絡分析

1

引言2圖和網絡基本概念3樹圖與網絡分析14:224最短路問題5網絡最大流67最小費用與最大流題網絡計劃技術中國郵路問題8知識點聚焦本章主要介紹有關圖的概念、圖的表示方法、圖的應用。如最短路問題、最大流問題、最小費用問題，網絡計劃等問題。同時對圖的遍歷可以得到另一種沒有回路的形式——樹及其最小樹作了介紹。14:2214:22已經學習了哪些？14:22本章主要介紹有關圖的概念、圖的表示方法、圖的應用。如最短路問題、最大流問題、最小費用問題，網絡計劃等問題。同時對圖的遍歷可以得到另一種沒有回路的形式——樹及其最小樹作了介紹?！局R點聚焦】圖論是組合優(yōu)化、運籌學、電子學、通訊等學科重要基礎。它已廣泛地應用在控制論、信息論、電子計算機、交通管理等各個領域。在實際生活、工作中，有很多問題可以用圖的理論和方法來解決。例如，在組織生產中，為完成某項生產任務，各工序之間怎樣銜接，才能使生產任務完成得既快又好。一個郵遞員送信，要走完他負責投遞的全部街道，完成任務后回到郵局，應該按照怎樣的路線走，所走的路程最短。再例如，各種通信網絡的合理架設，交通網絡的合理分布等問題，應用圖論的方法都能得到較好的解決。圖論是專門研究圖的理論的一門數學分支，屬于離散數學范疇，與運籌學有交叉，它有200多年歷史，大體可劃分為三個階段。14:228.1引言第一階段從十八世紀中葉到十九世紀中葉，處于萌芽階段，多數問題由游戲而產生，最有代表性的工作就是所謂的Euler七橋問題，即一筆畫問題。如圖8-1所示。14:228.1引言第二階段從十九世紀中葉到二十世紀中葉，圖的問題大量涌現，如Hamilton問題，地圖染色的四色問題以及可平面性問題等，同時也出現用圖解決實際問題，如Cayley把樹應用于化學領域，Kirchhoff用樹去研究電網絡等。14:228.1引言第三階段二十世紀中葉以后，由生產管理、軍事、交通、運輸、計算機網絡等方面提出實際問題，以及大型計算機使大規(guī)模問題的求解成為可能，特別是以Ford和Fulkerson建立的網絡流理論，與線性規(guī)劃、動態(tài)規(guī)劃等優(yōu)化理論和方法相互滲透，促進了圖論對實際問題的應用。最后，數學家Euler在1736年巧妙地給出了這個問題的答案，并因此奠定了圖論的基礎。Euler把A、B、C、D四塊陸地分別收縮成四個頂點，把橋表示成連接對應頂點之間的邊，問題轉化為從任意一點出發(fā)，能不能經過各邊一次且僅一次，最后返回該點。這就是著名的Euler問題。類似問題還有很多。14:228.1引言圖論中所說的圖與一般所說的幾何圖形或代數函數的圖形是完全不同的概念。圖論中的圖是指由一些點的集合V和連接其中某些點對的線構成的集合E所組成的圖形。下面先通過幾個直觀的實例認識什么是圖。14:228.2圖和網絡基本概念在實際生活中，人們?yōu)榱朔从骋恍ο笾g的關系，常常在紙上用點和線畫出各種各樣的示意圖?！纠?-1】圖8-2是我國北京、上海等10個城市間的鐵路交通圖，反映了這10個城市間的鐵路分布情況。若用點代表城市，用點和點之間的連線代表兩個城市之間的鐵路線。如圖8-2所示。諸如此類的還有電話線分布、天然氣管道、高速公路、高等級鐵路等圖。14:228.2圖和網絡基本概念8.2.1圖的應用實例【例8-2】有甲、乙、丙、丁、戊5個球隊，它們之間的比賽就可以用圖表示出來，如圖8-4。已知甲隊和其他各隊都比賽過一次，乙隊和甲隊比賽過，丙隊和乙、丁隊比賽過，丁隊和丙、戊隊比賽過，戊隊和甲、丁隊比賽過。為反映比賽情況，可以用點分別代表這5個隊，若兩個隊之間已比賽過，就在這兩個隊所對應的點之間連一條線，這條線不過其他的點，如圖8-3所示。14:228.2.1圖的應用實例8.2圖和網絡基本概念圖是反映對象之間關系的一種工具。在一般情況下，圖中點的相對位置如何，點與點之間連線的長短曲直，對于反映對象之間的關系，并不是重要的。如例8-2，也可以用如圖8-4所示的圖去反映5個球隊的比賽情況，這與圖8-3沒有本質的區(qū)別，圖論中的圖與幾何圖、工程圖等是不同的。因為研究的思路方法不同，達到的目標也不同。14:228.2.1圖的應用實例8.2圖和網絡基本概念前面兩個例子中涉及的對象之間的“關系”具有“對稱性”，就是說，如果甲與乙有這種關系，那么同時乙也與甲有這種關系。在實際生活中，有許多關系不具有這種對稱性。譬如人們之間的認識關系，甲認識乙并不意味著乙也認識甲。比賽中的勝負關系也是這樣，甲勝乙和乙勝甲是不同的。反映這種非對稱的關系，只用一條連線就不行了。如例8-2，如果人們關心的是5個球隊比賽的勝負情況，那么從圖8-3中就看不出來了。為了反映這一類關系，可以用一條帶箭頭的連線表示。例如球隊v1勝了球隊v2，可以引一條帶箭頭的連線表示。圖8-5反映了5個球隊比賽的勝負情況，可見v1三勝一負，v4打了三場球，全負等。類似勝負這種非對稱性的關系，在生產相生活中是常見的，如交通運輸申的“單行線”，部門之間的領導與被領導的關系、一項工程中各工序之間的先后關系等。14:228.2.1圖的應用實例8.2圖和網絡基本概念圖是反映對象之間關系的一種工具。在一般情況下，圖中點的相對位置如何，點與點之間連線的長短曲直，對于反映對象之間的關系，并不是重要的。如例8-2，也可以用如圖8-4所示的圖去反映5個球隊的比賽情況，這與圖8-3沒有本質的區(qū)別，圖論中的圖與幾何圖、工程圖等是不同的。因為研究的思路方法不同，達到的目標也不同。14:228.2.1圖的應用實例8.2圖和網絡基本概念圖8-45個球隊比賽示意圖【定義8-1】(1)圖由點集V=（vi）和V中元素的無序對的集合E=（ek）所構成的二元組，稱為圖。記為G=（V，E）。其中：V=（v1，v2，…，vm），是m個頂點集合；E=（e1，e2，…，en），是n條邊集合?；蛘哒f：一個圖是由一些點及一些點之間的連線(不帶箭頭或帶箭頭)所組成。14:228.2.2.圖的幾個基本概念8.2圖和網絡基本概念(2)邊(弧)把兩點之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。(3)無向圖由點和邊所構成的圖，稱之為無向圖(也簡稱為圖)，記為G=(V，E)，式中V，E分別是G的頂點集合和邊集合。一條連接點vi，vjV的邊e，記為e=[vi，vj]，或e=[vj，vi]。(4)有向圖由點和弧所構成的圖稱為有向圖，記為D=(V，A)，式中V，A分別表示D的頂點集合和弧的集合。一條方向是從vi指向vj的弧a記為a=<vi，vj>。vi稱為a的始點，vj稱為a的終點。14:228.2.2.圖的幾個基本概念8.2圖和網絡基本概念【定義8-2】(1)頂點數和邊數圖G=(V，E)中，V中元素的個數稱為圖G的頂點數，記作p(G)或簡記為p；E中元素的個數稱為圖G的邊數，記作q(G)，或簡記為q。(2)端點和關聯(lián)邊若ei=[vi，vj]E，則稱頂點vi，vj為邊ei的端點，邊ei是頂點vi，和vj的關聯(lián)邊。(3)相鄰頂點和相鄰邊同一條邊的兩個端點稱為相鄰頂點，簡稱鄰點；有公共端點的兩條邊稱為相鄰邊，簡稱鄰邊。(4)多重邊與環(huán)具有相同端點的邊稱為多重邊或平行邊；兩個端點落在一個頂點的邊稱為環(huán)。14:228.2.2.圖的幾個基本概念8.2圖和網絡基本概念(5)多重圖和簡單圖含有多重邊的圖稱為多重圖；無環(huán)也無多重邊的圖稱為簡單圖。(6)度以vi為端點的邊的條數稱為頂點的度(有些書中也叫做次)，記作d(vi)。(7)懸掛點和懸掛邊度為1的點稱為懸掛點；與懸掛點相連的邊稱為懸掛邊。(8)孤立點度為零的點稱為孤立點。(9)奇點與偶點度為奇數的頂點稱為奇點；度為偶數的頂點稱為偶點。例如，圖8-6中，P(G)=6，q(G)=8；e3=[v4，v3]，v3與v4是e3的端點，e3是點v3和v4的關聯(lián)邊；v2與v5是鄰點，e3與e2是鄰邊；e7與e8是多重邊，e4是一個環(huán)；圖8-6是一個多重圖；v1是懸掛點，e1是懸掛邊；v6是孤立點；v2是奇點，v3是偶點。14:228.2.2.圖的幾個基本概念8.2圖和網絡基本概念【定理8-1】圖G=(V，E)中，所有頂點的度之和是邊數的2倍。即(8-1)14:228.2.2.圖的幾個基本概念8.2圖和網絡基本概念定理8-1是顯然的，因為在計算各頂點的度時，每條邊都計算了兩次，于是圖G中全部頂點的度之和就是邊數的2倍?！径ɡ?-2】任一圖G中，奇點的個數為偶數。證明設V1、V2分別是G中奇點和偶點的集合，由定理8-1可知14:228.2.2.圖的幾個基本概念8.2圖和網絡基本概念(2)邊(弧)把兩點之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。(3)無向圖由點和邊所構成的圖，稱之為無向圖(也簡稱為圖)，記為G=(V，E)，式中V，E分別是G的頂點集合和邊集合。一條連接點vi，vjV的邊e，記為e=[vi，vj]，或e=[vj，vi]。(4)有向圖由點和弧所構成的圖稱為有向圖，記為D=(V，A)，式中V，A分別表示D的頂點集合和弧的集合。一條方向是從vi指向vj的弧a記為a=<vi，vj>。vi稱為a的始點，vj稱為a的終點。14:228.2.2.圖的幾個基本概念8.2圖和網絡基本概念(2)邊(弧)把兩點之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。(3)無向圖由點和邊所構成的圖，稱之為無向圖(也簡稱為圖)，記為G=(V，E)，式中V，E分別是G的頂點集合和邊集合。一條連接點vi，vjV的邊e，記為e=[vi，vj]，或e=[vj，vi]。(4)有向圖由點和弧所構成的圖稱為有向圖，記為D=(V，A)，式中V，A分別表示D的頂點集合和弧的集合。一條方向是從vi指向vj的弧a記為a=<vi，vj>。vi稱為a的始點，vj稱為a的終點。14:228.2.2.圖的幾個基本概念8.2圖和網絡基本概念(2)邊(弧)把兩點之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。(3)無向圖由點和邊所構成的圖，稱之為無向圖(也簡稱為圖)，記為G=(V，E)，式中V，E分別是G的頂點集合和邊集合。一條連接點vi，vjV的邊e，記為e=[vi，vj]，或e=[vj，vi]。(4)有向圖由點和弧所構成的圖稱為有向圖，記為D=(V，A)，式中V，A分別表示D的頂點集合和弧的集合。一條方向是從vi指向vj的弧a記為a=<vi，vj>。vi稱為a的始點，vj稱為a的終點。14:228.2.2.圖的幾個基本概念8.2圖和網絡基本概念如何把圖的有關信息輸入和存儲到計算機里去呢?由于圖的最本質的內容是頂點與頂點的關系或者邊與頂點間的關聯(lián)關系，因此可用矩陣來表示這種關聯(lián)關系。1)關聯(lián)矩陣給定無向圖G=(V，E)，其中V={v1，v2，...，vn}，E={e1，e2，...，en}。若用矩陣的行標號i對應圖G的頂點下標，用列標號j對應圖G的邊的下標，可構造一個n*m矩陣B(G)=(bij)n*m，與圖G對應，其中14:228.2.3.圖的矩陣表示8.2圖和網絡基本概念(8-3)(2)邊(弧)把兩點之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。(3)無向圖由點和邊所構成的圖，稱之為無向圖(也簡稱為圖)，記為G=(V，E)，式中V，E分別是G的頂點集合和邊集合。一條連接點vi，vjV的邊e，記為e=[vi，vj]，或e=[vj，vi]。(4)有向圖由點和弧所構成的圖稱為有向圖，記為D=(V，A)，式中V，A分別表示D的頂點集合和弧的集合。一條方向是從vi指向vj的弧a記為a=<vi，vj>。vi稱為a的始點，vj稱為a的終點。14:228.2.3.圖的矩陣表示8.2圖和網絡基本概念(2)邊(弧)把兩點之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。(3)無向圖由點和邊所構成的圖，稱之為無向圖(也簡稱為圖)，記為G=(V，E)，式中V，E分別是G的頂點集合和邊集合。一條連接點vi，vjV的邊e，記為e=[vi，vj]，或e=[vj，vi]。(4)有向圖由點和弧所構成的圖稱為有向圖，記為D=(V，A)，式中V，A分別表示D的頂點集合和弧的集合。一條方向是從vi指向vj的弧a記為a=<vi，vj>。vi稱為a的始點，vj稱為a的終點。14:228.2.3.圖的矩陣表示8.2圖和網絡基本概念(2)邊(弧)把兩點之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。(3)無向圖由點和邊所構成的圖，稱之為無向圖(也簡稱為圖)，記為G=(V，E)，式中V，E分別是G的頂點集合和邊集合。一條連接點vi，vjV的邊e，記為e=[vi，vj]，或e=[vj，vi]。(4)有向圖由點和弧所構成的圖稱為有向圖，記為D=(V，A)，式中V，A分別表示D的頂點集合和弧的集合。一條方向是從vi指向vj的弧a記為a=<vi，vj>。vi稱為a的始點，vj稱為a的終點。14:228.2.3.圖的矩陣表示8.2圖和網絡基本概念(2)邊(弧)把兩點之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。(3)無向圖由點和邊所構成的圖，稱之為無向圖(也簡稱為圖)，記為G=(V，E)，式中V，E分別是G的頂點集合和邊集合。一條連接點vi，vjV的邊e，記為e=[vi，vj]，或e=[vj，vi]。(4)有向圖由點和弧所構成的圖稱為有向圖，記為D=(V，A)，式中V，A分別表示D的頂點集合和弧的集合。一條方向是從vi指向vj的弧a記為a=<vi，vj>。vi稱為a的始點，vj稱為a的終點。14:228.3.1.樹及其性質8.3.樹(2)邊(弧)把兩點之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。(3)無向圖由點和邊所構成的圖，稱之為無向圖(也簡稱為圖)，記為G=(V，E)，式中V，E分別是G的頂點集合和邊集合。一條連接點vi，vjV的邊e，記為e=[vi，vj]，或e=[vj，vi]。(4)有向圖由點和弧所構成的圖稱為有向圖，記為D=(V，A)，式中V，A分別表示D的頂點集合和弧的集合。一條方向是從vi指向vj的弧a記為a=<vi，vj>。vi稱為a的始點，vj稱為a的終點。14:228.3.1.樹及其性質8.3.樹【例8-4】某工廠的組織機構如圖8-10所示。如果用圖表示，該工廠的組織機構圖就是一棵樹，如圖8-11所示?！径x8-6】一個無圈的連通圖稱為樹，通常以T表示，用二元組表示為T=(V，E)。從樹的定義可以推出以下幾點性質：1)具有n個頂點的樹，其邊數恰好為n-1條。2)樹的任意兩個頂點之間有且僅有一條鏈。3)在樹T中去掉任一條邊，則T成為不連通圖。4)在樹T中不相鄰的兩個頂點間添上一條邊，則恰好得到一個圈。如果再從這個圈上任意去掉一條邊，可以得到一個樹。14:228.3.1.樹及其性質8.3.樹【定義8-7】設圖T=(V，E’)是圖G=(V，E)的支撐子圖，如果圖T=(V，E’)是一棵樹，則稱T是G的一棵支撐樹。例如圖8-12b是圖8-12a所示圖G的一棵支撐樹。若T=(V，E)是G=(V，E)的一棵支撐樹，則顯然，樹T中邊的個數是P(G)-l，G中不屬于樹T的邊數是q(G)-p(G)+1。14:228.3.2.圖的支撐樹8.3.樹【定義8-7】設圖T=(V，E’)是圖G=(V，E)的支撐子圖，如果圖T=(V，E’)是一棵樹，則稱T是G的一棵支撐樹。例如圖8-12b是圖8-12a所示圖G的一棵支撐樹。若T=(V，E)是G=(V，E)的一棵支撐樹，則顯然，樹T中邊的個數是P(G)-l，G中不屬于樹T的邊數是q(G)-p(G)+1。14:228.3.2.圖的支撐樹8.3.樹【例8-5】在圖8-13中，用破圈法求出圖的一棵支撐樹。解：取一個圈(v1，v2，v3，v1)，從這個圈中去掉邊e3=[v2，v3]；在余下的圖中，再取一個圈(v1，v2，v4，v3，v1)，去掉邊e4=[v2，v4]；在余下的圖中，從圈(v3，v4，v5，v3)中去掉邊e6=[v5，v3]；再從圈(v1，v2，v5，v4，v3，v1)中去掉邊e8=[v2，v5]。這時，剩余的圖中不含圈，于是得到一個支撐樹，如圖8-13中粗線所示。也可以用另一種方法來尋求連通圖的支撐樹。在圖中任取一條邊e1，找一條與e1不構成圈的邊e2，再找一條與{e1，e2}不構成圈的邊e3，一般，設已有{e1，e2，...，ek}，找一條與{e1，e2，...，ek}中的任何一些邊不構成圈的邊ek+1。重復這個過程，直到不能進行為止。這時，由所有取出的邊所構成的圖是一個支撐樹，稱這種方法為“避圈法”。14:228.3.2.圖的支撐樹8.3.樹【例8-6】在圖8-14中，用避圈法求出一個支撐樹。解：首先任取邊e1，因e1與e2不構成圈，所以可以取e2，因為e5與{e1，e2}不構成圈，故可以取e5[因e3與{e1，e2}構成一個圈(v1，v2，v3，v1)，所以不能取e3]；因e6與{e1，e2，e5}不構成圈，故可取e6；因e8與{e1，e2，e5，e6}不構成圈，故可取e8，(注意，因e7與{e1，e2，e5，e6}中的e5，e6能夠成圈，故不能取e7)。這時由{e1，e2，e5，e6，e8}所構成的圖就是一個支撐樹，如圖8-14中粗線所示。14:228.3.2.圖的支撐樹8.3.樹【定義8-8】給定圖G=(V，E)，對G中的每一條邊[vi，vj]，相應地有一個數wij，則稱這樣的圖G為賦權圖，wij稱為邊[vi，vj]上的權?！径x8-9】設有一個連通圖G=(V，E)，每一邊e=[vi，vj]有一個非負權w(e)=wij(wij≧0)。如果T=(V，E')是G的一個支撐樹，稱E'中所有邊的權之和為支撐樹T的權，記為w(T)。即14:228.3.3.最小支撐樹問題8.3.樹(8-5)如果支撐樹T*的權w(T*)是G的所有支撐樹的權中最小者，則稱T*是G的最小支撐樹(簡稱最小樹)，即最小支撐樹問題就是要求出連通圖G的最小支撐樹。假設給定一些城市，已知每對城市間交通線的建造費用，要求建造一個連接這些城市的交通網，使總的建造費用最小，這個問題就是賦權圖上的最小支撐樹問題。下面介紹求最小支撐樹的兩個方法。方法1(避圈法kruskal)：在連通圖G中，開始選一條最小權的邊，以后每一步中，總從未被選取的邊中選一條權最小的邊，并使之與已選取的邊不構成圈(每一步中，如果有兩條或兩條以上的邊都是權最小的邊，則從中任選一條)。重復下去，直到不存在與已選邊不構成圈的邊為止。已選邊與頂點構成的圖G就是所求最小支撐樹T。14:228.3.3.最小支撐樹問題8.3.樹【例8-7】某工廠內連接6個車間的道路網如圖8-15a所示。已知每條道路的長，要求沿道路架設連接6個車間的電話線網，使電話線的總長最小。解：這個問題就是要求圖8-15a所示的賦權圖上的最小支撐樹。用避圈法求解。從E中選最小權邊[v2，v3]，E1={[v2，v3]}；從E\E1中選最小權邊[v2，v4]，E2={[v2，v3]，[v2，v4]}；從從E\E2中選[v4，v5]，令E3={[v2，v3]，[v2，v4]，[v4，v5]}；從E\E3中選[v5，v6](或選[v4，v6])，令E4={[v2，v3]，[v2，v4]，[v4，v5]，[v5，v6]}；從E\E4中選[v1，v2]，令E5={[v2，v3]，[v2，v4]，[v4，v5]，[v5，v6]，[v1，v2]}。這時，任一條未選的邊都與己選的邊構成圈，故停止。(V，E5)就是所要求的最小支撐樹，電話總長最小的電話線網方案，如圖8-15b所示，電話線總長為15單位。14:228.3.3.最小支撐樹問題8.3.樹從E中選最小權邊[v2，v3]，E1={[v2，v3]}；從E\E1中選最小權邊[v2，v4]，E2={[v2，v3]，[v2，v4]}；從從E\E2中選[v4，v5]，令E3={[v2，v3]，[v2，v4]，[v4，v5]}；從E\E3中選[v5，v6](或選[v4，v6])，令E4={[v2，v3]，[v2，v4]，[v4，v5]，[v5，v6]}；從E\E4中選[v1，v2]，令E5={[v2，v3]，[v2，v4]，[v4，v5]，[v5，v6]，[v1，v2]}。14:228.3.3.最小支撐樹問題8.3.樹方法2(破圈法)：在連通圖G中，任取一個圈，從圈中去掉一條權最大的邊(如果有兩條或兩條以上的邊都是權最大的邊，則任意去掉其中一條)。在余下的圖中，重復這個步驟，一直得到一個不含圈的圖為止，這時的圖便是最小支撐樹?！纠?-8】用破圈法求圖8-15a所示賦權圖的最小支撐樹。解：任取一個圈，譬如(v1，v2，v3，v1)，邊[v1，v3]是這個圈中權最大的邊，于是去掉邊[v1，v3]；再取圈(v3，v5，v2，v3)，去掉邊[v2，v5]；取圈(v3，v5，v4，v2，v3)，去掉邊[v3，v5]；取圈(v5，v6，v4，v5)，這個圈中，[v5，v6]及[v4，v6]都是權最大的邊，去掉其中的一條，比如說[v4，v6]。這時得到一個不含圈的圖，如圖8-15b所示，即為最小支撐樹。14:228.3.3.最小支撐樹問題8.3.樹在企業(yè)的經營活動和日常生活中，經常會遇到所謂最短路問題。當你早晨從家中出發(fā)上班時，面臨著走怎樣的路線才能在最短時間內到達單位；當你假日外出旅游時，怎樣選擇旅游路線使花費最??；在企業(yè)的經營中，譬如需要運送一批物資到達某地，應沿著怎樣的路線運輸，才能使其運輸費用最省，還有諸如各種管道鋪設、線路安排、廠區(qū)布局、設備更新等，也屬最短路間題?！纠?-9】從油田鋪設管道，把原油運到原油加工廠。要求管道必須沿圖8-16所給定的路線鋪設。圖中vi點為油田，v9點為原油加工廠，弧權為該條道路的長度，要求使管道總長最短的鋪設方案。14:228.4.1.引例8.4.最短路問題顯而易見，可能的鋪設方案是很多的，如沿路線v1→v2→v4→v7→v9，或沿路線v1→v3→v5→v8→v9等。不同的方案管道總長是不同的，如按第一種方案鋪設，管道總長為16；按第二種方案鋪設為12等。14:228.4.1.引例8.4.最短路問題用圖論的語言來描述，一個方案對應著一條從v1到v9的路，管道總長為這條路線的總權，則上述問題就是求一條從v1到v9的路線，使路線的權最小，這樣的路稱為最短路徑。因此在賦權有向圖G中，設v1、vn是其中的兩點，最短路徑問題，就是要求從始點v1到終點v9的一條有向路線，使其在所有從v1到vn的有向路線中，它是總權最小的一條。14:228.4.1.引例8.4.最短路問題最短路徑問題可以化成線性規(guī)劃問題求解，也可以處理成動態(tài)規(guī)劃問題求解，這里著重介紹目前常用的一種好算法----迪杰斯特拉(Dijkstra)算法，這種算法要求每條弧的權wij≧0。在實際的管理工作中，一般都能滿足這個要求。利用該算法，能求出從v1到任一點vn的最短路(對于含負權弧，即有wij<0的最短路問題，目前也有算法來解決，此處不作介紹)。算法進行時是對每一個頂點給定一個標號，標號分臨時標號和固定標號(分別稱T類標號和P類標號)。頂點i的臨時標號記成T(i)，它表示發(fā)點s到頂點i的最短距離的上界；頂點i的固定標號記成P(i)，它表示發(fā)點s到頂點i的實際最短距離。已得到P類標號的頂點不再改變其標號，而沒有標上P類標號的頂點必須標上T類標號，算法的每一步要把某一頂點的T類標號改為P類標號。當終點獲得P類標號時，就求得了從發(fā)點到終點的最短路線。14:228.4.2.最短路算法（標號法）8.4.最短路問題算法開始時給發(fā)點s標上固定標號P(s)=0，這表示從s到s的最短距離為零。其余頂點標上臨時標號T(j)=。(1)設頂點i是剛得到P類標號的頂點，把與頂點i有弧直接相連而又屬T類標號的各頂點j的標號，改為下列T類標號T(j)=min{T(j)，P(i)+wij}(8-7)(2)在T類標號中選標號最小的頂點j0并把它的臨時標號T(j0)改為固定標號P(j0)。若終點獲得P類標號，則算法終止，最短路已經找到；否則轉回“(1)”。要找出從發(fā)點s到點T的最短路中頂點的順序，在算法進行時要做好標記，以表明每一固定標號的頂點是從哪個頂點得到標號的，然后從終點反向追蹤到發(fā)點，這樣就可找出一條最短路。另一個辦法是從終點反向逆算，看哪個頂點的固定標號與終點標號的差數剛好等于與終點直接相連的相應弧長，譬如是頂點j，則頂點j在終點T之前，對頂點j又可這樣做，如此逐點逆算，就可找到最短路。14:228.4.2.最短路算法（標號法）8.4.最短路問題下面用例子說明狄杰斯特拉算法?！纠?-10】用狄杰斯特拉算法求無向圖8-17中頂點1到頂點6的最短距離及其路線。解：用狄杰斯特拉標號算法求解時，首先給頂點1標上P類標號0，即P(1)=0，其余頂點標上T類標號，即T(j)=(j=2，3，...，6)。第1步1)與頂點1直接相連又為臨時標號的頂點是2和3，這兩個頂點的臨時標號改為T(2)=min[T(2)，P(1)+w12]=min[，0+4]=4T(3)=min[T(3)，P(1)+w13]=min[，0+3]=314:228.4.2.最短路算法（標號法）8.4.最短路問題2)在所有T類標號中，最小的為T(3)=3，于是令P(3)=3，即頂點3獲得固定標號P(3)。第2步1)與頂點3直接相連又為臨時標號的頂點是2和5，它們的T類標號改為T(2)=min[T(2)，P(3)+w32]=min[4，3+2]=4T(5)=min[T(5)，P(3)+w35]=min[，3+2]=52)在所有T類標號中，T(2)=4最小，于是有P(2)=4第3步1)對頂點2，有T(4)=min[T(4)，P(2)+w24]=min[，4+3]=7T(5)=min[T(5)，P(2)+w25]=min[，4+1]=52)在所有T類標號中T(5)=5最小，于是令P(5)=514:228.4.2.最短路算法（標號法）8.4.最短路問題第4步1)對頂點5，有T(4)=min[T(4)，P(5)+w24]=min[7，5+2]=7T(6)=min[T(6)，P(5)+w56]=min[，5+4]=92)在所有T類標號中，T(4)=7最小，令P(4)=7第5步1)對頂點4有T(6)=min[T(6)，P(4)+w46]=min[9，7+3]=92)顯然應令P(6)=9，終點(頂點6)獲得固定標號，算法到此結束。頂點1到頂點6的最短距離為9。14:228.4.2.最短路算法（標號法）8.4.最短路問題要找出從頂點1到頂點6的最短路徑各頂點的順序，可從頂點6反向逆算。與頂點6直接相連的是頂點4和頂點5，而頂點6與頂點4或頂點5固定標號之差為2和4，與頂點6相連的弧長中只有弧(5,6)的距離為4，因此頂點5在頂點6之前。類似地可得出，頂點3在頂點5之前，頂點1在頂點3之前，即最短路徑是1→3→5→6；或者可得出，頂點2在頂點5之前，頂點1在頂點2之前，即有另一條最短路徑1→2→5→6。它們的最短距離都為9。14:228.4.2.最短路算法（標號法）8.4.最短路問題【例8-11】設備更新問題某企業(yè)使用一臺設備，在每年年初，企業(yè)決策者就要決定是購置新的，還是繼續(xù)使用舊的。若購置新設備，就要支付一定的購置費用；若繼續(xù)使用舊設備，則需支付一定的維修費用。現在的問題是如何制訂一個幾年之內的設備更新計劃，使得總的支付費用最少。現用一個5年之內要更新某種設備的計劃為例，已知該種設備在各年年初的價格(見表8-1)，還已知使用不同時間(年)的設備所需要的維修費用(見表8-2)。14:228.4.3.最短路問題應用舉例8.4.最短路問題可供選擇的設備更新方案顯然是很多的。例如,每年都購置一臺新設備,則其購置費用為11+11+12+12+13=59，而每年支付的維修費用為5,五年合計為25。于是五年總的支付費用為59+25=84。又如決定在第一、三、五年各購進一臺,這個方案的設備購置費為11+12+13=36,維修費為5+6+5+6+5=27。五年總的支付費用為63。如何制定使得總的支付費用最少的設備更新計劃呢?可以把這個問題化為最短路問題,見圖8-18。14:228.4.3.最短路問題應用舉例8.4.最短路問題【例8-11】設備更新問題某企業(yè)使用一臺設備，在每年年初，企業(yè)決策者就要決定是購置新的，還是繼續(xù)使用舊的。若購置新設備，就要支付一定的購置費用；若繼續(xù)使用舊設備，則需支付一定的維修費用。現在的問題是如何制訂一個幾年之內的設備更新計劃，使得總的支付費用最少。現用一個5年之內要更新某種設備的計劃為例，已知該種設備在各年年初的價格(見表8-1)，還已知使用不同時間(年)的設備所需要的維修費用(見表8-2)。14:228.4.3.最短路問題應用舉例8.4.最短路問題用點vi代表“第i年年初購進一臺新設備”這種狀態(tài)(加設一點v6，可以理解為第5年年底)。從vi到vi+1，...，v6各畫一條弧?；?vi,vj)表示在第i年年初購進的設備一直使用到第j年年初(即第j-1年底)。每條弧的權可按已知資料計算出來。例如,(v1,v4)是第1年年初購進一臺新設備(支付購置費11萬元),一直使用到第3年年底(支付維修費5+6+8=19萬元),故(v1,v4)上的權為30萬元。這樣一來,制定一個最優(yōu)的設備更新計劃問題就等價于尋求從v1到v6的最短路的問題。于是按求解最短路的計算方法,{v1,v3,v6}及{v1,v4,v6}均為最短路,即有兩個最優(yōu)方案。一個方案是在第1年、第3年各購置一臺新設備；另一個方案是在第1年、第4年各購置一臺新設備。五年總的支付費用均為53萬元。14:228.4.3.最短路問題應用舉例8.4.最短路問題【例8-12】選址問題選址就是指在某一指定區(qū)域內選擇服務性設施(如市郊商店區(qū)、消防站、醫(yī)院、工廠、倉庫等)最佳位置的問題。解決這類問題的關鍵是求出相應圖中所有點間的最短路。例如，已知有6個村莊，各村莊間的距離如圖8-19所示，各村的小學生人數見表8-3?，F在計劃在這片區(qū)域內建造一所醫(yī)院和一所小學，間醫(yī)院應建在哪個村莊才能使最遠村莊到醫(yī)院看病所走的總路程最短?又間小學建在哪個村莊才能使學生上學走的總路程最短。14:228.4.3.最短路問題應用舉例8.4.最短路問題利用最短路計算(對于這種無向圖G中的最短路問題，當其所有的邊權wij≧0時，可直接利用前面求解有向圖最短路徑問題的最短路算法)。首先求出任意兩點vi，vj間的最短路線Sij得到矩陣S(Sij表示從vi出發(fā)到vj的最短路徑長度)。14:228.4.3.最短路問題應用舉例8.4.最短路問題設想醫(yī)院建在村莊vj，則其他村莊的村民就要分別走S1j，S2j，...，S6j的路程，對于點vj，Sij中必有最大者(最遠距離)，對每一點求出這個最大值。當然希望醫(yī)院建立在這些最大值之中的最小值對應的村莊。這相當于對S中每一列求出元素的最大值，它們分別是11、9、6、7、8、11。這些數中6最小，即第3列達到最小，即醫(yī)院應建立在v3，其他村莊到該村莊的距離最遠為6。設想小學建立在vj，則其他村莊的小學生們所走的總路程就是14:228.4.3.最短路問題應用舉例8.4.最短路問題對每一點求出這個值，它們的最小值所對應的vj就是所要選擇的最佳位置，這相當于將矩陣S中每一行元素分別乘上對應村莊里小學生的人數，然后分別求出各列的和，得矩陣D各列總和。14:228.4.3.最短路問題應用舉例8.4.最短路問題對每一點求出這個值，它們的最小值所對應的vj就是所要選擇的最佳位置，這相當于將矩陣S中每一行元素分別乘上對應村莊里小學生的人數，然后分別求出各列的和，得矩陣D各列總和。14:228.5.1.引例8.5.網絡最大流許多系統(tǒng)包含了流量問題。例如交通系統(tǒng)有車輛流，金融系統(tǒng)有現金流，控制系統(tǒng)有信息流等。最大流問題主要是確定這類系統(tǒng)網絡所能承受的最大流量以及如何達到這個最大流通量。【例8-13】如圖8-20是連接某產品產地vi和銷地vj的交通網?；?vi，vj)表示從vi到vj的運輸線，弧旁的數字表示這條運輸線的最大通過能力?，F要求制訂一個運輸方案，使從vs運到vt的產品數量最多。本例提出的問題就是一個最大流問題。實際上最大流問題是一個特殊的線性規(guī)劃問題。本節(jié)將介紹利用圖的特點求解這類問題的方法，它比用線性規(guī)劃求解簡單而直觀得多。14:228.5.2.基本概念與定理8.5.網絡最大流【定義8-10】(1)網絡給一個有向圖D=(V,A），在V中指定了一點稱為發(fā)點(記為vs)，指定另一點稱為收點(記為vt)，其余的點叫中間點。對于A中的弧(vi,vj），對應有一個c(vi,vj)≧0(簡記Cij)，稱之為弧的容量。通常把這樣的D叫做網絡，記為D=(V，A，C)。例如，如圖8-20就是一個網絡，其中弧旁的數字為Cij，表示(vi,vj)線路上最大通過能力。14:228.5.2.基本概念與定理8.5.網絡最大流(2)網絡流網絡上的流是指定義在弧集A上一個非負函數f={f(vi,vj)}，并稱f(vi,vj)為弧(vi,vj)的流量，簡記fij。流量的集合f={fij)}稱為網絡的流，從發(fā)點到收點的總流量記為v(f)。如圖8-21所給定的運輸方案，就可看作是這個網絡上的流，每條弧上的運輸量即為該弧上的流量，有fs2=6，fs3=4，f32=2，f46=1，f25=5等。14:228.5.2.基本概念與定理8.5.網絡最大流在圖8-21的運輸網絡中，可以發(fā)現，對于網絡中的流有兩個明顯的要求：一是每條線路上的運輸量(括號中的數字)不能超過該線路的最大運送能力(即弧的容量)；二是中間點的流量為零，因為對于每個點，運出該點的產品總量與運進這點的產品總量之差，是該點的凈輸出量，則稱之為該點的流量；由于中間點只起到運轉作用，所以中間點的流量必為零。而且發(fā)點的凈流出量和收點的凈流入量必相等，也就是這個方案的總輸送量。14:228.5.2.基本概念與定理8.5.網絡最大流(3)可行流設f={fij)}為一網絡流，當f滿足下列條件時，稱為可行流。①容量限制條件對每一弧(vi,vj)∈A，有0≦fij≦Cij0平衡條件對于中間點vi(is,t)，流入量等于流出量，即14:228.5.2.基本概念與定理8.5.網絡最大流(3)可行流設f={fij)}為一網絡流，當f滿足下列條件時，稱為可行流。①容量限制條件對每一弧(vi,vj)∈A，有0≦fij≦Cij0平衡條件對于中間點vi(is,t)，流入量等于流出量，即14:228.5.2.基本概念與定理8.5.網絡最大流(3)可行流設f={fij)}為一網絡流，當f滿足下列條件時，稱為可行流。①容量限制條件對每一弧(vi,vj)∈A，有0≦fij≦Cij0平衡條件對于中間點vi(is,t)，流入量等于流出量，即14:228.5.2.基本概念與定理8.5.網絡最大流【定義8-11】(1)飽和弧與非飽和弧若給定一個可行流f={fij}，則稱網絡中fij=cij的弧為飽和弧；fij<cij的弧為非飽和弧(或不飽和弧)。(2)零流弧與非零流弧若給定一個可行流f={fij}，稱fij=0的弧為零流弧，fij>0的弧為非零流弧。例如圖8-21中，弧(v2,v5)是飽和弧，其余的都為非飽和?。粓D中沒有零流弧，所有的弧都為非零流弧。(3)前向弧與后向弧若μ是網絡中連接發(fā)點vs與收點vt的一條鏈，定義鏈的方向是從vs到vt，則鏈上的弧被分為兩類：一類弧的方向與鏈的方向一致，稱為前向弧，前向弧的全體記為μ+；另一類弧與鏈的方向相反，稱之為后向弧，后向弧的全體記為μ-。14:228.5.2.基本概念與定理8.5.網絡最大流例如圖8-21，在鏈μ=(vs,v2,v3,v6,vt)中：μ+={(vs,v2),(v3,v6),(v6,vt)}μ-={(v3,v2)}值得一提的是，前向弧和后向弧是相對于某一具體的鏈而言的。一條弧相對于不同的鏈，可能是前向弧，也可能是后向弧?！径x8-12】設f={fij}是一個可行流，μ是從vs到vt的一條鏈。若μ滿足：1)在弧(vi,vj)∈μ+上，0≦fij≦cij。即所有前向弧都是非飽和弧。2)在弧(vi,vj)∈μ-上，0<fij≦cij，即所有的后向弧都是非零流弧。則稱μ是關于可行流f的一條增廣鏈。例如圖8-21中，鏈μ=(vs,v2,v3,v6,vt)是一條增廣鏈。14:228.5.3.截集和截量8.5.網絡最大流(1)截集給定網絡D=(V,A,C)，若點集V被分割為兩個非空子集V1和，且vt∈，，則由始點在中，終點在中的所有弧組成的集合稱為網絡的一個截集，記為(，)。顯然，若把某一截集的弧從網絡中去掉，則從vs到vt便不存在路。所以，直觀上說，是從vs到vt必經之道。(2)截量給定一截集(，)，把截集(，)中所有弧的容量之和稱為這個截集的容量(簡稱為截量)，記為。c(，)，即14:228.5.3.截集和截量8.5.網絡最大流(1)截集給定網絡D=(V,A,C)，若點集V被分割為兩個非空子集V1和，且vt∈，，則由始點在中，終點在中的所有弧組成的集合稱為網絡的一個截集，記為(，)。顯然，若把某一截集的弧從網絡中去掉，則從vs到vt便不存在路。所以，直觀上說，是從vs到vt必經之道。(2)截量給定一截集(，)，把截集(，)中所有弧的容量之和稱為這個截集的容量(簡稱為截量)，記為。c(，)，即14:228.5.3.截集和截量8.5.網絡最大流【定理8-4】可行流f*是最大流，當且僅當不存在關于f*的增廣鏈。最大流最小截量定理；任一個網絡D中，從vs到vt的最大流的流量等于分離vs、vt的最小截集的容量。定理8-4提供了尋求網絡中最大流的一個方法。若給了一個可行流f，只要判斷D中有無關于f的增廣鏈。如果有增廣鏈，則可以改進f，得到一個流量增大的新的可行流。如果沒有增廣鏈，則得到最大流。在實際計算時，一般是用給頂點標號的方法來定義的。在標號過程中，有標號的定點表示是中的點，沒有標號的點表示不是中的點。一旦vt有了標號，就表明找到一條增廣鏈；如果標號過程進行不下去，而vt尚未標號，則說明不存在增廣鏈，于是得到最大流。而且同時也得到一個最小截集。14:228.5.4.尋求最大流的標號法(Ford-Fulkemon)8.5.網絡最大流1.算法的基本思想求最大流的Ford-FuIkewon標號法的基本思想是從某個可行流出發(fā)(若網絡圖中沒有給定可行流f，則可以設f是零流或按可行流的條件給定)，用給頂點標號的方法來找增廣鏈，一旦終點vt有了標號，表明找到了一條增廣鏈，對此增廣鏈上的流f進行調整，對調整后的可行流重新進行標號，試圖尋找新的增廣鏈。如此反復。如果標號過程進行不下去，即vt得不到標號，則說明不存在增廣鏈，也就說明已經得到了最大流。14:228.5.4.尋求最大流的標號法(Ford-Fulkemon)8.5.網絡最大流2.算法步驟尋求最大流的標號法一般包括兩步；標號過程和調整過程。(1)標號過程在這個過程中，網絡圖中的頂點分為兩部分，即標號的點和末標號的點，標號的點又分為已檢查點和未檢查點，即每個標號點vj的標號包含兩部分：第1個標號表明它的標號是從哪一點得到的，以便找出增廣鏈；第2個標號是為確定增廣鏈的調整量θ用的。具體標號過程如下：14:228.5.4.尋求最大流的標號法(Ford-Fulkemon)8.5.網絡最大流第1步：給發(fā)點vs標上(0，+∞)，這時vs是標號而未檢查的點，其余的點都是未標標號點。第2步：取一個標號而未檢查的點vi，對一切未標標號點vj，按以下規(guī)則處理：1)若在弧（vi，vj）上，vj未標標號，且fij<cij，則給vj標號(vi,l(vj))，其中l(wèi)(vj)=min{l(vi)，cij-fij}。2)若在弧（vi，vj）上，vj未標標號，且fij>0，則給vj標號(-vi，l(vj))，其中l(wèi)(vj)=min{l(vi)，fji}。這時點vj成為標號而未檢查的點，而vi成為標號并已檢查過的點。第3步：重復第2步，一旦vt被標上號，表明得到一條從vs到vt的增廣鏈μ，轉入調整過程；若所有標號都己檢查過了，vt不能得到標號，而且不存在其他可標號的頂點時，算法終止，這時的可行流就是最大流。14:228.5.4.尋求最大流的標號法(Ford-Fulkemon)8.5.網絡最大流(2)調整過程第1步：按vt及其他點的第1個標號，利用“反向追蹤”的辦法，找出增廣鏈μ。例如設vt的第1個標號為vk(或-vk)，則弧(vk,vt)(或相應的(vt,vk))是μ上的弧。接下來檢查vk的第1個標號，若為vi(或-vi)，則找出(vi,vk)(或相應的(vk,vi))。再檢查vt的第1個標號，依此下去，直到vs為止。這時被找出的鏈即為增廣鏈μ。第2步：調整增廣鏈μ上的流量。確定調整量θ=l(vt)，即vt的第2個標號14:228.5.4.尋求最大流的標號法(Ford-Fulkemon)8.5.網絡最大流(2)調整過程第1步：按vt及其他點的第1個標號，利用14:228.5.4.尋求最大流的標號法(Ford-Fulkemon)8.5.網絡最大流(1)標號過程針對當前可行流(v(f)=8)尋找增廣鏈。1)給vs標上(0,+∞)，vs為己標號而未檢查點。2)檢查vs。v1可得標號(vs，2)，v2、v3不能得到標號，因為弧(vs，v2)和(vs，v3)為飽和弧。這樣vs為標號已檢查點，v1成為標號未檢查點。3)檢查v1。狐(v3，v1)是反向弧，且f31=1>0，則v3可得到標號(-v1，1)；弧(v1，v4)是飽和弧，故v4不能得到標號。這樣v1為標號已檢查點，v3成為標號未檢查點。4)檢查v3?；?v3,v4)和弧(v3,v5)均為正向飽和弧，不滿足標號條件；而弧(v3，v2)為正向不飽和弧，則v2可得到標號(v3，1)。此時，v3為標號已檢查點，v2成為標號未檢查點。14:228.5.4.尋求最大流的標號法(Ford-Fulkemon)8.5.網絡最大流5)檢查v2?；?v2，v5)為正向不飽和弧，則v5可得到標號(v2,1)。此時，v2為標號已檢查點，v5成為標號未檢查點。6)檢查v5?；?v5，vt)為正向飽和弧，不滿足標號條件；而弧(v5，v4)為正向不飽和弧，則v4可得到標號(v5，1)。此時，v5為標號已檢查點，v4成為標號未檢查點。7)檢查v4。弧(v4，vt)為正向不飽和弧，則vt可得到標號(v4，1)。因為vt已得到標號，故存在從vs到vt的增廣鏈，轉入調整過程。(2)調整過程首先按vt及其他頂點的第1個標號，利用“反向追蹤”的辦法，找到一條增廣鏈如圖8-24中雙線所示。14:228.5.4.尋求最大流的標號法(Ford-Fulkemon)8.5.網絡最大流(2)調整過程首先按vt及其他頂點的第1個標號，利用“反向追蹤”的辦法，找到一條增廣鏈如圖8-24中雙線所示。μ=(vs，v1，v3，v2，v5，v4，vt)14:228.5.4.尋求最大流的標號法(Ford-Fulkemon)8.5.網絡最大流顯而易見：μ+={(vs，v1)，(v3，v2)，(v2，v5)，(v5，v4)，(v4，vt)}μ-={(v3，v1)}14:228.5.4.尋求最大流的標號法(Ford-Fulkemon)8.5.網絡最大流按θ=l(vt)=1，在μ上調整f，μ+上的弧fij+θ，μ-上的弧fij-θ，其余弧上的fij不變。調整后，得到圖8-25所示的可行流，v(f)=8+1=9，對流量值為9的可行流進行標號，尋找增廣鏈。首先給vs標號(0,+∞)，檢查vs，給v1標號(vs，1)，檢查v1，弧(v1，v4)為前向飽和弧(f14=c14=2)，弧(v3，v1)為后向零流弧(f31=0)，均不符合標號條件，故標號過程無法進行下去，算法終止。這時的可行流(見圖8-25)即為所求的最大流，其最大流量為14:228.6.1.問題描述8.6.最小費用最大流問題在最大流問題中，己經討論了如何尋求網絡的最大流。但是在實際生活中，涉及網絡“流”的問題時，往往不僅要考慮流量，還要考慮“費用”因素。例如，在運輸網絡中，從發(fā)點vs到收點vt所經過的路程，經常因為交通工具不同或道路本身狀況不同而導致不同運輸方案的交通費用不同。這樣，問題就變成了不僅要求使vs到vt的運輸量最大，而且要求這種運輸方案的總費用最小。像這樣一類問題就是所謂的最小費用最大流問題。下面給出最小費用最大流問題的一般描述：給定網絡D=(V，A，C)，在每一條弧(vi,vj)∈A上，除容量cij外還涉及單位流量費用b(vi，vj)≧0(簡記為bij)。如果f是D的一個可行流，則其總費用為14:228.6.1.問題描述8.6.最小費用最大流問題要求b(f)為最小且流量為某確定值v(f)的可行流問題，稱為最小費用流問題；求b(f)為最小且流量v(f)為最大的問題，稱為最小費用最大流問題。如果把最小費用看成約束條件，和最大流問題一樣，最小費用流問題也是一個線性規(guī)劃問題，并且求最小費用流實際上是求該線性規(guī)劃問題的可行解，求最小費用最大流問題實際上是求該線性規(guī)劃問題的最優(yōu)解。自然，可行解經過調整即可得到最優(yōu)解。當然，用圖論方法求解比用一般線性規(guī)劃求解要簡單便捷得多。14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題1)算法思想根據最大流問題算法可知，尋求最大流的方法是從某個可行流出發(fā)，找到關于這個流的一條增廣鏈μ，沿著μ調整f，對新的可行流再試圖尋找關于它的增廣鏈，反復進行直至最大流。現在要尋求最小費用最大流，首先考察一下，當沿著一條關于可行流f的增廣鏈μ進行調整，以θ=1進行調整，得到新可行流f'。這時，可行流f'與f在增廣鏈μ上的流量相差1，其他弧上的流量相同。所以，可行流f'與f的費用只在增廣鏈上有差異，其他弧上費用相當。因此，兩者的費用差為14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題其中，μ+為μ的前向弧集；μ-為μ的后向弧集。稱為這條增廣鏈μ的“費用”。(注：在這里，費用也可以是指距離、時間、成本等)。可以證明，若f是流量為v(f)的所有可行流中費用最小者，而μ是關于f的所有增廣鏈中費用最小的增廣鏈，那么沿著μ去調整f，得到的可行流f'就是流量為v(f')的所有可行流中的最小費用流。這樣，當f'是最大流時，它也就是最小費用最大流。因為bij≧0，所以f=0(零流或平凡流)的總費用b(f)=0必是流量為零的最小費用流，所以通常稱零流為最小費用流問題的初始解。14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題一般地，設已知f是流量為v(f)的最小費用流，問題在于如何尋求關于f的最小費用增廣鏈。費用最小的增廣鏈有兩層含義：一方面，對費用bij網絡來說，它是一條費用最小的鏈，這可以通過求以bij為權的網絡的最短路來獲得；另一方面，對容量流量網絡{cij，fij)來說，它必須是一條能增大流量的增廣鏈。下面分析網絡流圖D(f)中弧的基本情況。對于弧(vi，vj)一般有以下3種情形：(1)0<fij<cij，則弧(vi，vj)既可作為增廣鏈μ的前向弧，也可作為增廣鏈μ的后向弧。若(vi，vj)∈μ+，鏈上增流時弧也增流，使總費用增加；若(vi，vj)∈μ-，鏈上增流時則減流，使總費用減少。14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題(2)0<fij=cij。則弧(vi，vj)只能作為增廣鏈的后向弧，也可作為增廣鏈的前向弧。鏈增流時弧則減流，使總費用減少。(3)fij=0，則弧(vi，vj)只能作為增廣鏈μ的前向弧，鏈增流時弧也增流，使總費用增。根據以上的分析，不難構造網絡流圖D(f)的以費用為權的有向圖(簡稱費用網絡圖)w(f)，以求得關于流f的最小費用增廣鏈。構造費用網絡圖的規(guī)則為(1)頂點為原網絡流圖的頂點。作兩條方向相反的弧(vi，vj)和(vj，vi)，0<fij<cij。(2)?。鹤饕粭l與D(f)同向的弧，fij=0作一條與D(f)反向的弧，0<fij=cij。14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題(3)權于是在原網絡流圖D(f)中尋求關于f的最小費用增廣鏈就等價于在費用網絡圖w(f)中尋求從vs到vt的最短路。14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題【例8-15】以圖8-26為例，構造其費用網絡圖w(f)?；∨缘臄底譃?bij，cij，fij)。解:首先取頂點V={vs，v1，v2，v3，vt}?；。涸贒中弧(vs，v1)和(vs，v2)均滿足0<fij<cij，即fs1=2<cs1=10，fs2=10<cs2=8。14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題因此，在w(f)中頂點vs、v1間和頂點vs、v2間各作兩條方向相反的??；在D中，弧(v1，vt)和(v2，v1)均滿足fij=cij。因此在w(f)中對應頂點間各作一條與D(f)中弧(v1，vt)和(v2，v1)方向相反的弧，即(vt，v1)和(v1，v2)；再在D(f)中，弧(v2，v3)、(v1，v3)和(v3，vt)均有fij=0，因此在w(f)中對應頂點各作一條與D(f)中弧方向相同的弧，即(v2，v3)、(v1，v3)和(v3，vt)。權：圖w(f)中與D(f)中方向相同的對應弧wij=bij，方向相反的弧wij=-bij。如圖8-27所示。另外，還有一種構造費用網絡圖w(f)的規(guī)則：(1)頂點為原網絡圖D的頂點。(2)?。喊袲中的每條弧(vi，vj)變成兩條方向相反的弧(vi，vj和(vj，vi)。14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題如圖8-27所示。14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題2)算法步驟最小費用最大流的算法通常采用對偶算法，其具體算法步驟如下：開始時取初始可行流為零流，即v(f0)=0。在其對應的費用網絡w(f0)上，用求最短路的方法求出從vs到vt的最短路，即尋找最小費用的增廣鏈μ0；并在容量網絡上沿著μ0調整流量，再在新的可行流f1的基礎上構造新的費用網絡w(f1)，重新尋找最小費用增廣鏈。如此，在第k-1步后得到最小費用流fk-1，再構造對應的費用網絡w(fk-1)，繼續(xù)尋找從vs到vt的最短路。若不存在最短路，則fk-1就是最小費用最大流；若存在最短路，則在原流量網絡中得到相應的增廣鏈μ，在增廣鏈μ上對fk-1進行調整，允許的調整量為14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題調整后新的可行流fk為再對fk重復上述步驟。算法的流程圖如圖8-28所示。14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題【例8-16】求圖8-29所示的網絡中從vs到vt的最小費用最大流，其中每條弧上的數字為(bij，cij)，bij為單位費用，cij為容量。解(1)取初始可行流f0=0，構造相應的費用網絡w(f0)，如圖8-30a所示。(2)在w(f0)上用Dijkstra算法求出vs到vt的最短路(即最小費用鏈)，如圖8-30a中雙線所示：vs→v1→v3→vt；在原網絡流圖D(f0)中與這條最短路相應的增廣鏈為μ0=(vs，v1，v3，vt)，沿著該增廣鏈調整流量，調整量θ=4，得新的可行流f1，其流值v(f1)=4，如圖8-30b所示。14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題(3)再構造與D(f1)相對應的費用網絡w(f1)，如圖8-31a所示。由于圖中含有負權，則用標號法求vs到vt的最短路，如圖8-31a中雙線所示：vs→v2→v3→vt；在流量網絡D(f1)中與這條最短路相對應的增廣鏈為μ1=(vs，v2，v3，vt)，在增廣鏈μ1上對f1進行調整，調整量θ=1，得新的可行流f2，其流值v(f2)=5，如圖8-31b所示。14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題(4)再構造與D(f2)相對應的費用網絡w(f2)，如圖8-32a所示。并在w(f2)即上求最短路，即在w(f2)上得到相應的增廣鏈μ2=(vs，v1，v4，vt)，在增廣鏈μ2上對f2進行調整，調整量θ=3，得新的可行流f3，其流值v(f3)=8，如圖8-32b所示。(5)繼續(xù)作w(f3)，如圖8-33a所示，并在w(f3)上求最短路徑，即在D(f3)上得到相應的增廣鏈μ3=(vs，v2，v3，v4，vt)，調整流量后得如圖8-33b所示的流量圖D(f4)，新增流量θ=4，流值v(f4)=12。14:228.6.2.最小費用最大流問題求解8.6.最小費用最大流問題(6)作w(f4)，如圖8-34所示，由于從w(f4)中無法找到vs到vt的最短路，說明在D(f4)中己不存在增廣鏈，求解終止。故D(f4)所示的流即為所求的最小費用最大流。此時v(f4)=12,最小費用為b(f4)=7x12+5x15+0x14+5x25+4x18+3x20+4x11+7x22+5x13=679。14:228.7.申國郵路問題假設一個郵遞員負責某一街區(qū)的信件投遞，他每天要從郵局出發(fā)，走遍該區(qū)所有的街道投遞完信件后再返回郵局。問他如何選擇一條投遞的路線才能使他所走的總路程最短?這個問題是由我國管梅谷教授在1962年首先提出的，因此國際上統(tǒng)稱為中國郵路問題。用圖論的語言可描述為：給定一個連通網絡G，要求一個圈C經G的每邊至少一次，且使C的權和最小。14:228.7.1.歐拉圖8.7.申國郵路問題若在一個連通圖G中，存在一條鏈恰好經過每條邊一次，則稱該鏈為歐拉鏈，若該鏈是首尾相接的，則稱為歐拉圈。如果一個圖含有歐拉圈，則稱該圖為歐拉圖。“七橋問題”其實就是要在圖中尋找一個歐拉圈。關于歐拉圖可以證明如下結論：【定理8-5】連通圖G是歐拉圖的充分必要條件是C中無奇點。證明：必要性因G是歐拉圖，故存在一個歐拉圈C，它經過G的所有邊。又因G是連通的，從而C包含了G的所有頂點，即G的任一頂點必出現在C中。設v0為C的始點(終點)，當沿著C的某一方向前進時，每通過任一頂點時，必是一進一出，而每邊在C中恰好出現一次，故對于G中任一異于v0的頂點必是偶頂點。而對于v0，由于C始于v0又終于v0，故v0也是偶頂點。因此，圖G無奇點。14:228.7.1.歐拉圖8.7.申國郵路問題充分性：由于圖G中無奇頂點，從任一頂點v1出發(fā)，經關聯(lián)邊e1進入e2，由于v2是偶頂點，故必可由v2經關聯(lián)邊e2進入另一頂點v3.......如此進行下去，每邊必經過一次。因圖G中頂點數有限，故這條路不能無休止地走下去，必可走回v1，得到一個圈C1。若回路C1經過G的所有邊，則C1就是歐拉圈。否則，從G中刪去C1后得到子圖G1，則G1中每個頂點仍為偶頂點。因為圖G是連通圖，所以C1與G1至少有一個公共頂點u，在G1中，從頂點u出發(fā)，重復前面構造C1的方法，又得到一個圈C2。把C1與C2合并在一起可得到一個更大的圈，如果它等于圖G，則得到歐拉圈，否則重復前面構造的過程，又可得圈C3。依次類推，由于圖G中邊數有限，故最終可得一個經過圖G每邊恰好一次的圈，即為歐拉圈。14:228.7.1.歐拉圖8.7.申國郵路問題從這個定理可以得到以下推論：推論：連通圖G含歐拉鏈的充分必要條件是G恰有兩個奇頂點。上述定理和推論提供了識別一個圖能否一筆畫出的較為簡單的辦法。如前面的“七橋問題”，有4個奇點，所以不能一筆畫出。14:228.7.2.奇偶點圖上作業(yè)法8.7.申國郵路問題根據上面的討論，如果在某郵遞員所負責的范圍內，街道圖中沒有奇點，那么他就可以從郵局出發(fā)，走過每條街道一次，且僅一次，最后回到郵局，這樣他所走的路程也就是最短的路程。對于有奇點的街道圖，就必須在某些街道上重復走一次或多次。將郵遞員管轄的街道圖視為無向圖G=(V,E)，若G沒有奇頂點，則G是一個歐拉圖，G含的歐拉圈即為所求。若G中有奇頂點，要求連續(xù)經過每邊至少一次，則必然有些邊不止經過一次，這相當于在圖G中對某些邊添加一些重復邊，使所得到的新圖G'沒有奇頂點且便總路程最短。顯然，添加的重復邊的總長度最短，由此有求解中國郵路間題的奇偶點圖上作業(yè)法：14:228.7.2.奇偶點圖上作業(yè)法8.7.申國郵路問題1)把圖G的奇頂點兩兩配對，并將每對奇頂點間的通路上的各邊作為重復邊添加到圖G上，得到的新圖全部頂點都是偶頂點。如果某邊上的重復邊多于一條，則可從中刪去偶數條，使每邊的重復邊最多只有一條。2)檢查圖G中的每個初級圈。若每個圈的重復邊的總長度不大于該圈長度的一半時，則得到最優(yōu)方案。否則，若有一個初級圈，該圈的重復邊的總長度大于該圈長度的一半，就將該圈的原有重復邊刪去，給該圈原來沒有重復邊的各邊都加上一條重復邊。重復這個過程，直到沒有這種圈為止。14:228.7.2.奇偶點圖上作業(yè)法8.7.申國郵路問題【例8-17】求解如圖8-35所示網絡的中國郵路間題。解：第1步，確定初始可行方案。先找出圖中的奇頂點，有v2，v4，v6，v8，把v2與v4配對，v6與v8配對。在v2與v4間添加重復邊v2v3；在v6與v8間添加重復邊v6v7和v7v8，如圖8-36所示。此圖沒有奇頂點，已是歐拉圖。這個初始可行方案的全部重復邊的總長度為21。14:228.7.2.奇偶點圖上作業(yè)法8.7.申國郵路問題第2步，調整可行方案。檢查發(fā)現圖8-36中有一個初級圈{v2v3v4v5v2}，它的重復邊的總長度為5+9=14，大于該圈長度的一半12。因此，去掉該圈的重復邊v2v3和v3v4而代之以總長度較短的重復邊v2v5和v5v4，如圖8-37所示。這樣調整后，可行方案的全部重復邊的總長度為17。第3步，繼續(xù)調整方案。檢查圖8-37發(fā)現有一個初級圈{v1v2v5v8v7v6v1}。它的重復邊總長度為4+3+6=13，大于該圈長度的一半12。因此，去掉該圈的重復邊v6v7、v7v8和v2v5，而代之以總長度較短的重復邊v2v1、v1v6和v5v8，如圖8-38所示。這樣調整后，可行方案的全部重復邊總長度為15。14:228.7.2.奇偶點圖上作業(yè)法8.7.申國郵路問題在圖8-38中，每個初級圈的重復邊總長度均不超過該圈長度的一半，因此，該可行方案就是最優(yōu)方案，圖8-38中的任一個歐拉圈就是郵遞員的最優(yōu)郵遞路線。奇偶點圖上作業(yè)法在實際運用中已作出許多貢獻。它不僅可以提高郵遞員的工作效率，而且對于街道清掃路線、紡織工看車路線、倉庫員巡視貨物路線等類似問題的研究，都有實際意義。這種方法特點是比較容易實現，但要檢查每個初級圈，當圖G的頂點數和邊數較多時，運算量極大。Edmods和Johnson于1973年提出了一種比較有效的方法，即化為最短路及最優(yōu)匹配問題求解。14:228.8.網絡計劃技術網絡圖是圖論方法在解決工程和管理問題的一項重要應用。在管理工作中，除了可以應用網絡分析方法制訂決策外，還廣泛地應用網絡方法編制計劃。把繪制網絡圖的規(guī)則及計算相關參數(主要是時間參數)的方法稱為網絡方法。把以網絡圖表示的、用網絡方法編制的計劃稱為網絡計劃。網絡計劃技術是一種以總的工程進度著眼的組織管理技術，把一項復雜的工程分解成許多工序，按工序的先后順序相互聯(lián)系建立網絡圖，進行定量分析、找出主要矛盾線達到重點控制；計算時間參數，找出時差，從而對時間和資源進行合理的計劃、配置與控制，以保證工程提前或按期完成。在考慮進度的同時，結合考慮完成任務的總成本，統(tǒng)籌兼顧，多快好省。14:228.8.網絡計劃技術網絡計劃技術主要包括關鍵路線法(CPM)和計劃評審法(PERT)，CPM借助于網絡表示各項工作所需要的時間及各項工作間的相互關系，從而找出編制與執(zhí)行計劃的關鍵路線；PERT同樣應用網絡方法和網絡形式，但它注重于對各項任務安排的評價和審查。1965年，我國開始應用推廣這種方法，并根據其主要特點統(tǒng)籌安排，把它也稱為統(tǒng)籌方法。14:228.8.1.網絡圖基本概念及繪制規(guī)則8.8.網絡計劃技術【例8-18】某項研制新產品工程的各個工序與所需時間以及它們之間的相互關系見表14:228.8.1.網絡圖基本概念及繪制規(guī)則8.8.網絡計劃技術要求編制該項工程的網絡計劃。為編制網絡計劃，首先需繪制網絡圖。網絡圖是由節(jié)點(點)、弧及權所構成的有向圖。即有向的賦權圖。節(jié)點：表示一個事項(或事件)，它是一個或若干個工序的開始或結束，是相鄰工序在時間上的分界點。節(jié)點用圓圈和里面的數字表示，數字表示節(jié)點的編號，如①、②、...等?；。罕硎疽粋€工序，工序是指為了完成工程項目，在工藝技術和組織管理上相對獨立的工作或活動。一項工程由若干個工序組成。工序需要一定的人力、物力等資源和時間?；∮眉€→表示。權：表示為完成某個工序所需要的時間或資源等。通常標注在箭線下面或其他合適的位置上。根據表8-4的已知條件和數據，繪制的網絡圖如圖8-39所示。14:228.8.1.網絡圖基本概念及繪制規(guī)則8.8.網絡計劃技術根據表8-4的已知條件和數據，繪制的網絡圖如圖8-39所示。14:228.8.1.網絡圖基本概念及繪制規(guī)則8.8.網絡計劃技術在圖8-39申，箭頭線a、b、...、l分別代表10個工序。箭線下面的數字表示為完成該個工序所需的時間(天數)。節(jié)點①、②、...、⑧分別表示某一或某些工序的開始和結束。例如，節(jié)點②表示a工序的結束和b、c、d、e等工序的開始，即a工序結束后，后4個工序才能開始。在網絡圖8-39中，用一條弧和兩個節(jié)點表示一個確定的工序。例如，②→⑦表示一個確定的工序b。工序開始的節(jié)點常以i表示，稱為箭尾節(jié)點。工序結束的節(jié)點常以j表示，稱為箭頭節(jié)點。i稱為箭尾事項，j稱為箭頭事項。工序的箭尾事項與箭頭事項稱為該工序的相關事項。在一個網絡圖中，只能有始點和終點兩個節(jié)點，分別表示工程的開始和結束，其他節(jié)點既表示上一個(或若干個)工序的結束，又表示下一個(或若干個)工序的開始。14:228.8.1.網絡圖基本概念及繪制規(guī)則8.8.網絡計劃技術為正確反映工程中各個工序的相互關系，在繪制網絡圖時，應遵以下規(guī)循以下規(guī)則：(1)方向、時序與節(jié)點編號網絡圖是有向圖，按照工藝流程的順序，規(guī)定工序從左向右排列。網絡圖中的各個節(jié)點都有一個時間(某一個或若千個工序開始或結束的時間)，一般按各個節(jié)點的時間順序編號。為了便于修改編號及調整計劃，可以在編號過程中，留出一些編號。始點編號可以從1開始，也可以從零開始。(2)緊前工序與緊后工序例如，在圖8-