运筹学三学习.pptx

《运筹学三学习.pptx》由会员分享，可在线阅读，更多相关《运筹学三学习.pptx（165页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

2、的可行域是凸集线性规划的最优解在极点上凸集凸集不是凸集极点第5页/共165页线性规划的基本概念线性规划的基矩阵、基变量、非基变量=目标函数约束条件行列式0基矩阵右边常数第6页/共165页第7页/共165页基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=20第8页/共165页基变量x1、x2、x4，非基变量x3、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=18第

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

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

5、件基矩阵=第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 A第20页/共165页几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基础解可行域的极点基础可行解目标函数等值线：一组平行线 目标函数值等于一个常数的解第21页/共165页单纯形表第22页/共165页求解线性规划问题写成标准化形式第23页/

6、共165页写出单纯形表25/136/20-3-20-2-72011/201-1/27/1/21x51/2101/218/1/2071811/21/2x20 x6离基，x2进基，x5离基，x1进基，第24页/共165页0-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页第26页/共165页第27页/共165页第28页/共165页第29页/共165页线性规划的矩阵表示=第30页/共165页=第31页/共165页第32页/共16

7、5页第33页/共165页CBTB-1aj-cj=zj-cj 称为非基变量的检验数（Reduced Cost）B-1aj=Yj，B-1b=，CBTB-1b=z0第34页/共165页第35页/共165页第二章第二章 对偶线性规划对偶线性规划对偶的定义对偶问题的性质原始对偶关系 目标函数值之间的关系 最优解之间的关系互补松弛关系 最优解的Kuhn-Tucher条件对偶可行基对偶单纯形法对偶的经济解释DUAL第36页/共165页一、对偶的定义原始问题min z=CTXs.t.AXbX 0对偶问题max y=bTWs.t.ATWCW 0minbACTCATbTmaxmnmn第37页/共165页二、对偶问

8、题的性质1、对偶的对偶就是原始问题max z=-CTXs.t.-AX-bX 0min y=-bTWs.t.-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分别是

9、原始问题和对偶问题的可行解z=CTXF WTAXF WTb=y2、最优解的目标函数值之间的关系 设Xo、Wo分别是原始问题和对偶问题的最优解 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=

10、bTWs.t.ATW+WS=CW,WS 0XTWS=0WTXS=0mn=WWSATICn=AXS-IbnmmX原始问题和对偶问题变量、松弛变量的维数第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)对

11、偶可行条件（DFC）ATW+WS=CW,WS 0(3)互补松弛条件（CSC）XTWS=0WTXS=0第44页/共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对偶问题原始

12、问题引进松弛变量引进松弛变量第46页/共165页min z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW+WS=C W,WS0WT=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页min z=CTXs.t.AX+XS=b X,XS0max y=bTWs.t.ATW+WS=C W 0,WS0WT

13、=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页/共165页max z=CTXs.t.AX-XS=b X,XS0min y=bTWs.t.ATW-WS=C W 0,WS0WT=CBTB-1WST=WTA-CT第51页/共165页max z=CTXs.t.AX+XS=b X,XS0max y=bTWs.t.ATW-WS=C W,W

14、S0max z=CTXs.t.AX b X 0min y=bTWs.t.ATW C W 0单纯形表和对偶(4)对偶问题原始问题引进松弛变量引进松弛变量第52页/共165页max z=CTXs.t.AX+XS=b X,XS0min y=bTWs.t.ATW-WS=C W,WS0WT=CBTB-1WST=WTA-CT第53页/共165页2、对偶单纯形法（初始解原始不可行的问题）第54页/共165页第55页/共165页第56页/共165页已获得最优解：（x1,x2,x3,x4,x5,x6）=（5,7,6,0,0,0）min z=35对偶问题的最优解为：（w1,w2,w3,w4,w5,w6）=（-1,

