运筹学教程课程.ppt

《运筹学教程课程.ppt》由会员分享，可在线阅读，更多相关《运筹学教程课程.ppt（155页珍藏版）》请在三一办公上搜索。

1、运筹学课件,天津工业大学,目 录,第一章线性规划第二章对偶第三章整数规划第四章运输问题第五章网络优化第六章动态规划,第一章 线性规划,线性规划模型线性规划的图解可行域的性质线性规划的基本概念基础解、基础可行解单纯形表线性规划的矩阵表示,线性规划模型,线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,unr,0线性规划的标准形式目标函数：min约束条件：=变量符号：0,线性规划的图解,max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,可行域的性质,线性规划的可行域是凸集线性规划的最

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

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

4、域的一个极点。目标函数值为：z=15,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基础解但不是可行解。,目标函数,约束条件,基矩阵,右边常数,进基变量、离基变量、基变换,基变量,进基变量,离基变量,目标函数,约束条件,右边常数,目标函数,约束条件,新的基矩阵,右边常数,进基变量,离基变量,目标函数,约束条件,基矩阵,目标函数,约束条件,新的基矩阵,右边常数,基础解、基础可行解,max z=x1+3x2Ds.t.x1+x2+x3=6 B-x1+2x2+x4=8 x4=0 C x3=0 x1,x2,x3

5、,x40 x1=0 E O x2=0 A,几何概念,代数概念,约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集：凸多边形,满足一组不等式约束的解,约束直线的交点,基础解,可行域的极点,基础可行解,目标函数等值线：一组平行线,目标函数值等于一个常数的解,单纯形表,求解线性规划问题,写成标准化形式,写出单纯形表,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进基，,x5离基，,x1进基，,0,-4,-2

6、,-2,-1,-86,0,1,1,0,2,-1,1,x1,0,1,-1,1,0,14,11,0,1,0,x2,0,得到最优解，最优解为：,（x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0）min z=-86，max z=86,线性规划的矩阵表示,=,=,Right Hand Side右边常数,CBTB-1aj-cj=zj-cj 称为非基变量的检验数（Reduced Cost）B-1aj=Yj，B-1b=，CBTB-1b=z0,第二章 对偶线性规划,对偶的定义对偶问题的性质原始对偶关系 目标函数值之间的关系 最优解之间的关系互补松弛关系 最优解的Kuhn-Tucher条件对偶

7、可行基对偶单纯形法对偶的经济解释,DUAL,一、对偶的定义,原始问题min z=CTXs.t.AXbX 0,对偶问题max y=bTWs.t.ATWCW 0,min,b,A,CT,C,AT,bT,max,m,n,m,n,二、对偶问题的性质,1、对偶的对偶就是原始问题,2、其他形式问题的对偶,三、原始对偶关系,1、可行解的目标函数值之间的关系 设XF、WF分别是原始问题和对偶问题的可行解z=CTXF WTAXF WTb=y2、最优解的目标函数值之间的关系 设Xo、Wo分别是原始问题和对偶问题的最优解 z=CTXo=WoTAXo=WoTb=y,3、原始问题和对偶问题最优解之间的互补松弛关系,min

8、 z=CTXs.t.AX-XS=b X,XS0,max y=bTWs.t.ATW+WS=C W,WS0,min z=CTXs.t.AXb X 0,max y=bTWs.t.ATWC W0,互补松弛关系,min z=CTXs.t.AX-XS=bX,XS 0,max y=bTWs.t.ATW+WS=CW,WS 0,XTWS=0WTXS=0,m,n,=,W,WS,AT,I,C,n,=,A,XS,-I,b,n,m,m,X,原始问题和对偶问题变量、松弛变量的维数,w1 wi wm wm+1 wm+j wn+m,x1 xj xn xn+1 xn+i xn+m,对偶问题的变量 对偶问题的松弛变量,原始问题的

9、变量 原始问题的松弛变量,xjwm+j=0wixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0,Kuhn-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 0,min z=CTXs.t.AX b X 0,max z=CTXs.t.AX b X 0,max z=CTXs.t.AX b X

