浙大運(yùn)籌學(xué)PPT參考課件.ppt

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

2、 x1 0, x20,可行域,目標(biāo)函數(shù)等值線,最優(yōu)解,6,4,-8,6,0,x1,x2,5,可行域的性質(zhì),線性規(guī)劃的可行域是凸集 線性規(guī)劃的最優(yōu)解在極點(diǎn)上,凸集,凸集,不是凸集,極點(diǎn),6,線性規(guī)劃的基本概念,線性規(guī)劃的基矩陣、基變量、非基變量,=,=,目標(biāo)函數(shù),約束條件,行列式0 基矩陣,右邊常數(shù),7,8,基變量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,9,基變量x1、x2、x4，非基變量x3、x5、x6,基礎(chǔ)解為 （x1，x2，x3，x4，x5，x6）=

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

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

5、,18,進(jìn)基變量,離基變量,目標(biāo)函數(shù),約束條件,基矩陣,19,目標(biāo)函數(shù),約束條件,新的基矩陣,右邊常數(shù),20,基礎(chǔ)解、基礎(chǔ)可行解,max z=x1+3x2D s.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,21,幾何概念,代數(shù)概念,約束直線,滿足一個(gè)等式約束的解,約束半平面,滿足一個(gè)不等式約束的解,約束半平面的交集： 凸多邊形,滿足一組不等式約束的解,約束直線的交點(diǎn),基礎(chǔ)解,可行域的極點(diǎn),基礎(chǔ)可行解,目標(biāo)函數(shù)等值線： 一組平行線,目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解,22,單純形表,23,求解線性規(guī)劃問

6、題,寫成標(biāo)準(zhǔn)化形式,24,寫出單純形表,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/2,0,7,18,1,1/2,1/2,x2,0,x6離基，,x2進(jìn)基，,x5離基，,x1進(jìn)基，,25,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,26,27,28,29,30,線性規(guī)劃的矩陣表示,=

7、,=,31,32,33,34,CBTB-1aj-cj=zj-cj 稱為非基變量的檢驗(yàn)數(shù)（Reduced Cost） B-1aj=Yj， B-1b= ，CBTB-1b=z0,35,36,第二章 對偶線性規(guī)劃,對偶的定義 對偶問題的性質(zhì) 原始對偶關(guān)系 目標(biāo)函數(shù)值之間的關(guān)系 最優(yōu)解之間的關(guān)系互補(bǔ)松弛關(guān)系 最優(yōu)解的Kuhn-Tucher條件 對偶可行基對偶單純形法 對偶的經(jīng)濟(jì)解釋,DUAL,37,一、對偶的定義,原始問題 min z=CTX s.t.AXb X 0,對偶問題 max y=bTW s.t. ATWC W 0,min,b,A,CT,C,AT,bT,max,m,n,m,n,38,二、對偶問題

