运筹学演示学习

《运筹学演示学习》由会员分享，可在线阅读，更多相关《运筹学演示学习（165页珍藏版）》请在装配图网上搜索。

1、目 录第一章线性规划第二章对偶第三章整数规划第四章运输问题第五章网络优化第六章动态规划第七章排 队 论第1页/共165页第一章 线性规划线性规划模型线性规划的图解可行域的性质线性规划的基本概念基础解、基础可行解单纯形表线性规划的矩阵表示第2页/共165页线性规划模型线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,unr,0线性规划的标准形式目标函数：min约束条件：=变量符号：0unr,0)(Xb),(AX.t.sXCzmax(min)T0XbAX.t.sXCzminT第3页/共165页线性规划的图解max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,

2、x20可行域目标函数等值线最优解64-860 x1x2第4页/共165页可行域的性质线性规划的可行域是凸集线性规划的最优解在极点上凸集凸集不是凸集极点第5页/共165页线性规划的基本概念线性规划的基矩阵、基变量、非基变量=目标函数约束条件行列式0基矩阵右边常数第6页/共165页maxz=2x1+3x2+x3s.t.x1+3x2+x3152x1+3x2-x318x1-x2+x33x1,x2,x30min z=-2x1-3x2-x3stx1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1,x2,x3,x4,x5,x60第7页/共165页x1+3x2+x3=1

3、52x1+3x2-x3=18x1-x2+x3=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=20第8页/共165页x1+3x2+x4=152x1+3x2=18x1-x2=3基变量x1、x2、x4，非基变量x3、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2

4、+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3第9页/共165页x1+3x2=152x1+3x2+x5=18x1-x2=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x5，非基变量x3、x4、x6基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）是基础解，但不是可行解，不是一个极点。第10页/共165页x1+3x2=152x1+3x2=18x1-x2+x6=3基变量x1、x2、x6，非基变量x3、x4、x5基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4

5、）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3第11页/共165页3x2+x3+x4=153x2-x3=18-x2+x3=3基变量x2、x3、x4，非基变量x1、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基础解，但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3第12页/共165页3x2+x3=153x2-x3+x5=18-x2+x3=3基变量x1、x2、x3，非基变量x4、x5、x

6、6基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=15x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3第13页/共165页3x2+x3=153x2-x3=18-x2+x3+x6=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基础解但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3第14页/共165页=目标函数约束条件基矩阵右边常数

7、进基变量、离基变量、基变换=基变量第15页/共165页=进基变量离基变量目标函数约束条件右边常数=第16页/共165页=目标函数约束条件新的基矩阵右边常数=第17页/共165页=进基变量离基变量目标函数约束条件基矩阵=第18页/共165页=目标函数约束条件新的基矩阵右边常数=第19页/共165页基础解、基础可行解max z=x1+3x2Ds.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 AOABCDE基变量x3 x4x1 x4x1 x2x2 x3x2 x4x1 x3非基变量x1 x2x2 x3x3 x4x1

8、 x4x1 x3x2 x4xj0-x4x1基础可行解是是是是否否第20页/共165页几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基础解可行域的极点基础可行解目标函数等值线：一组平行线 目标函数值等于一个常数的解第21页/共165页单纯形表第22页/共165页maxz=3x1+4x2-x3+2x4s.t.x1+x2+x3+x425x1+2x2+x3+2x436x1x2x3x40minz=-3x1-4x2+x3-2x4s.t.x1+x2+x3+x4+x5=25x1+2x2+x3+2x4+x6=36x1x2

9、x3x4x5x60求解线性规划问题写成标准化形式第23页/共165页zx1x2x3x4x5x6R H Sz134-12000011111025012120136写出单纯形表25/136/20-3-20-2-72011/201-1/27/1/21x51/2101/218/1/2071811/21/2x20 x6离基，x2进基，x5离基，x1进基，zx1x2x3x4x5x6R H Sz134-12000 x5011111025x6012120136第24页/共165页zx1x2x3x4x5x6RH Sz110-3-20-2-72x501/201/201-1/27x201/211/2101/2180

10、-4-2-2-1-8601102-11x101-1101411010 x20得到最优解，最优解为：（x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0）min z=-86，max z=86第25页/共165页maxz=2x1+3x2+x3stx1+3x2+x3152x1+3x2-x318x1-x2+x33x1,x2,x30min z=-2x1-3x2-x3stx1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1,x2,x3,x4,x5,x60第26页/共165页zx1x2x3x4x5x6RHSz12310000 x401311001515

11、/3x5023-10101818/3x601-110013-min z=-2x1-3x2-x3stx1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1,x2,x3,x4,x5,x60第27页/共165页zx1x2x3x4x5x6RHSz12310000 x401311001515/3x5023-10101818/3x601-110013-zx1x2x3x4x5x6RHSz1100-100-15x201/311/31/30055/1/3x5010-2-11033/1x604/304/31/30188/4/3zx1x2x3x4x5x6RHSz10020-10

12、-18x200112/3-1/3044/1x1010-2-1103-x600045/3-4/3144/4第28页/共165页zx1x2x3x4x5x6RHSz10020-10-18x200112/3-1/3044/1x1010-2-1103-x600045/3-4/3144/4x3进基，x6离基zx1x2x3x4x5x6RHSz1000-5/6-1/3-1/2-20 x200101/40-1/43x10100-1/61/31/25x300015/12-1/31/41最优解:(x1,x2,x3,x4,x5x6)=(5,3,1,0,0,0),max z=20第29页/共165页线性规划的矩阵表示0

13、X,XbXXN,B.t.sXXC,CzminNBNBNBTNTB0XbAX.t.sXCzminT=第30页/共165页0X,XNXBbBX.t.sX)CNBC(bBCzminNBN11BNTN1TB1TB=0X,XbNXBX.t.sXCXCzminNBNBNTNBTB=0X,XNXBbBX.t.sXCXCzminNBN11BNTNBTB第31页/共165页0XbAX.t.sXCzminTzXBXNRHSz1-CBT-CNT0XB0IB-1NB-1b0X,XbNXBX.t.sXCXCzminNBNBNTNBTBzXRHSz1-CT00Ab0X,XNXBbBX.t.sXCXCzminNBN11BN

14、TNBTBzXBXNRHSz1-CBT-CNT00BNb第32页/共165页0X,XNXBbBX.t.sX)CNBC(bBCzminNBN11BNTN1TB1TBzXBXNRHSz10TCBTB-1N-CNTCBTB-1bXB0IB-1NB-1b第33页/共165页zXBxjRHSz1-CBT-cj00BajbzXBxjRHSz10TCBTB-1aj-cj CBTB-1b0IB-1ajB-1bCBTB-1aj-cj=zj-cj 称为非基变量的检验数（Reduced Cost）B-1aj=Yj，B-1b=，CBTB-1b=z0b第34页/共165页zXBxjRHSz10Tzj-cjz0XB0IY

15、jbzXBxjRHSz10TCBTB-1aj-cj CBTB-1b0IB-1ajB-1b第35页/共165页第二章 对偶线性规划对偶的定义对偶问题的性质原始对偶关系 目标函数值之间的关系 最优解之间的关系互补松弛关系 最优解的Kuhn-Tucher条件对偶可行基对偶单纯形法对偶的经济解释DUAL第36页/共165页一、对偶的定义原始问题min z=CTXs.t.AXbX 0对偶问题max y=bTWs.t.ATWCW 0minbACTCATbTmaxmnmn第37页/共165页二、对偶问题的性质1、对偶的对偶就是原始问题max z=-CTXs.t.-AX-bX 0min y=-bTWs.t.-

16、ATW-CW 0max y=bTWs.t.ATWCW 0min z=CTXs.t.AXb X 0对偶的定义对偶的定义第38页/共165页min z=CTXs.t.AXbX 0max y=bTWs.t.ATWC W 02、其他形式问题的对偶min z=CTXs.t.AXbX 0max y=bTWs.t.ATWC W 0min z=CTXs.t.AX=bX 0max y=bTWs.t.ATWC W：unr第39页/共165页三、原始对偶关系1、可行解的目标函数值之间的关系 设XF、WF分别是原始问题和对偶问题的可行解z=CTXF WTAXF WTb=y2、最优解的目标函数值之间的关系 设Xo、Wo

17、分别是原始问题和对偶问题的最优解 z=CTXo=WoTAXo=WoTb=y第40页/共165页3、原始问题和对偶问题最优解之间的互补松弛关系min z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW+WS=C W,WS0min z=CTXs.t.AXb X 0max y=bTWs.t.ATWC W0对偶引进松弛变量引进松弛变量XTWS=0 WTXS=0互补松弛关系X，XsW，Ws第41页/共165页min z=CTXs.t.AX-XS=bX,XS 0max y=bTWs.t.ATW+WS=CW,WS 0XTWS=0WTXS=0mn=WWSATICn=AXS-Ibnmm

18、X原始问题和对偶问题变量、松弛变量的维数第42页/共165页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)在一对变量中，其中一个大于0，另一个一定等于0第43页/共165页Kuhn-Tucher 条件3、原始问题和对偶问题最优解的充分必要条件 (1)原始可行条件（PFC）AX-XS=bX,XS 0(2)对偶可行条件（DFC）ATW+WS=CW,WS 0(3)互补松弛条件（CSC）XTWS=0WTXS=0第44页

