運(yùn)籌學(xué)

Operations

Research

Chapter6網(wǎng)絡(luò)模型NetworkModeling6.1最小(支撐)樹問題Minimal(Spanning)TreeProblem6.2最短路問題ShortestPathProblem

6.3最大流問題MaximalFlowProblem6.4旅行售貨員與中國郵路問題

TravelingSalesmanandChinaCarrierProblem

5v1v2v3v4v5v6843752618圖6－1運(yùn)籌學(xué)中研究的圖具有下列特征：（1）用點(diǎn)表示研究對象，用邊（有方向或無方向）表示對象之間某種關(guān)系。（2）強(qiáng)調(diào)點(diǎn)與點(diǎn)之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀。（3）每條邊上都賦有一個(gè)權(quán)，其圖稱為賦權(quán)圖。實(shí)際中權(quán)可以代表兩點(diǎn)之間的距離、費(fèi)用、利潤、時(shí)間、容量等不同的含義。（4）建立一個(gè)網(wǎng)絡(luò)模型，求最大值或最小值。邊用[vi,vj]表示或簡記為[i，j]，集合記為如圖6－1所示，點(diǎn)集合記為邊上的數(shù)字稱為權(quán)，記為w[vi,vj]、w[i，j]或wij，集合記為連通的賦權(quán)圖稱為網(wǎng)絡(luò)圖，記為

G＝｛V，E，W｝5v1v2v3v4v5v6843752618圖6－16.1最小(支撐)樹問題

Minimal(Spanning)TreeProblem6.1.1樹的概念一個(gè)無圈并且連通的無向圖稱為樹圖或簡稱樹(Tree)。組織機(jī)構(gòu)、家譜、學(xué)科分支、因特網(wǎng)絡(luò)、通訊網(wǎng)絡(luò)及高壓線路網(wǎng)絡(luò)等都能表達(dá)成一個(gè)樹圖?？梢宰C明：（1）一棵樹的邊數(shù)等于點(diǎn)數(shù)減1；（2）在樹中任意兩個(gè)點(diǎn)之間添加一條邊就形成圈；（3）在樹中去掉任意一條邊圖就變?yōu)椴贿B通。在一個(gè)連通圖G中，取部分邊連接G的所有點(diǎn)組成的樹稱為G的部分樹或支撐樹(SpanningTree

)。圖6－2是圖6－1的部分樹。v1v2v3v4v5v64321圖6－276.1最小樹問題

Minimaltreeproblem6.1.2最小部分樹將網(wǎng)絡(luò)圖G邊上的權(quán)看作兩點(diǎn)間的長度（距離、費(fèi)用、時(shí)間），定義G的部分樹T的長度等于T中每條邊的長度之和，記為C(T)。G的所有部分樹中長度最小的部分樹稱為最小部分樹，或簡稱為最小樹。最小部分樹可以直接用作圖的方法求解，常用的有破圈法和加邊法。破圈法：任取一圈，去掉圈中最長邊，直到無圈。6.1最小樹問題

Minimaltreeproblem5v1v2v3v4v5v6843752618圖6－1【例6.1】用破圈法求圖6－1的最小樹。圖6－4圖6－4就是圖6－1的最小部分樹，最小樹長為

C(T)=4+3+5+2+1=15。當(dāng)一個(gè)圈中有多個(gè)相同的最長邊時(shí)，不能同時(shí)都去掉，只能去掉其中任意一條邊。最小部分樹有可能不唯一，但最小樹的長度相同6.1最小樹問題

Minimaltreeproblem加邊法：取圖G的n個(gè)孤立點(diǎn)｛v1，v2，…，vn}作為一個(gè)支撐圖，從最短邊開始往支撐圖中添加，見圈回避，直到連通（有n－1條邊）

v1v2v3v4v5v643521圖6－5在圖6－5中，如果添加邊[v1,v2]就形成圈｛v1,v2,v4｝，這時(shí)就應(yīng)避開添加邊[v1,v2]，添加下一條最短邊[v3,v6]。破圈法和加邊法得到樹的形狀可能不一樣，但最小樹的長度相等5v1v3v515v2v4v684375268×MinC(T)=156.1最小樹問題

Minimaltreeproblem下一節(jié)：最短路問題1.樹、支撐樹、最小支撐樹的概念2.掌握求最小樹的方法：（1）破圈法（2）加邊法作業(yè)：P149T1，4，56.1最小樹問題

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

①②③④⑤⑥⑦610123214675811165圖6－69【例6.3】圖6－6中的權(quán)cij表示vi到vj的距離（費(fèi)用、時(shí)間），從v1修一條公路或架設(shè)一條高壓線到v7，如何選擇一條路線使距離最短，建立該問題的網(wǎng)絡(luò)數(shù)學(xué)模型。6.2最短路問題ShortestPathProblem

【解】設(shè)xij為選擇弧(i，j)的狀態(tài)變量，選擇弧(i，j)時(shí)xij＝1，不選擇弧(i，j)時(shí)xij＝0，得到最短路問題的網(wǎng)絡(luò)模型：6.2最短路問題ShortestPathProblem

6.2.2有向圖的狄克斯屈拉(Dijkstra)標(biāo)號算法點(diǎn)標(biāo)號：b(j)—起點(diǎn)vs到點(diǎn)vj的最短路長；邊標(biāo)號：k(i，j)=b(i)+cij，步驟：(1)令起點(diǎn)的標(biāo)號；b(s)＝0。先求有向圖的最短路，設(shè)網(wǎng)絡(luò)圖的起點(diǎn)是vs,終點(diǎn)是vt,以vi為起點(diǎn)vj為終點(diǎn)的弧記為（i，j）,距離為cij(2)找出所有vi已標(biāo)號vj未標(biāo)號的弧集合B={(i，j)}，如果這樣的弧不存在或vt已標(biāo)號則計(jì)算結(jié)束；(3)計(jì)算集合B中弧k(i，j)=b(i)+cij的標(biāo)號(4)選一個(gè)點(diǎn)標(biāo)號返回到第(2)步。6.2最短路問題ShortestPathProblem