8、的性質(zhì),1、對偶的對偶就是原始問題,39,2、其他形式問題的對偶,40,三、原始對偶關(guān)系,1、可行解的目標(biāo)函數(shù)值之間的關(guān)系 設(shè)XF、WF分別是原始問題和對偶問題的可行解 z=CTXF WTAXF WTb=y 2、最優(yōu)解的目標(biāo)函數(shù)值之間的關(guān)系 設(shè)Xo、Wo分別是原始問題和對偶問題的最優(yōu)解 z=CTXo=WoTAXo=WoTb=y,41,3、原始問題和對偶問題最優(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,互

9、補(bǔ)松弛關(guān)系,42,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,原始問題和對偶問題變量、松弛變量的維數(shù),43,w1 wi wm wm+1 wm+j wn+m,x1 xj xn xn+1 xn+i xn+m,對偶問題的變量 對偶問題的松弛變量,原始問題的變量 原始問題的松弛變量,xjwm+j=0wixn+i=0(i=1,2,m; j=1,2,n) 在一對變量中，其中一個(gè)大于0，另一個(gè)一定等于0,44,Kuhn-T

10、ucher 條件,3、原始問題和對偶問題最優(yōu)解的充分必要條件 (1)原始可行條件（PFC） AX-XS=b X, XS 0 (2)對偶可行條件（DFC） ATW+WS=C W, WS 0 (3)互補(bǔ)松弛條件（CSC） XTWS=0 WTXS=0,45,四、對偶單純形法,1、用單純形表求解原始問題的四種形式,min 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）,46,單純形表和對偶(1),min z=CTX s.t. AX-XS=

11、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,對偶問題,原始問題,引進(jìn)松弛變量,引進(jìn)松弛變量,47,min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW+WS=C W, WS0,WT=CBTB-1 WST=CT-WTA,48,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.

12、ATWC W 0,單純形表和對偶(2),對偶問題,原始問題,引進(jìn)松弛變量,引進(jìn)松弛變量,49,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,50,max z=CTX s.t. AX-XS=b X, XS0,max y=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,單純形表和對偶(3),對偶問題,原始問題,引進(jìn)松弛變量,引進(jìn)松弛變量,51,max z=CTX s.t. A

13、X-XS=b X, XS0,min y=bTW s.t. ATW-WS=C W 0, WS0,WT=CBTB-1 WST=WTA- CT,52,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 C W 0,單純形表和對偶(4),對偶問題,原始問題,引進(jìn)松弛變量,引進(jìn)松弛變量,53,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-

14、CT,54,2、對偶單純形法（初始解原始不可行的問題）,55,56,57,已獲得最優(yōu)解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35 對偶問題的最優(yōu)解為： （w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35,58,3、初始解原始、對偶都不可行的問題,59,解法1：先解決原始可行性,60,61,在得到原始可行解時(shí)同時(shí)得到對偶可行解，已獲得最優(yōu)解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 對偶問題的最優(yōu)解為： （w1

15、, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,62,解法2：先解決對偶可行性,已得到對偶可行解，再用對偶單純形法求解,63,64,得到原始可行解，已獲得最優(yōu)解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 對偶問題的最優(yōu)解為： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,65,五、對偶的經(jīng)濟(jì)解釋,1、原始問題是利潤最大化的生產(chǎn)計(jì)劃問題,單位產(chǎn)品的利潤（元/件）,產(chǎn)品產(chǎn)量（件）,總利潤（元）,資源限量（噸）,單位

16、產(chǎn)品消耗的資源（噸/件）,剩余的資源（噸）,消耗的資源（噸）,66,2、對偶問題,資源限量（噸）,資源價(jià)格（元/噸）,總利潤（元）,對偶問題是資源定價(jià)問題，對偶問題的最優(yōu)解w1、w2、.、wm稱為m種資源的影子價(jià)格（Shadow Price）,原始和對偶問題都取得最優(yōu)解時(shí)，最大利潤 max z=min y,67,3、資源影子價(jià)格的性質(zhì),影子價(jià)格越大，說明這種資源越是相對緊缺 影子價(jià)格越小，說明這種資源相對不緊缺 如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0,68,w1 w2 wm,4、產(chǎn)品的機(jī)會成本,機(jī)會成本 表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤,增加單位資源可以增加的

17、利潤,減少一件產(chǎn)品可以節(jié)省的資源,69,機(jī)會成本,利潤,差額成本,5、產(chǎn)品的差額成本（Reduced Cost）,差額成本=機(jī)會成本 - 利潤,70,5、互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋,在利潤最大化的生產(chǎn)計(jì)劃中 （1）邊際利潤大于0的資源沒有剩余 （2）有剩余的資源邊際利潤等于0 （3）安排生產(chǎn)的產(chǎn)品機(jī)會成本等于利潤 （4）機(jī)會成本大于利潤的產(chǎn)品不安排生產(chǎn),71,第四章 運(yùn)輸問題,運(yùn)輸問題的表示 網(wǎng)絡(luò)圖、線性規(guī)劃模型、運(yùn)輸表 初始基礎(chǔ)可行解 西北角法、最小元素法 非基變量的檢驗(yàn)數(shù) 閉回路法、對偶變量法 確定進(jìn)基變量，調(diào)整運(yùn)量，確定離基變量,72,2,3,2,1,3,4,1,運(yùn)輸問題網(wǎng)絡(luò)圖,s2=27,

18、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,73,運(yùn)輸問題線性規(guī)劃模型,供應(yīng)地約束,需求地約束,74,運(yùn)輸問題的表格表示,75,初始基礎(chǔ)可行解西北角法,8,13,13,14,6,6,76,初始基礎(chǔ)可行解最小元素法（1）,77,最小元素法（2）,78,最小元素法（3）,79,最小元素法（4）,80,最小元素法（5）,81,最小元素法（6）,82,-5,非基變量xij的檢驗(yàn)數(shù)zij-cij閉回路法(1),z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5,83,

19、-5,閉回路法(2),z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5,-5,84,-5,閉回路法(3),z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7,-7,-5,85,-5,閉回路法(4),z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9,-9,-5,-7,86,-5,閉回路法(5),z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11,+11,-5,-7,-9,87,-5,閉回路法(6),z32-c32=(c22-c23+ c3

20、3)-c32=(4-2+10)-9=+3,+3,-5,-7,-9,+11,88,非基變量xij的檢驗(yàn)數(shù)zij-cij對偶變量法(1),v4=0,89,對偶變量法(2),u3+v4=c34u3=6,90,對偶變量法(3),u3+v3=c33v3=4,91,對偶變量法(4),u2+v3=c23u2=-2,92,對偶變量法(5),u2+v2=c22v2=6,93,對偶變量法(6),u2+v1=c21v1=10,94,對偶變量法(7),u1+v1=c11u1=-4,95,對偶變量法(8),z12-c12=u1+v2-c12=(-4)+6-7=-5,-5,96,對偶變量法(9),z13-c13=u1+v

21、3-c13=(-4)+4-5=-5,-5,-5,97,對偶變量法(10),z14-c14=u1+v4-c14=(-4)+0-3=-7,-7,-5,-5,98,對偶變量法(11),z24-c24=u2+v4-c24=(-2)+0-7=-9,-9,-5,-5,-7,99,對偶變量法(12),z31-c31=u3+v1-c31=6+10-5=11,11,-5,-5,-7,-9,100,對偶變量法(13),z32-c32=u3+v2-c32=6+6-9=+3,+3,-5,-5,-7,-9,11,101,選擇進(jìn)基變量,確定離基變量,x31進(jìn)基, minx21,x33=min8,6=6, x33離基,+3

22、,-5,-5,-7,-9,11,102,調(diào)整運(yùn)量,重新計(jì)算檢驗(yàn)數(shù),確定進(jìn)基、離基變量,x14進(jìn)基, minx11,x34=min14,13=13, x34離基,-11,-5,-5,+4,+2,-8,103,調(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,104,第五章 網(wǎng)絡(luò)優(yōu)化,網(wǎng)絡(luò)的基本概念 網(wǎng)絡(luò)最小費(fèi)用流問題 網(wǎng)絡(luò)最大流問題 最短路徑問題,105,網(wǎng)絡(luò)的基本概念,節(jié)點(diǎn)與（有向）邊 每一條邊和兩個(gè)節(jié)點(diǎn)關(guān)聯(lián)，一條邊可以用兩個(gè)節(jié)點(diǎn)的標(biāo)號表示（i，j）,路徑（Path）

23、前后相繼并且方向相同的邊序列 P=(1,2),(2,3),(3,4),4,2,3,1,4,2,3,1,網(wǎng)絡(luò)由節(jié)點(diǎn)和邊組成,106,回路（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,107,連通圖 任意兩個(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,樹(Tr

24、ee) 無圈的連通圖稱為樹 樹中只與一條邊關(guān)聯(lián)的節(jié)點(diǎn)稱為懸掛節(jié)點(diǎn),108,樹的性質(zhì),任何樹至少有一個(gè)懸掛節(jié)點(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)之間增加一條邊，則形成唯一的圈,109,網(wǎng)絡(luò)的生成樹,由網(wǎng)絡(luò)的所有節(jié)點(diǎn)（m個(gè)）和網(wǎng)絡(luò)的m-1條邊組成的樹稱為網(wǎng)絡(luò)的生成樹，網(wǎng)絡(luò)中不屬于生成樹的邊稱為生成樹的弦,110,網(wǎng)絡(luò)的生成樹的變換,網(wǎng)絡(luò)的一個(gè)生成樹，增加一條弦，形成唯一的圈，去掉生成樹的一條邊，得到一個(gè)新的網(wǎng)絡(luò)的生成樹,生成樹2,生成樹3,生成樹1,/,/,111,

25、網(wǎng)絡(luò)的生成樹和線性規(guī)劃的關(guān)系,網(wǎng)絡(luò)的一個(gè)生成樹對應(yīng)于線性規(guī)劃的一個(gè)基 生成樹上的邊對應(yīng)于線性規(guī)劃的基變量 生成樹的弦對應(yīng)于線性規(guī)劃的非基變量 生成樹的變換對應(yīng)于線性規(guī)劃單純形法的進(jìn)基和離基變換,112,網(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)用,113,初始基礎(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,114,確定非基變量x2

26、4和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,3,4,5,6,1,b4=3,115,求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,116,求x34的檢驗(yàn)數(shù)z34 -c34 閉回路法,z34 -c34 =(-c46+c56+

27、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,c34=4,c12=6,2,3,4,5,6,1,117,變量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,118,確定非基變量x24和x56,b2=-2,b4=3,b3=5,b5=-6,b6=-5,b1=5,x

28、46=5,x13=3,x35=6,x34=2,x12=2,2,3,4,5,6,1,119,計(jì)算x24和x56的檢驗(yàn)數(shù)z24 -c24 、z56-c56,z24 -c24 =(c34+c13-c12)-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,120,最優(yōu)解,最優(yōu)解的目標(biāo)函數(shù)值為：min z=62+33+42+26+15=46,b2=-

29、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,121,網(wǎng)絡(luò)最大流問題,122,邊的容量和流量 容量uij，流量xij 可行流 滿足以下條件的流稱為可行流： 1、每一個(gè)節(jié)點(diǎn)流量平衡 2、0 xij uij,邊的容量和流量、可行流,123,飽和邊、不飽和邊、流量的間隙,（1，2）是飽和的,2、如果xijuij，邊從i到j(luò)的方向是不飽和的；,（1，2）是不飽和的 間隙為12=u12-x12=5-3=2,1、如果xij=uij，邊從i到j(luò)的方向是飽和的；,124,3、如果xij=0，邊從j到i的方向是飽和的

30、；,（2，1）是飽和的,如果xij0，邊從j到i的方向是不飽和的；,（2，1）是不飽和的 間隙為12=x12=5,125,給出一個(gè)初始的可行流xij=0,126,找到所有的不飽和邊，以及各邊可以調(diào)整流量的方向,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,x=0,127,找到一條從1到7的不飽和鏈,鏈的間隙為： = min8,3,1,8=1 調(diào)整鏈的流量：xij=xij+ ,2,3,5,4,6,7,1,f=0,f=

31、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,128,調(diào)整流量，f=1。繼續(xù)求出網(wǎng)絡(luò)的不飽和邊,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,129,求出一條從1到7的不飽和鏈,2,3,5,4,6,7,1,f=1,f=1,u=6,u=2

32、,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,130,調(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,u=9,u=8,u=8,x=1,x=0,x=0,x=1,x=0,x=0,x=0,x=1,x=1,x=1,x=1,x=0,131,求出一條從1到7的不飽和鏈,=5

33、,=8,=7,=min 7,5,8=5, 調(diào)整流量 xij=xij+5, f=f+5=2+5=7,132,調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊,2,3,5,4,6,7,1,f=7,f=7,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=6,x=0,x=0,x=1,x=0,x=0,x=0,x=6,x=1,x=1,x=6,x=0,133,求出一條從1到7的不飽和鏈,=min 6,7,4,3=3, 調(diào)整流量 xij=xij+3, f=f+3=7+3=10,=4,=4,=3,=6,134,調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊,2,3,5,4,6,7,1,f=

34、10,f=10,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=6,x=0,x=3,x=4,x=3,x=0,x=0,x=9,x=1,x=1,x=6,x=0,135,求出一條從1到7的不飽和鏈,2,3,5,4,6,7,1,f=10,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=6,x=0,x=3,x=4,x=3,x=0,x=0,x=9,x=1,x=1,x=6,x=0,f=10,=1,=3,=7,=3,=min 3,1,3,7=1, 調(diào)整流量 xij=xij+1, f=f+1=10+1=11,

35、136,調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊,2,3,5,4,6,7,1,f=11,f=11,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=6,x=0,x=4,x=5,x=3,x=1,x=0,x=9,x=2,x=1,x=6,x=0,已找不到一條從1到7的不飽和鏈，從1開始可以到達(dá)的節(jié)點(diǎn)為1，2，3,137,已求得最大流,2,3,5,4,6,7,1,f=11,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=6,x=0,x=4,x=5,x=3,x=1,x=0,x=9,x=2,x=1,x=6,x=0

36、,f=11,最大流f=11，最小割集為（2,5）（3,4）（3,5） u25+u34+u35=6+4+1=11,138,最短路徑問題,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求從1到8的最短路徑,139,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1, w1=0,min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1 X=1,4, w4=1,w1=0,w1=0,140,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8

37、,2,X=1,4,min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 X=1,2,4, w2=2,w1=0,w4=1,w2=2,141,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 X=1,2,4,6, w6=3,w2=2,w4=1,w1=0,w6=3,142,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,

38、4,6,min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 X=1,2,4,6,7, w7=3,w2=2,w4=1,w1=0,w6=3,w7=3,143,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 X=1,2,4,5,6,7, w5=6,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,144,2,3,7,1,8,4,5,6,6,1,3,4,10,

39、5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 X=1,2,3,4,5,6,7, w3=8,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,145,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10 X=1,2,3,4,5,6,7,8, w8=10,w2=2,w4=1,w1=0,w

40、6=3,w7=3,w5=6,w3=8,w8=10,146,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到10的最短路徑為1，4，7，5，8，長度為10。,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,147,第六章 動(dòng)態(tài)規(guī)劃,最短路徑問題 資源分配問題 背包問題 機(jī)器負(fù)荷分配問題,148,一、最短路徑問題,求從A到E的最短路徑,149,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,

41、E,C2,f5(E)=0,150,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,151,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,152,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D

42、2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,153,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,154,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,155,2,5,1,1

43、2,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,156,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=21,157,2,5,1,12,14,10