1、運(yùn)籌學(xué)演示課件,目 錄,第一章線性規(guī)劃 第二章對(duì)偶 第三章整數(shù)規(guī)劃 第四章運(yùn)輸問題 第五章網(wǎng)絡(luò)優(yōu)化 第六章動(dòng)態(tài)規(guī)劃 第七章排 隊(duì) 論,第一章 線性規(guī)劃,線性規(guī)劃模型 線性規(guī)劃的圖解 可行域的性質(zhì) 線性規(guī)劃的基本概念 基礎(chǔ)解、基礎(chǔ)可行解 單純形表 線性規(guī)劃的矩陣表示,線性規(guī)劃模型,線性規(guī)劃模型的結(jié)構(gòu) 目標(biāo)函數(shù) ：max，min 約束條件：,=, 變量符號(hào)：0, unr, 0 線性規(guī)劃的標(biāo)準(zhǔn)形式 目標(biāo)函數(shù)：min 約束條件：= 變量符號(hào)：0,線性規(guī)劃的圖解,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目標(biāo)函數(shù)等值線,最優(yōu)解,6,4,-8,6,0

2、,x1,x2,可行域的性質(zhì),線性規(guī)劃的可行域是凸集 線性規(guī)劃的最優(yōu)解在極點(diǎn)上,凸集,凸集,不是凸集,極點(diǎn),線性規(guī)劃的基本概念,線性規(guī)劃的基矩陣、基變量、非基變量,=,=,目標(biāo)函數(shù),約束條件,行列式0 基矩陣,右邊常數(shù),基變量x1、x2、x3，非基變量x4、x5、x6,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。 目標(biāo)函數(shù)值為：z=20,基變量x1、x2、x4，非基變量x3、x5、x6,基礎(chǔ)解為 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。 目標(biāo)函數(shù)值為

3、：z=18,基變量x1、x2、x5，非基變量x3、x4、x6,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基礎(chǔ)解，但不是可行解，不是一個(gè)極點(diǎn)。,基變量x1、x2、x6，非基變量x3、x4、x5,基礎(chǔ)解為（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。 目標(biāo)函數(shù)值為：z=18,基變量x2、x3、x4，非基變量x1、x5、x6,基礎(chǔ)解為 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0） 是基礎(chǔ)解，但不是可行解。,基變量x1、x2、x3，非基變量x4、x5、x6,基礎(chǔ)解為（x

4、1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0） 是基礎(chǔ)可行解，表示可行域的一個(gè)極點(diǎn)。 目標(biāo)函數(shù)值為：z=15,基變量x1、x2、x3，非基變量x4、x5、x6,基礎(chǔ)解為 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基礎(chǔ)解但不是可行解。,目標(biāo)函數(shù),約束條件,基矩陣,右邊常數(shù),進(jìn)基變量、離基變量、基變換,基變量,進(jìn)基變量,離基變量,目標(biāo)函數(shù),約束條件,右邊常數(shù),目標(biāo)函數(shù),約束條件,新的基矩陣,右邊常數(shù),進(jìn)基變量,離基變量,目標(biāo)函數(shù),約束條件,基矩陣,目標(biāo)函數(shù),約束條件,新的基矩陣,右邊常數(shù),基礎(chǔ)解、基礎(chǔ)可行解,max z=x1+3x2D s

5、.t. x1+ x2+x3=6 B -x1+2x2 +x4=8 x4=0 C x3=0 x1, x2,x3,x40 x1=0 E O x2=0 A,幾何概念,代數(shù)概念,約束直線,滿足一個(gè)等式約束的解,約束半平面,滿足一個(gè)不等式約束的解,約束半平面的交集： 凸多邊形,滿足一組不等式約束的解,約束直線的交點(diǎn),基礎(chǔ)解,可行域的極點(diǎn),基礎(chǔ)可行解,目標(biāo)函數(shù)等值線： 一組平行線,目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解,單純形表,求解線性規(guī)劃問題,寫成標(biāo)準(zhǔn)化形式,寫出單純形表,25/1,36/2,0,-3,-2,0,-2,-72,0,1,1/2,0,1,-1/2,7/1/2,1,x5,1/2,1,0,1/2,18/1/