10、 0,（2）,（3）,（4）,（1）,单纯形表和对偶(1),min z=CTXs.t.AX-XS=b X,XS0,max y=bTWs.t.ATW+WS=C W,WS0,min z=CTXs.t.AXb X 0,max y=bTWs.t.ATWC W0,对偶问题,原始问题,引进松弛变量,引进松弛变量,min z=CTXs.t.AX-XS=b X,XS0,max y=bTWs.t.ATW+WS=C W,WS0,WT=CBTB-1WST=CT-WTA,min z=CTXs.t.AX+XS=b X,XS0,max y=bTWs.t.ATW+WS=C W 0,WS0,min z=CTXs.t.AX b

11、 X 0,max y=bTWs.t.ATWC W 0,单纯形表和对偶(2),对偶问题,原始问题,引进松弛变量,引进松弛变量,min z=CTXs.t.AX+XS=b X,XS0,max y=bTWs.t.ATW+WS=C W 0,WS0,WT=CBTB-1WST=CT-WTA,max z=CTXs.t.AX-XS=b X,XS0,max y=bTWs.t.ATW-WS=C W 0,WS0,max z=CTXs.t.AX b X 0,min y=bTWs.t.ATW C W 0,单纯形表和对偶(3),对偶问题,原始问题,引进松弛变量,引进松弛变量,max z=CTXs.t.AX-XS=b X,X

12、S0,min y=bTWs.t.ATW-WS=C W 0,WS0,WT=CBTB-1WST=WTA-CT,max z=CTXs.t.AX+XS=b X,XS0,max y=bTWs.t.ATW-WS=C W,WS0,max z=CTXs.t.AX b X 0,min y=bTWs.t.ATW C W 0,单纯形表和对偶(4),对偶问题,原始问题,引进松弛变量,引进松弛变量,max z=CTXs.t.AX+XS=b X,XS0,min y=bTWs.t.ATW-WS=C W,WS0,WT=CBTB-1WST=WTA-CT,2、对偶单纯形法（初始解原始不可行的问题）,已获得最优解：（x1,x2,x

13、3,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,3、初始解原始、对偶都不可行的问题,解法1：先解决原始可行性,在得到原始可行解时同时得到对偶可行解，已获得最优解：（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,解法2：先解决对偶可行性,已得到对偶可行解，再用对偶单纯形法求解,得到原始可行解，已获得最优解：（x1,x2,x3,x4,x

14、5,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、原始问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨/件）,剩余的资源（吨）,消耗的资源（吨）,2、对偶问题,资源限量（吨）,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 max z=min y,

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

16、四章 运输问题,运输问题的表示网络图、线性规划模型、运输表初始基础可行解西北角法、最小元素法非基变量的检验数闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量,2,3,2,1,3,4,1,运输问题网络图,s2=27,s3=19,d1=22,d2=13,d3=12,d4=13,s1=14,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,运输问题线性规划模型,供应地约束,需求地约束,运输问题的表格表示,初始基础可行解西北角法,8,13,13,14,6,6,初始基础可行解最小元素法（1）,最小元素法（2）,最小元素法（3）,最小元素法（4）,最小元素法（