②③④⑤⑥⑦610123214675811165圖6－690610129209186①161217162432182929【例6.4】用Dijkstra算法求圖6－6所示v1到v7的最短路及最短路長v1

到v7的最短路為：p17=｛v1,v2,v3,v5,v7｝，最短路長為L17=296.2最短路問題ShortestPathProblem

14從上例知，只要某點(diǎn)已標(biāo)號，說明已找到起點(diǎn)vs到該點(diǎn)的最短路線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)號，求出vs到任意點(diǎn)的最短路線，如果某個(gè)點(diǎn)vj不能標(biāo)號，說明vs不可達(dá)vj

。6.2.3無向圖最短路的求法無向圖最短路的求法只將上述步驟（2）改動(dòng)一下即可。點(diǎn)標(biāo)號：b(i)—起點(diǎn)vs到點(diǎn)vj的最短路長；邊標(biāo)號：k(i，j)=b(i)+cij，步驟：(1)令起點(diǎn)的標(biāo)號；b(s)＝0。(3)計(jì)算集合B中邊標(biāo)號：k[i，j]=b(i)+cij(4)選一個(gè)點(diǎn)標(biāo)號:

返回到第(2)步。(2)找出所有一端vi已標(biāo)號另一端vj未標(biāo)號的邊集合

B={[i，j]}如果這樣的邊不存在或vt已標(biāo)號則計(jì)算結(jié)束；6.2最短路問題ShortestPathProblem

【例6.5】求圖6-10所示v1到各點(diǎn)的最短路及最短距離①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有點(diǎn)都已標(biāo)號，點(diǎn)上的標(biāo)號就是v1到該點(diǎn)的最短距離，最短路線就是紅色的鏈。圖6-106.2最短路問題ShortestPathProblem

6.2.4最短路的Floyd算法Floyd算法基本步驟:(1)寫出vi一步到達(dá)vj

的距離矩陣，L1也是一步到達(dá)的最短距離矩陣。如果vi與vj之間沒有邊關(guān)聯(lián)，則令cij=+∞(2)計(jì)算二步最短距離矩陣。設(shè)vi到vj經(jīng)過一個(gè)中間點(diǎn)vr兩步到達(dá)vj，則vi到vj的最短距離為最短距離矩陣記為(3)計(jì)算k步最短距離矩陣。設(shè)

vi經(jīng)過中間點(diǎn)vr

到達(dá)vj，vi經(jīng)過k－1步到達(dá)點(diǎn)vr的最短距離為，vr經(jīng)過k－1步到達(dá)點(diǎn)vj

的最短距離為，則

vi經(jīng)k步

到達(dá)vj的最短距離為(6.1)6.2最短路問題ShortestPathProblem

最短距離矩陣記為(4)比較矩陣Lk與Lk－1，當(dāng)Lk＝Lk－1時(shí)得到任意兩點(diǎn)間的最短距離矩陣Lk。設(shè)圖的點(diǎn)數(shù)為n并且cij≥0，迭代次數(shù)k由式(6.3)估計(jì)得到。(6.2)(6.3)6.2最短路問題ShortestPathProblem

63①②③④⑤⑥⑦⑧45212789326121610【例6.6】圖6-14是一張8個(gè)城市的鐵路交通圖，鐵路部門要制作一張兩兩城市間的距離表。這個(gè)問題實(shí)際就是求任意兩點(diǎn)間的最短路問題。【解】(1)依據(jù)圖6-14,寫出任意兩點(diǎn)間一步到達(dá)距離表L1。見表6.1所示。本例n=8，，因此計(jì)算到L3

圖6-146.2最短路問題ShortestPathProblem

v1v2v3v4v5v6v7v8v106∞5∞4∞∞v260328∞∞∞v3∞30∞7∞∞16v452∞09123∞v5∞8790∞106v64∞∞12∞02∞v7∞∞∞3102012v8∞∞16∞6∞120表6-1最短距離表L16.2最短路問題ShortestPathProblem

表6-2最短距離表L2v1v2v3v4v5v6v7v8v106951446∞v26032810514v393057∞1713v4525095315v514879012106v6410∞5120214v765173102012v8∞141315614120計(jì)算說明：L(2)ij等于表6-1中第i行與第j列對應(yīng)元素相加取最小值。如6.2最短路問題ShortestPathProblem

表6-3計(jì)算示例:等于表6-2中第i行與第j列對應(yīng)元素相加取最小值。例如，v3經(jīng)過三步（最多三個(gè)中間點(diǎn)4條邊）到達(dá)v6的最短距離是表6-3最短距離表L3v1v2v3v4v5v6v7v8v10695144618v2603287514v39305710813v4525095315v514879012106v647105120214v76583102012v8181413156141206.2最短路問題ShortestPathProblem

【例6.7】求圖6－15中任意兩點(diǎn)間的最短距離。【解】圖6－15是一個(gè)混合圖，有3條邊的權(quán)是負(fù)數(shù),有兩條邊無方向。依據(jù)圖6－15,寫出任意兩點(diǎn)間一步到達(dá)距離表L1。表中第一列的點(diǎn)表示弧的起點(diǎn)，第一行的點(diǎn)表示弧的終點(diǎn)，無方向的邊表明可以互達(dá)，見表6-4所示。計(jì)算過程見表6-5～6-7。①②③④⑤⑥⑦44574－3－271028圖6－15－156.2最短路問題ShortestPathProblem

表6-4一步到達(dá)距離表L1v1v2v3v4v5v6v7v105∞∞

4∞∞v2∞04－2∞∞∞v3∞407∞∞2v44∞∞010∞7v5－1∞∞∞0－3∞v6∞∞∞5∞08v7∞∞2∞∞∞06.2最短路問題ShortestPathProblem

表6-7最短距離表L4v1v2v3v4v5v6v7v10593419v2204-2635v364021072v44990857v5-14720-35v69141051308v786241290經(jīng)計(jì)算L4＝L5，L4是最優(yōu)表。表6-7不是對稱表，vi到vj與vj到vi的最短距離不一定相等。對于有負(fù)權(quán)圖情形，公式(6.3)失效。6.2最短路問題ShortestPathProblem

