运筹学复习资料.ppt

《运筹学复习资料.ppt》由会员分享，可在线阅读，更多相关《运筹学复习资料.ppt（100页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学复习资料运筹学复习资料q线性规划的基本概念q单纯形法和对偶单纯形法q对偶线性规划q运输问题q网络最小费用流问题q网络最大流问题q网络最短路径问题q动态规划最短路径问题q动态规划资源分配问题q动态规划背包问题学而时习之不亦乐乎线性规划的基本概念线性规划的基本概念min z=x1+2x2s.t.x1+x24(1)-x1+x21(2)x2 3(3)x1,x2 0OABCDEFGH41234123x1x2x3=0 x4=0 x2=0 x1=0 x5=0引进松弛变量x3,x4,x5min z=x1+2x2s.t.x1+x2+x3 =4 -x1+x2 -x4=1 x2 +x5=3 x1,x2 x3,

2、x4,x50基础解O A B C D E F G HB C E FB C E F基础可行解可行域目标函数等值线.最优解COABCDEFGH41234123x1x2x3=0 x4=0 x2=0 x1=0 x5=0qA不是可行解，是由于变量（）0。qG不是可行解，是由于变量（）0。q满足 x1，x2，x3，x50，x40 的区域是（）。q满足 x1，x2，x4，x50，x30 的区域是（）。q满足 x1，x2，x3，x40，x50 的区域是（）。qA点对应的解，基变量为（），非基变量为（）。qF点对应的解，基变量为（），非基变量为（）。qC点对应的解，基变量为（），非基变量为（）。x1 x4 x5

3、x1 x2 x4x2 x3 x5x2 x3x3 x5x1 x4x4x3OABCBFGEFHOABCDEFGH41234123x1x2x3=0 x4=0 x2=0 x1=0 x5=0q从O点到C点的单纯形叠代，进基变量为（），离基变量为（）。q从C点到B点的单纯形叠代，进基变量为（），离基变量为（）。q从B点到F点的单纯形叠代，进基变量为（），离基变量为（）。x2x4x1x3x4x5单纯形法和对偶单纯形法单纯形法和对偶单纯形法q单纯形法适用的问题约束条件全部为，右边常数全部为非负，对目标函数的系数没有要求。q对偶单纯形法应用的条件约束条件中至少有一个是，相应的右边常数为非负，目标函数系数全部为非

4、负。min z=3x1-2x2s.t.x1+2x212 2x1+x218 x1,x20min z=3x1+2x2s.t.x1+2x212 2x1+x218 x1,x20单纯形法的算法描述将线性规划问题标准化是否有初始基础可行解用两阶段法得到初始基础可行解列出单纯形表，将单纯形表变为标准形式根据非基变量检验数选择进基变量根据非基变量检验数选择进基变量是否所有检验数全小于等于0已得到最优解NYYN是否有可行解无可行解STEP 0 将线性规划问题标准化STEP 1 是否有明显的初始基础可行解，如果有，转STEP 3，否则，转STEP 2。STEP 2 构造辅助问题，用两阶段法求解辅助问题。如果辅助问

5、题最优解的目标函数值大于0，原问题无可行解，算法终止。否则转STEP 3。STEP 3 写出单纯形表，将基变量在约束条件中的系数消为单位矩阵，将基变量在目标函数中的系数消为0。转STEP 4。STEP 4 如果所有非基变量的检验数全为负数或0，则已获得最优解，算法终止。否则，选择检验数为正数并且绝对值最大的非基变量为进基变量。转STEP 5。STEP 5 如果进基变量在约束条件中的系数全为负数或0，目标函数无界，算法终止。否则根据右边常数和正的系数的最小比值，确定离基变量。转STEP 6。STEP 6 进基变量列和离基变量行交叉的元素称为主元。对单纯形表进行行变换，将主元变为1，将主元所在列的