19、/共165页四、对偶单纯形法1、用单纯形表求解原始问题的四种形式min z=CTXs.t.AXb X 0min z=CTXs.t.AX b X 0max z=CTXs.t.AX b X 0max z=CTXs.t.AX b X 0（2）（3）（4）（1）第45页/共165页单纯形表和对偶(1)min z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW+WS=C W,WS0min z=CTXs.t.AXb X 0max y=bTWs.t.ATWC W0对偶问题原始问题引进松弛变量引进松弛变量第46页/共165页zXXSRHS1-WST-WTCBTB-1b0B-1A-B-

20、1B-1bzXXSRHS1-CT0T00A-Ibmin z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW+WS=C W,WS0zXXSRHS1CBTB-1A-CT-CBTB-1CBTB-1b0B-1A-B-1B-1bWT=CBTB-1WST=CT-WTA第47页/共165页min z=CTXs.t.AX+XS=b X,XS0max y=bTWs.t.ATW+WS=C W 0,WS0min z=CTXs.t.AX b X 0max y=bTWs.t.ATWC W 0单纯形表和对偶(2)对偶问题原始问题引进松弛变量引进松弛变量第48页/共165页zXXSRHS1-WST

21、WTCBTB-1b0B-1AB-1B-1bzXXSRHS1-CT0T00AIbmin z=CTXs.t.AX+XS=b X,XS0max y=bTWs.t.ATW+WS=C W 0,WS0zXXSRHS1CBTB-1A-CTCBTB-1CBTB-1b0B-1AB-1B-1bWT=CBTB-1WST=CT-WTA第49页/共165页max z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW-WS=C W 0,WS0max z=CTXs.t.AX b X 0min y=bTWs.t.ATW C W 0单纯形表和对偶(3)对偶问题原始问题引进松弛变量引进松弛变量第50页/共

