运筹学基最短路松弛互补ppt课件

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

2、可行域目标函数等值线最优解64-860 x1x2可行域的性质线性规划的可行域是凸集线性规划的最优解在极点上凸集凸集不是凸集极点线性规划的基本概念线性规划的基矩阵、基变量、非基变量=目标函数约束条件行列式0基矩阵右边常数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 x1+3x2+x3=152x1+3x2-x3=18x1-x2+x3=3x1+3x2+x3+x4=

3、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 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+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1+3x2=1

4、52x1+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）是基础解，但不是可行解，不是一个极点。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）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+

5、x3+x6=33x2+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=33x2+x3=153x2-x3+x5=18-x2+x3=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=15x1+3x2+x3+x4=152x1+3

6、x2-x3+x5=18x1-x2+x3+x6=33x2+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=目标函数约束条件基矩阵右边常数进基变量、离基变量、基变换=基变量=进基变量离基变量目标函数约束条件右边常数=目标函数约束条件新的基矩阵右边常数=进基变量离基变量目标函数约束条件基矩阵=目标函数约束条件新的基矩阵右边常数=基础解、基础可行解max

7、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 x4x1 x3x2 x4xj0-x4x1基础可行解是是是是否否几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基础解可行域的极点基础可行解目标函数等值线：一组平行线 目标函数值等于一个常数的解单纯形表maxz=3x1+4x

8、2-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=36x1x2x3x4x5x60求解线性规划问题写成标准化形式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-1

9、2000 x5011111025x6012120136zx1x2x3x4x5x6R H Sz110-3-20-2-72x501/201/201-1/27x201/211/2101/2180-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=86maxz=2x1+3x2+x3stx1+3x2+x3152x1+3x2-x318x1-x2+x33x1,x2,x30min z= -2x1-3x2-x3stx1+3x2+x3+x4=152x1+3x2-x3+

10、x5=18x1-x2+x3+x6=3x1,x2,x3,x4,x5,x60zx1x2x3x4x5x6RHSz12310000 x401311001515/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,x60zx1x2x3x4x5x6RHSz12310000 x401311001515/3x5023-10101818/3x601-110013-zx1x2x3x4x5x6RHSz1100-100-15x201/311/31/3005

11、5/1/3x5010-2-11033/1x604/304/31/30188/4/3zx1x2x3x4x5x6RHSz10020-10-18x200112/3-1/3044/1x1010-2-1103-x600045/3-4/3144/4zx1x2x3x4x5x6RHSz10020-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,x