6.2.4最短路應(yīng)用舉例6.2最短路問題ShortestPathProblem

【例6.8】設(shè)備更新問題。企業(yè)在使用某設(shè)備時(shí)，每年年初可購置新設(shè)備，也可以使用一年或幾年后賣掉重新購置新設(shè)備。已知4年年初購置新設(shè)備的價(jià)格分別為2.5、2.6、2.8和3.1萬元。設(shè)備使用了1～4年后設(shè)備的殘值分別為2、1.6、1.3和1.1萬元，使用時(shí)間在1～4年內(nèi)的維修保養(yǎng)費(fèi)用分別為0.3、0.8、1.5和2.0萬元。試確定一個(gè)設(shè)備更新策略，在下例兩種情形下使4年的設(shè)備購置和維護(hù)總費(fèi)用最小。（1）第4年年末設(shè)備一定處理掉；（2）第4年年末設(shè)備不處理。【解】畫網(wǎng)絡(luò)圖。用點(diǎn)(1,i,…,j)表示第1年年初購置設(shè)備使用到第i年年初更新，經(jīng)過若干次更新使用到第j年年初，第1年年初和第5年年初分別用①及⑤表示。使用過程用弧連接起來，弧上的權(quán)表示總費(fèi)用(購置費(fèi)＋維護(hù)費(fèi)－殘值)，如圖6－16所示6.2最短路問題ShortestPathProblem

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

點(diǎn)（1,3）和點(diǎn)（1,2,3）不能合并成一個(gè)點(diǎn)，雖然都是第三年年初購置新設(shè)備，購置費(fèi)用相同，但殘值不同。點(diǎn)(1,3)的殘值等于1.6(使用了兩年)，點(diǎn)(1,2,3)的殘值等于2(使用了一年)。點(diǎn)（1,3）到點(diǎn)（1,3,4）的總費(fèi)用為第三年的購置費(fèi)＋第一年的維護(hù)費(fèi)－設(shè)備使用兩年后的殘值＝2.8+0.3－1.6=1.5點(diǎn)（1,3）到點(diǎn)⑤的總費(fèi)用為第三年的購置費(fèi)＋第一年的維護(hù)費(fèi)＋第二年的維護(hù)費(fèi)－設(shè)備使用兩年后的殘值－第四年末的殘值＝2.8+0.3+0.8－1.6－1.6=0.7。費(fèi)用表見教材P135表6-8。①⑤6圖6－16(1,2,3)(1,4)(1,3,4)(1,2,4)(1,2,3,4)(1,2)(1,3)第一年第二年第三年第四年5.10.91.50.73.62.81.7-0.21.91.12.10.3-0.6-0.66.2最短路問題ShortestPathProblem

（2）第四年末不處理設(shè)備：將圖6－16第4年的數(shù)據(jù)換成表6-8最后一列，求點(diǎn)①到點(diǎn)⑤的最短路。最短路線為：①→(1,2)→(1,2,3)→⑤，最短路長為5.6，即總費(fèi)用為5.6萬元。更新方案與第一種情形相同。（1）第四年末處理設(shè)備：求點(diǎn)①到點(diǎn)⑤的最短路。用Dijkstra算法得到最短路線為：①→(1,2)→(1,2,3)→⑤，最短路長為4。

4年總費(fèi)用最小的設(shè)備更新方案是：第1年購置設(shè)備使用1年，第2年更新設(shè)備使用1年后賣掉，第3年購置設(shè)備使用2年到第4年年末，4年的總費(fèi)用為4萬元。【例6.9】服務(wù)網(wǎng)點(diǎn)設(shè)置問題。以圖6－14為例，現(xiàn)提出這樣一個(gè)問題，在交通網(wǎng)絡(luò)中建立一個(gè)快速反應(yīng)中心，應(yīng)選擇哪一個(gè)城市最好。類似地，在一個(gè)網(wǎng)絡(luò)中設(shè)置一所學(xué)校、醫(yī)院、消防站、購物中心，還有廠址選擇、總部選址、公司銷售中心選址等問題都屬于最佳服務(wù)網(wǎng)點(diǎn)設(shè)置問題?！窘狻繉τ诓煌膯栴}，尋求最佳服務(wù)點(diǎn)有不同的標(biāo)準(zhǔn)。像圖6－14只有兩點(diǎn)間的距離，可以采用“使最大服務(wù)距離達(dá)到最小”為標(biāo)準(zhǔn)，計(jì)算步驟如下。第一步：利用Floyd算法求出任意兩點(diǎn)之間的最短距離表（表6－3）。第二步：計(jì)算最短距離表中每行的最大距離的最小值，即6.2最短路問題ShortestPathProblem

引用例6.6計(jì)算的結(jié)果，對表3－3每行取最大值再取最小值，見表6－9倒數(shù)第二列。v1v2v3v4v5v6v7v8MaxLij總運(yùn)量v10695144618183220v2603287514142465v39305710813132955v4525095315152450v514879012106143780v647105120214142960v76583102012122560v818141315614120185040產(chǎn)量8050704030356065表6－9表6－9中倒數(shù)第二列最小值為12，位于第7行，則v7為網(wǎng)絡(luò)的中心，最佳服務(wù)點(diǎn)應(yīng)設(shè)置在v7。6.2最短路問題ShortestPathProblem

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

下一節(jié)：最大流問題6.2最短路問題ShortestPathProblem