22、165页zXXSRHS1WST-WTCBTB-1b0B-1A-B-1B-1bzXXSRHS1-CT0T00A-Ibmax z=CTXs.t.AX-XS=b X,XS0min y=bTWs.t.ATW-WS=C W 0,WS0zXXSRHS1CBTB-1A-CT-CBTB-1CBTB-1b0B-1A-B-1B-1bWT=CBTB-1WST=WTA-CT第51页/共165页max z=CTXs.t.AX+XS=b X,XS0max y=bTWs.t.ATW-WS=C W,WS0max z=CTXs.t.AX b X 0min y=bTWs.t.ATW C W 0单纯形表和对偶(4)对偶问题原始问题

23、引进松弛变量引进松弛变量第52页/共165页zXXSRHS1WSTWTCBTB-1b0B-1AB-1B-1bzXXSRHS1-CT0T00AIbmax z=CTXs.t.AX+XS=b X,XS0min y=bTWs.t.ATW-WS=C W,WS0zXXSRHS1CBTB-1A-CTCBTB-1CBTB-1b0B-1AB-1B-1bWT=CBTB-1WST=WTA-CT第53页/共165页2、对偶单纯形法（初始解原始不可行的问题）0 xxx2xx2x5xx3x24xxx.t.sxx2x3zmin3213213213213210 xxxxxx2xxx2x5xxx3x24xxxx.t.sxx2x