12、2,x3,x4,x5x6)=(5,3,1,0,0,0), max z=20线性规划的矩阵表示0X,XbXXN,B. t . sXXC,CzminNBNBNBTNTB0XbAX. t . sXCzminT=0X,XNXBbBX. t . sX)CNBC(bBCzminNBN11BNTN1TB1TB=0X,XbNXBX. t . sXCXCzminNBNBNTNBTB=0X,XNXBbBX. t . sXCXCzminNBN11BNTNBTB0XbAX. t . sXCzminTzXBXNRHSz1-CBT-CNT0XB0IB-1NB-1b0X,XbNXBX. t . sXCXCzminNBNBN

13、TNBTBzXRHSz1-CT00Ab0X,XNXBbBX. t . sXCXCzminNBN11BNTNBTBzXBXNRHSz1-CBT-CNT00BNb0X,XNXBbBX. t . sX)CNBC(bBCzminNBN11BNTN1TB1TBzXBXNRHSz10TCBTB-1N-CNTCBTB-1bXB0IB-1NB-1bzXBxjRHSz1-CBT-cj00BajbzXBxjRHSz10TCBTB-1aj-cj CBTB-1b0IB-1ajB-1bCBTB-1aj-cj=zj-cj 称为非基变量的检验数Reduced Cost）B-1aj=Yj， B-1b= ，CBTB-1b=z0

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

15、W-CW 0max y=bTWs.t. ATWCW 0min z=CTXs.t. AXb X 0对偶的定义对偶的定义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三、原始对偶关系1、可行解的目标函数值之间的关系 设XF、WF分别是原始问题和对偶问题的可行解z=CTXF WTAXF WTb=y2、最优解的目标函数值之间的关系 设Xo、Wo分别是原始问题和对偶问题的最优解

16、 z=CTXo=WoTAXo=WoTb=y3、原始问题和对偶问题最优解之间的互补松弛关系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，Wsmin z=CTXs.t.AX-XS=bX, XS 0max y=bTWs.t. ATW+WS=CW, WS 0XTWS=0WTXS=0mn=WWSATICn=AXS-IbnmmX原始问题和对偶问题变量、松弛变量的维数w1 wi w

17、m wm+1 wm+j wn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量xjwm+j=0 wixn+i=0 (i=1,2,m; j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0Kuhn-Tucher 条件3、原始问题和对偶问题最优解的充分必要条件 (1)原始可行条件PFC）AX-XS=bX, XS 0(2)对偶可行条件DFC）ATW+WS=CW, WS 0(3)互补松弛条件CSC）XTWS=0WTXS=0四、对偶单纯形法1、用单纯形表求解原始问题的四种形式min z=CTXs.t. AXb X 0mi

18、n 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）单纯形表和对偶(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对偶问题原始问题引进松弛变量引进松弛变量zXXSRHS1-WST-WTCBTB-1b0B-1A-B-1B-1bzXXSRHS1-CT0T00A-Ibmin z=CTXs.t. AX-XS=b X, XS0max y=bTWs.t.

19、 ATW+WS=C W, WS0zXXSRHS1CBTB-1A-CT-CBTB-1CBTB-1b0B-1A-B-1B-1bWT=CBTB-1WST=CT-WTAmin 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)对偶问题原始问题引进松弛变量引进松弛变量zXXSRHS1-WSTWTCBTB-1b0B-1AB-1B-1bzXXSRHS1-CT0T00AIbmin z=CTXs.t. AX+XS=b X, XS0max y=bT

20、Ws.t. ATW+WS=C W 0, WS0zXXSRHS1CBTB-1A-CTCBTB-1CBTB-1b0B-1AB-1B-1bWT=CBTB-1WST=CT-WTAmax 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)对偶问题原始问题引进松弛变量引进松弛变量zXXSRHS1WST-WTCBTB-1b0B-1A-B-1B-1bzXXSRHS1-CT0T00A-Ibmax z=CTXs.t. AX-XS=b X, XS0

21、min y=bTWs.t. ATW-WS=C W 0, WS0zXXSRHS1CBTB-1A-CT-CBTB-1CBTB-1b0B-1A-B-1B-1bWT=CBTB-1WST=WTA- CTmax 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)对偶问题原始问题引进松弛变量引进松弛变量zXXSRHS1WSTWTCBTB-1b0B-1AB-1B-1bzXXSRHS1-CT0T00AIbmax z=CTXs.t. AX+XS=b

22、X, XS0min y=bTWs.t. ATW-WS=C W, WS0zXXSRHS1CBTB-1A-CTCBTB-1CBTB-1b0B-1AB-1B-1bWT=CBTB-1WST=WTA- CT2、对偶单纯形法初始解原始不可行的问题）0 xxx2xx2x5xx3x24xxx. t . sxx2x3zmin3213213213213210 xxxxxx2xxx2x5xxx3x24xxxx. t . sxx2x3zmin6543216321532143213210 xxxxxx2xxx2x25xxx3x24xxxx. t . sxx2x3zmin654321632153214321321zx1x

23、2x3x4x5x6RHSz1-3-2-10000 x401-111004x502-31010-5x60-22-1001-2-3/-2-1/-1zx1x2x3x4x5x6RHSz1-1000-4-530 x40-100112-5x200100-1-17x302010-2-316zx1x2x3x4x5x6RHSz1-1-4000-12x40-1101012x500-10011-7x302-2100-12zx1x2x3x4x5x6RHSz1000-1-5-735x10100-1-1-25x200100-1-17x300012016已获得最优解：（x1, x2, x3, x4, x5, x6）=（5,