6、其他元素变为0。转STEP 4。单纯形表min z=3x1-2x2s.t.x1+2x212 2x1+x218 x1,x20zx1x2x3x4RHSz1-32000 x3012101212/2x4021011818/1x2进基，x3离基min z=3x1-2x2s.t.x1+2x2+x3 =12 2x1+x2 +x4 =18 x1,x2,x3,x40最优解为：(x1,x2,x3,x4)=(0,6,0,12)，min z=-12zx1x2x3x4RHSz1-40-10-12x201/211/206x403/20-1/2112zx1x2x3x4RHSz1-32000 x3012101212/2x40

7、21011818/1min z=3x1+2x2s.t.x1+2x2-x3 =12 2x2+x2 -x4=18 x1,x2,x3,x40对偶单纯形法的例子min z=3x1+2x2s.t.x1+2x212 2x1+x218 x1,x209x4=061812x1x2最优解（x1,x2,x3,x4）=（8,2,0,0）x3=0 x1=0 x2=0zx1x2x3x4RHS1-3-2000 x30-1-210-12x40-2-101-18zx1x2x3x4RHS1-3-2000 x3012-1012x40210-118约束两边同乘以-1zx1x2x3x4RHS1-3-2000 x30-1-210-12x

8、40-2-101-18-3/-2-2/-1zx1x2x3x4RHS1-3-2000 x30-1-210-12x1011/20-1/29x4离基，x1进基。第二个约束两边同除以-2，得到zx1x2x3x4RHS1-3-2000 x30-1-210-12x1011/20-1/29zx1x2x3x4RHS10-1/20-3/227x300-3/21-1/2-3x1011/20-1/291/33/1x3离基，x2进基消去主元所在列的其他元素，得到zx1x2x3x4RHS10-1/20-3/227x200-3/21-1/2-3x1011/20-1/29zx1x2x3x4RHS10-1/20-3/227x

9、2001/2-1/31/61x1011/20-1/29第一个约束两边同除以-3，得到zx1x2x3x4RHS10-1/20-3/227x2001/2-1/31/61x1011/20-1/29zx1x2x3x4RHS100-1/3-4/328x2001/2-1/31/61x10101/3-2/38消去主元所在列的其他元素，得到zx1x2x3x4RHS100-1/3-4/328x2001-2/31/32x10101/3-2/38zx1x2x3x4RHS100-1/3-4/328x2001/2-1/31/61x10101/3-2/38原始问题的最优解为(x1,x2,x3,x4)=(8,2,0,0)，

10、min z=28对偶问题的最优解为(w1,w2,w3,w4)=(1/3,4/3,0,0)max y=28将主元所在行乘以2，得到9061812x1x2对偶单纯形叠代的过程如下图所示x3=0 x4=0 x1=0 x2=0对偶线性规划对偶线性规划min z=2x1+4x2-x3s.t.3x1-x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max y=6w1+12w2+8w3+15w4s.t.3w1-w2+2w3+w4 2 -w1+2w2+w3+3w4 4 2w1-3w2+2w3-w4 -1 w1 0,w2 ,w3 0,w4 0=unr=x10 x

11、20 x3:unrq原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质，用 表示 原始问题约束条件的性质影响对偶问题变量的性质，用 表示max z=3x1+4x2-x3s.t.4x1+2x2+5x338 -x1+3x2-x318 2x1-x2+3x326 3x1+x2-2x3 10 x1,x2,x30min y=38w1+18w2+26w3+10w4s.t.4w1-w2+2w3+3w4 3 2w1+3w2-w3+w4 4 5w1-w2+3w3-2w4-1w10,w20,w30,w40

12、|变量|松弛变量|(x1,x2,x3,x4,x5,x6,x7)(0,19,0,0,39,45,9)(2,0,0,0,5,0,11)(w1,w2,w3,w4,w5,w6,w7)|变量|松弛变量|互补松弛关系+x4 =38-x5 =18+x6 =26-x7=10 x4,x5,x6,x7 0-w5 =3-w6 =4-w7 =-1,w5,w6,w70原始问题对偶问题 原始问题的每一个变量和对偶问题相应的松弛变量组成互补松弛对，每一对变量中至少有一个等于0。对偶问题的每一个变量和原始问题相应的松弛变量组成互补松弛对，每一对变量中至少有一个等于0。max z=9x1+4x2+x3s.t.4x1+2x2+5

