運籌學ch7網(wǎng)絡(luò)模型

運籌學 Chapter7網(wǎng)絡(luò)模Network最小(支撐)樹問題Minimal(Spanning)Tree最短路問 ShortestPath最大流問 alFlow旅行售貨員與中國郵路問TravelingSalesmanandChinaCarrier

25825

1

圖運籌學中研究的圖具有下列特征用點表示研究對象，用邊（有方向或無方向）象之間某種關(guān)系強調(diào)點與點之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀?？梢源韮牲c之間的距離、費用、利潤、時間、容量等不同含義如圖7－1所示，點集合記

25 25邊用[vi,vj]表示或簡記為[i，j]，集合記

圖邊上的數(shù)字稱為權(quán)，記為w[vi,vj]、w[i，j]或wij，集合記 連通的賦權(quán)圖稱為網(wǎng)絡(luò)圖，記幾個基本概念

55212 6圖定理1、 鏈圈最小(支撐)樹問Minimal(Spanning)Tree樹的概

最小樹問Minimaltree

(。組織機構(gòu)、家譜、學科分支、因特網(wǎng)絡(luò)、通訊網(wǎng)絡(luò)及高壓線路網(wǎng)絡(luò)等都能表達成一個樹圖?？梢宰C明一棵樹的邊數(shù)等于點數(shù)減在通圖G中，

4

v5 (SpanningTree圖7－2是圖7－1部分樹

圖最小部分

最小樹問Minimaltree

最小部分樹可以直接用作圖的方法求解，常用的有破圈法加邊法破圈法：任取一最小樹問Minimaltree【例7.1】用破圈法求圖7－1的最小樹

5 2 圖7－4就是圖7－1當一個圈中有多個相同的最長邊時，不能同時都去掉，只能去掉其中任意一條邊。最小部分樹有可能不唯一，但最小樹的長度相同最小樹問Minimaltree

加邊法：取圖G的n個孤立點｛v1，v2，…vn}作為一個支撐 54

5 5

圖

45v 45v6

28 28Min在圖7－5中，如果添加邊[v1,v2]就形成圈｛v1,v2,v4｝，這時就應(yīng)避開添加邊[v1v2]，添加下一條最短邊[v3v6]。破圈法和加邊最小樹問Minimaltree

樹、支撐樹、最小支撐樹的概掌握求最小樹的方法破圈加邊作業(yè)：P281T10.4（b）、下一節(jié)：最短路問最短路問ShortestPath最短路問ShortestPath

最短路問題的網(wǎng)絡(luò)模最短路問題，就是從給定的網(wǎng)絡(luò)圖中找出一點到各點或任意點之間距離最短的一條最短路問題在實際中具有廣泛的應(yīng)用，如管道鋪設(shè)、線路選擇等問題，還有些如設(shè)備更新、投資等問題也可以歸結(jié)為求最短路問題求最短路有兩種算法—是求從某一點至其它各點之間最短離的狄克斯屈拉(Dijkstra)算另一種是求網(wǎng)絡(luò)圖上任意兩點之間最短路的 矩陣算最短路問ShortestPath

【例7.3】圖7－6中的權(quán)ij表示i到j(luò)的距離（費用、時間），從1修一條公路或架設(shè)一條高壓線到7最短，建立該問題的網(wǎng)絡(luò)數(shù)學模型。 圖最短路問ShortestPath

【解】設(shè)xij為選擇弧(i，j)的狀態(tài)變量，選擇弧(i，j)時xij＝1，不min

(i,j

cij

x14

0

2, ,(i,j

(k,i

x67x

j)有向圖的狄克斯屈拉(Dijkstra)標號算

開始節(jié)點標標記[P,0],其余為臨時標記[T使之成為標志。L為兩節(jié)點間距離，1表示始 保持、新設(shè)或更改這些節(jié)點的標志為[最短距離， 點標號k[Dii

j從從i-j例例：狄克斯屈方法求最短

[T,-8

[T,-

[T,-

[T,- 6[T,- [T,- 最短路問ShortestPath有向圖的狄克斯屈拉(Dijkstra)標號算法

先求有向圖的最短路，設(shè)網(wǎng)絡(luò)圖的起點是vs,終點是vt,以vi為起點標號：b(j起點vs到點vj的最短路長；步驟：(1)令起點的標號；b(s)＝0找出所有vi已標號vj未標號的弧集合B={(i，j)}，如果這樣計算集合B中弧k(i，j)=b(i)+cij的標

j

j)|

最短路問ShortestPath

【例7.4】用Dijkstra算法求圖7－6所示v1到v7的最短路及最短路 96 9690 10 90

⑤ 圖v1到v7的最短路為：p17=｛v1v2v3v5v7｝，最短路長為7.2最短路問ShortestPath

到該點的最短路到任意點的最短路線，如果某個點j不能標號，說明不可達j。無向圖最短路的求無向圖最短路的求法只將上述步驟（2）點標號：b(i起點vs到點vj的最短路邊標號：k(i，j)=b(i)+cij，找出所有一端vi已標號另一端vj未標號的邊集合B={[i，j]}如計算集合B中邊標號選一個點標號返回到第(2)

j

j]|

7.2最短路問ShortestPath

【例7.5】求圖7-10所示v到各點的最短路及最短距 24 ⑧18 66圖7-所有點都已標號，點上的標號就是到該點的最短距離，最短路線就是紅色的鏈。7.2最短路問ShortestPath最短路的Floyd算Floyd算法基本步驟

寫出vi一步到達vj的距離矩 ，L1也是一步到達最短距離矩陣。如果vi與vj之間沒有邊關(guān)聯(lián)，則令計算二步最短距離矩陣。設(shè)vi到vj經(jīng)過一個中間點vr兩步到vj，則vi到vj的最短距離

c最短距離矩陣記

計算k步最短距離矩陣。設(shè)vi經(jīng)過中間點vr到達vj，vi經(jīng)過步到達點

的最短距離

(k

經(jīng)過k－1步到達點

的最LL(L(1)1L(L(2)2

，則vi經(jīng)k步到達vj的最短距離7.2最短路問ShortestPath

最短距離矩陣記

LL(L(k)k比較矩陣Lk與Lk－1，當Lk＝Lk－1離矩陣Lk設(shè)圖的點數(shù)為n并且cij≥0，迭代次數(shù)k由式(6.3)估計得到2k1－1n22kkk1lg(n1)7.2最短路問ShortestPath

【例7.6】圖7-14是一張8個城市的鐵路交通圖，鐵路部門要制一張兩兩城市間的距離表。這個問題實際就是求任意兩點間的短路問題①【解】(1)依據(jù)圖7-14,寫出 表L1。見表7.1所示。本

算到

，因此計

圖7-7.2最短路問ShortestPath表7-1最短距離

06∞5∞4∞∞60328∞∞∞∞30∞7∞∞52∞093∞∞8790∞64∞∞∞02∞∞∞∞320∞∞∞6∞07.2最短路問ShortestPath表7-2最短距離表

069546∞60328593057∞52509534∞50265320∞0 minmin5計算說明：L(2)ij minmin57.2最短路問ShortestPath表7-3最短距離表

06954660328759305785250953475026583200表7-3計算示例

等于表6-2中第i行與第j列對應(yīng)元素相加取最小值。例如v3經(jīng)過三步（最多三個中間點4條邊）到達v6的最短距離

minL(2) min9 7.2最短路問ShortestPath【例7.7】求圖7－15

【解】圖7－15是一個混合圖，有3條邊的權(quán)是負數(shù),無方向。依據(jù)圖7－15,寫出任意兩點間一步到達距離表L1。中第一列的點表示弧的起點，第一行的點表示弧的終點，無方向的邊表明可以互達，見表4所示。計算過程見表～7。 775 圖7.2最短路問ShortestPath表7-4一步到達距離表

05∞∞4∞∞∞04∞∞∞∞407∞∞24∞∞0∞7∞∞∞0∞∞∞∞5∞08∞∞2∞∞∞07.2最短路問ShortestPath表7-7最短距離表

0593419204-6356402724990857-4720-59508862490經(jīng)計算4＝5，L是最優(yōu)表。表77不是對稱表，i到j(luò)與j到的7.3失效。7.2.4最短路應(yīng)用舉

7.2最短路問ShortestPath

【例】設(shè)備更新問題。企業(yè)在使用某設(shè)備時，每年年初可購置新設(shè)備，也可以使用一年或幾年后賣掉重新購置新設(shè)備。已知年年初購置新設(shè)備的價格分別為2.56、萬元。設(shè)備使用了1～4年后設(shè)備的殘值分別為2、1.6、1.3和1.萬元，使用時間在～年內(nèi)的維修保養(yǎng)費用分別為3、2.0萬元。試確定一個設(shè)備更新策略，在下例兩種情形下4年的設(shè)備購置和 總費用最小。第4第4 7.2最短路問ShortestPath

①

6

(1,2,3,4)-

-⑤

-第一第二第三第四圖網(wǎng)絡(luò)圖7－16說明：如圖中點(1,)表示第1年購置設(shè)備使用兩年到第3年年初更新購置新設(shè)備，這時有2種更新方案，使用1年到第4年年初、使用2年到第5年年初,更新方案用弧表示，點（1,2,3）表示第1年購置設(shè)備使用一年到第二年年初又更新，使用一年到第三年初再更新，這時仍然有種更新方案，使用1年到第4年年初和使用2年到第5年年初。7.2最短路問ShortestPath

點（）和點（3）不能合并成一個點，雖然都是第三年(1,3的殘值等于使用了兩年，點1,2,3的殘值等于2使用了一年。點（1,3）到點（1,3,4）的總費用第三年的購置費＋第一年 費－設(shè)備使用兩年后的殘點（1,3）到點⑤的總費用 ＝2.8+0.3+0.8－1.6－1.6=0.7費用表 P135表7-8①

6

(1,2,3,4)-

-

⑤

-第一第二第三第四圖7.2最短路問ShortestPath

第四年末處理設(shè)備：求點①到點⑤的最短路。用a算法得到最短路線為：①→(1,2)→(1,2,3)→⑤，最短路長為4年總費用最小的設(shè)備更新方案是：第年購置設(shè)備使用1年，第2年更新設(shè)備使用1年后賣掉，第3年購置設(shè)備使用2年到第4年年末，年的總費用為4萬元。第四年末不處理設(shè)備：將圖7－16第4年的數(shù)據(jù)換成表6-8后一列，求點①到點⑤的最短路。最短路線為①→(1,2)→(1,2,3)→⑤，最短路長為5.6，即總費用為5.6更新方案與第一種情形相同7.2最短路問ShortestPath

LLij【例】服務(wù)網(wǎng)點設(shè)置問題。以圖－為例，現(xiàn)提出這樣一個問題，在交通網(wǎng)絡(luò)中建立一個快速反應(yīng)中心，應(yīng)選擇哪一個城市最好。類似地，在一個網(wǎng)絡(luò)中設(shè)置一所學校、醫(yī)院、消防站、購物中心，還有廠址選擇、總部選址、公司銷售中心選址等問題都屬于最佳服務(wù)網(wǎng)點設(shè)置問題?！窘狻繉τ诓煌膯栴}，尋求最佳服務(wù)點有不同的標準。像第一步：利用Floyd算法求出任意兩點之間的最短距離（表7－3）第二步：計算最短距離表中每行的最大距離的最小值，7.2最短路問ShortestPath

例7.6計算的結(jié)果，對表7－3表7－9倒數(shù)第二列。表Max總運06954660328759305785250953475026583200產(chǎn)表7－9中倒數(shù)第二列最小值為12，位于第7行，則7為網(wǎng)絡(luò)的中心，最佳服務(wù)點應(yīng)設(shè)置在。7.2最短路問ShortestPath

如果每個點還有一個權(quán)數(shù)，例如一個網(wǎng)點的人數(shù)、需要運送的物質(zhì)數(shù)量、產(chǎn)量等，這時采用“使總運量最小”為標準，計算方法是將上述第二步的最大距離改為總運量，總運量的最小值對應(yīng)的點就是最佳服務(wù)點。表6－9中最后一行是點j的產(chǎn)量，將各行的最小距離分別乘以產(chǎn)量求和得到總運量，例如，＋0＋1×＝3220，見表6－9最后一列，最小運量為2450置在4。7.2最短路問ShortestPath

最短路的概念及應(yīng)用有向圖、無向圖一點到各點最短路的Dijkstra算任意兩點最短路的Floyd算本節(jié)介紹了兩個應(yīng)用：設(shè)備更新問題和最佳服務(wù)點設(shè)置作業(yè) T下一節(jié)：最大流問7.3最大流問alFlow 基本概

最大流問alFlow

node），定義了一個收點v7，稱為匯（sink，demandnode），其余點v2，v3，…，v6為中間點，稱為轉(zhuǎn)運點(transshipmentnodes)。如果 4 36 圖7.3最大流問alFlow設(shè)cij為?。╥，j）的容量，fij為?。╥，j）的流量

13121312 mj所有中間點m所有弧單位時間內(nèi)的實際通過量，流量的集合f={fij}稱為網(wǎng)絡(luò)的流。發(fā)到收點的總流量記為v=val(f)，v也是網(wǎng)絡(luò)的流量圖7－18最大流問題的線性規(guī)劃數(shù)學模型7.3最大流問alFlow滿足下例3個條件的流fij的集ffij}稱為可行

)0

所有弧(ij)

v

發(fā)點vs流出的總流量等于流入收點vt的總流7.3最大流問alFlow

鏈：從發(fā)點到收點的一條路線（弧的方向不一定都同向）從發(fā)點到收點的方向規(guī)定為鏈的方向前向?。号c鏈的方向相同的弧稱為前向弧。后向?。号c鏈的方向相反的弧稱為后向弧。增廣鏈:設(shè)f是一個可行流，如果存在一條從vs到vt的鏈，滿足所有前向弧上前向所有后向弧上前向

4則該鏈稱為增廣容容

4

6 流（5）流③

9后向后向7.3最大流問alFlow7.3.2Ford-Fulkerson標號算法第一步：找出第一個可行流，例如所有弧的流量fij第二步：對點進行標號找一條增廣鏈（1）發(fā)點標號

（2）選一個點vi已標號并且另一端未標號的弧沿著某條鏈向收如果弧的方向向前（前向?。┎⑶矣衒ij<cij，則vj標號如果弧的方向指向vi（后向?。┎⑶矣衒ji>0，則vj標號i的標號反向跟蹤得到一條增廣鏈。當收點不能得到標號時，說明不存在增廣鏈，計算結(jié)束。7.3最大流問alFlow

第三步：調(diào)整流求增廣鏈上點vi的標號的最小值j調(diào)整流j

fij 1(i,j)(i,j)(i,j)得到新的可行流f1，去掉所有標號，返回標號尋找增廣鏈，直到收點不能標號為【定理7.1】可行流f是最大流的充分必要條件是不存在發(fā)點到7.3最大流問alFlow

【例7.10】求圖7－18發(fā)點v1到收點v7的最大流及最大流【解】給定初始可行流，見圖7-8①

②③

4④

⑤3⑥

⑦圖7.3最大流問alFlow

cij=fij，vcij=fij，v4、v5不能標

,v標號2（①

8

4

（③，③

3⑥

⑦（④后向弧f32>0,（

v3標號

圖增廣鏈μ＝{(1,2)，(3,2)，(3,4)，(4,7)(4,7)},μ－={(3，2)}，調(diào)整量為增廣鏈上點標號的最小7.3最大流問alFlow

調(diào)整后的可行流8①

②③

4④

⑤3⑥

⑦圖第二輪標號（③②

7.3最大流問Cij=fij，Cij=fij，v4、v5不能標號，返回到⑤

8

4

（④①

（③ ）

3⑥

圖增廣鏈μ＝μ＋＝{(1,3)，(3,4)，(4,7)}，調(diào)整量7.3最大流問alFlow

調(diào)整后得到可行流②

⑤8①

③

④

3⑥

⑦圖7.3最大流問alFlow

第三輪標號②

⑤8

4

①

（⑥,1） ）

3⑥

（（① （③圖增廣鏈μ＝μ＋＝{(1,3)，(3,6)，(6,4)，(4,7)}，調(diào)整量調(diào)整后得到可行流②

7.3最大流問alFlow⑤

8①

③

④

3⑥

⑦圖第四輪標號（③

7.3最大流問alFlowCij=fij，v4、v5

8①

④

⑦）

3⑥

（①

Cij=fij，v4、v6圖v7得不到標號，不存在v1到v7的增廣鏈，圖7-22所示的可行是最大流，最大流量7.3最大流問alFlow截集將圖G＝（V，E）的點

V稱為一個截集，截集中所有弧的容量之和稱為截集的截量下圖所示的截集

6

62244466 66171123 23

3932⑤27.3最大流問alFlow又如下圖所示的(V1,V1)(2,43,4

截量C(V1,V1666①

4269 6 617101030 3012 12③上圖所示的截集 ③

1

所有截量中此截量最小且等于最大流量，此截集稱為最小截集【定理】最大流7.3.4最小費用

7.3最大流問alFlow

最小費用流問題最小費用最大流問題。設(shè)?。╥j）的單位流量費用為dij≥，弧的容量為ij設(shè)可行流的一條增廣鏈為μ，稱d()

dij

dij為增廣鏈μ的費用。第一個求和式是增廣鏈中d(μ最小的增廣鏈稱為最小費用增廣鏈。圖6－2是一個 網(wǎng)絡(luò)圖，將工廠1，2及的物質(zhì)數(shù)量限運往6，4和5是中轉(zhuǎn)點，弧上的數(shù)字為（ijij。7.3最大流問alFlow

①

④

費最小的方案；屬于最小費⑥(2)制定使運量最大并且總運費②

⑤

圖

④

⑤

圖設(shè)給定的流量為v

7.3最大流問alFlow

最小費用流的標號算法步驟如下第1步：取初始流量為零的可行流(0＝0，令網(wǎng)絡(luò)中所有弧的權(quán)等于dij得到一個賦權(quán)圖，用ka算法求出最短路，這條最短路就是初始最小費用增廣鏈μ。第2步最大流算法一樣，前向弧上令θjij－ij，后向弧上令θj＝ij，調(diào)整量為θ=inθj。調(diào)整后得到最小費用流k)，流量為k＝k－1＋，當k＝時計算結(jié)束，否則轉(zhuǎn)第步繼續(xù)計算。第3步：作賦權(quán)圖D并尋找最小費用增廣鏈7.3最大流問alFlow

fijcij c,0 (1)對可行流f(k－1)的最小費用增廣鏈上的弧（i，j）第一種情形：當弧（i，j）上的流量滿足0<fij<cij時，在點vi與vj間添加一條方向相反的弧（j，i），權(quán)為（－dij）第二種情形：當弧（，）上的流量滿足ijij時將弧（i，j）反向變?yōu)椋╦，i）權(quán)為（－bij）。不在最小費用增廣鏈上的弧不作任何變動，得到一個賦權(quán)網(wǎng)絡(luò)圖。求賦權(quán)圖這條最短路就是k步。賦權(quán)圖的所 非負時，可用a算法求最短路，存在負權(quán)時用loyd算法。如果賦權(quán)圖不存在從發(fā)點到收點的最短路，說明k－已是最大流量，不存在流量等于的流，計算結(jié)束。7.3最大流問alFlow

【例7.11】對圖7－28，制定一個運量v＝15最小 方案【解】令所有弧的流量等于零，得到初始可行流流量v(0)＝0，總運費d(f(0))=0 ⑤ f(0)，賦權(quán)圖圖最小費用增廣鏈μ1：s→①→④→⑥,見圖7.3最大流問alFlow

調(diào)整量θ＝4，對f(0)＝{0}進行調(diào)整得到f(1)，括號（）內(nèi)的數(shù)如圖7－29(b)①

④

⑥圖中：（cij，dijfij

③

f圖

⑤7.3最大流問alFlow

1＝，沒有得到最小費用流。在圖b中，弧s和(4,6滿足條件0<ij<，添加兩條邊(1s和(6,4，權(quán)分別為“0”和“－”，邊1s可以去掉，弧1,4上有ij＝i說明已飽和，將弧(1,4反向變?yōu)?4,1，權(quán)為“－2”，如圖7－29。 5 06 f(1)，賦權(quán)圖

④3⑥⑤圖7.3最大流問alFlow

用Floyd算法得到最小費用增廣鏈μ2：s→②→④→⑥，調(diào)量θ＝3，調(diào)整后得到最小費用流f(2)，流量v(2)＝7如圖7－29(d)①s(6,0)(3)

④⑥

③

⑤圖中：（cij，dijfij

f圖7.3最大流問alFlow

2＝7<1，對最小費用增廣鏈μ上的弧進行調(diào)整，在圖6－中，弧和4,6滿足條件ij<ij，添加兩條邊2,s和(6,4，權(quán)分別為“0”和“－3”，邊(2,s可以去掉，弧(6,4已經(jīng)存在，弧2,4上有i＝ij說明已飽和，將弧2,反向變?yōu)?,2，權(quán)為“－5”，如圖7－29。 06

④3⑥⑤f(2)，賦權(quán)圖圖7.3最大流問alFlow

用Floyd算法得到最小費用增廣鏈μ3：s→③→④→量θ＝1，調(diào)整后得到最小費用流f(3)，流量v(3)＝8如圖7－29(f)①

④ss

⑥

f圖

⑤

7.3最大流問alFlow

s

④3⑥⑤

類似地，得到圖

f(3)，賦權(quán)圖圖

ss

④⑥最小費用增廣鏈⑤→⑥，調(diào)整量

③

⑤＝v(4)＝10。見圖

f圖

7.3最大流問到圖7－29(i),

④3⑥⑤①

圖7－29(i)f(4)，賦權(quán)圖

最小最小費用增廣鏈ss

④⑥

③

⑤圖 f7.3最大流問alFlow

求最小費用最大流。對圖7－29(i)的最小費用增廣鏈μ5，取整量θ＝6對流量調(diào)整，得到圖7－30(a)及賦權(quán)圖①

④ss

⑥

③

⑤ f圖7.3最大流問alFlow

圖7－30(b)的最小費用增廣鏈①0 0③

4f(5)，賦權(quán)圖

④3⑥⑤圖7.3最大流問alFlow

調(diào)整量θ＝1，流量v(6)＝17，最小費用流為f(6)，見圖7－30(c)①

④ss

⑥

③

f圖7.3最大流問alFlow

賦權(quán)圖見圖7－（）。圖－不存在從發(fā)點到6的最短路，則圖7－30(的流就是最小費用最大流，最大流量=，最小的總運費為d4×4＋4×6＋5×3＋4×1＋6×1＋3×2＋3×8＋9×9＝176

④3⑥

⑤圖

f(6)，賦權(quán)圖3個工廠分別運送10、4及3個單位物質(zhì)到，總運量為17，運費為7.3.5最大流應(yīng)用舉

7.3最大流問alFlow

1.1.【例7.12】某公司需要招聘5個專業(yè)的畢業(yè)生各一個，通過本人報名和篩選，公司最后認為有人都達到錄取條件。這人所學專業(yè)見表710表中打“”表示該生所學專業(yè)。公司應(yīng)招聘哪幾位畢業(yè)生，如何分配他們的工作表7-畢業(yè)A.B.工程管C.管理信D.計算E.企業(yè)管1√√2√√3√√4√√5√√6√√7.3最大流問alFlow

【解】畫出一個二分圖，虛設(shè)一個發(fā)點和一收點，每條弧上容量等于，問題為求發(fā)點到收點的最大流，求解結(jié)果之一見圖7－32。公司錄取第2～6號畢業(yè)生，安排的工作依次為管理信息、企業(yè)管理市場 、程理計機。①(1)

(1)

D(1)⑥

E圖7.3最大流問alFlow

過80人，表7-工需要勞動力（人月A.通5～7B人行天6～7C新建道5～8D道路維8【解】將工程計劃用網(wǎng)絡(luò)圖6－表示。設(shè)點5、、、分別表示5～8月份，i、i、i、i表示工程在第個月內(nèi)完成的部分，用弧表示某月完成某項工程的狀態(tài)，弧的容量為勞動力限制。就是求圖7－33從發(fā)點到收點的最大流問題。7.3最大流問alFlow

⑤

8080

5

A

B6B80

80(80)

(120)

80

80

80

80

8

D80圖6.3最大流問alFlow

odulkn標號算法求解得到圖－3，括號內(nèi)的數(shù)字為弧的流量。每個月的勞動力分配見表71。5月份有剩余勞動力人，4項工程恰好按期完成表7-月投入勞動項目A(人項目B(人項目C(人項目D(人5678合計(人最大流問alFlow

最大流的概念：容量、流量、可行流、最大流、前向弧、后向弧、增廣鏈、截集、截量、最小截量與最大流量的關(guān)系、最小費用流、最小費用最大流。有向圖、無向圖最大流的Ford-Fulkerson標號算最小費用流、最小費用最大流的算本節(jié)介紹了兩個應(yīng)用：最大匹配問題和勞動力合理配置問作業(yè) T下一節(jié)：旅行售貨員與中國郵路問7.4旅行售貨員與中國郵路問TravelingSalesmanandChinaCarrier旅行售貨員與中國郵路問

【例7.14】某電動汽車公司與學校合作，擬定在校園內(nèi)開通無污染無噪音的“綠交”線圖4是某大學教學樓和學生宿舍樓的分布圖，其中、之間是兩條單向通道，邊上的數(shù)字為汽車通過兩點的常間分）電汽公司何設(shè)計一條路線，使汽車通過每一處教學樓和宿舍樓一次后總時間最少。 A【解】求解過程電動汽車公司的行車路線

A→B→F→E→D→C→A，汽車在園行駛一圈需要15.6

D C

3

7.4旅行售貨員與中國郵路問中國郵路問題(Chinacarrier【例7.15】求解圖7－35（a）

1541548142圖7.4旅行售貨員與中國郵路問【解】最優(yōu)解如圖7-

4

55 12 12圖圖7-36為最 回路，重復經(jīng)過了[1，2]和[6，7]兩條7.4旅行售貨員與中國郵路問

Hamilton回路、Euler回路。旅行售貨員問中國郵路問作業(yè):P283TofChapter習題6.4解

1

5

3

7

圖習題6.4解

1

vv9

圖習題

習題6.4解4

2

v6

0圖習題6.4解

1

3

圖習題

6863 3

G圖習題習題6.6(a)求A到H、I的最短路及最短路【解】用Dijkstra算

8 8

800

8666

92

95 95

5

13圖習題習題6.6(b)求A到H、I的最短路及最短路

B8A C5D

E4

9 圖習題

習題6.6(b)求A到H、I的最短路及最短路【解】用Dijkstra算88 8

66

11

060

6 3

2

5 5

1399圖習題

習題6.7已知某設(shè)備可繼續(xù)使用5年，也可以在每年年末賣掉重新購置新設(shè)備。已知5年年初購置新設(shè)備的價格分別為3.5、3.8、4.0、4.2和4.5萬元。使用時間在1～5年內(nèi) 費用分別為0.40.9、1.4、2.3和3萬元。試確定一個的設(shè)備更新策略，5年的設(shè)備購置和 總費用最小

00

⑤

⑥

8.8

2 3 51 1 5

6 5圖習題6.10

6.10如圖6－44，（1）求v1到v10求最小割集和最小割 5 圖習題6.10

【解】給出一個

5

6

5

圖習題6.10

第一輪標號：得到一條增廣鏈，調(diào)整量等于5，如下圖所9 5

5