1.最短路的概念及應(yīng)用。2.有向圖、無向圖一點(diǎn)到各點(diǎn)最短路的Dijkstra算法3.任意兩點(diǎn)最短路的Floyd算法4.本節(jié)介紹了兩個(gè)應(yīng)用：設(shè)備更新問題和最佳服務(wù)點(diǎn)設(shè)置問題作業(yè)：P149T2,6,7,8,96.3最大流問題MaximalFlowProblem6.3最大流問題MaximalFlowProblem6.3.1基本概念①②③④⑤⑥814563381076⑦3圖6－184圖6－18所示的網(wǎng)絡(luò)圖中定義了一個(gè)發(fā)點(diǎn)v1，稱為源(source，supplynode），定義了一個(gè)收點(diǎn)v7，稱為匯（sink，demandnode），其余點(diǎn)v2，v3，…，v6為中間點(diǎn)，稱為轉(zhuǎn)運(yùn)點(diǎn)(transshipmentnodes)。如果有多個(gè)發(fā)點(diǎn)和收點(diǎn)，則虛設(shè)發(fā)點(diǎn)和收點(diǎn)轉(zhuǎn)化成一個(gè)發(fā)點(diǎn)和收點(diǎn)。圖中的權(quán)是該弧在單位時(shí)間內(nèi)的最大通過能力，稱為弧的容量(capacity)。最大流問題是在單位時(shí)間內(nèi)安排一個(gè)運(yùn)送方案，將發(fā)點(diǎn)的物質(zhì)沿著弧的方向運(yùn)送到收點(diǎn)，使總運(yùn)輸量最大。設(shè)cij為?。╥，j）的容量，fij為弧（i，j）的流量。容量是?。╥，j）單位時(shí)間內(nèi)的最大通過能力，流量是?。╥，j）單位時(shí)間內(nèi)的實(shí)際通過量，流量的集合f={fij}稱為網(wǎng)絡(luò)的流。發(fā)點(diǎn)到收點(diǎn)的總流量記為v=val(f)，v也是網(wǎng)絡(luò)的流量。圖6－18最大流問題的線性規(guī)劃數(shù)學(xué)模型為6.3最大流問題MaximalFlowProblem滿足下例3個(gè)條件的流fij

的集合f={fij

}稱為可行流發(fā)點(diǎn)vs流出的總流量等于流入收點(diǎn)vt的總流量6.3最大流問題MaximalFlowProblem鏈：從發(fā)點(diǎn)到收點(diǎn)的一條路線（弧的方向不一定都同向）稱為鏈。從發(fā)點(diǎn)到收點(diǎn)的方向規(guī)定為鏈的方向。前向?。号c鏈的方向相同的弧稱為前向弧。后向?。号c鏈的方向相反的弧稱為后向弧。增廣鏈:

設(shè)f

是一個(gè)可行流，如果存在一條從vs到vt的鏈，滿足：1.所有前向弧上fij<Cij2.所有后向弧上fij>0則該鏈稱為增廣鏈①②③④⑤⑥前向弧后向弧容量流量這是一條增廣鏈84469（5）(2)(3)(4)(6)6.3最大流問題MaximalFlowProblem步驟如下：第二步：對點(diǎn)進(jìn)行標(biāo)號找一條增廣鏈。（1）發(fā)點(diǎn)標(biāo)號（∞）（2）選一個(gè)點(diǎn)vi已標(biāo)號并且另一端未標(biāo)號的弧沿著某條鏈向收點(diǎn)檢查：

A．如果弧的方向向前（前向?。┎⑶矣衒ij<cij，則vj標(biāo)號:θj＝cij－fijB．如果弧的方向指向vi（后向弧）并且有fji>0，則vj標(biāo)號:

θj＝fji當(dāng)收點(diǎn)已得到標(biāo)號時(shí)，說明已找到增廣鏈，依據(jù)vi

的標(biāo)號反向跟蹤得到一條增廣鏈。當(dāng)收點(diǎn)不能得到標(biāo)號時(shí)，說明不存在增廣鏈，計(jì)算結(jié)束。第一步：找出第一個(gè)可行流，例如所有弧的流量fij

=06.3.2Ford-Fulkerson標(biāo)號算法6.3最大流問題MaximalFlowProblem第三步：調(diào)整流量（1）求增廣鏈上點(diǎn)vi

的標(biāo)號的最小值，得到調(diào)整量（2）調(diào)整流量得到新的可行流f1，去掉所有標(biāo)號，返回到第二步從發(fā)點(diǎn)重新標(biāo)號尋找增廣鏈，直到收點(diǎn)不能標(biāo)號為止【定理6.1】可行流f是最大流的充分必要條件是不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈6.3最大流問題MaximalFlowProblem①②③④⑤⑥814563381076⑦3圖6－19(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)【例6.10】求圖6－18發(fā)點(diǎn)v1到收點(diǎn)v7的最大流及最大流量【解】給定初始可行流，見圖6-196.3最大流問題MaximalFlowProblem①②③④⑤⑥814563381076⑦3圖6－20(b)(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)∞2337第一輪標(biāo)號：c12>f12,v2標(biāo)號2cij=fij，v4、v5不能標(biāo)號后向弧f32>0,v3標(biāo)號θ3=f32增廣鏈μ＝{(1,2)，(3,2)，(3,4)，(4,7)},μ+={(1,2)，(3,4)，(4,7)},μ－={(3，2)}，調(diào)整量為增廣鏈上點(diǎn)標(biāo)號的最小值θ＝min{∞，2，3，3，7}＝26.3最大流問題MaximalFlowProblem①②③④⑤⑥814563381076⑦3圖6－21(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)調(diào)整后的可行流：6.3最大流問題MaximalFlowProblem①②③④⑤⑥814563381076⑦3圖6－22(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)∞4415第二輪標(biāo)號：Cij=fij，v4、v5不能標(biāo)號，返回到v3增廣鏈μ＝μ＋＝{(1,3)，(3,4)，(4,7)}，調(diào)整量為

θ＝min{∞，4，1，5}＝16.3最大流問題MaximalFlowProblem①②③④⑤⑥814563381076⑦3圖6－23(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)調(diào)整后得到可行流：6.3最大流問題MaximalFlowProblem①②③④⑤⑥814563381076⑦3圖6－22(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)∞314第三輪標(biāo)號：增廣鏈μ＝μ＋＝{(1,3)，(3,6)，(6,4)，(4,7)}，調(diào)整量為

θ＝min{∞，3，1，2，4}＝126.3最大流問題MaximalFlowProblem①②③④⑤⑥814563381076⑦3圖6－25(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)調(diào)整后得到可行流：6.3最大流問題MaximalFlowProblem①②③④⑤⑥814563381076⑦3圖6－22(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)∞2第四輪標(biāo)號：v7得不到標(biāo)號，不存在v1到v7的增廣鏈，圖6-22所示的可行流是最大流，最大流量為

v＝f12+f13＝8+12=20Cij=fij，v4、v5不能標(biāo)號Cij=fij，v4、v6不能標(biāo)號46.3最大流問題MaximalFlowProblem無向圖最大流標(biāo)號算法無向圖不存在后向弧，可以理解為所有弧都是前向弧，對一端vi已標(biāo)號另一端vj未標(biāo)號的邊只要滿足Cij－fij>0則vj就可標(biāo)號（Cij－fij）【例】求下圖v1到則v7標(biāo)的最大流7①②③④⑤⑥⑦1292085148691316(10)(6)(10)(8)(2)(3)(7)(6)(5)(13)(0)(13)∞239936.3最大流問題MaximalFlowProblem7①②③④⑤⑥⑦1292085148691316(12)(6)(10)(8)(4)(3)(7)(6)(7)(13)(2)(15)∞37717①②③④⑤⑥⑦1292085148691316(12)(7)(10)(8)(4)(3)(7)(6)(8)(13)(3)(16)V=29∞105666.3最大流問題MaximalFlowProblem1截集將圖G＝（V，E）的點(diǎn)集分割成兩部分稱為一個(gè)截集，截集中所有弧的容量之和稱為截集的截量。①②③④⑤⑥68441226796411322306下圖所示的截集為6.3最大流問題MaximalFlowProblem①②③④⑤⑥68441226796401322106又如下圖所示的截集為上圖所示的截集為所有截量中此截量最小且等于最大流量，此截集稱為最小截集?！径ɡ怼孔畲罅髁康扔谧钚〗丶慕亓?。6.3最大流問題MaximalFlowProblem6.3.4最小費(fèi)用流滿足流量達(dá)到一個(gè)固定數(shù)使總費(fèi)用最小，就是最小費(fèi)用流問題。另一個(gè)問題是滿足流量到達(dá)最大使總費(fèi)用最小，稱為最小費(fèi)用最大流問題。圖6－27是一個(gè)運(yùn)輸網(wǎng)絡(luò)圖，將工廠v1，v2及v3的物質(zhì)(數(shù)量不限)運(yùn)往v6，v4和v5是中轉(zhuǎn)點(diǎn)，弧上的數(shù)字為（cij，dij)。設(shè)?。╥,j）的單位流量費(fèi)用為dij≥0，弧的容量為cij≥0

