《運(yùn)籌學(xué)》模擬試題及參考答案

《運(yùn)籌學(xué)》模擬試題及參考答案一、判斷題(在下列各題中，你認(rèn)為題中描述的內(nèi)容為正確者，在題尾括號(hào)內(nèi)寫“√”，錯(cuò)誤者寫“×”。)1.圖解法提供了求解線性規(guī)劃問題的通用方法。 ()2.用單純形法求解一般線性規(guī)劃時(shí)，當(dāng)目標(biāo)函數(shù)求最小值時(shí)，若所有的檢驗(yàn)數(shù)Cj-Zj≥0，則問題達(dá)到最優(yōu)。 ()3.在單純形表中，基變量對(duì)應(yīng)的系數(shù)矩陣往往為單位矩陣。 ()4.滿足線性規(guī)劃問題所有約束條件的解稱為基本可行解。 ()5.在線性規(guī)劃問題的求解過程中，基變量和非基變量的個(gè)數(shù)是固定的。 ()6.對(duì)偶問題的目標(biāo)函數(shù)總是與原問題目標(biāo)函數(shù)相等。 ()7.原問題與對(duì)偶問題是一一對(duì)應(yīng)的。 ()8.運(yùn)輸問題的可行解中基變量的個(gè)數(shù)一定遵循m＋n－1的規(guī)則。 ()9.指派問題的解中基變量的個(gè)數(shù)為m＋n。 ()10.網(wǎng)絡(luò)最短路徑是指從網(wǎng)絡(luò)起點(diǎn)至終點(diǎn)的一條權(quán)和最小的路線。 ()11.網(wǎng)絡(luò)最大流量是網(wǎng)絡(luò)起點(diǎn)至終點(diǎn)的一條增流鏈上的最大流量。 ()12.工程計(jì)劃網(wǎng)絡(luò)中的關(guān)鍵路線上事項(xiàng)的最早時(shí)間和最遲時(shí)間往往不相等。 ()13.在確定性存貯模型中不許缺貨的條件下，當(dāng)費(fèi)用項(xiàng)目相同時(shí)，生產(chǎn)模型的間隔時(shí)間比訂購(gòu)模型的間隔時(shí)間長(zhǎng)。 ()14.單目標(biāo)決策時(shí)，用不同方法確定的最佳方案往往是一致的。 ()15.動(dòng)態(tài)規(guī)劃中運(yùn)用圖解法的順推方法和網(wǎng)絡(luò)最短路徑的標(biāo)號(hào)法上是一致的。 ()二、簡(jiǎn)述題1.用圖解法說明線性規(guī)劃問題單純形法的解題思想。2.運(yùn)輸問題是特殊的線性規(guī)劃問題，但為什么不用單純形法求解。3.建立動(dòng)態(tài)規(guī)劃模型時(shí)，應(yīng)定義狀態(tài)變量，請(qǐng)說明狀態(tài)變量的特點(diǎn)。三、填空題1.圖的組成要素；。2.求最小樹的方法有、。3.線性規(guī)劃解的情形有、、、。4.求解指派問題的方法是。5.按決策環(huán)境分類，將決策問題分為、、。6.樹連通，但不存在。四、下列表是線性規(guī)劃單純形表（求Zmax），請(qǐng)根據(jù)單純形法原理和算法。1.計(jì)算該規(guī)劃的檢驗(yàn)數(shù) C Cj → 3 2 0 0 0Ci xB x1 x2 x3 x4 x53 x1 3 1 0 -1 02 x3 4 0 1 1 1/2 0 zj 3 3.5 2 -2 0 cj－zj 2.計(jì)算對(duì)偶問題的目標(biāo)函數(shù)值3.確定上表中輸入，輸出變量五、已知一個(gè)線性規(guī)劃原問題如下，請(qǐng)寫出對(duì)應(yīng)的對(duì)偶模型六、下圖為動(dòng)態(tài)規(guī)劃的一個(gè)圖示模型，邊上的數(shù)字為兩點(diǎn)間的距離，請(qǐng)用逆推法求出S至F點(diǎn)的最短路徑及最短路長(zhǎng)。BB110710710610C110610C181258125514FS514FS6613766137C210A2C210A29B9B3七、自己選用適當(dāng)?shù)姆椒?，?duì)下圖求最小(生成)樹。VV1233523356V3V2V4V5V6八、用標(biāo)號(hào)法求下列網(wǎng)絡(luò)V1→V7的最短路徑及路長(zhǎng)。VV1V7V5V6V4V3V2543531761731九、下圖是某一工程施工網(wǎng)絡(luò)圖(統(tǒng)籌圖)，圖中邊上的數(shù)字為工序時(shí)間(天)，請(qǐng)求出各事項(xiàng)的最早時(shí)間和最遲時(shí)間，求出關(guān)鍵路線，確定計(jì)劃工期。223145651249105094十、某企業(yè)生產(chǎn)三種產(chǎn)品A1、A2、A3。每種產(chǎn)品在銷售時(shí)可能出現(xiàn)銷路好(S1)，銷路一般(S2)和銷路差(S3)三種狀態(tài)，每種產(chǎn)品在不同銷售狀態(tài)的獲利情況(效益值)如表1所示，請(qǐng)按樂觀法則進(jìn)行決策，選取生產(chǎn)哪種產(chǎn)品最為合適。狀態(tài)效益值狀態(tài)效益值產(chǎn)品