13、x3 38（1）原料总量约束 2x1+x2+3x3 26（2）排放污染约束 30 x1+10 x2+20 x3100（3）销售总额约束 x1+x2+x3 18（4）总产量约束 x1,x2,x3 0产品A产品B产品C条件利润（万元/吨）941总利润最大化耗用原料（吨/吨）425耗用原料总量不超过38吨排放污染（m3/吨）213排放污染总量不超过26m3销售价格（万元/吨）301020销售总额不低于100万元总产量（吨）111总产量不低于18吨对偶的经济解释TITLE 线性规划的经济解释!产品A 产品B 产品C!-!利润（万元/吨）9 4 1!原料约束（吨/吨）4 2 5 不超过38吨!排放污染（

14、m3/吨）2 1 3 不超过26m3!销售额（万元/吨）30 10 20 不低于100万元!总产量（吨）不低于18吨!-max 9x1+4x2+x3 !总利润最大化st4x1+2x2+5x338 !原料约束2x1+x2+3x3100 !销售总额约束x1+x2+x318 !总产量约束end LP OPTIMUM FOUND AT STEP 4 OBJECTIVE FUNCTION VALUE 1)77.00000 VARIABLE VALUE REDUCED COST X1 1.000000 0.000000 X2 17.000000 0.000000 X3 0.000000 10.500000

15、 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 2.500000 3)7.000000 0.000000 4)100.000000 0.000000 5)0.000000 -1.000000 NO.ITERATIONS=4 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 9.000000 INFINITY 1.000000 X2 4.000000 0.5

16、00000 INFINITY X3 1.000000 10.500000 INFINITY RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 38.000000 14.000000 2.000000 3 26.000000 INFINITY 7.000000 4 100.000000 100.000000 INFINITY 5 18.000000 1.000000 8.500000产品A产品B产品C右边常数松弛变量影子价格利润（万元/吨）941最大利润为77万元耗用原料（吨/吨）42538

17、02.5排放污染（m3/吨）2132670.0销售价格（万元/吨）3010201001000.0总产量（吨）111180-1.0最优计划产量（吨）1170机会成本（万元/吨）9411.5差额称本（万元/吨）0010.5q原料是紧缺约束，增加原料供应可以增加利润，边际利润为2.5万元/吨q总产量不小于18吨限制了利润增加，减少总产量的限制对增加利润有利q产品C不生产，是由于利润太小，利润至少要增加到11.5万元/吨，才有可能安排生产给出运输问题的初始基础可行解最小元素法西北角法求出各非基变量的检验数对偶变量法闭回路法确定离基变量确定进基变量调整运量 12341129111412027151382

18、3031065418012585110210运输问题运输问题12341129111412027151382303106541801258511021012510508535018003030075357507500用最小元素法得到一个初始基础可行解12341129111412027151382303106541801258511021012585180303575-7求非基变量x11的检验数12341129111412027151382303106541801258511021012585180303575-7-8求非基变量x14的检验数1234112911141202715138230310

19、6541801258511021012585180303575-7-8-4求非基变量x22的检验数12341129111412027151382303106541801258511021012585180303575-7-8-6-7求非基变量x31的检验数12341129111412027151382303106541801258511021012585180303575-7-8-4-7+1求非基变量x32的检验数12341129111412027151382303106541801258511021012585180303575-7-8-4-7+1+4求非基变量x33的检验数12341129

20、111412027151382303106541801258511021012585180303575-7-8-6-7+1+4x33=75进基，x23=0离基，x24=30+75=105，x34=180-75=105确定进基变量和离基变量123411291114120271513823010531065418075125851102101258510535-3求非基变量x11的检验数123411291114120271513823010531065418075125851102101258510535-3-4求非基变量x14的检验数1234112911141202715138230105310

21、65418075125851102101258510535-3-4-8求非基变量x22的检验数123411291114120271513823010531065418075125851102101258510535-6-4-4-8求非基变量x23的检验数123411291114120271513823010531065418075125851102101258510535-5-4-4-7-8求非基变量x31的检验数123411291114120271513823010531065418075125851102101258510535-5-4-4-7-3-8得到最优解：x12=85,x13=35