24、 7, 6, 0, 0, 0） min z=35对偶问题的最优解为：（w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=353、初始解原始、对偶都不可行的问题0 xxx2xx2x5xx3x24xxx. t . sx2x2x3zmin3213213213213210 xxxxxx2xxx2x5xxx3x24xxxx. t . sx2x2x3zmin6543216321532143213210 xxxxxx2xxx2x25xxx3x24xxxx. t . sx2x2x3zmin654321632153214321321zx1x2x3x4x5x6RH

25、Sz1-3-220000 x401-111004x502-31010-5x60-22-1001-2解法1：先解决原始可行性zx1x2x3x4x5x6RHSz1-700024-18x40-100112-5x200100-1-17x302010-2-316zx1x2x3x4x5x6RHSz1-720002-4x40-1101012x500-10011-7x302-2100-12zx1x2x3x4x5x6RHSz1000-7-5-1017x10100-1-1-25x200100-1-17x300012016在得到原始可行解时同时得到对偶可行解，已获得最优解：（x1, x2, x3, x4, x5,

26、x6）=（5, 7, 6, 0, 0, 0） min z=17对偶问题的最优解为：（w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17zx1x2x3x4x5x6RHSz1-3-220000 x401-111004x502-31010-5x60-22-1001-2zx1x2x3x4x5x6RHSz1-500-200-8x301-111004x501-20-110-9x60-1101012解法2：先解决对偶可行性已得到对偶可行解，再用对偶单纯形法求解zx1x2x3x4x5x6RHSz1000-7-5-1017x300012016x200100

27、-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得到原始可行解，已获得最优解：（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五、对偶的经济解释1、原始问题是利润最大化的生产计划问题0 xxxxxxbxxaxaxabxxaxaxabxxaxaxa.

28、 t . sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111222211单位产品的利润元/件）产品产量件）总利润元）资源限量吨）单位产品消耗的资源吨/件）剩余的资源吨）消耗的资源吨）2、对偶问题0wwwwwwcwwawawacwwawawacwwawawa. t . swbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211资源限量吨）资源价格元/吨）总利润元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格Shadow Price）