設(shè)可行流f的一條增廣鏈為μ，稱為增廣鏈μ的費(fèi)用。第一個(gè)求和式是增廣鏈中前向弧的費(fèi)用之和，第二個(gè)求和式是增廣鏈中后向弧的費(fèi)用之和。d(μ)最小的增廣鏈稱為最小費(fèi)用增廣鏈。6.3最大流問題MaximalFlowProblem(1)制定一個(gè)總運(yùn)量等于15總運(yùn)費(fèi)最小的運(yùn)輸方案；屬于最小費(fèi)用流問題(3,5)(6,4)(4,2)(3,4)(1,6)(2,3)(9,12)①②③④⑤⑥(12,3)(3,5)(6,4)(4,2)(3,4)(1,6)(2,3)(9,12)①②③④⑤⑥s(10,0)(6,0)(3,0)圖6－27圖6－28(12,3)

(2)制定使運(yùn)量最大并且總運(yùn)費(fèi)最小的運(yùn)輸方案，屬于最小費(fèi)用最大流問題6.3最大流問題MaximalFlowProblem設(shè)給定的流量為v。最小費(fèi)用流的標(biāo)號算法步驟如下。第1步：取初始流量為零的可行流f(0)＝{0}，令網(wǎng)絡(luò)中所有弧的權(quán)等于dij得到一個(gè)賦權(quán)圖D，用Dijkstra算法求出最短路，這條最短路就是初始最小費(fèi)用增廣鏈μ。第2步：調(diào)整流量。在最小費(fèi)用增廣鏈上調(diào)整流量的方法與前面最大流算法一樣，前向弧上令θj＝cij－fij，后向弧上令θj＝fij，調(diào)整量為θ=min{θj}。調(diào)整后得到最小費(fèi)用流f(k)

，流量為v(k)＝

v(k－1)＋θ，當(dāng)v(k)＝v時(shí)計(jì)算結(jié)束，否則轉(zhuǎn)第3步繼續(xù)計(jì)算。第3步：作賦權(quán)圖D并尋找最小費(fèi)用增廣鏈。6.3最大流問題MaximalFlowProblem(1)對可行流f(k－1)的最小費(fèi)用增廣鏈上的?。╥，j）作如下變動(dòng)第一種情形：當(dāng)?。╥，j）上的流量滿足0<fij<cij時(shí)，在點(diǎn)vi與vj之間添加一條方向相反的?。╦，i），權(quán)為（－dij）。第二種情形：當(dāng)弧（i，j）上的流量滿足fij＝cij時(shí)將弧（i，j）反向變?yōu)椋╦，i）,權(quán)為（－bij）。不在最小費(fèi)用增廣鏈上的弧不作任何變動(dòng)，得到一個(gè)賦權(quán)網(wǎng)絡(luò)圖D。（2）求賦權(quán)圖D從發(fā)點(diǎn)的收點(diǎn)的最短路，如果最短路存在，則這條最短路就是f(k－1)的最小費(fèi)用增廣鏈，轉(zhuǎn)第2步。賦權(quán)圖D的所有權(quán)非負(fù)時(shí)，可用Dijkstra算法求最短路，存在負(fù)權(quán)時(shí)用Floyd算法。（3）如果賦權(quán)圖D不存在從發(fā)點(diǎn)到收點(diǎn)的最短路，說明v(k－1)已是最大流量，不存在流量等于v的流，計(jì)算結(jié)束。6.3最大流問題MaximalFlowProblem【例6.11】對圖6－28，制定一個(gè)運(yùn)量v＝15及運(yùn)量最大總運(yùn)費(fèi)最小的運(yùn)輸方案?！窘狻苛钏谢〉牧髁康扔诹悖玫匠跏伎尚辛鱢(0)＝{0}，流量v(0)＝0，總運(yùn)費(fèi)d(f(0))=0。354246312圖6－29①②③④⑤⑥s000(a)f(0)，賦權(quán)圖D0最小費(fèi)用增廣鏈μ1：s→①→④→⑥,見圖6－29(a)6.3最大流問題MaximalFlowProblem