22、,x21=125,x24=105,x33=75,x34=105 min z=3660求非基变量x32的检验数1254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c14=6c46=5c13=2c34=3c45=1c35=7c67=9c57=8网络最小费用流问题网络最小费用流问题给出最小费用流问题的初始基础可行解求出各非基变量的检验数对偶变量法闭回路法确定离基变量确定进基变量调整流量 1254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c14=6c46=5c13=2c34=3c45=1c35=7c67=9c57=8找到一个初始

23、的基础可行解生成树x12=3x13=6x35=1x57=5x46=8x67=11254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c14=6c46=5c13=2c35=7c67=9c57=8计算各非基变量的检验数x12=3x13=6x35=1x57=5x46=8x67=1z24-c24=(-c46-c67+c54+c35+c13-c12)-c24=-5-9+8+7+2-4-6=-71254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c46=5c13=2c34=3c35=7c67=9c57=8计算各非基变量的检验数x12=3

24、x13=6x35=1x57=5x46=8x67=1z24-c24=(-c46-c67+c54+c35+c13-c12)-c24=-5-9+8+7+2-4-6=-7z34-c34=(-c46-c67+c57+c35)-c34=-5-9+8+7-3=-21254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c46=5c13=2c45=1c35=7c67=9c57=8计算各非基变量的检验数，确定进基变量x12=3x13=6x35=1x57=5x46=8x67=1z24-c24=(-c46-c67+c54+c35+c13-c12)-c24=-5-9+8+7+2-4-6

25、=-7z34-c34=(-c46-c67+c57+c35)-c34=-5-9+8+7-3=-2z45-c45=(-c57+c67+c46)-c45=-8+9+5-1=+5，x45进基1254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c14=6c46=5c13=2c34=3c45=1c35=7c67=9c57=8确定离基变量x12=3x13=6x35=1x57=5x46=8x67=1min x67,x46=min1,8=1，x67离基1254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c14=6c46=5c13=2c34=

26、3c45=1c35=7c67=9c57=8得到新的基础可行解x12=3x13=6x35=1x57=6x46=7x45=11254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c14=6c46=5c13=2c34=3c45=1c35=7c67=9c57=8求非基变量x24的检验数x12=3x13=6x35=1x57=6x46=7x45=1z24-c24=(-c45+c35+c13-c12)-c24=-1+7+2-4-6=-21254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c14=6c46=5c13=2c34=3c45=1c

27、35=7c67=9c57=8x12=3x13=6x35=1x57=6x46=7x45=1求非基变量x34的检验数z24-c24=(-c45+c35+c13-c12)-c24=-1+7+2-4-6=-2z34-c34=(-c45+c35)-c34=-1+7-3=+31254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c14=6c46=5c13=2c34=3c45=1c35=7c67=9c57=8x12=3x13=6x35=1x57=6x46=7x45=1求非基变量x67的检验数，确定进基变量z24-c24=(-c45+c35+c13-c12)-c24=-1+7

28、+2-4-6=-2z34-c34=(-c45+c35)-c34=-1+7-3=+3z67-c67=(c57-c45+c46)-c67=8+1-5-9=-5，x34进基1254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c14=6c46=5c13=2c34=3c45=1c35=7c67=9c57=8x12=3x13=6x35=1x57=6x46=7x45=1确定离基变量minx35=1，x35离基1254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c14=6c46=5c13=2c34=3c45=1c35=7c67=9c57=

29、8x12=3x13=6x34=1x57=6x46=7x45=2得到新的基础可行解1254367b1=9b2=-3b3=-5b4=8b5=4b6=-7b7=-6c12=4c14=6c46=5c13=2c34=3c45=1c35=7c67=9c57=8x12=3x13=6x34=1x57=6x46=7x45=2分别求非基变量x24、x35、x67的检验数z24-c24=(c34+c13-c12)-c24=3+2-4-6=-5z35-c35=(c45+c34)-c35=1+3-7=-3z67-c67=(c57-c45+c46)-c67=8+1-5-9=-5，获得最优解1254367b1=9b2=-3