24、3zmin654321632153214321321第54页/共165页0 xxxxxx2xxx2x25xxx3x24xxxx.t.sxx2x3zmin654321632153214321321zx1x2x3x4x5x6RHSz1-3-2-10000 x401-111004x502-31010-5x60-22-1001-2-3/-2-1/-1第55页/共165页zx1x2x3x4x5x6RHSz1-1000-4-530 x40-100112-5x200100-1-17x302010-2-316zx1x2x3x4x5x6RHSz1-1-4000-12x40-1101012x500-10011-7

25、x302-2100-12第56页/共165页zx1x2x3x4x5x6RHSz1000-1-5-735x10100-1-1-25x200100-1-17x300012016已获得最优解：（x1,x2,x3,x4,x5,x6）=（5,7,6,0,0,0）min z=35对偶问题的最优解为：（w1,w2,w3,w4,w5,w6）=（-1,5,7,0,0,0）max y=35第57页/共165页3、初始解原始、对偶都不可行的问题0 xxx2xx2x5xx3x24xxx.t.sx2x2x3zmin3213213213213210 xxxxxx2xxx2x5xxx3x24xxxx.t.sx2x2x3zm

26、in654321632153214321321第58页/共165页0 xxxxxx2xxx2x25xxx3x24xxxx.t.sx2x2x3zmin654321632153214321321zx1x2x3x4x5x6RHSz1-3-220000 x401-111004x502-31010-5x60-22-1001-2解法1：先解决原始可行性第59页/共165页zx1x2x3x4x5x6RHSz1-700024-18x40-100112-5x200100-1-17x302010-2-316zx1x2x3x4x5x6RHSz1-720002-4x40-1101012x500-10011-7x302

27、-2100-12第60页/共165页zx1x2x3x4x5x6RHSz1000-7-5-1017x10100-1-1-25x200100-1-17x300012016在得到原始可行解时同时得到对偶可行解，已获得最优解：（x1,x2,x3,x4,x5,x6）=（5,7,6,0,0,0）min z=17对偶问题的最优解为：（w1,w2,w3,w4,w5,w6）=（-7,5,10,0,0,0）max y=17第61页/共165页zx1x2x3x4x5x6RHSz1-3-220000 x401-111004x502-31010-5x60-22-1001-2zx1x2x3x4x5x6RHSz1-500-

28、200-8x301-111004x501-20-110-9x60-1101012解法2：先解决对偶可行性已得到对偶可行解，再用对偶单纯形法求解第62页/共165页zx1x2x3x4x5x6RHSz1000-7-5-1017x300012016x200100-1-17x10100-1-1-25zx1x2x3x4x5x6RHSz1-500-200-8x301/2013/2-1/2017/2x20-1/2101/2-1/209/2x60-1/2001/21/21-5/2第63页/共165页得到原始可行解，已获得最优解：（x1,x2,x3,x4,x5,x6）=（5,7,6,0,0,0）min z=17

29、对偶问题的最优解为：（w1,w2,w3,w4,w5,w6）=（-7,5,10,0,0,0）max y=17第64页/共165页五、对偶的经济解释1、原始问题是利润最大化的生产计划问题0 xxxxxxbxxaxaxabxxaxaxabxxaxaxa.t.sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111222211单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）第65页/共165页2、对偶问题0wwwwwwcwwawawacwwawawacwwawawa.t.

30、swbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min y第66页/共165页3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0种资源的边际利润第种资源的增量第最大利润的增量iibzwiooimmii2211w