調(diào)整量θ＝4，對f(0)＝{0}進(jìn)行調(diào)整得到f(1)，括號（）內(nèi)的數(shù)字為弧的流量，網(wǎng)絡(luò)流量v(1)＝4，總運(yùn)費(fèi)

d(f(1))＝0×4＋2×4＋3×4＝20如圖6－29(b)。圖6－29(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)①②③④⑤⑥s(10,0)(6,0)(3,0)(b)f(1)(4)(4)(4)(6,4)(4,2)圖中：（cij，dij)(

fij

)6.3最大流問題MaximalFlowProblem354－246312圖6－29①②③④⑤⑥s000(c)f(1)，賦權(quán)圖D1－3(3)v(1)＝4<15，沒有得到最小費(fèi)用流。在圖6－29(b)中，弧(s,1)和(4,6)滿足條件0<fij<cij，添加兩條邊(1,s)和(6,4)，權(quán)分別為“0”和“－3”，邊(1,s)可以去掉，弧(1,4)上有fij＝cij說明已飽和，將弧(1,4)反向變?yōu)?4,1)，權(quán)為“－2”，如圖6－29(c)。6.3最大流問題MaximalFlowProblem(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)圖6－29①②③④⑤⑥s(10,0)(6,0)(3,0)(d)f(2)(4)(4)(7)(6,4)(4,2)(3)(3)圖中：（cij，dij)(fij

)用Floyd算法得到最小費(fèi)用增廣鏈μ2：s→②→④→⑥，調(diào)整量θ＝3，調(diào)整后得到最小費(fèi)用流f(2)，流量v(2)＝7，總運(yùn)費(fèi)

d(f(2))＝2×4＋3×7＋5×3＝44如圖6－29(d)。6.3最大流問題MaximalFlowProblem(4)v(2)＝7<15，對最小費(fèi)用增廣鏈μ2上的弧進(jìn)行調(diào)整，在圖6－29(c)中，弧(s,2)和(4,6)滿足條件0<fij<cij，添加兩條邊(2,s)和(6,4)，權(quán)分別為“0”和“－3”，邊(2,s)可以去掉，弧(6,4)已經(jīng)存在，弧(2,4)上有fij＝cij說明已飽和，將弧(2,4)反向變?yōu)?4,2)，權(quán)為“－5”，如圖6－29(e)。3－54－246312圖6－29①②③④⑤⑥s000(e)f(2)，賦權(quán)圖D2－36.3最大流問題MaximalFlowProblem用Floyd算法得到最小費(fèi)用增廣鏈μ3：s→③→④→⑥，調(diào)整量θ＝1，調(diào)整后得到最小費(fèi)用流f(3)，流量v(3)＝8，總運(yùn)費(fèi)