S1

S2

S3A13010-6A220129A3151312(表1)十一、已知運(yùn)輸問題的運(yùn)價(jià)表和發(fā)量和收量如表2所示，請(qǐng)用最小元素法求出運(yùn)輸問題的一組可解釋。BB1B2B3B4A1291279A213524A31042653546(表2)十二、下列表3是一個(gè)指派問題的效率表(工作時(shí)間表)，其中Ai為工作人員(i=1,2,3,4)、Bj為工作項(xiàng)目(j=1,2,3,4)，請(qǐng)作工作安排，使總的工作時(shí)間最小。BB1B2B3B4A14174A22235A35643A46324 參考答案一、判斷題(1)×(2)√(3)√(4)×(5)√(6)×(7)√(8)√(9)×(10)√(11)×(12)×(13)√(14)×(15)×二、簡(jiǎn)述題1、在可行域內(nèi)先確定一個(gè)基本可行解，然后通過迭代計(jì)算，逐步使目標(biāo)函數(shù)增大（求Zmax），求出新解，計(jì)算出方案機(jī)會(huì)成本后，得出相應(yīng)檢驗(yàn)數(shù)，當(dāng)所有的Cj–Zj≤0時(shí)即得最優(yōu)解。2、運(yùn)輸問題可以用單純形求解，但由于虛設(shè)的變量多，運(yùn)算復(fù)雜，十分不合算，所以不用單純形法求解，而用簡(jiǎn)單的表上作業(yè)法求解。3、由于動(dòng)態(tài)規(guī)劃的求解過程是一個(gè)多段決定過程，其狀態(tài)變量必須滿足無后效性和可知性的特征要求。三、填空題1.樹2.破圈法和避圈法3.可行解、退化解、無界解、多重解4.匈牙利法5.確定性決策，不確定性決策，風(fēng)險(xiǎn)性決策。6.圈。四. c cj → 3 2 0 0 0 0Ci X0 b X1 X2 X3 X4 X5 X6 (3) X1 3 1 0 1/2 -1 0 1/2(2) X2 4 0 1 1 1/2 -1 0 Zj 3 2 7/2 -2 -2 3/2 Cj–Zj 0 0 (-7/2) (2) 2 -3/22.Smin=153.X4輸入，Xi輸出。五、Zmax=-7y1+16y2B1B1SA2710B39C213FC110710512149610568(32)(27)(17)(10)(0)(13)(16)(26)(18)S—A1—B1—C1—F32七、5252V1V2V44353V3V5V6424最小樹為圖中雙線所示，最小樹長(zhǎng)14VV2V5V7V6V2V4V1(v1,0)(v1,4)(v1,6)(v1,13)(v6,10)(v3,9)(v5,7)(v1,3)(v1,5)431573175631八、最短路徑：v1→v3→v5→v6→v7L①②①②④⑥③⑤4012510994550102031200102731620十、

S1

S2

S3

