【正文】 管 理 運(yùn) 籌 學(xué) 1 第五章 圖與網(wǎng)絡(luò)模型 167。 1 圖與網(wǎng)絡(luò)的基本概念 167。 2 最短路問(wèn)題 167。 3 最小生成樹(shù)問(wèn)題 167。 4 最大流問(wèn)題 167。 5 車(chē)間作業(yè)計(jì)劃 167。 6 統(tǒng)籌法（網(wǎng)絡(luò)規(guī)劃） 管 理 運(yùn) 籌 學(xué) 圖論是專(zhuān)門(mén)研究圖的理論的一門(mén)數(shù)學(xué)分支 ， 屬于離散數(shù)學(xué)范疇 ，與運(yùn)籌學(xué)有交叉 ， 它有 200多年歷史 ，大體可劃分為 三個(gè)階段 ： 第一階段是從十八世紀(jì)中葉到十九世紀(jì)中葉 ，處于萌芽階段 ， 多數(shù)問(wèn)題為游戲而產(chǎn)生 ， 最有代表性的工作是所謂的Euler七橋問(wèn)題 (1736年 )， 即一筆畫(huà)問(wèn)題 。 管 理 運(yùn) 籌 學(xué) 第二階段 是從十九世紀(jì)中葉到二十世紀(jì)中葉 ， 這時(shí) ， 圖論問(wèn)題大量出現(xiàn) ， 如 Hamilton問(wèn)題 ， 地圖染色的四色問(wèn)題以及可平面性問(wèn)題等 ， 這時(shí) ， 也出現(xiàn)用圖解決實(shí)際問(wèn)題 ， 如 Cayley把樹(shù)應(yīng)用于化學(xué)領(lǐng)域 ， Kirchhoff用樹(shù)去研究電網(wǎng)絡(luò)等 . 管 理 運(yùn) 籌 學(xué) 第三階段 是二十世紀(jì)中葉以后 ， 由生產(chǎn)管理 、 軍事 、 交通 、 運(yùn)輸 、 計(jì)算機(jī)網(wǎng)絡(luò)等方面提出實(shí)際問(wèn)題 ， 以及大型計(jì)算機(jī)使大規(guī)模問(wèn)題的求解成 為 可 能 ， 特 別 是 以 Ford 和Fulkerson建立的網(wǎng)絡(luò)流理論 ， 與線性規(guī)劃 、 動(dòng)態(tài)規(guī)劃等優(yōu)化理論和方法相互滲透 ， 促進(jìn)了圖論對(duì)實(shí)際問(wèn)題的應(yīng)用 。 管 理 運(yùn) 籌 學(xué) 例 101： 哥尼斯堡七橋問(wèn)題 哥尼斯堡 （ 現(xiàn)名加里寧格勒 ）是歐洲一個(gè)城市 ， Pregei河把該城分成兩部分 ， 河中有兩個(gè)小島 ， 十八世紀(jì)時(shí) ， 河兩邊及小島之間共有七座橋 ， 當(dāng)時(shí)人們提出這樣的問(wèn)題：有沒(méi)有辦法從某處 （ 如 A） 出發(fā) ，經(jīng)過(guò)各橋一次且僅一次最后回到原地呢 ？ 管 理 運(yùn) 籌 學(xué) A B C D 管 理 運(yùn) 籌 學(xué) 最后 ， 數(shù)學(xué)家 Euler在 1736年巧妙地給出了這個(gè)問(wèn)題的答案 ， 并因此奠定了圖論的基礎(chǔ) ， Euler把 A、B、 C、 D四塊陸地分別收縮成四個(gè)頂點(diǎn) ， 把橋表示成連接對(duì)應(yīng)頂點(diǎn)之間的邊 ， 問(wèn)題轉(zhuǎn)化為從任意一點(diǎn)出發(fā) ， 能不能經(jīng)過(guò)各邊一次且僅一次 ，最后返回該點(diǎn) 。 這就是著名的 Euler問(wèn)題 。 管 理 運(yùn) 籌 學(xué) A C B D 管 理 運(yùn) 籌 學(xué) 有 7個(gè)人圍桌而坐 ， 如果要求每次相鄰的人都與以前完全不同 ， 試問(wèn)不同的就座方案共有多少種 ？ 用頂點(diǎn)表示人 ， 用邊表示兩者相鄰 ， 因?yàn)樽畛跞魏蝺蓚€(gè)人都允許相鄰 ， 所以任何兩點(diǎn)都可以有邊相連 。 管 理 運(yùn) 籌 學(xué) 1 2 3 7 6 4 5 管 理 運(yùn) 籌 學(xué) 假定第一次就座方案是 （ 1， 2， 3， 4， 5， 6， 7， 1） ，那么第二次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 。 管 理 運(yùn) 籌 學(xué) 1 2 3 7 6 4 5 管 理 運(yùn) 籌 學(xué) 1 2 3 7 6 4 5 管 理 運(yùn) 籌 學(xué) 假定第二次就座方案是 （ 1， 3， 5， 7， 2， 4， 6， 1） ，那么第三次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 。 管 理 運(yùn) 籌 學(xué) 1 2 3 7 6 4 5 管 理 運(yùn) 籌 學(xué) 1 2 3 7 6 4 5 管 理 運(yùn) 籌 學(xué) 假定第三次就座方案是 （ 1， 4， 7， 3， 6， 2， 5， 1） ，那么第四次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰 ， 只能從圖中刪去這些邊 ， 只留下 7點(diǎn)孤立點(diǎn) ， 所以該問(wèn)題只有三個(gè)就座方案 。 管 理 運(yùn) 籌 學(xué) 1 2 3 7 6 4 5 管 理 運(yùn) 籌 學(xué) 1 2 3 7 6 4 5 管 理 運(yùn) 籌 學(xué) 哈密頓 （ Hamilton） 回路是十九世紀(jì)英國(guó)數(shù)學(xué)家哈密頓提出 ， 給出一個(gè)正 12面體圖形 ， 共有 20個(gè)頂點(diǎn)表示 20個(gè)城市 ， 要求從某個(gè)城市出發(fā)沿著棱線尋找一條經(jīng)過(guò)每個(gè)城市一次而且僅一次 ， 最后回到原處的周游世界線路 （ 并不要求經(jīng)過(guò)每條邊 ） 。 管 理 運(yùn) 籌 學(xué) 管 理 運(yùn) 籌 學(xué) 22 167。 1 圖與網(wǎng)絡(luò)的基本概念 圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。 例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)表示，下圖就是一個(gè)表示這種關(guān)系的圖。 (v1) 趙 (v2)錢(qián) (v3)孫 (v4)李 (v5) 周 (v6)吳 (v7)陳 e2 e1 e3 e4 e5 管 理 運(yùn) 籌 學(xué) 23 167。 1 圖與網(wǎng)絡(luò)的基本概念 當(dāng)然圖論不僅僅是要描述對(duì)象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的，如對(duì)趙等七人的相互認(rèn)識(shí)關(guān)系我們也可以表示如下，可見(jiàn)圖論中的圖與幾何圖、工程圖是不一樣的。 (v1) 趙 (v2)錢(qián) 孫 (v3) 李 (v4) 周 (v5) 吳 (v6) 陳 (v7) e2 e1 e3 e4 e5 管 理 運(yùn) 籌 學(xué) 24 167。 1 圖與網(wǎng)絡(luò)的基本概念 a1 a2 a3 a4 a14 a7 a8 a9 a6 a5 a10 a12 a11 a13 a15 (v1) 趙 (v2)錢(qián) (v3)孫 (v4)李 (v5) 周 (v6)吳 (v7)陳 如果我們把上面例子中的“相互認(rèn)識(shí)”關(guān)系改為“認(rèn)識(shí)” 的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫(huà)他們之間的關(guān)系了，這時(shí)我們引入一個(gè)帶箭頭的聯(lián)線，稱(chēng)為弧。下圖就是一個(gè)反映這七人“認(rèn)識(shí)”關(guān)系的圖。相互認(rèn)識(shí)用兩條反向的弧表示。 管 理 運(yùn) 籌 學(xué) 25 167。 1 圖與網(wǎng)絡(luò)的基本概念 ? 無(wú)向圖： 由點(diǎn)和邊構(gòu)成的圖，記作 G=（ V， E）。 ? 有向圖： 由點(diǎn)和弧構(gòu)成的圖，記作 D=（ V， A）。 ? 連通圖 ： 對(duì)無(wú)向圖 G，若任何兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則 G為連通圖。 ? 回路： 若路的第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)相同，則該路為回路。 ? 賦權(quán)圖： 對(duì)一個(gè)無(wú)向圖 G的每一條邊 (vi,vj)，相應(yīng)地有一個(gè)數(shù) wij，則稱(chēng)圖 G為賦權(quán)圖， wij稱(chēng)為邊 (vi,vj)上的權(quán)。 ? 網(wǎng)絡(luò)： 在賦權(quán)的有向圖 D中指定一點(diǎn)，稱(chēng)為發(fā)點(diǎn)，指定另一點(diǎn)稱(chēng)為收點(diǎn)，其它點(diǎn)稱(chēng)為中間點(diǎn)，并把 D中的每一條弧的賦權(quán)數(shù)稱(chēng)為弧的容量， D就稱(chēng)為網(wǎng)絡(luò)。 管 理 運(yùn) 籌 學(xué) 26 167。 2 最短路問(wèn)題 ? 最短路問(wèn)題：對(duì)一個(gè)賦權(quán)的有向圖 D中的指定的兩個(gè)點(diǎn) Vs和 Vt找到一條從 Vs 到 Vt 的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱(chēng)之為從 Vs到 Vt的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱(chēng)為從 Vs到 Vt的距離。 解最短路的 Dijkstra算法 (雙標(biāo)號(hào)法） 步驟： V1以標(biāo)號(hào) (0,s) I，沒(méi)標(biāo)號(hào)的點(diǎn)的集合 J以及弧的集合 3. 如果上述弧的集合是空集，則計(jì)算結(jié)束。如果 vt已標(biāo)號(hào)（ lt,kt），則 vs到 vt的距離為 lt，而從 vs到 vt的最短路徑，則可以從 kt 反向追蹤到起點(diǎn)vs 而得到。如果 vt 未標(biāo)號(hào)，則可以斷言不存在從 vs到 vt的有向路。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。 4. 對(duì)上述弧的集合中的每一條弧，計(jì)算 sij=li+cij 。在所有的 sij中，找到其值為最小的弧。不妨設(shè)此弧為（ Vc,Vd），則給此弧的終點(diǎn)以雙標(biāo)號(hào)（ scd,c） ,返回步驟 2。 { ( , ) | , }i j i jv v v I v J??管 理 運(yùn) 籌 學(xué) 最短路問(wèn)題是網(wǎng)絡(luò)分析中的一個(gè)基本問(wèn)題，它不僅可以直接應(yīng)用于于解決生產(chǎn)實(shí)際的許多問(wèn)題，若管道鋪設(shè)、線路安排、廠區(qū)布局等，而且經(jīng)常被作為一個(gè)基本工具，用于解決其它的優(yōu)化問(wèn)題 . 定義 給定一個(gè)賦權(quán)有向圖 D = (V,A)，記 D中每一條弧 上的權(quán)為為 。給定 D中一個(gè)起點(diǎn) 和 終點(diǎn)，設(shè) P是 D中從 到 的一條路 .則定義路 P的權(quán)是 P中所有弧的權(quán)之和 .記為 ，即 又若 P*是 D圖中 到 的一條路，且滿(mǎn)足 則稱(chēng) P*為從 到 的最短路。 ija ?? ?)(sv tvsv tv)(P? ???PvvijjiP),()( ??sv tv)(m i n*)( PP ?? ?tvsv管 理 運(yùn) 籌 學(xué) 28 最短路問(wèn)題 網(wǎng)絡(luò)： 規(guī)定起點(diǎn)、中間點(diǎn)和終點(diǎn)的賦權(quán)圖； 有向網(wǎng)絡(luò)： 網(wǎng)絡(luò)中每個(gè)邊都是有向邊； 無(wú)向網(wǎng)絡(luò)： 網(wǎng)絡(luò)中每個(gè)邊都是無(wú)向邊； 混合網(wǎng)絡(luò)： 網(wǎng)絡(luò)中既有有向邊，又有無(wú)向邊； 網(wǎng)絡(luò)最短路線問(wèn)題： 尋找網(wǎng)絡(luò)中從起點(diǎn) v1 到終點(diǎn) vn 的最短路線。 Min L(?) = ? lij ?為從 v1 到 vn 的通路； lij?? 其中， lij為從 vi 到 vj 的一步距離。 管 理 運(yùn) 籌 學(xué) 29 ? 結(jié)合例題學(xué)習(xí)、掌握求最短路的狄克斯拉、海斯和福德三個(gè)方法： 狄克斯拉方法：適用于滿(mǎn)足所有權(quán)系數(shù)大于等于 0（ lij≥0）的網(wǎng)絡(luò)最短路問(wèn)題，能求出起點(diǎn) v1 到所有其它點(diǎn) vj 的最短距離； 海斯方法：基本思想是在最短路線上任意兩點(diǎn)間路線也是最短路線。利用 vi 到 vj 的一步距離求出 vi 到 vj 的兩步距離再求出 vi 到 vj 的四步距離 …… 經(jīng)有限次迭代可求出 vi 到 vj 的最短距離； 福德方法：適用于有負(fù)權(quán)系數(shù)，但無(wú)負(fù)回路的有向或無(wú)向網(wǎng)絡(luò)的最短路問(wèn)題，能求出起點(diǎn) v1 到所有其它點(diǎn) vj 的最短距離。 管 理 運(yùn) 籌 學(xué) 30 167。 2 最短路問(wèn)題 例 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èn)題： 尋找網(wǎng)絡(luò)中從起點(diǎn) v1 到終點(diǎn) vn 的最短路線。 標(biāo)注 vk(lk， k1) 定義： k=1時(shí)， l1=0， k1=s， v1(0， s） min(? lij ) Min L(?) = ? lij ?為從 v1 到 vn 的通路； lij?? 其中， lij為從 vi 到 vj 的一步距離。 最短路問(wèn)題 管 理 運(yùn) 籌 學(xué) 32 167。