d(f(3))＝2×4＋3×8＋5×3＋6×1＝53如圖6－29(f)。(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)圖6－29①②③④⑤⑥s(10,0)(6,0)(3,0)(f)f(3)(4)(4)(8)(6,4)(4,2)(3)(3)(1)(1)6.3最大流問題MaximalFlowProblem(5)類似地，得到圖6－29(g)3－54－24－6312圖6－29①②③④⑤⑥s000(g)f(3)，賦權(quán)圖D3－3(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)圖6－29①②③④⑤⑥s(10,0)(6,0)(3,0)(h)f(4)(4)(4)(8)(6,4)(4,2)(3)(3)(3)(1)(2)(2)最小費(fèi)用增廣鏈μ4：s→③→⑤→⑥，調(diào)整量θ＝2，流量v(4)＝10。見圖6－29(h)6.3最大流問題MaximalFlowProblem最小費(fèi)用增廣鏈μ5：s→①→⑤→⑥,調(diào)整量θ＝6，取θ＝5，流量v(5)＝v＝15得到滿足，最小費(fèi)用流見圖6－29(j)，問題1計(jì)算結(jié)束。3－54－24－6－312圖6－29①②③④⑤⑥s000(i)f(4)，賦權(quán)圖D4－3－12(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)圖6－29①②③④⑤⑥s(10,0)(6,0)(3,0)(j)f(5)(9)(4)(8)(6,4)(4,2)(3)(3)(3)(1)(2)(7)(5)(6)由圖6－29(g)及(h),得到圖6－29(i),6.3最大流問題MaximalFlowProblem(7)求最小費(fèi)用最大流。對圖6－29(i)的最小費(fèi)用增廣鏈μ5，取調(diào)整量θ＝6對流量調(diào)整，得到圖6－30(a)及賦權(quán)圖6－30(b)(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)圖6－30①②③④⑤⑥s(10,0)(6,0)(3,0)(a)f(5)(10)(4)(8)(6,4)(4,2)(3)(3)(3)(1)(2)(8)(6)6.3最大流問題MaximalFlowProblem3－5－4－24－6－312圖6－30①②③④⑤⑥s000(b)f(5)，賦權(quán)圖D5－3－12(8)圖6－30(b)的最小費(fèi)用增廣鏈μ6：s→②→⑤→⑥，6.3最大流問題MaximalFlowProblem(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)圖6－30①②③④⑤⑥s(10,0)(6,0)(3,0)(c)f(6)(10)(4)(8)(6,4)(4,2)(4)(3)(3)(1)(2)(9)(6)(1)調(diào)整量θ＝1，流量v(6)＝17，最小費(fèi)用流為f(6)，見圖6－30(c)。6.3最大流問題MaximalFlowProblem賦權(quán)圖見圖6－30（d）。圖6－30(d)不存在從vs發(fā)點(diǎn)到v6的最短路，則圖6－30(c)的流就是最小費(fèi)用最大流，最大流量v=17，最小的總運(yùn)費(fèi)為d(f)=4×4＋4×6＋5×3＋4×1＋6×1＋3×2＋3×8＋9×9＝1763－5－4－24－6－3－12圖6－30①②③④⑤⑥s000(d)f(6)，賦權(quán)圖D6－3－43個(gè)工廠分別運(yùn)送10、4及3個(gè)單位物質(zhì)到v6，總運(yùn)量為17，運(yùn)費(fèi)為1766.3最大流問題MaximalFlowProblem6.3.5最大流應(yīng)用舉例1.二分圖的最大匹配問題【例6.12】某公司需要招聘5個(gè)專業(yè)的畢業(yè)生各一個(gè)，通過本人報(bào)名和篩選，公司最后認(rèn)為有6人都達(dá)到錄取條件。這6人所學(xué)專業(yè)見表6-10,表中打“√”表示該生所學(xué)專業(yè)。公司應(yīng)招聘哪幾位畢業(yè)生，如何分配他們的工作畢業(yè)生A.市場營銷B.工程管理C.管理信息D.計(jì)算機(jī)E.企業(yè)管理1√√2√√3√√4√√5√√6√√表6-106.3最大流問題MaximalFlowProblem①②③④⑤⑥ABCDEst(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)圖6－32【解】畫出一個(gè)二分圖，虛設(shè)一個(gè)發(fā)點(diǎn)和一收點(diǎn)，每條弧上的容量等于1，問題為求發(fā)點(diǎn)到收點(diǎn)的最大流，求解結(jié)果之一見圖6－32。公司錄取第2～6號畢業(yè)生，安排的工作依次為管理信息、企業(yè)管理、市場營銷、工程管理和計(jì)算機(jī)。6.3最大流問題MaximalFlowProblem【例6.13】某市政工程公司在未來5～8月份內(nèi)需完成4項(xiàng)工程：A.修建一條地下通道、B.修建一座人行天橋、C.新建一條道路及D.道路維修。工期和所需勞動(dòng)力見表6-11。該公司共有勞動(dòng)力120人，任一項(xiàng)工程在一個(gè)月內(nèi)的勞動(dòng)力投入不能超過80人，問公司如何分配勞動(dòng)力完成所有工程，是否能按期完成工期需要?jiǎng)趧?dòng)力（人月）A.地下通道5～7月100B.人行天橋6～7月80C.新建道路5～8月200D.道路維修8月80表6-12【解】將工程計(jì)劃用網(wǎng)絡(luò)圖6－33表示。設(shè)點(diǎn)v5、v6、v7、v8分別表示5～8月份，Ai、Bi

、Ci

、Di表示工程在第i個(gè)月內(nèi)完成的部分，用弧表示某月完成某項(xiàng)工程的狀態(tài)，弧的容量為勞動(dòng)力限制。就是求圖6－33從發(fā)點(diǎn)到收點(diǎn)的最大流問題。6.3最大流問題MaximalFlowProblem⑤⑥⑦⑧A5B6C7D8st圖6－33A6C5A7C6B7C8ABCD12012012012080808080808080808080808080808080808080801008020080(100)(120)(120)(120)(20)(80)(40)(80)(0)(40)(80)(0)(40)(80)(20)(80)(80)(40)(80)(80)(40)(0)(40)(80)(100)(80)(200)(80)6.3最大流問題MaximalFlowProblem

Ford-Fulkerson標(biāo)號算法求解得到圖6－33，括號內(nèi)的數(shù)字為弧的流量。每個(gè)月的勞動(dòng)力分配見表6-13。5月份有剩余勞動(dòng)力20人，4項(xiàng)工程恰好按期完成

表6-13月份投入勞動(dòng)力項(xiàng)目A(人)項(xiàng)目B(人)項(xiàng)目C(人)項(xiàng)目D(人)510020

80

6120

4080

71208040

8120

4080合計(jì)(人)46010080200806.3最大流問題MaximalFlowProblem下一節(jié)：旅行售貨員與中國郵路問題1.最大流的概念：容量、流量、可行流、最大流、前向弧、后向弧、增廣鏈、截集、截量、最小截量與最大流量的關(guān)系、最小費(fèi)用流、最小費(fèi)用最大流。2.有向圖、無向圖最大流的Ford-Fulkerson標(biāo)號算法3.最小費(fèi)用流、最小費(fèi)用最大流的算法4.本節(jié)介紹了兩個(gè)應(yīng)用：最大匹配問題和勞動(dòng)力合理配置問題作業(yè)：P149T3，10，116.3最大流問題MaximalFlowProblem6.4旅行售貨員與中國郵路問題

TravelingSalesmanandChinaCarrierProblem6.4旅行售貨員與中國郵路問題6.4.1旅行售貨員問題(Travelingsalesmanproblem)【例6.14】某電動(dòng)汽車公司與學(xué)校合作，擬定在校園內(nèi)開通無污染無噪音的“綠色交通”路線。圖6－34是某大學(xué)教學(xué)樓和學(xué)生宿舍樓的分布圖，其中C、F之間是兩條單向通道，邊上的數(shù)字為汽車通過兩點(diǎn)間的正常時(shí)間（分鐘）。電動(dòng)汽車公司如何設(shè)計(jì)一條路線，使汽車通過每一處教學(xué)樓和宿舍樓一次后總時(shí)間最少。ABCDEF42.5332.81.61.82.64.22.21.5【解】求解過程略（見教材P145）。電動(dòng)汽車公司的行車路線是A→B→F→E→D→C→A，汽車在校園行駛一圈需要15.6分鐘。6.4旅行售貨員與中國郵路問題6.4.2中國郵路問題(Chinacarrierproblem)