17、5）,最小元素法（6）,-5,非基变量xij的检验数zij-cij闭回路法(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=(

18、8-2+10)-5=+11,+11,-5,-7,-9,-5,闭回路法(6),z32-c32=(c22-c23+c33)-c32=(4-2+10)-9=+3,+3,-5,-7,-9,+11,非基变量xij的检验数zij-cij对偶变量法(1),v4=0,对偶变量法(2),u3+v4=c34u3=6,对偶变量法(3),u3+v3=c33v3=4,对偶变量法(4),u2+v3=c23u2=-2,对偶变量法(5),u2+v2=c22v2=6,对偶变量法(6),u2+v1=c21v1=10,对偶变量法(7),u1+v1=c11u1=-4,对偶变量法(8),z12-c12=u1+v2-c12=(-4)+6

19、-7=-5,-5,对偶变量法(9),z13-c13=u1+v3-c13=(-4)+4-5=-5,-5,-5,对偶变量法(10),z14-c14=u1+v4-c14=(-4)+0-3=-7,-7,-5,-5,对偶变量法(11),z24-c24=u2+v4-c24=(-2)+0-7=-9,-9,-5,-5,-7,对偶变量法(12),z31-c31=u3+v1-c31=6+10-5=11,11,-5,-5,-7,-9,对偶变量法(13),z32-c32=u3+v2-c32=6+6-9=+3,+3,-5,-5,-7,-9,11,选择进基变量,确定离基变量,x31进基,minx21,x33=min8,6

20、=6,x33离基,+3,-5,-5,-7,-9,11,调整运量,重新计算检验数,确定进基、离基变量,x14进基,minx11,x34=min14,13=13,x34离基,-11,-5,-5,+4,+2,-8,调整运量,重新计算检验数,所有zij-cij0,得到最优解。Min z=61+3 13+8 2+4 13+2 12+5 19=142,-11,-5,-5,-4,-8,-2,第五章 网络优化,网络的基本概念最短路径问题 网络最大流问题,网络的基本概念,节点与（有向）边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j）,路径（Path）前后相继并且方向相同的边序列 P=(1,2

21、),(2,3),(3,4),4,2,3,1,4,2,3,1,网络由节点和边组成,回路（Circuit）起点和终点重合的路径称为回路=(1,2),(2,4),(4,1)回路中各条边方向相同,4,2,3,1,链（Chain）前后相继并且方向不一定相同的边序列称为链 C=(1,2),(3,2),(3,4),4,2,3,1,连通图 任意两个节点之间至少有一条链的图称为连通图,2,4,3,5,1,圈(Cycle)起点和终点重合的链称为圈=(1,2),(2,4),(3,4),(1,3)圈中各条边方向不一定相同,4,2,3,1,树(Tree)无圈的连通图称为树 树中只与一条边关联的节点称为悬挂节点,树的性质

22、,任何树至少有一个悬挂节点,2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,如果树的节点个数为m，则边的个数为m-1,树中任意两个节点之间只有唯一的一条链,在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈,网络的生成树,由网络的所有节点（m个）和网络的m-1条边组成的树称为网络的生成树，网络中不属于生成树的边称为生成树的弦,网络的生成树的变换,网络的一个生成树，增加一条弦，形成唯一的圈，去掉生成树的一条边，得到一个新的网络的生成树,生成树2,生成树3,生成树1,/,/,最短路径问题,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2

23、,求从1到8的最短路径,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=1X=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=2X=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

24、,5,9,3,4,6,8,2,X=1,2,4,min c16,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=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=3X=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,

25、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=6X=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=8X=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,

26、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=10X=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，长度为10。,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,

27、网络最大流问题,边的容量和流量容量uij，流量xij可行流满足以下条件的流称为可行流：1、每一个节点流量平衡2、0 xij uij,边的容量和流量、可行流,饱和边、不饱和边、流量的间隙,（1，2）是饱和的,2、如果xijuij，边从i到j的方向是不饱和的；,（1，2）是不饱和的间隙为12=u12-x12=5-3=2,1、如果xij=uij，边从i到j的方向是饱和的；,3、如果xij=0，边从j到i的方向是饱和的；,（2，1）是饱和的,如果xij0，边从j到i的方向是不饱和的；,（2，1）是不饱和的间隙为12=x12=5,给出一个初始的可行流xij=0,找到所有的不饱和边，以及各边可以调整流量的

28、方向,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,找到一条从1到7的不饱和链,链的间隙为：=min8,3,1,8=1调整链的流量：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,

29、调整流量，f=1。继续求出网络的不饱和边,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,调整

30、流量 xij=xij+1,f=f+1=2,调整流量，继续求出网络的不饱和边,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,调整流量 xij=xij+5,f=f+5=2+5=7,调整流量，继续求出网络的不饱和边,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=

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

32、,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,调整流量 xij=xij+1,f=f+1=10+1=11,调整流量，继续求出网络的不饱和边,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的不饱

33、和链，从1开始可以到达的节点为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,第六章 动态规划,最短路径问题资源分配问题背包问题机器负荷分配问题,一、最短路径问题,求从A到E的最短路径,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C

34、1,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,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

35、,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,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,2,5,1,12,

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

37、,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(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=21,f2(B2)=14,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(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,

38、f2(B1)=21,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(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2,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,

39、f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2（B2，C1）C1,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(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B

40、2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2（B2，C1）C1（C1，D1）D1,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(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E从A到E的最短路径为19，路线为AB 2C1 D1 E,2、资源分配问题,4万元资金，如何分配给A、B、C三个项目，使总效益最大,4万元,2万元,1万元,0万元,4万元,2万元,1万元,0万元,4万元,2万元,1万元,0万元,4万元,x1A项目 x2B项目 x3C项目 x4,3万元,3万元,3万元,0,f,