15、5,7,0,0,0）max y=35第57页/共165页3、初始解原始、对偶都不可行的问题第58页/共165页解法1：先解决原始可行性第59页/共165页第60页/共165页在得到原始可行解时同时得到对偶可行解，已获得最优解：（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页解法2：先解决对偶可行性已得到对偶可行解，再用对偶单纯形法求解第62页/共165页第63页/共165页得到原始可行解，已获得最优解：（x1,x2,x3,x4,x5,x

16、6）=（5,7,6,0,0,0）min z=17对偶问题的最优解为：（w1,w2,w3,w4,w5,w6）=（-7,5,10,0,0,0）max y=17第64页/共165页五、对偶的经济解释1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）第65页/共165页2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min

17、y第66页/共165页3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0第67页/共165页w1w2wm4、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源第68页/共165页机会成本利润差额成本5、产品的差额成本（Reduced Cost）差额成本=机会成本-利润第69页/共165页5、互补松弛关系的经济解释在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机

18、会成本等于利润（4）机会成本大于利润的产品不安排生产第70页/共165页第四章 运输问题运输问题的表示网络图、线性规划模型、运输表初始基础可行解西北角法、最小元素法非基变量的检验数闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量第71页/共165页2321341运输问题网络图s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106第72页/共165页运输问题线性规划模型供应地约束需求地约束第73页/共165页运输问题的表格表示第74页/共165页初始基础可行解西北角法813131466第75页/共165页初始基础可行解

19、最小元素法（1）第76页/共165页最小元素法（2）第77页/共165页最小元素法（3）第78页/共165页最小元素法（4）第79页/共165页最小元素法（5）第80页/共165页最小元素法（6）第81页/共165页-5非基变量xij的检验数zij-cij闭回路法(1)z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5第82页/共165页-5闭回路法(2)z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5-5第83页/共165页-5闭回路法(3)z14-c14=(c11-c21+c21-c23+c33-c14)-c13=(6-8+2-10+6)-3=

20、-7-7-5第84页/共165页-5闭回路法(4)z24-c24=(c23-c33+c34)-c24=(2-10+6)-7=-9-9-5-7第85页/共165页-5闭回路法(5)z31-c31=(c21-c23+c33)-c31=(8-2+10)-5=+11+11-5-7-9第86页/共165页-5闭回路法(6)z32-c32=(c22-c23+c33)-c32=(4-2+10)-9=+3+3-5-7-9+11第87页/共165页非基变量xij的检验数zij-cij对偶变量法(1)v4=0第88页/共165页对偶变量法(2)u3+v4=c34u3=6第89页/共165页对偶变量法(3)u3+v

21、3=c33v3=4第90页/共165页对偶变量法(4)u2+v3=c23u2=-2第91页/共165页对偶变量法(5)u2+v2=c22v2=6第92页/共165页对偶变量法(6)u2+v1=c21v1=10第93页/共165页对偶变量法(7)u1+v1=c11u1=-4第94页/共165页对偶变量法(8)z12-c12=u1+v2-c12=(-4)+6-7=-5-5第95页/共165页对偶变量法(9)z13-c13=u1+v3-c13=(-4)+4-5=-5-5-5第96页/共165页对偶变量法(10)z14-c14=u1+v4-c14=(-4)+0-3=-7-7-5-5第97页/共165页

22、对偶变量法(11)z24-c24=u2+v4-c24=(-2)+0-7=-9-9-5-5-7第98页/共165页对偶变量法(12)z31-c31=u3+v1-c31=6+10-5=1111-5-5-7-9第99页/共165页对偶变量法(13)z32-c32=u3+v2-c32=6+6-9=+3+3-5-5-7-911第100页/共165页选择进基变量,确定离基变量x31进基,minx21,x33=min8,6=6,x33离基+3-5-5-7-911第101页/共165页调整运量,重新计算检验数,确定进基、离基变量x14进基,minx11,x34=min14,13=13,x34离基-11-5-5

