四川大學(xué)運(yùn)籌學(xué)課件.ppt

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

2、,4,-8,6,0,x1,x2,可行域的性質(zhì),線(xiàn)性規(guī)劃的可行域是凸集 線(xiàn)性規(guī)劃的最優(yōu)解在極點(diǎn)上,凸集,凸集,不是凸集,極點(diǎn),線(xiàn)性規(guī)劃的基本概念,線(xiàn)性規(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è)極

3、點(diǎn)。 目標(biāo)函數(shù)值為：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、

4、x6,基礎(chǔ)解為（x1，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=

5、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,幾何概念,代數(shù)概念,約束直線(xiàn),滿(mǎn)足一個(gè)等式約束的解,約束半平面,滿(mǎn)足一個(gè)不等式約束的解,約束半平面的交集： 凸多邊形,滿(mǎn)足一組不等式約束的解,約束直線(xiàn)的交點(diǎn),基礎(chǔ)解,可行域的極點(diǎn),基礎(chǔ)可行解,目標(biāo)函數(shù)等值線(xiàn)： 一組平行線(xiàn),目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解,單純形表,求解線(xiàn)性規(guī)劃問(wèn)題,寫(xiě)成標(biāo)準(zhǔn)化形式,寫(xiě)出單純形表,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,

6、1/2,18/1/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,線(xiàn)性規(guī)劃的矩陣表示,=,=,CBTB-1aj-cj=zj-cj 稱(chēng)為非基變量的檢驗(yàn)數(shù)（Reduced Cost） B-1aj=Yj， B-1b= ，CBTB-1b=z0,第二章 對(duì)偶線(xiàn)性規(guī)劃,對(duì)偶的定義 對(duì)偶問(wèn)題的性質(zhì) 原始

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

8、始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解 z=CTXo=WoTAXo=WoTb=y,3、原始問(wèn)題和對(duì)偶問(wèn)題最優(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,原始問(wèn)題和對(duì)偶問(wèn)題變量、

9、松弛變量的維數(shù),w1 wi wm wm+1 wm+j wn+m,x1 xj xn xn+1 xn+i xn+m,對(duì)偶問(wèn)題的變量 對(duì)偶問(wèn)題的松弛變量,原始問(wèn)題的變量 原始問(wèn)題的松弛變量,xjwm+j=0wixn+i=0(i=1,2,m; j=1,2,n) 在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0,Kuhn-Tucher 條件,3、原始問(wèn)題和對(duì)偶問(wèn)題最優(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、用單純形表求解原始

10、問(wèn)題的四種形式,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）,單純形表和對(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ì)偶問(wèn)題,原始問(wèn)題,引進(jìn)松弛變量,引進(jìn)松弛變量,min z=CTX s.t. AX-XS=b X, XS0,max y=bTW

11、 s.t. ATW+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ì)偶問(wèn)題,原始問(wèn)題,引進(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, X

12、S0,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,單純形表和對(duì)偶(3),對(duì)偶問(wèn)題,原始問(wèn)題,引進(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

13、s.t. ATW C W 0,單純形表和對(duì)偶(4),對(duì)偶問(wèn)題,原始問(wèn)題,引進(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ì)偶單純形法（初始解原始不可行的問(wèn)題）,已獲得最優(yōu)解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35 對(duì)偶問(wèn)題的最優(yōu)解為： （w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35,3、初始解原始、對(duì)偶都不可行的問(wèn)題,解

14、法1：先解決原始可行性,在得到原始可行解時(shí)同時(shí)得到對(duì)偶可行解，已獲得最優(yōu)解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 對(duì)偶問(wèn)題的最優(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ì)偶問(wèn)題的最優(yōu)解為： （w1, w2, w3, w4, w5, w6）=（-7,

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

16、生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0,w1 w2 wm,4、產(chǎn)品的機(jī)會(huì)成本,機(jī)會(huì)成本 表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤(rùn),增加單位資源可以增加的利潤(rùn),減少一件產(chǎn)品可以節(jié)省的資源,機(jī)會(huì)成本,利潤(rùn),差額成本,5、產(chǎn)品的差額成本（Reduced Cost）,差額成本=機(jī)會(huì)成本 - 利潤(rùn),5、互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋,在利潤(rùn)最大化的生產(chǎn)計(jì)劃中 （1）邊際利潤(rùn)大于0的資源沒(méi)有剩余 （2）有剩余的資源邊際利潤(rùn)等于0 （3）安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本等于利潤(rùn) （4）機(jī)會(huì)成本大于利潤(rùn)的產(chǎn)品不安排生產(chǎn),第四章 運(yùn)輸問(wèn)題,運(yùn)輸問(wèn)題的表示 網(wǎng)絡(luò)圖、線(xiàn)性規(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è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)輸問(wèn)題線(xiàn)性規(guī)劃模型,供應(yīng)地約束,需求地約束,運(yùn)輸問(wèn)題的表格表示,初始基礎(chǔ)可行解西北角法,8,13,13,14,6,6,初始基礎(chǔ)可行解最小元素法（1）,最小元素法（2）,最小元素法（3）,最小元素法（4）,最小元素法（5）,最小元素法（6）,-5,非基變量xij的檢驗(yàn)數(shù)zij-cij閉回路法(

18、1),z12-c12=(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,

19、閉回路法(6),z32-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+

20、v3-c13=(-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,

21、調(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,調(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èn)題 網(wǎng)絡(luò)最大流問(wèn)題 最短路徑問(wèn)題,網(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,

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

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

24、的弦對(duì)應(yīng)于線(xiàn)性規(guī)劃的非基變量 生成樹(shù)的變換對(duì)應(yīng)于線(xiàn)性規(guī)劃單純形法的進(jìn)基和離基變換,網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題,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ǔ)可行解生成樹(shù),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=

25、4,c12=6,2,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,c3

26、5=2,c56=4,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 =(c

27、34+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,最優(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ò)最大流問(wèn)題,邊的容量和流量 容量uij

28、，流量xij 可行流 滿(mǎn)足以下條件的流稱(chēng)為可行流： 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

29、,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,找到一條從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。繼

30、續(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,求出一條從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=xi

31、j+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,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,求出一條從1到7的不飽和鏈,=5,=8,=7,=min 7,5,8=5, 調(diào)整流量 xij=xij+5, f=f+5=2+5=7,調(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,

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

33、,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,調(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的不飽和鏈

34、，從1開(kāi)始可以到達(dá)的節(jié)點(diǎn)為1，2，3,已求得最大流,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,f=11,最大流f=11，最小割集為（2,5）（3,4）（3,5） u25+u34+u35=6+4+1=11,最短路徑問(wèn)題,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的最短路徑,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,

35、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,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,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,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

36、 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,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,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,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=

37、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,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,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,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6

38、,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,w6=3,w7=3,w5=6,w3=8,w8=10,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，長(zhǎng)度為10。,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,第六章 動(dòng)態(tài)規(guī)劃,最短路徑問(wèn)題 資源分配問(wèn)題 背包問(wèn)題 機(jī)器負(fù)荷分配問(wèn)題

39、,一、最短路徑問(wèn)題,求從A到E的最短路徑,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,f5(E)=0,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,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,

40、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(C1)=8,f4(D1)=5,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,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,D

41、2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,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(B1)=20,f3(C2)=7,f3(C1)=8,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,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,