maxA13010-630A22012920A315131215選方案A1十一、BB1B2B3B4aiA12⑨12⑦9A2①35②6A310④②65bj3746………||||||||||||||||33436十二、BB1B2B3B4A14①74A2②235A3564③A463②4 B1 B B1 B2 B3 B4 3 … 0 … 6 … 3 | | | | | | | 0 … 0 … 1 … 3 | | | | | | | 2 … 3 … 1 … 0 | | | | | | | 4 … 1 … 0 … 2S=8(表3)《運(yùn)籌學(xué)》試題參考答案一、填空題（每空2分，共10分）1、在線性規(guī)劃問題中，若存在兩個(gè)最優(yōu)解時(shí)，必有相鄰的頂點(diǎn)是最優(yōu)解。2、樹圖中，任意兩個(gè)頂點(diǎn)間有且僅有一條鏈。3、線性規(guī)劃的圖解法適用于決策變量為兩個(gè)線性規(guī)劃模型。4、在線性規(guī)劃問題中，將約束條件不等式變?yōu)榈仁剿氲淖兞勘环Q為松弛變量。5、求解不平衡的運(yùn)輸問題的基本思想是設(shè)立虛供地或虛需求點(diǎn)，化為供求平衡的標(biāo)準(zhǔn)形式。6、運(yùn)輸問題中求初始基本可行解的方法通常有最小費(fèi)用法與西北角法兩種方法。7、稱無圈的連通圖為樹，若圖的頂點(diǎn)數(shù)為p，則其邊數(shù)為p－1。二、（每小題5分，共10分）用圖解法求解下列線性規(guī)劃問題：⑴⑵⑶⑷⑸⑴⑵⑶⑷⑸、⑹

⑵⑶⑷、⑸⑵⑶⑷、⑸⑹⑴解：從上圖分析，可行解域?yàn)閍bcde，最優(yōu)解為e點(diǎn)。由方程組解出x1=5，x2=3∴X*==（5，3）T∴minz=Z*=2×5+3=13三、（15分）一家工廠制造甲、乙、丙三種產(chǎn)品，需要三種資源——技術(shù)服務(wù)、勞動(dòng)力和行政管理。每種產(chǎn)品的資源消耗量、單位產(chǎn)品銷售后所能獲得的利潤(rùn)值以及這三種資源的儲(chǔ)備量如下表所示：技術(shù)服務(wù)勞動(dòng)力行政管理單位利潤(rùn)甲110210乙1426丙1564資源儲(chǔ)備量1006003001）建立使得該廠能獲得最大利潤(rùn)的生產(chǎn)計(jì)劃的線性規(guī)劃模型；（5分）2）用單純形法求該問題的最優(yōu)解。（10分）解：1）建立線性規(guī)劃數(shù)學(xué)模型：設(shè)甲、乙、丙三種產(chǎn)品的生產(chǎn)數(shù)量應(yīng)為x1、x2、x3，則x1、x2、x3≥0，設(shè)z是產(chǎn)品售后的總利潤(rùn)，則maxz=10x1+6x2+4x3s.t.2）用單純形法求最優(yōu)解：加入松弛變量x4，x5，x6，得到等效的標(biāo)準(zhǔn)模型：maxz=10x1+6x2+4x3+0x4+0x5+0x6s.t.列表計(jì)算如下：

CBXBb1064000θLx1x2x3x4x5x60x41001111001000x5600（10）45010600x630022600115000000010↑640000x4400（3/5）1/21－1/100200/310x16012/51/201/1001500x618006/550－1/51150104501002↑－10－106x2200/3015/65/3－1/6010x1100/3101/6－2/31/600x6100004－20110620/310/32/3000－8/3－10/3－2/30∴X*=（，，0，0，0，100）T∴maxz=10×+6×=四、（10分）用大M法或?qū)ε紗渭冃畏ㄇ蠼馊缦戮€性規(guī)劃模型：minz=540x1＋450x2＋720x3解：用大M法，先化為等效的標(biāo)準(zhǔn)模型：maxz/=－540x1－450x2－720x3s.t.增加人工變量x6、x7，得到：maxz/=－540x1－450x2－720x3－Mx6－Mx7大M法單純形表求解過程如下：