30、b3=-5b4=8b5=4b6=-7b7=-6c12=4c14=6c46=5c13=2c34=3c45=1c35=7c67=9c57=8x12=3x13=6x34=1x57=6x46=7x45=2最优解最优解如上图所示min z=c12x12+c13x13+c34x34+c45x45+c46x46+c57x57 =(43)+(2 6)+(3 1)+(1 2)+(5 7)+(8 6)=1121254367最大流问题最大流问题36112743847125uij求从1到7的最大流125436736112743847125uij检查每一条边不饱和的方向，用 表示x=0 x=0 x=0 x=0 x=0

31、x=0 x=0 x=0 x=0 x=0 x=0 x=0 =min12,26,67=min3,6,12=3 =min13,35,57=min11,4,5=4125436736112743847125uij寻找从1到7的不饱和链，用 表示，求出每一条不饱和链的间隙 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0=3=6=12=11=4=5125436736112743847125uij增加不饱和链的流量检查每一条边不饱和的方向，用 表示x=3x=3x=4x=0 x=0 x=0 x=0 x=0 x=3x=4x=4x=0f=7f=7寻找从1到7的不饱和链

32、，用 表示，求出每一条不饱和链的间隙 125436736112743847125uijx=3x=3x=4x=0 x=0 x=0 x=0 x=0 x=3x=4x=4x=0=7f=7f=7=min13,34,46,67=min7,3,4,8=3=3=4=9125436736112743847125uij增加不饱和链的流量检查每一条边不饱和的方向，用 表示x=3x=3x=7x=0 x=0 x=3x=3x=0 x=6x=4x=4x=0f=10f=10寻找从1到7的不饱和链，用 表示，求出每一条不饱和链的间隙 125436736112743847125uijx=3x=3x=7x=0 x=0 x=3x=3

33、x=0 x=6x=4x=4x=0f=10f=10 =min13,32,26,67=min4,2,3,6=2=4=2=3=6增加不饱和链的流量检查每一条边不饱和的方向，用 表示125436736112743847125uijx=3x=5x=9x=2x=0 x=3x=3x=0 x=8x=4x=4x=0f=12f=12寻找从1到7的不饱和链125436736112743847125uijx=3x=5x=9x=2x=0 x=3x=3x=0 x=8x=4x=4x=0f=12f=12已不存在从1到7的不饱和链。获得最大流，f=12X=1,3，X=2,4,5,6,7最小割集为(1,2),(3,2),(3,4

34、),(3,5)，用 表示最小割集的容量为u12+u32+u34+u35=3+2+3+4=1212345678263958476104117126最短路径问题最短路径问题求1到8的最短路径12345678263958476104117126w1=0X=1min0+2,0+6,0+3=min2,6,3=2，w2=212345678263958476104117126w1=0X=1,2min2+9,2+5,2+4,0+6,0+3=min11,7,6,6,3=3，w4=3w2=212345678263958476104117126w1=0w2=2X=1,2,4min2+9,2+5,2+4,0+6,3+

35、7,3+6,3+10=min11,7,6,6,10,9,13=6，w3=6w4=312345678263958476104117126w1=0w2=2X=1,2,3,4min2+9,2+5,6+8,3+6,3+10=min11,7,14,9,13=7，w6=7w4=3w3=612345678263958476104117126w1=0w2=2X=1,2,3,4,6min2+9,7+4,7+11,3+10=min11,11,18,13=11，w5=11w4=3w3=6w6=712345678263958476104117126w1=0w2=2X=1,2,3,4,5,6min11+12,7+7,7

36、+11,3+10=min23,14,18,13=13，w7=13w4=3w3=6w6=7w5=1112345678263958476104117126w1=0w2=2X=1,2,3,4,6,7min11+12,7+7,13+6=min23,14,19=14，w8=14w4=3w3=6w6=7w5=11w7=1312345678263958476104117126w1=0w2=2X=1,2,3,4,6,7,8min11+12,7+7,13+6=min23,14,19=14，w8=14w4=3w3=6w6=7w5=11w7=13w8=1412345678263958476104117126w1=0

37、w2=2w4=3w3=6w6=7w5=11w7=13w8=14从1到8的最短路径为14，最短路径为12 6 8从1到其他节点的最短路径如上图红线所示，其中到3和5的最短路径有两条。2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02511214106104131112396581052C1C3