6、2,0,7,18,1,1/2,1/2,x2,0,x6離基，,x2進(jìn)基，,x5離基，,x1進(jìn)基，,0,-4,-2,-2,-1,-86,0,1,1,0,2,-1,1,x1,0,1,-1,1,0,14,11,0,1,0,x2,0,得到最優(yōu)解，最優(yōu)解為：,（x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0） min z=-86，max z=86,線性規(guī)劃的矩陣表示,=,=,CBTB-1aj-cj=zj-cj 稱為非基變量的檢驗(yàn)數(shù)（Reduced Cost） B-1aj=Yj， B-1b= ，CBTB-1b=z0,第二章 對(duì)偶線性規(guī)劃,對(duì)偶的定義 對(duì)偶問題的性質(zhì) 原始對(duì)偶關(guān)系 目標(biāo)函數(shù)

7、值之間的關(guān)系 最優(yōu)解之間的關(guān)系互補(bǔ)松弛關(guān)系 最優(yōu)解的Kuhn-Tucher條件 對(duì)偶可行基對(duì)偶單純形法 對(duì)偶的經(jīng)濟(jì)解釋,DUAL,一、對(duì)偶的定義,原始問題 min z=CTX s.t.AXb X 0,對(duì)偶問題 max y=bTW s.t. ATWC W 0,min,b,A,CT,C,AT,bT,max,m,n,m,n,二、對(duì)偶問題的性質(zhì),1、對(duì)偶的對(duì)偶就是原始問題,2、其他形式問題的對(duì)偶,三、原始對(duì)偶關(guān)系,1、可行解的目標(biāo)函數(shù)值之間的關(guān)系 設(shè)XF、WF分別是原始問題和對(duì)偶問題的可行解 z=CTXF WTAXF WTb=y 2、最優(yōu)解的目標(biāo)函數(shù)值之間的關(guān)系 設(shè)Xo、Wo分別是原始問題和對(duì)偶問題的

8、最優(yōu)解 z=CTXo=WoTAXo=WoTb=y,3、原始問題和對(duì)偶問題最優(yōu)解之間的互補(bǔ)松弛關(guān)系,min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW+WS=C W, WS0,min z=CTX s.t. AXb X 0,max y=bTW s.t. ATWC W0,互補(bǔ)松弛關(guān)系,min z=CTX s.t.AX-XS=b X, XS 0,max y=bTW s.t. ATW+WS=C W, WS 0,XTWS=0 WTXS=0,m,n,=,W,WS,AT,I,C,n,=,A,XS,-I,b,n,m,m,X,原始問題和對(duì)偶問題變量、松弛變量的維數(shù),w

9、1 wi wm wm+1 wm+j wn+m,x1 xj xn xn+1 xn+i xn+m,對(duì)偶問題的變量 對(duì)偶問題的松弛變量,原始問題的變量 原始問題的松弛變量,xjwm+j=0wixn+i=0(i=1,2,m; j=1,2,n) 在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0,Kuhn-Tucher 條件,3、原始問題和對(duì)偶問題最優(yōu)解的充分必要條件 (1)原始可行條件（PFC） AX-XS=b X, XS 0 (2)對(duì)偶可行條件（DFC） ATW+WS=C W, WS 0 (3)互補(bǔ)松弛條件（CSC） XTWS=0 WTXS=0,四、對(duì)偶單純形法,1、用單純形表求解原始問題的四種形式,m

10、in z=CTX s.t. AXb X 0,min z=CTX s.t. AX b X 0,max z=CTX s.t. AX b X 0,max z=CTX s.t. AX b X 0,（2）,（3）,（4）,（1）,單純形表和對(duì)偶(1),min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW+WS=C W, WS0,min z=CTX s.t. AXb X 0,max y=bTW s.t. ATWC W0,對(duì)偶問題,原始問題,引進(jìn)松弛變量,引進(jìn)松弛變量,min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW

11、+WS=C W, WS0,WT=CBTB-1 WST=CT-WTA,min z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW+WS=C W 0, WS0,min z=CTX s.t. AX b X 0,max y=bTW s.t. ATWC W 0,單純形表和對(duì)偶(2),對(duì)偶問題,原始問題,引進(jìn)松弛變量,引進(jìn)松弛變量,min z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW+WS=C W 0, WS0,WT=CBTB-1 WST=CT-WTA,max z=CTX s.t. AX-XS=b X, XS0,max y=

12、bTW s.t. ATW-WS=C W 0, WS0,max z=CTX s.t. AX b X 0,min y=bTW s.t. ATW C W 0,單純形表和對(duì)偶(3),對(duì)偶問題,原始問題,引進(jìn)松弛變量,引進(jìn)松弛變量,max z=CTX s.t. AX-XS=b X, XS0,min y=bTW s.t. ATW-WS=C W 0, WS0,WT=CBTB-1 WST=WTA- CT,max z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW-WS=C W, WS0,max z=CTX s.t. AX b X 0,min y=bTW s.t. ATW