CBXBb－540－450－72000－M－MθLx1x2x3x4x5x6x7－Mx670359－101070/3－Mx730（9）530－10130/9=10/3－12－10－12MM－M－M12M－54010M－4512M－72－M－M00－Mx660010/3（8）－11/31－1/3－540x110/315/91/30－1/901/910/3/1/3=10-300+10/3-8M－－M－M/3+60－MM/3－600-150+10/38M-540MM/3－600－M/3+60－720x315/205/121－1/81/241/8－1/2415/2/5/12=18－540x15/61（5/12）01/24－1/8－1/241/85/6/5/12=2－540－572－720－135/2475/12－135/2－75/20125↑0135/2－475/12135/2－M75/2－M－720－450x320/3－1011/61/61/6－1/6x2212/5101/10－3/10－1/103/10－5700－360－450－7207515－75－15－18000－75－1575－M15－M∴該對(duì)偶問題的最優(yōu)解是x*=（0，2，，0，0）T最優(yōu)目標(biāo)函數(shù)值minz=－（－5700）=5700

五、（12分）給定下列運(yùn)輸問題：（表中數(shù)據(jù)為產(chǎn)地Ai到銷地Bj的單位運(yùn)費(fèi)）B1B2B3B4siA1A2A32011

86

59

10

2

187

4

15

1015dj

33

12121）用最小費(fèi)用法求初始運(yùn)輸方案，并寫出相應(yīng)的總運(yùn)費(fèi)；（4分）2）用1）得到的基本可行解，繼續(xù)迭代求該問題的最優(yōu)解。（10分）解：用“表上作業(yè)法”求解。1）先用最小費(fèi)用法（最小元素法）求此問題的初始基本可行解：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4SiA1201186532××A25910210×××10A31874115×1122dj331212303032B32B1B2A11212B1212B2B4A3B310A2B4Z=20×3+11×2+2×10+7×1+4×12+1×2=1592）①用閉回路法，求檢驗(yàn)數(shù)：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4SiA12011806－1532××A25129－110－5210×××10A318－274115×1122dj3312123030∵=12＞0，其余≤0∴選作為入基變量迭代調(diào)整。②用表上閉回路法進(jìn)行迭代調(diào)整：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4SiA12011812611523××A259－1310－152101××9A318－147－124115××123dj3312123030再選作為入基變量迭代調(diào)整。地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4SiA120－121186－15×32×A259－110－52103××7A318－14704115××105dj3312123030調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)≤0，已得最優(yōu)解?！嘧顑?yōu)方案為：332B2B3A13737B1B4A2105B3B4A3最小運(yùn)費(fèi)Z=11×3+8×2+5×3+2×7+4×10+1×5=123六、（8分）一個(gè)公司經(jīng)理要分派4個(gè)推銷員去4個(gè)地區(qū)推銷某種商品。4個(gè)推銷員各有不同的經(jīng)驗(yàn)和能力，因而他們?cè)诿恳坏貐^(qū)能獲得的利潤(rùn)不同，其估計(jì)值如下表所示：D1D2D3D4甲35272837乙28342940丙35243233丁24322528問：公司經(jīng)理應(yīng)怎樣分派4個(gè)推銷員才使總利潤(rùn)最大？解：用求極大值的“匈牙利法”求解。效率矩陣表示為：行約簡(jiǎn)M－CijM=40行約簡(jiǎn)M－CijM=40標(biāo)號(hào)列約簡(jiǎn)所畫（）0元素少于n（n＝4），未得到最優(yōu)解，需要繼續(xù)變換矩陣（求能覆蓋所有0元素的最少數(shù)直線集合）：標(biāo)號(hào)列約簡(jiǎn)√√√√√√標(biāo)號(hào)未被直線覆蓋的最小元素為cij=2,在未被直線覆蓋處減去2，在直線交叉處加上2。標(biāo)號(hào)∴得最優(yōu)解：∴使總利潤(rùn)為最大的分配任務(wù)方案為：甲→D1，乙→D4，丙→D3，丁→D2此時(shí)總利潤(rùn)W=35+40+32+32=139七、（6分）計(jì)算下圖所示的網(wǎng)絡(luò)從A點(diǎn)到M點(diǎn)的最短路線及其長(zhǎng)度。11B11B117457117457885MG1317DA5MG1317DA9999956895684HIEFC4HIEFC6868解：此為動(dòng)態(tài)規(guī)劃之“最短路問題”，可用逆向追蹤“圖上標(biāo)號(hào)法”解決如下：21121121121111B11B754811775481172616502616505MG1317DA5MG1317DA9999895689564HIEFC4HIEFC68681810918109最佳策略為：A→C→F→G→M此時(shí)的最短距離為8+8+5+5=26八、（8分）用P→T標(biāo)號(hào)法求下圖從至的最短路。（需寫出最短路線）v8vv8v5v231313971v115v6623971v115v66226v91v48v126v91v48v1744132174413211v109v7v31v109v7v3解：此為網(wǎng)絡(luò)分析之“最短路問題”，可用順向追蹤“TP標(biāo)號(hào)法”解決如下：v5v2v8v5v2v81132v1031v103120410v68v423971v115620410v68v423971v1156826v91826v91714413271441321v109v7v31v109v7v387158715v1到v7的最短路線是：v1→v2→v5→v9→v8→v11，最短距離2+1+1+7+9=20。