23、+4+2-8第102页/共165页调整运量,重新计算检验数所有zij-cij0,得到最优解。Min z=61+3 13+8 2+4 13+2 12+5 19=142-11-5-5-4-8-2第103页/共165页第五章 网络优化网络的基本概念网络最小费用流问题网络最大流问题最短路径问题第104页/共165页网络的基本概念节点与（有向）边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j）ji路径（Path）前后相继并且方向相同的边序列 P=(1,2),(2,3),(3,4)42314231网络由节点和边组成第105页/共165页回路（Circuit）起点和终点重合的路径称为回路

24、=(1,2),(2,4),(4,1)回路中各条边方向相同4231链（Chain）前后相继并且方向不一定相同的边序列称为链 C=(1,2),(3,2),(3,4)4231第106页/共165页连通图 任意两个节点之间至少有一条链的图称为连通图24351圈(Cycle)起点和终点重合的链称为圈 =(1,2),(2,4),(3,4),(1,3)圈中各条边方向不一定相同4231树(Tree)无圈的连通图称为树 树中只与一条边关联的节点称为悬挂节点第107页/共165页树的性质任何树至少有一个悬挂节点243512435124351如果树的节点个数为m，则边的个数为m-1树中任意两个节点之间只有唯一的一条

25、链在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈第108页/共165页网络的生成树由网络的所有节点（m个）和网络的m-1条边组成的树称为网络的生成树，网络中不属于生成树的边称为生成树的弦4231423142314231423142314231第109页/共165页网络的生成树的变换4231网络的一个生成树，增加一条弦，形成唯一的圈，去掉生成树的一条边，得到一个新的网络的生成树423142314231生成树2生成树3生成树1/第110页/共165页网络的生成树和线性规划的关系网络的一个生成树对应于线性规划的一个基生成树上的边对应于线性规划的基变量生成树的弦对应于线性规划的非基变量生成树

26、的变换对应于线性规划单纯形法的进基和离基变换第111页/共165页网络最小费用流问题b2=-2b4=3b3=5b5=-6b6=-5b1=5c24=5c46=1c13=3c35=2c56=4c34=4c12=6234561需求节点供应节点cij 单位流量的费用第112页/共165页初始基础可行解生成树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

27、第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=6234561第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页变量x

28、34进基，确定离基变量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=3b3=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

29、-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=-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，流

30、量xij可行流满足以下条件的流称为可行流：1、每一个节点流量平衡2、0 xij uij边的容量和流量、可行流第122页/共165页21xij=5uij=521xij=3uij=5饱和边、不饱和边、流量的间隙（1，2）是饱和的2、如果xij0，边从j到i的方向是不饱和的；（2，1）是不饱和的间隙为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页找到所有的不饱和边，以

31、及各边可以调整流量的方向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,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。继续求出网络的不饱和边

32、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=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第129页/共165页调整流量，继续求出网络的不饱和边2354671f=2f=2u=6u=

33、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=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第131页/共165页调整流量，继续求出网络的不饱和边2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=

34、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=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=3

35、x=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=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=

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

37、14,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=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

38、页/共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页237184566134105275934682X=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页237184566134105275

39、934682X=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页237184566134105275934682X=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页23718456613410527

40、5934682X=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页2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径第148页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0第149页/共165页25112141061041311123965810

41、52C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0第150页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5第151页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5第152页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8第

42、153页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7第154页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8第155页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f

43、4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21第156页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14第157页/共165页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2

44、)=14f2(B1)=21第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

45、)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1第160页/共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 （C1，D1）D1第161页

46、/共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 （C1，D1）D1 （D1，E）E从A到E的最短路径为19，路线为AB 2C1 D1 E 第162页/共165页2、资源分配问题4万元资金，如何分配给A、B、C三个项目，使总效益最大第163页/共165页4万元2万元1万元0万元4万元2万元1万元0万元4万元2万元1万元0万元4万元 x1A项目 x2B项目 x3C项目 x43万元3万元3万元0f第164页/共165页感谢您的观看！第165页/共165页