13、C W 0,單純形表和對(duì)偶(4),對(duì)偶問題,原始問題,引進(jìn)松弛變量,引進(jìn)松弛變量,max z=CTX s.t. AX+XS=b X, XS0,min y=bTW s.t. ATW-WS=C W, WS0,WT=CBTB-1 WST=WTA- CT,2、對(duì)偶單純形法（初始解原始不可行的問題）,已獲得最優(yōu)解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35 對(duì)偶問題的最優(yōu)解為： （w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35,3、初始解原始、對(duì)偶都不可行的問題,解法1：先解決原始可

14、行性,在得到原始可行解時(shí)同時(shí)得到對(duì)偶可行解，已獲得最優(yōu)解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 對(duì)偶問題的最優(yōu)解為： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,解法2：先解決對(duì)偶可行性,已得到對(duì)偶可行解，再用對(duì)偶單純形法求解,得到原始可行解，已獲得最優(yōu)解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 對(duì)偶問題的最優(yōu)解為： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0

15、, 0, 0） max y=17,五、對(duì)偶的經(jīng)濟(jì)解釋,1、原始問題是利潤最大化的生產(chǎn)計(jì)劃問題,單位產(chǎn)品的利潤（元/件）,產(chǎn)品產(chǎn)量（件）,總利潤（元）,資源限量（噸）,單位產(chǎn)品消耗的資源（噸/件）,剩余的資源（噸）,消耗的資源（噸）,2、對(duì)偶問題,資源限量（噸）,資源價(jià)格（元/噸）,總利潤（元）,對(duì)偶問題是資源定價(jià)問題，對(duì)偶問題的最優(yōu)解w1、w2、.、wm稱為m種資源的影子價(jià)格（Shadow Price）,原始和對(duì)偶問題都取得最優(yōu)解時(shí)，最大利潤 max z=min y,3、資源影子價(jià)格的性質(zhì),影子價(jià)格越大，說明這種資源越是相對(duì)緊缺 影子價(jià)格越小，說明這種資源相對(duì)不緊缺 如果最優(yōu)生產(chǎn)計(jì)劃下某種資源

16、有剩余，這種資源的影子價(jià)格一定等于0,w1 w2 wm,4、產(chǎn)品的機(jī)會(huì)成本,機(jī)會(huì)成本 表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤,增加單位資源可以增加的利潤,減少一件產(chǎn)品可以節(jié)省的資源,機(jī)會(huì)成本,利潤,差額成本,5、產(chǎn)品的差額成本（Reduced Cost）,差額成本=機(jī)會(huì)成本 - 利潤,5、互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋,在利潤最大化的生產(chǎn)計(jì)劃中 （1）邊際利潤大于0的資源沒有剩余 （2）有剩余的資源邊際利潤等于0 （3）安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本等于利潤 （4）機(jī)會(huì)成本大于利潤的產(chǎn)品不安排生產(chǎn),第四章 運(yùn)輸問題,運(yùn)輸問題的表示 網(wǎng)絡(luò)圖、線性規(guī)劃模型、運(yùn)輸表 初始基礎(chǔ)可行解 西北角法、最小元素法 非基變

17、量的檢驗(yàn)數(shù) 閉回路法、對(duì)偶變量法 確定進(jìn)基變量，調(diào)整運(yùn)量，確定離基變量,2,3,2,1,3,4,1,運(yùn)輸問題網(wǎng)絡(luò)圖,s2=27,s3=19,d1=22,d2=13,d3=12,d4=13,s1=14,供應(yīng)量,供應(yīng)地,運(yùn)價(jià),需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,運(yùn)輸問題線性規(guī)劃模型,供應(yīng)地約束,需求地約束,運(yùn)輸問題的表格表示,初始基礎(chǔ)可行解西北角法,8,13,13,14,6,6,初始基礎(chǔ)可行解最小元素法（1）,最小元素法（2）,最小元素法（3）,最小元素法（4）,最小元素法（5）,最小元素法（6）,-5,非基變量xij的檢驗(yàn)數(shù)zij-cij閉回路法(1),z12-c1

18、2=(c11-c21+c22)-c12=6-8+4-7=-5,-5,閉回路法(2),z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5,-5,-5,閉回路法(3),z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7,-7,-5,-5,閉回路法(4),z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9,-9,-5,-7,-5,閉回路法(5),z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11,+11,-5,-7,-9,-5,閉回路法(6),z