九、（10分）用找增廣鏈的方法求如下網(wǎng)絡(luò)的最大流。（需寫出相應(yīng)的增廣鏈）（弧旁的數(shù)字為該弧容量）v4v4v1117344734423vtv3vs23vtv3vs85310853104v5v24v5v2解：此為網(wǎng)絡(luò)分析之“尋求網(wǎng)絡(luò)最大流問題”，可用“尋求網(wǎng)絡(luò)最大流的標(biāo)號(hào)法（福特—富克爾遜算法）”解決如下：㈠標(biāo)號(hào)過程：1、給vs標(biāo)上（0，∞）；2、檢查vs，在?。╲s，v1）上，fs1=0，Cs1=4，fs1<Cs1，給v1標(biāo)號(hào)(s，β(v1))，其中，（s，4）（s，4）v4v11173447344（0，∞）23vtv3vs（0，∞）23vtv3vs85310853104v5v24v5v2（（s，10）同理，給v2標(biāo)號(hào)(s，β(v2))，其中，3、檢查v1，在弧（v1，v3）上，f13=0，C13=3，f13<C13，給v3標(biāo)號(hào)(1，β(v3))，其中，（3，3）（s，4）（3，3）（s，4）v4v11173447344（0，∞）23vtv3vs（0，∞）23vtv3vs（1，3）85310（1，3）853104v5v24v5v2（2，4）（（2，4）（s，10）檢查v3，同理，給v4標(biāo)號(hào)(3，β(v4))，其中，檢查v2，同理，給v5標(biāo)號(hào)(2，β(v5))，其中，4、檢查v4，在?。╲4，vt）上，f4t=0，C4t=7，f4t<C4t，給vt標(biāo)號(hào)(4，β(vt))，其中，vt得到標(biāo)號(hào)，標(biāo)號(hào)過程結(jié)束。（3，3）（s，4）（3，3）（s，4）v4v11173447344（4，3）（0，∞）23vtv3vs（4，3）（0，∞）23vtv3vs（1，3）85310（1，3）853104v5v24v5v2（2，4）（（2，4）（s，10）㈡調(diào)整過程：從vt開始逆向追蹤，找到增廣鏈。（3，3）（s，4）（3，3）（s，4）v4v11173447344（4，3）（0，∞）23vtv3vs（4，3）（0，∞）23vtv3vs（1，3）85310（1，3）853104v5v24v5v2（2，4）（（2，4）（s，10）μ（vs，v1，v3，v4，vt），=3，在μ上進(jìn)行流量=3的調(diào)整，得可行流f'如圖所示：v4v4v1（1，0）（1，0）（7，3）（4，3（7，3）（4，3）（4，3）（3，3）（2，0）（3，0）vtv3vs（2，0）（3，0）vtv3vs（10，0）（8，0）（5，0）（3，0）（10，0）（8，0）（5，0）（3，0）（4，0）v5v2（4，0）v5v2去掉各點(diǎn)標(biāo)號(hào)，從vs開始，重新標(biāo)號(hào)。