29、原始和对偶问题都取得最优解时，最大利润 max z=min y3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0种资源的边际利润第种资源的增量第最大利润的增量iibzwiooimmii2211wbwbwbwbyzmmiii2211wbw)bb(wbwbzziiwbzw1w2wm4、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润mmjiij2j21j1wawawawa增加单位资源可以增加的利润减少一件产品可以节省的资源0 xxxxbxaxaxaxabxaxaxaxabxa

30、xaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211机会成本利润差额成本0wwwwwwcwwawawacwwawawacwwawawa. t . swbwbwbyminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm22115、产品的差额成本Reduced Cost）差额成本=机会成本 - 利润jjTjmjmj22j11jmcaWc)awawaw(w5、互补松弛关系的经济解释0 x0w0w0 x0wx0w0 x0 x0w0 xwjjmjmjjmjiinin

31、iini在利润最大化的生产计划中（1边际利润大于0的资源没有剩余（2有剩余的资源边际利润等于0（3安排生产的产品机会成本等于利润（4机会成本大于利润的产品不安排生产第四章 运输问题运输问题的表示网络图、线性规划模型、运输表初始基础可行解西北角法、最小元素法非基变量的检验数闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量2321341运输问题网络图s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106运输问题线性规划模型0 xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xx

32、xxs.t.x6x10 x9x5x7x2x4x8x3x5x7x6zmin343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211供应地约束需求地约束运输问题的表格表示123467531x11x12x13x141484272x21x22x23x2427591063x31x32x33x341922131213初始基础可行解西北角法 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 8131314

33、66123467531148427212271559106319221312130初始基础可行解最小元素法1）最小元素法2）1234675311314184272122715591063192213121300最小元素法3）123467531131418427213122725910631922131213000最小元素法4）1234675311314184272131227259106319190221312133000最小元素法5）12346753111314084272131227259106319190221312132000最小元素法6）12346753111314084272213

34、12270591063191902213121300001234675311414842728136275910636131922131213-5非基变量xij的检验数zij-cij闭回路法(1)z12-c12=(c11-c21+c22)-c12=6-8+4-7=-51234675311414842728136275910636131922131213-5闭回路法(2)z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5-51234675311414842728136275910636131922131213-5闭回路法(3)z14-c14=(c11-c21+ c21 -

35、c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7-7-51234675311414842728136275910636131922131213-5闭回路法(4)z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9-9-5-71234675311414842728136275910636131922131213-5闭回路法(5)z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11+11-5-7-91234675311414842728136275910636131922131213-5闭回路法(6)z32-c32

36、=(c22-c23+ c33)-c32=(4-2+10)-9=+3+3-5-7-9+1112346753114u1842728136u2591063613u3v1v2v3v4=0非基变量xij的检验数zij-cij对偶变量法(1)v4=012346753114u1842728136u2591063613u3=6v1v2v3v4=0对偶变量法(2)u3+v4=c34u3=612346753114u1842728136u2591063613u3=6v1v2v3=4v4=0对偶变量法(3)u3+v3=c33v3=412346753114u1842728136u2=-2591063613u3=6v1v

37、2v3=4v4=0对偶变量法(4)u2+v3=c23u2=-212346753114u1842728136u2=-2591063613u3=6v1v2=6v3=4v4=0对偶变量法(5)u2+v2=c22v2=612346753114u1842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(6)u2+v1=c21v1=1012346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(7)u1+v1=c11u1=-412346753114u1=-4842728136u2=-2591

38、063613u3=6v1=10v2=6v3=4v4=0对偶变量法(8)z12-c12=u1+v2-c12=(-4)+6-7=-5-512346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(9)z13-c13=u1+v3-c13=(-4)+4-5=-5-5-512346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(10)z14-c14=u1+v4-c14=(-4)+0-3=-7-7-5-512346753114u1=-4842728136u2=-

39、2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(11)z24-c24=u2+v4-c24=(-2)+0-7=-9-9-5-5-712346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(12)z31-c31=u3+v1-c31=6+10-5=1111-5-5-7-912346753114u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0对偶变量法(13)z32-c32=u3+v2-c32=6+6-9=+3+3-5-5-7-9111234675311

40、4u1=-4842728136u2=-2591063613u3=6v1=10v2=6v3=4v4=0选择进基变量,确定离基变量x31进基, minx21,x33=min8,6=6, x33离基+3-5-5-7-91112346753114148427221312275910636131922131213调整运量,重新计算检验数,确定进基、离基变量x14进基, minx11,x34=min14,13=13, x34离基-11-5-5+4+2-812346753111314842722131227591063191922131213调整运量, 重新计算检验数所有zij-cij0,得到最优解。Min

41、 z=61+3 13+8 2+4 13+2 12+5 19=142-11-5-5-4-8-2第五章 网络优化网络的基本概念网络最小费用流问题网络最大流问题最短路径问题网络的基本概念节点与有向边 每一条边和两个节点关联，一条边可以用两个节点的标号表示i，j）ji途径Path） 前后相继并且方向相同的边序列 P=(1,2),(2,3),(3,4)42314231网络由节点和边组成回路Circuit） 起点和终点重合的路径称为回路 =(1,2),(2,4),(4,1) 回路中各条边方向相同4231链Chain） 前后相继并且方向不一定相同的边序列称为链 C=(1,2),(3,2),(3,4)4231

42、连通图 任意两个节点之间至少有一条链的图称为连通图24351圈(Cycle) 起点和终点重合的链称为圈 =(1,2),(2,4),(3,4),(1,3) 圈中各条边方向不一定相同4231树(Tree) 无圈的连通图称为树 树中只与一条边关联的节点称为悬挂节点树的性质任何树至少有一个悬挂节点243512435124351如果树的节点个数为m，则边的个数为m-1树中任意两个节点之间只有唯一的一条链在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈网络的生成树由网络的所有节点m个和网络的m-1条边组成的树称为网络的生成树，网络中不属于生成树的边称为生成树的弦423142314231423142

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

44、b4=3b3=5b5=-6b1=5x13=3x46=3x35=8x56=2x12=2234561确定非基变量x24和x34b2=-2b6=-5b3=5b5=-6b1=5c24=5c46=1c13=3c35=2c56=4c34=4c12=6234561b4=3求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=6234561求x34的检验数z34 -c34 闭回路法z34 -c34 =(-c

45、46+c56+c35)-c34=(-1+4+2)-4=+1，x34进基b2=-2b4=3b3=5b5=-6b6=-5b1=5c46=1c13=3c35=2c56=4c34=4c12=6234561变量x34进基，确定离基变量minx56,x35=min2,8=2, x56离基，调整流量，进行基变换b2=-2b4=3b3=5b5=-6b6=-5b1=5x46=3x13=3x35=8x56=2x34=0 x12=2234561确定非基变量x24和x56b2=-2b4=3b3=5b5=-6b6=-5b1=5x46=5x13=3x35=6x34=2x12=2234561计算x24和x56的检验数z24

46、 -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最优解最优解的目标函数值为：min z=62+33+42+26+15=46b2=-2b4=3b3=5b5=-6b6=-5b1=5x46=5x13=3x35=6x34=2x12=2234561网络最大流问题2354671ffu25=6u42=2 u45=4u23

47、=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8边的容量和流量容量uij，流量xij可行流满足以下条件的流称为可行流：1、每一个节点流量平衡2、0 xij uij边的容量和流量、可行流21xij=5uij=521xij=3uij=5饱和边、不饱和边、流量的间隙（1，2是饱和的2、如果xij0，边从j到i的方向是不饱和的；（2，1是不饱和的间隙为12=x12=5给出一个初始的可行流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

48、=0 x=0 x=0找到所有的不饱和边，以及各边可以调整流量的方向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找到一条从1到7的不饱和链链的间隙为： = min8,3,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调整流量，f=1。继续求出网络的不饱

49、和边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求出一条从1到7的不饱和链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=1=6=9=7=min 7,1,6,9=1, 调整流量 xij=xij+1, f=f+1=2调整流量，继续求出网络的不饱和边2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=

50、1u=7u=9u=8u=8x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0求出一条从1到7的不饱和链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=5=8=7=min 7,5,8=5, 调整流量 xij=xij+5, f=f+5=2+5=7调整流量，继续求出网络的不饱和边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=

51、1x=1x=6x=02354671f=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求出一条从1到7的不饱和链=min 6,7,4,3=3, 调整流量 xij=xij+3, f=f+3=7+3=10=4=4=3=6调整流量，继续求出网络的不饱和边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求出一条从1到7的不饱和链2354671f=10u=6u=

52、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=3=7=3=min 3,1,3,7=1, 调整流量 xij=xij+1, f=f+1=10+1=11调整流量，继续求出网络的不饱和边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已求得最大流2354671f=11u=6u=2u=4u=3u=7u=4

53、u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0f=11最大流f=11，最小割集为2,5）（3,4）（3,5）u25+u34+u35=6+4+1=11最短路径问题237184566134105275934682求从1到8的最短路径237184566134105275934682X=1, w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4, w4=1w1=0w1=0237184566134105275934682X=1,4min c12,c16,c42,c47=min 0+2,0

54、+3,1+10,1+2=min 2,3,11,3=2X=1,2,4, w2=2w1=0w4=1w2=2237184566134105275934682X=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=3237184566134105275934682X=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=323718456613

55、4105275934682X=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=6237184566134105275934682X=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=8237184566134105275934682X=1,2,3,4,6,7mi

56、n 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=10237184566134105275934682X=1,2,3,4,6,7,81到10的最短路径为1，4，7，5，8，长度为10。w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10第六章 动态规划最短路径问题资源分配问题背包问题机器负荷分配问题2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径2511

57、214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f)ED(d)D(f51142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)E(f)ED(d)D(f52242511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5112421141113DC8118min2953min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min)C