19、32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3,+3,-5,-7,-9,+11,非基變量xij的檢驗(yàn)數(shù)zij-cij對(duì)偶變量法(1),v4=0,對(duì)偶變量法(2),u3+v4=c34u3=6,對(duì)偶變量法(3),u3+v3=c33v3=4,對(duì)偶變量法(4),u2+v3=c23u2=-2,對(duì)偶變量法(5),u2+v2=c22v2=6,對(duì)偶變量法(6),u2+v1=c21v1=10,對(duì)偶變量法(7),u1+v1=c11u1=-4,對(duì)偶變量法(8),z12-c12=u1+v2-c12=(-4)+6-7=-5,-5,對(duì)偶變量法(9),z13-c13=u1+v3-c13=(-

20、4)+4-5=-5,-5,-5,對(duì)偶變量法(10),z14-c14=u1+v4-c14=(-4)+0-3=-7,-7,-5,-5,對(duì)偶變量法(11),z24-c24=u2+v4-c24=(-2)+0-7=-9,-9,-5,-5,-7,對(duì)偶變量法(12),z31-c31=u3+v1-c31=6+10-5=11,11,-5,-5,-7,-9,對(duì)偶變量法(13),z32-c32=u3+v2-c32=6+6-9=+3,+3,-5,-5,-7,-9,11,選擇進(jìn)基變量,確定離基變量,x31進(jìn)基, minx21,x33=min8,6=6, x33離基,+3,-5,-5,-7,-9,11,調(diào)整運(yùn)量,重新計(jì)算

21、檢驗(yàn)數(shù),確定進(jìn)基、離基變量,x14進(jìn)基, minx11,x34=min14,13=13, x34離基,-11,-5,-5,+4,+2,-8,調(diào)整運(yùn)量, 重新計(jì)算檢驗(yàn)數(shù),所有zij-cij0,得到最優(yōu)解。 Min z=61+3 13+8 2+4 13+2 12+5 19=142,-11,-5,-5,-4,-8,-2,第五章 網(wǎng)絡(luò)優(yōu)化,網(wǎng)絡(luò)的基本概念 網(wǎng)絡(luò)最小費(fèi)用流問題 網(wǎng)絡(luò)最大流問題 最短路徑問題,網(wǎng)絡(luò)的基本概念,節(jié)點(diǎn)與（有向）邊 每一條邊和兩個(gè)節(jié)點(diǎn)關(guān)聯(lián)，一條邊可以用兩個(gè)節(jié)點(diǎn)的標(biāo)號(hào)表示（i，j）,路徑（Path） 前后相繼并且方向相同的邊序列 P=(1,2),(2,3),(3,4),4,2,3,

22、1,4,2,3,1,網(wǎng)絡(luò)由節(jié)點(diǎn)和邊組成,回路（Circuit） 起點(diǎn)和終點(diǎn)重合的路徑稱為回路 =(1,2),(2,4),(4,1) 回路中各條邊方向相同,4,2,3,1,鏈（Chain） 前后相繼并且方向不一定相同的邊序列稱為鏈 C=(1,2),(3,2),(3,4),4,2,3,1,連通圖 任意兩個(gè)節(jié)點(diǎn)之間至少有一條鏈的圖稱為連通圖,2,4,3,5,1,圈(Cycle) 起點(diǎn)和終點(diǎn)重合的鏈稱為圈 =(1,2),(2,4),(3,4),(1,3) 圈中各條邊方向不一定相同,4,2,3,1,樹(Tree) 無圈的連通圖稱為樹 樹中只與一條邊關(guān)聯(lián)的節(jié)點(diǎn)稱為懸掛節(jié)點(diǎn),樹的性質(zhì),任何樹至少有一個(gè)懸掛節(jié)

23、點(diǎn),2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,如果樹的節(jié)點(diǎn)個(gè)數(shù)為m，則邊的個(gè)數(shù)為m-1,樹中任意兩個(gè)節(jié)點(diǎn)之間只有唯一的一條鏈,在樹的任意兩個(gè)不相鄰的節(jié)點(diǎn)之間增加一條邊，則形成唯一的圈,網(wǎng)絡(luò)的生成樹,由網(wǎng)絡(luò)的所有節(jié)點(diǎn)（m個(gè)）和網(wǎng)絡(luò)的m-1條邊組成的樹稱為網(wǎng)絡(luò)的生成樹，網(wǎng)絡(luò)中不屬于生成樹的邊稱為生成樹的弦,網(wǎng)絡(luò)的生成樹的變換,網(wǎng)絡(luò)的一個(gè)生成樹，增加一條弦，形成唯一的圈，去掉生成樹的一條邊，得到一個(gè)新的網(wǎng)絡(luò)的生成樹,生成樹2,生成樹3,生成樹1,/,/,網(wǎng)絡(luò)的生成樹和線性規(guī)劃的關(guān)系,網(wǎng)絡(luò)的一個(gè)生成樹對(duì)應(yīng)于線性規(guī)劃的一個(gè)基 生成樹上的邊對(duì)應(yīng)于線性規(guī)劃的基變量 生成樹的弦對(duì)應(yīng)于線性規(guī)劃