（3，1）（s，1）（3，1）（s，1）v4v1（1，0）（1，0）（7，3）（4，3）（4，3）（3，3）（7，3）（4，3）（4，3）（3，3）（4，1）（2，0）（3，0）（0，∞）vtv3vs（4，1）（2，0）（3，0）（0，∞）vtv3vs（10，0）（8，0）（5，0）（3，0）（2，3）（10，0）（8，0）（5，0）（3，0）（2，3）（4，0）v5v2（4，0）v5v2（2，4）（（2，4）（s，10）vt又得到標(biāo)號(hào)，標(biāo)號(hào)過程結(jié)束。再次從vt開始逆向追蹤，找到增廣鏈。（3，1）（s，1）（3，1）（s，1）v4v1（1，0）（1，0）（7，3）（4，3）（4，3）（3，3）（7，3）（4，3）（4，3）（3，3）（4，1）（2，0）（3，0）（0，∞）vtv3vs（4，1）（2，0）（3，0）（0，∞）vtv3vs（10，0）（8，0）（5，0）（3，0）（2，3）（10，0）（8，0）（5，0）（3，0）（2，3）（4，0）v5v2（4，0）v5v2（2，4）（（2，4）（s，10）μ（vs，v2，v3，v4，vt），=1，在μ上進(jìn)行流量=1的調(diào)整，得可行流f'如圖所示：

v4v4v1（1，0）（1，0）（7，4）（4，4（7，4）（4，4）（4，3）（3，3）（2，0）（3，0）vtv3vs（2，0）（3，0）vtv3vs（10，1）（8，0）（10，1）（8，0）（5，0）（3，1）（4，0）v5v2（4，0）v5v2去掉各點(diǎn)標(biāo)號(hào)，從vs開始，重新標(biāo)號(hào)。（1，1）（s，1）（1，1）（s，1）v4v1（1，0）（1，0）（7，4）（4，4）（4，3）（3，3）（7，4）（4，4）（4，3）（3，3）（4，1）（2，0）（3，0）（0，∞）vtv3vs（4，1）（2，0）（3，0）（0，∞）vtv3vs（10，1）（8，0）（5，0）（3，1）（2，2）（10，1）（8，0）（5，0）（3，1）（2，2）（4，0）v5v2（4，0）v5v2（2，4）（（2，4）（s，9）vt又得到標(biāo)號(hào)，標(biāo)號(hào)過程結(jié)束。再次從vt開始逆向追蹤，找到增廣鏈。

（1，1）（s，1）（1，1）（s，1）v4v1（1，0）（1，0）（7，4）（4，4）（4，3）（3，3）（7，4）（4，4）（4，3）（3，3）（4，1）（2，0）（3，0）（0，∞）vtv3vs（4，1）（2，0）（3，0）（0，∞）vtv3vs（10，1）（8，0）（5，0）（3，1）（2，2）（10，1）（8，0）（5，0）（3，1）（2，2）（4，0）v5v2（4，0）v5v2（2，4）（（2，4）（s，9）μ（vs，v1，v4，vt），=1，在μ上進(jìn)行流量=1的調(diào)整，得可行流f'如圖所示：v4v4v1（1，1）（1，1）（7，5）（4，4）（4，（7，5）（4，4）（4，4）（3，3）（2，0）（3，0）vtv3vs（2，0）（3，0）vtv3vs（10，1）（8，0）（5，0）（3，1）（10，1）（8，0）（5，0）（3，1）（4，0）v5v2（4，0）v5v2去掉各點(diǎn)標(biāo)號(hào)，從vs開始，重新標(biāo)號(hào)。

（5，2）（-3，2）v4（5，2）（-3，2）v4v1（1，1）（1，1）（7，5）（4，4）（4，4）（3，3）（7，5）（4，4）（4，4）（3，3）（4，2）（2，0）（3，0）（0，∞）vtv3vs（4，2）（2，0）（3，0）（0，∞）vtv3vs（2，2）（10，1）（8，0）（5，0）（3，1）（2，2）（10，1）（8，0）（5，0）（3，1）（4，0）v5v2（4，0）v5v2（2，4）（（2，4）（s，9）vt又得到標(biāo)號(hào)，標(biāo)號(hào)過程結(jié)束。再次從vt開始逆向追蹤，找到增廣鏈。（5，2）（-3，2）v4（5，2）（-3，2）v4v1（1，1）（1，1）（7，5）（4，4）（4，4）（3，3）（7，5）（4，4）（4，4）（3，3）（4，2）（2，0）（3，0）（0，∞）vtv3vs（4，2）（2，0）（3，0）（0，∞）vtv3vs（2，2）（10，1）（8，0）（5，0）（3，1）（2，2）（10，1）（8，0）（5，0）（3，1）（4，0）v5v2（4，0）v5v2（2，4）（（2，4）（s，9）μ（vs，v2，v5，v4，vt），=2，在μ上進(jìn)行流量=2的調(diào)整，得可行流f'如圖所示：