38、D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72511214

39、106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2

40、)=7f3(C1)=8f2(B1)=21f2(B2)=142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优

41、决策 状态 最优决策 状态 最优决策 状态A （A，B2）B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(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）C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=1

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

43、 （D1，E）E从A到E的最短路径为19，路线为AB 2C1 D1 E 资源分配问题 4台设备，分配给A、B、C三个工厂，每个工厂分配到不同数量的设备所能产生的效益（万吨）如下表所示。求设备的最优分配方案，使总效益最大。设备台数产生的效益（万吨）工厂A工厂B工厂C0000115129228282734042474505553动态规划模型工厂A工厂B工厂C k=1k=2k=3k=4状态变量xk：尚未分配的设备台数x2x3x4决策变量dk：每个工厂分配的设备台数d1d2d3x2=x1-d1阶段kx1x3=x2-d2x4=x3-d3决策允许集合Dk(xk)：分配台数dk的范围0d1 x10d2 x2

44、0d3 x3状态转移方程Dk(xk)：状态如何随上一状态以及决策变化阶段指标Vk(xk,dk)：每个工厂分配设备产生的效益v1(x1,d1)v2(x2,d2)v3(x3,d3)最优指标函数fk(xk)fk(xk)=maxvk(xk,dk)+fk+1(xk+1)终端条件fn(xn)f4(x4)=0 x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*00000+0=00010100+0=0911099+0=9*20200+0=02721199+0=9202727+0=27*30300+0=04731299+0=9212727+0=27304747+0=47*4

45、0400+0=05341399+0=9222727+0=27314747+0=47405353+0=53*x3f3(x3)d3*000191227234734534f3(x3)f4(x4)x4f4(x4)0010203040 x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00000+0=00010100+9=9121101212+0=12*20200+27=27282111212+9=21202828+0=28*30300+47=47*470121212+27=39212828+9=37304242+0=4240400+53=53591131212+4

46、7=59*222828+27=55314242+9=51405555+0=55x3f3(x3)d3*000191227234734534f3(x3)x2f2(x2)d2*0001121228234704591f2(x2)f4(x4)=0 x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*40400+59=59621131515+47=62*222828+28=56314040+12=52405050+0=50 x1f1(x1)d1*4621x2f2(x2)d2*0001121228234704591x3f3(x3)d3*000191227234734534

47、最优解为：x1=4,d1*=1x2=x1-d1=3,d2*=0 x3=x2-d2=3,d3*=3x4=x3-d3=0即工厂A分配1台，工厂B不分配，工厂C分配3台，最大效益为62万吨，设备没有剩余。背包问题一艘货轮载重量为1000吨，装载以下三种货物：货物A货物B货物C重量（吨/件）240320430价值（万元/件）354663单位总量价值0.1460.1440.147每种货物各装载多少件，使一船货物价值最高。x1240吨x2320吨x31000吨0件 1000吨0件 1000吨1件680吨2件360吨3件40吨1件760吨0件760吨1件440吨2件120吨2件520吨0件520吨1件200

48、吨3件280吨0件280吨4件40吨0件40吨x1x2x31000404028012052020076028010003604405206807601000列举各阶段可能的状态x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*4004000+0=000120012000+0=000200020000+0=000280028000+0=000360036000+0=000440044000+0=06311106363+0=63*520052000+0=06311906363+0=63*680068000+0=063112506363+0=63*7600760

49、00+0=063113306363+0=63*10000100000+0=0126215706363+0=632140126126+0=126*x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*4004000+0=000280028000+0=000520052000+63=63*63012004646+0=46760076000+63=63109*114404646+63=109*21209292+0=9210000100000+126=126138316804646+63=10923609292+0=92340138138+0=138*x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*10000100000+138=138144117603535+109=144*25207070+63=1333280105105+0=105440140140+0=140最优解为：x1=1000，d1*=1，x2=x1-240d1*=760，d2*=1x3=x2-320d2*=440，d3*=1，x4=x3-430d3*=10f1(x1)=f1(1000)=144即货物A、B、C各装1件，最大价值为144万元。货轮装载量还剩余10吨。