24、的非基變量 生成樹的變換對(duì)應(yīng)于線性規(guī)劃單純形法的進(jìn)基和離基變換,網(wǎng)絡(luò)最小費(fèi)用流問題,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,c24=5,c46=1,c13=3,c35=2,c56=4,c34=4,c12=6,cij 單位流量的費(fèi)用,初始基礎(chǔ)可行解生成樹,b6=-5,b2=-2,b4=3,b3=5,b5=-6,b1=5,x13=3,x46=3,x35=8,x56=2,x12=2,2,3,4,5,6,1,確定非基變量x24和x34,b2=-2,b6=-5,b3=5,b5=-6,b1=5,c24=5,c46=1,c13=3,c35=2,c56=4,c34=4,c12=6,2

25、,3,4,5,6,1,b4=3,求x24的檢驗(yàn)數(shù)z24-c24 閉回路法,z24 -c24 =(-c46+c56+c35+c13-c12)-c24=(-1+4+2+3-6)-5=-3,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,c24=5,c46=1,c13=3,c35=2,c56=4,c12=6,2,3,4,5,6,1,求x34的檢驗(yàn)數(shù)z34 -c34 閉回路法,z34 -c34 =(-c46+c56+c35)-c34=(-1+4+2)-4=+1，x34進(jìn)基,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,c46=1,c13=3,c35=2,c56=4

26、,c34=4,c12=6,2,3,4,5,6,1,變量x34進(jìn)基，確定離基變量,minx56,x35=min2,8=2, x56離基，調(diào)整流量，進(jìn)行基變換,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,x46=3,x13=3,x35=8,x56=2,x34=0,x12=2,2,3,4,5,6,1,確定非基變量x24和x56,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,x46=5,x13=3,x35=6,x34=2,x12=2,2,3,4,5,6,1,計(jì)算x24和x56的檢驗(yàn)數(shù)z24 -c24 、z56-c56,z24 -c24 =(c34+c13-c1

27、2)-c24=(4+3-6)-5= -4 z56 -c56 =(c46+c34-c35)-c56=(1+4-2)-4= -1，獲得最優(yōu)解,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,c24=5,c46=1,c13=3,c35=2,c56=4,c34=4,c12=6,2,3,4,5,6,1,最優(yōu)解,最優(yōu)解的目標(biāo)函數(shù)值為：min z=62+33+42+26+15=46,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,x46=5,x13=3,x35=6,x34=2,x12=2,2,3,4,5,6,1,網(wǎng)絡(luò)最大流問題,邊的容量和流量 容量uij，流量xij 可行

28、流 滿足以下條件的流稱為可行流： 1、每一個(gè)節(jié)點(diǎn)流量平衡 2、0 xij uij,邊的容量和流量、可行流,飽和邊、不飽和邊、流量的間隙,（1，2）是飽和的,2、如果xijuij，邊從i到j(luò)的方向是不飽和的；,（1，2）是不飽和的 間隙為12=u12-x12=5-3=2,1、如果xij=uij，邊從i到j(luò)的方向是飽和的；,3、如果xij=0，邊從j到i的方向是飽和的；,（2，1）是飽和的,如果xij0，邊從j到i的方向是不飽和的；,（2，1）是不飽和的 間隙為12=x12=5,給出一個(gè)初始的可行流xij=0,找到所有的不飽和邊，以及各邊可以調(diào)整流量的方向,2,3,5,4,6,7,1,f=0,f=

29、0,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,找到一條從1到7的不飽和鏈,鏈的間隙為： = min8,3,1,8=1 調(diào)整鏈的流量：xij=xij+ ,2,3,5,4,6,7,1,f=0,f=0,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,=3,=1,=8,=8,x=0,調(diào)整流量，f=1。繼續(xù)求出網(wǎng)絡(luò)的不飽和

30、邊,2,3,5,4,6,7,1,f=1,f=1,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=1,x=1,x=1,x=1,求出一條從1到7的不飽和鏈,2,3,5,4,6,7,1,f=1,f=1,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=1,x=1,x=1,x=1,=1,=6,=9,=7,=min 7,1,6,9=1, 調(diào)整流量 xij=xij+1, f=f+1=2,調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊,2,3,5,4,6,7,1,f=2,f=2,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,