v4v4v1（1，1）（1，1）（7，7）（4，4）（4，4）（7，7）（4，4）（4，4）（3，3）（2，2）（3，0）vtv3vs（2，2）（3，0）vtv3vs（10，3）（8，0）（10，3）（8，0）（5，0）（3，1）（4，2）v5（4，2）v5v2去掉各點(diǎn)標(biāo)號(hào)，從vs開始，重新標(biāo)號(hào)。（-t，3）（-3，3）v4（-t，3）（-3，3）v4v1（1，1）（1，1）（7，7）（4，4）（4，4）（3，3）（7，7）（4，4）（4，4）（3，3）（5，3）（2，2）（3，0）（0，∞）vtv3vs（5，3）（2，2）（3，0）（0，∞）vtv3vs（s，3）（10，3）（8，0）（5，0）（3，1）（s，3）（10，3）（8，0）（5，0）（3，1）（4，2）v5v2（4，2）v5v2（3，3）（（3，3）（s，7）vt又得到標(biāo)號(hào)，標(biāo)號(hào)過程結(jié)束。再次從vt開始逆向追蹤，找到增廣鏈。

（-t，3）（-3，3）v4（-t，3）（-3，3）v4v1（1，1）（1，1）（7，7）（4，4）（4，4）（3，3）（7，7）（4，4）（4，4）（3，3）（5，3）（2，2）（3，0）（0，∞）vtv3vs（5，3）（2，2）（3，0）（0，∞）vtv3vs（s，3）（10，3）（8，0）（5，0）（3，1）（s，3）（10，3）（8，0）（5，0）（3，1）（4，2）v5v2（4，2）v5v2（3，3）（（3，3）（s，7）μ（vs，v3，v5，vt），=3，在μ上進(jìn)行流量=3的調(diào)整，得可行流f'如圖所示v4v4v1（1，1）（1，1）（7，7）（4，4）（4，4）（3，3）（7，7）（4，4）（4，4）（3，3）（2，2）（3，3）vtv3vs（2，2）（3，3）vtv3vs（10，3）（8，3）（10，3）（8，3）（5，3）（3，1）（4，2）v5v2（4，2）v5v2去掉各點(diǎn)標(biāo)號(hào)，從vs開始，重新標(biāo)號(hào)。

（-t，1）（-3，1）v4（-t，1）（-3，1）v4v1（1，1）（1，1）（7，7）（4，4）（4，4）（3，3）（7，7）（4，4）（4，4）（3，3）（5，1）（2，2）（3，3）（0，∞）vtv3vs（5，1）（2，2）（3，3）（0，∞）vtv3vs（2，1）（10，3）（8，3）（5，3）（3，1）（2，1）（10，3）（8，3）（5，3）（3，1）（4，2）v5v2（4，2）v5v2（3，1）（（3，1）（s，7）vt又得到標(biāo)號(hào)，標(biāo)號(hào)過程結(jié)束。再次從vt開始逆向追蹤，找到增廣鏈。（-t，1）（-3，1）v4（-t，1）（-3，1）v4v1（1，1）（1，1）（7，7）（4，4）（4，4）（3，3）（7，7）（4，4）（4，4）（3，3）（5，1）（2，2）（3，3）（0，∞）vtv3vs（5，1）（2，2）（3，3）（0，∞）vtv3vs（2，1）（10，3）（8，3）（5，3）（3，1）（2，1）（10，3）（8，3）（5，3）（3，1）（4，2）v5v2（4，2）v5v2（3，1）（（3，1）（s，7）μ（vs，v2，v3，v5，vt），=2，在μ上進(jìn)行流量=2的調(diào)整，得可行流f'如圖所示