【例6.15】求解圖6－35（a）的中國郵路問題35v1v2v4v5v6v74752618圖6－35v341(a)6.4旅行售貨員與中國郵路問題5v1v2v4v5v6v743752618v34141圖6－36【解】最優(yōu)解如圖6-3614圖6-36為最短歐拉回路，重復(fù)經(jīng)過了[1，2]和[6，7]兩條邊TheEndofChapter6作業(yè):P150T12(1)Hamilton回路、Euler回路。(2)旅行售貨員問題(3)中國郵路問題6.4旅行售貨員與中國郵路問題第6章部分習(xí)題答案v1v2v4v5v6v82685214v341v7v9v10327735234(a)圖6－41習(xí)題6.4解答v1v2v4v5v6v8221v31v7v9v1025234(a)圖6－41有4個(gè)解，minC(T)=21習(xí)題6.4解答v1v2v4v5v6v843721v33154v7v9v10562733234圖6－41(b)習(xí)題6.4習(xí)題6.4解答v1v2v4v5v6v8321v331v7v9v102323圖6－41(b)習(xí)題6.4解答B(yǎng)CDEFG451438686865AH1013圖6－42(a)I922習(xí)題6.6BCDEFG451438686865AH1013圖6－42(a)I922習(xí)題6.6(a)求A到H、I的最短路及最短路長

【解】用Dijkstra算法

0(8)(12)(14)(14)(10)(13)(9)(12)(5)(6)5689(22)12(14)(21)(22)14(28)2221習(xí)題6.6BCDEFG451438686865AH1013圖6－42(b)I922習(xí)題6.6(b)求A到H、I的最短路及最短路長

習(xí)題6.6BCDEFG451438686865AH1013圖6－42(b)I922習(xí)題6.6(b)求A到H、I的最短路及最短路長

【解】用Dijkstra算法

(6)0(8)(12)(14)(14)(10)(13)(9)(12)(5)56891113(11)20(21)(20)(21)(27)21習(xí)題6.6習(xí)題6.7已知某設(shè)備可繼續(xù)使用5年，也可以在每年年末賣掉重新購置新設(shè)備。已知5年年初購置新設(shè)備的價(jià)格分別為3.5、3.8、4.0、4.2和4.5萬元。使用時(shí)間在1～5年內(nèi)的維護(hù)費(fèi)用分別為0.4、0.9、1.4、2.3和3萬元。試確定一個(gè)的設(shè)備更新策略，使5年的設(shè)備購置和維護(hù)總費(fèi)用最小

①②③④⑤⑥3.94.24.44.64.94.86.28.511.56.56.78.85.35.55.10(3.9)(4.8)(6.2)(8.5)(11.5)3.9(8.1)(9)(10.4)(12.7)4.8(9.2)(10.1)6.2(11.7)(10.8)8.5(11.5)(13.4)11.5習(xí)題6.7243654121438108.8965194.85圖6－43圖6－44234567530318152091615188139151020223056.10如圖6－44，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量習(xí)題6.10解答圖6－4423456753031815209161518813915102022305【解】給出一個(gè)初始流，如下圖所示(15)(15)(15)(15)(15)(15)(15)(20)(5)(5)(5)(0)(0)(0)(0)(0)習(xí)題6.10解答圖6－4423456753031815209161518813915102022305第一輪標(biāo)號：得到一條增廣鏈，調(diào)整量等于5，如下圖所示(15)(15)(15)(15)(15)(15)(15)(20)(5)(5)(5)(0)(0)(0)(0)(0)∞59157習(xí)題6.10解答圖6－4423456753031815209161518813915102022305調(diào)整流量。第二輪標(biāo)號：得到一條增廣鏈，調(diào)整量等于2，如下圖所示(15)(15)(20)(20)(20)(15)(15)(20)(5)(5)(5)(0)(5)(0)(0)(0)∞102082習(xí)題6.10解答圖6－4423456753031815209161518813915102022305調(diào)整流量。第三輪標(biāo)號：得到一條增廣鏈，調(diào)整量為3，如下圖所示(15)(15)(20)(22)(20)(15)(15)(20)(7)(5)(5)(0)(5)(0)(2)(2)∞818153810習(xí)題6.10解答圖6－4423456753031815209161518813915102022305調(diào)整流量。第四輪標(biāo)號：不存在增廣鏈，最大流量等于45，如下圖所示(15)(15)(20)(22)(20)(12)(15)(23)(10)(5)(8)(0)(5)(3)(5)(2)∞81515最小截集{(3,7),(4,7),(6,9),(8,10)，最小截量等于453510習(xí)題6.10解答A1(4,6)(5,4)(10,7)(7,7)(8,10)(8,5)(4,5)(15,6)(3,3)A2A3C2C1B2B1圖6－456.11將3個(gè)天然氣田A1、A2、A3的天然氣輸送到2個(gè)地區(qū)C1、C2，中途有2個(gè)加壓站B1、B2，天然氣管線如圖6－45所示。輸氣管道單位時(shí)間的最大通過量cij及單位流量的費(fèi)用dij標(biāo)在弧上(cij,dij)。求(1)流量為22的最小費(fèi)用流；（2）最小費(fèi)用最大流。習(xí)題6.11解答A1(4,6)(5,4)(10,7)(7,7)(8,10)(8,5)(4,5)(15,6)(3,3)A2A3C2C1B2B1【解】1.虛擬一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)AC(4,0)(15,0)(8,0)(14,0)(18,0)T6.11－1習(xí)題6.11解答A16477105563A2A3C2C1B2B12.fij=0,最短路p1={A,A2,B1,C2,C}，L1=8AC00000T6.11－2習(xí)題6.11解答A1(4,6)(5,4)(10,7)(7,7)(8,10)(8,5)(4,5)(15,6)(3,3)A2A3C2C1B2B13.在最小費(fèi)用鏈上調(diào)整流量,調(diào)整量等于3，紅色的為弧的流量AC(4,0)(15,0)(8,0)(14,0)(18,0)(3)(3)(3)(3)T6.11－3習(xí)題6.11解答A1647710556－3A2A3C2C1B2B14.調(diào)整權(quán)