31、bwbwbwbyzmmiii2211wbw)bb(wbwbzziiwbz第67页/共165页w1w2wm4、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润mmjiij2j21j1wawawawa增加单位资源可以增加的利润减少一件产品可以节省的资源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211第68页/共165页机会成本利润差额成本0wwwwwwcwwawawacwwawawacwwawawa.t.swbwbwbyminnm2

32、m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm22115、产品的差额成本（Reduced Cost）差额成本=机会成本-利润jjTjmjmj22j11jmcaWc)awawaw(w第69页/共165页5、互补松弛关系的经济解释0 x0w0w0 x0wx0w0 x0 x0w0 xwjjmjmjjmjiininiini在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产第70页/共165页第四章 运输问题运输问题的表示网络图、线性规划模型、运输表

33、初始基础可行解西北角法、最小元素法非基变量的检验数闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量第71页/共165页2321341运输问题网络图s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106第72页/共165页运输问题线性规划模型0 xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs.t.x6x10 x9x5x7x2x4x8x3x5x7x6zmin3433323124232221141312113424143323133222123121113433323

34、12423222114131211343332312423222114131211供应地约束需求地约束第73页/共165页运输问题的表格表示123467531x11x12x13x141484272x21x22x23x2427591063x31x32x33x341922131213第74页/共165页初始基础可行解西北角法 1 2 3 4 6 7 5 3 1 14 8 4 2 7 2 27 5 9 10 6 3 19 22 13 12 13 813131466第75页/共165页123467531148427212271559106319221312130初始基础可行解最小元素法（1）第76页/

35、共165页最小元素法（2）1234675311314184272122715591063192213121300第77页/共165页最小元素法（3）123467531131418427213122725910631922131213000第78页/共165页最小元素法（4）1234675311314184272131227259106319190221312133000第79页/共165页最小元素法（5）12346753111314084272131227259106319190221312132000第80页/共165页最小元素法（6）1234675311131408427221312270

36、59106319190221312130000第81页/共165页1234675311414842728136275910636131922131213-5非基变量xij的检验数zij-cij闭回路法(1)z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5第82页/共165页1234675311414842728136275910636131922131213-5闭回路法(2)z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5-5第83页/共165页1234675311414842728136275910636131922131213-5闭回路法(3

37、)z14-c14=(c11-c21+c21-c23+c33-c14)-c13=(6-8+2-10+6)-3=-7-7-5第84页/共165页1234675311414842728136275910636131922131213-5闭回路法(4)z24-c24=(c23-c33+c34)-c24=(2-10+6)-7=-9-9-5-7第85页/共165页1234675311414842728136275910636131922131213-5闭回路法(5)z31-c31=(c21-c23+c33)-c31=(8-2+10)-5=+11+11-5-7-9第86页/共165页123467531141

38、4842728136275910636131922131213-5闭回路法(6)z32-c32=(c22-c23+c33)-c32=(4-2+10)-9=+3+3-5-7-9+11第87页/共165页12346753114u1842728136u2591063613u3v1v2v3v4=0非基变量xij的检验数zij-cij对偶变量法(1)v4=0第88页/共165页12346753114u1842728136u2591063613u3=6v1v2v3v4=0对偶变量法(2)u3+v4=c34u3=6第89页/共165页12346753114u1842728136u2591063613u3=6

39、v1v2v3=4v4=0对偶变量法(3)u3+v3=c33v3=4第90页/共165页12346753114u1842728136u2=-2591063613u3=6v1v2v3=4v4=0对偶变量法(4)u2+v3=c23u2=-2第91页/共165页12346753114u1842728136u2=-2591063613u3=6v1v2=6v3=4v4=0对偶变量法(5)u2+v2=c22v2=6第92页/共165页12346753114u1842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(6)u2+v1=c21v1=10第93页/共165

40、页12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(7)u1+v1=c11u1=-4第94页/共165页12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(8)z12-c12=u1+v2-c12=(-4)+6-7=-5-5第95页/共165页12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(9)z13-c13=u1+v3-c13=(-4)+4-5=-5-

41、5-5第96页/共165页12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(10)z14-c14=u1+v4-c14=(-4)+0-3=-7-7-5-5第97页/共165页12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(11)z24-c24=u2+v4-c24=(-2)+0-7=-9-9-5-5-7第98页/共165页12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v

42、4=0对偶变量法(12)z31-c31=u3+v1-c31=6+10-5=1111-5-5-7-9第99页/共165页12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(13)z32-c32=u3+v2-c32=6+6-9=+3+3-5-5-7-911第100页/共165页12346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0选择进基变量,确定离基变量x31进基,minx21,x33=min8,6=6,x33离基+3-5-5-7-911第101页/共

43、165页12346753114148427221312275910636131922131213调整运量,重新计算检验数,确定进基、离基变量x14进基,minx11,x34=min14,13=13,x34离基-11-5-5+4+2-8第102页/共165页12346753111314842722131227591063191922131213调整运量,重新计算检验数所有zij-cij0,得到最优解。Min z=61+3 13+8 2+4 13+2 12+5 19=142-11-5-5-4-8-2第103页/共165页第五章 网络优化网络的基本概念网络最小费用流问题网络最大流问题最短路径问题第1

44、04页/共165页网络的基本概念节点与（有向）边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j）ji路径（Path）前后相继并且方向相同的边序列 P=(1,2),(2,3),(3,4)42314231网络由节点和边组成第105页/共165页回路（Circuit）起点和终点重合的路径称为回路 =(1,2),(2,4),(4,1)回路中各条边方向相同4231链（Chain）前后相继并且方向不一定相同的边序列称为链 C=(1,2),(3,2),(3,4)4231第106页/共165页连通图 任意两个节点之间至少有一条链的图称为连通图24351圈(Cycle)起点和终点重合的链称为圈

45、 =(1,2),(2,4),(3,4),(1,3)圈中各条边方向不一定相同4231树(Tree)无圈的连通图称为树 树中只与一条边关联的节点称为悬挂节点第107页/共165页树的性质任何树至少有一个悬挂节点243512435124351如果树的节点个数为m，则边的个数为m-1树中任意两个节点之间只有唯一的一条链在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈第108页/共165页网络的生成树由网络的所有节点（m个）和网络的m-1条边组成的树称为网络的生成树，网络中不属于生成树的边称为生成树的弦4231423142314231423142314231第109页/共165页网络的生成树的变

46、换4231网络的一个生成树，增加一条弦，形成唯一的圈，去掉生成树的一条边，得到一个新的网络的生成树423142314231生成树2生成树3生成树1/第110页/共165页网络的生成树和线性规划的关系网络的一个生成树对应于线性规划的一个基生成树上的边对应于线性规划的基变量生成树的弦对应于线性规划的非基变量生成树的变换对应于线性规划单纯形法的进基和离基变换第111页/共165页网络最小费用流问题b2=-2b4=3b3=5b5=-6b6=-5b1=5c24=5c46=1c13=3c35=2c56=4c34=4c12=6234561需求节点供应节点cij 单位流量的费用第112页/共165页初始基础可

47、行解生成树b6=-5b2=-2b4=3b3=5b5=-6b1=5x13=3x46=3x35=8x56=2x12=2234561第113页/共165页确定非基变量x24和x34b2=-2b6=-5b3=5b5=-6b1=5c24=5c46=1c13=3c35=2c56=4c34=4c12=6234561b4=3第114页/共165页求x24的检验数z24-c24 闭回路法z24-c24=(-c46+c56+c35+c13-c12)-c24=(-1+4+2+3-6)-5=-3b2=-2b4=3b3=5b5=-6b6=-5b1=5c24=5c46=1c13=3c35=2c56=4c12=623456

48、1第115页/共165页求x34的检验数z34-c34 闭回路法z34-c34=(-c46+c56+c35)-c34=(-1+4+2)-4=+1，x34进基b2=-2b4=3b3=5b5=-6b6=-5b1=5c46=1c13=3c35=2c56=4c34=4c12=6234561第116页/共165页变量x34进基，确定离基变量minx56,x35=min2,8=2,x56离基，调整流量，进行基变换b2=-2b4=3b3=5b5=-6b6=-5b1=5x46=3x13=3x35=8x56=2x34=0 x12=2234561第117页/共165页确定非基变量x24和x56b2=-2b4=3b

49、3=5b5=-6b6=-5b1=5x46=5x13=3x35=6x34=2x12=2234561第118页/共165页计算x24和x56的检验数z24-c24、z56-c56z24-c24=(c34+c13-c12)-c24=(4+3-6)-5=-4z56-c56=(c46+c34-c35)-c56=(1+4-2)-4=-1，获得最优解b2=-2b4=3b3=5b5=-6b6=-5b1=5c24=5c46=1c13=3c35=2c56=4c34=4c12=6234561第119页/共165页最优解最优解的目标函数值为：min z=62+33+42+26+15=46b2=-2b4=3b3=5b5

50、=-6b6=-5b1=5x46=5x13=3x35=6x34=2x12=2234561第120页/共165页网络最大流问题2354671ffu25=6u42=2u45=4u23=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8第121页/共165页边的容量和流量容量uij，流量xij可行流满足以下条件的流称为可行流：1、每一个节点流量平衡2、0 xij uij边的容量和流量、可行流第122页/共165页21xij=5uij=521xij=3uij=5饱和边、不饱和边、流量的间隙（1，2）是饱和的2、如果xij0，边从j到i的方向是不饱和的；（2，1）是不饱和的

51、间隙为12=x12=5第124页/共165页给出一个初始的可行流xij=02354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0第125页/共165页找到所有的不饱和边，以及各边可以调整流量的方向2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0第126页/共165页找到一条从1到7的不饱和链链的间隙为：=min8,3

52、,1,8=1调整链的流量：xij=xij+2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0=3=1=8=8x=0第127页/共165页调整流量，f=1。继续求出网络的不饱和边2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=1x=1x=1x=1第128页/共165页求出一条从1到7的不饱和链2354671f=1f=1u=6u=2u=4u=3u=7

53、u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=1x=1x=1x=1=1=6=9=7=min 7,1,6,9=1,调整流量 xij=xij+1,f=f+1=2第129页/共165页调整流量，继续求出网络的不饱和边2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0第130页/共165页求出一条从1到7的不饱和链2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8

54、x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0=5=8=7=min 7,5,8=5,调整流量 xij=xij+5,f=f+5=2+5=7第131页/共165页调整流量，继续求出网络的不饱和边2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=0 x=1x=0 x=0 x=0 x=6x=1x=1x=6x=0第132页/共165页2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=0 x=1x=0 x=0 x=0 x=6x=1x=1x=

55、6x=0求出一条从1到7的不饱和链=min 6,7,4,3=3,调整流量 xij=xij+3,f=f+3=7+3=10=4=4=3=6第133页/共165页调整流量，继续求出网络的不饱和边2354671f=10f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=3x=4x=3x=0 x=0 x=9x=1x=1x=6x=0第134页/共165页求出一条从1到7的不饱和链2354671f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=3x=4x=3x=0 x=0 x=9x=1x=1x=6x=0f=10=1

56、=3=7=3=min 3,1,3,7=1,调整流量 xij=xij+1,f=f+1=10+1=11第135页/共165页调整流量，继续求出网络的不饱和边2354671f=11f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0已找不到一条从1到7的不饱和链，从1开始可以到达的节点为1，2，3第136页/共165页已求得最大流2354671f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0

57、f=11最大流f=11，最小割集为（2,5）（3,4）（3,5）u25+u34+u35=6+4+1=11第137页/共165页最短路径问题237184566134105275934682求从1到8的最短路径第138页/共165页237184566134105275934682X=1,w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,w4=1w1=0w1=0第139页/共165页237184566134105275934682X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3

58、=2X=1,2,4,w2=2w1=0w4=1w2=2第140页/共165页237184566134105275934682X=1,2,4min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6,w6=3w2=2w4=1w1=0w6=3第141页/共165页237184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,w7=3w2=2w4=1w1=0w6=3w7=3第142页/共165页23718

59、4566134105275934682X=1,2,4,6,7min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7,w5=6w2=2w4=1w1=0w6=3w7=3w5=6第143页/共165页237184566134105275934682X=1,2,4,6,7min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7,w3=8w2=2w4=1w1=0w6=3w7=3w5=6w3=8第144页/共165页2371845661341

60、05275934682X=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8,w8=10w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10第145页/共165页237184566134105275934682X=1,2,3,4,6,7,81到10的最短路径为1，4，7，5，8，长度为10。w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10第146页/共165页第六章 动态规划最短路径问题资源分配问题背包问题机器负荷分配问题第147页/共165页2511214106

61、104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径第148页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0第149页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f)ED(d)D(f5114第150页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)E(f)ED

62、(d)D(f5224第151页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5112421141113DC8118min2953min)D(f)D,C()D(f)D,C(min)C(f最优决策第152页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min

63、)C(f最优决策第153页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333DC121213min21058min)D(f)D,C()D(f)D,C(min)C(f最优决策第154页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=81133312321131

64、112CB20222120min1210714812min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策第155页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=211233322322131222CB14161714min12471086min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策第156页/共165页251121410610413111239

65、6581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142333332323131332CB19231921min1211712813min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策第157页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=

66、19f2(B2)=14f2(B1)=2123232221211BA19201923min191145212min)B(f)B,A()B(f)B,A()B(f)B,A(min)A(f最优决策第158页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2第159页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1第160页/共165页25112141061041311