第四节 连续型动态规划问题参考课件

1、资源分配问题,连续型,设备负荷分配问题,例,某公司有,500,辆运输卡车，在超负荷运输（即每天满载行,驶,500km,以上）情况下，年利润为,25,万元,辆，这时卡车的年,损坏率为,0.3,在低负荷下运输（即每天行驶,300km,以下）情,况下，年利润为,16,万元,辆。年损坏率为,0.1,现要制定一个,5,年计划，问每年年初应如何分配完好车辆，在两种不同的负荷,下运输的卡车数量，使在,5,年内的总利润最大,解：这是一个以时间为特征的多阶段决策问题,第,1,年,第,2,年,第,3,年,第,4,年,500,1,s,投,x,1,辆,超,负荷车,状态,2,s,1,1,2,2,0,9,0,x,s,s,

2、2,2,3,2,0,9,0,x,s,s,3,3,4,2,0,9,0,x,s,s,3,s,4,s,5,s,状态,状态,4,4,x,g,3,3,x,g,1,1,x,g,2,2,x,g,投,x,2,辆,超,负荷车,投,x,3,辆,超,负荷车,投,x,4,辆,超,负荷车,第,5,年,投,x,4,辆,超,负荷车,5,5,x,g,状态,状态,6,s,4,4,5,2,0,9,0,x,s,s,阶段：将,5,年运输计划看成,5,个阶段的决策问题,k=1,2,3,4,5,状态变量,第,k,阶段初完好卡车数量,其中,k,s,500,1,s,决策变量,表示第,k,阶段分配给超负荷运输的卡车数量,k,x,显然，分配给低

3、负荷的卡车数为,k,k,x,s,1,0,1,3,0,1,1,k,k,k,k,x,s,x,s,k,k,x,s,2,0,9,0,注,这里视,为连续变量。若,0.6,表示有一辆卡,车在第,k,年度有,60,的时间处于完好状态,0.7,表示有,一辆卡车在第,k,年度有,70,时间在超负荷运输等等,k,s,k,x,k,s,k,x,状态转移方程,1,0,1,3,0,1,1,k,k,k,k,x,s,x,s,k,k,x,s,2,0,9,0,5,4,3,2,1,k,阶段指标函数,表示第,k,年度利润,k,k,x,g,5,4,3,2,1,k,16,25,k,k,k,k,k,x,s,x,x,g,k,k,x,s,9,

4、16,5,4,3,2,1,k,最优指标函数,第,k,年度初完好车辆数为,时，采,用最优策略到第,5,年末所产生的最大利润,k,k,s,f,k,s,逆序递推式为,0,1,2,3,4,5,max,6,6,1,1,0,s,f,k,s,f,x,g,s,f,k,k,k,k,s,x,k,k,k,k,1,k=5,时,max,6,6,5,5,0,5,5,5,5,s,f,x,g,s,f,s,x,注意到此时,0,6,6,s,f,max,5,5,0,5,5,x,g,s,x,9,16,max,5,5,0,5,5,x,s,s,x,9,16,max,5,5,0,5,5,5,5,x,s,s,f,s,x,5,f,5,x,5,

5、s,5,16,s,o,5,5,5,25,9,16,s,s,s,5,5,s,x,此时,2,k=4,时,max,5,5,4,4,0,4,4,4,4,s,f,x,g,s,f,s,x,25,9,16,max,5,4,4,0,4,4,s,x,s,s,x,2,0,9,0,25,9,16,max,4,4,4,4,0,4,4,x,s,x,s,s,x,4,5,38,max,4,4,0,4,4,x,s,s,x,同理，只有当,4,4,s,x,时，函数,4,4,4,5,38,x,s,才能达到极大值。故有,4,4,s,x,4,4,4,5,42,s,s,f,3,k=3,时,max,4,4,3,3,0,3,3,3,3,s,

6、f,x,g,s,f,s,x,5,42,9,16,max,4,3,3,0,3,3,s,x,s,s,x,2,0,9,0,5,42,9,16,max,3,3,3,3,0,3,3,x,s,x,s,s,x,5,0,25,54,max,3,3,0,3,3,x,s,s,x,不难得到,3,3,s,x,3,3,3,75,54,s,s,f,4,k=2,时,max,3,3,2,2,0,2,2,2,2,s,f,x,g,s,f,s,x,2,0,9,0,75,54,9,16,max,2,2,2,2,0,2,2,x,s,x,s,s,x,95,1,275,65,max,2,2,0,2,2,x,s,s,x,2,f,2,x,2,

7、47,33,s,2,275,65,s,o,可见，只有当,0,2,x,时，函数,2,2,95,1,275,65,x,s,才能达到,极大值。故有,0,2,x,2,2,2,275,65,s,s,f,3,3,3,75,54,s,s,f,5,k=1,时,max,500,2,2,1,1,0,1,1,1,1,1,s,f,x,g,f,s,f,s,x,275,65,9,16,max,2,1,1,500,0,1,s,x,s,x,2,0,9,0,275,65,9,16,max,1,1,1,1,500,0,1,x,s,x,s,x,055,4,7475,74,max,1,1,500,0,1,x,s,x,同理，只有当,时

8、，函数,0,1,x,75,37373,500,7475,74,7475,74,1,1,1,s,s,f,0,1,x,1,1,055,4,7475,74,x,s,才能达到,极大值。故有,万元,所对应的最优策略分别为,0,1,x,时，由状态转移方程,k,k,k,x,s,s,2,0,9,0,1,450,500,9,0,2,0,9,0,1,1,2,x,s,s,由,0,2,x,且,405,450,9,0,2,0,9,0,2,2,3,x,s,s,再由,3,3,s,x,且,5,283,405,2,0,405,9,0,2,0,9,0,3,3,4,x,s,s,4,4,s,x,45,198,5,283,2,0,5,

9、283,9,0,2,0,9,0,4,4,5,x,s,s,5,5,s,x,15,138,45,198,2,0,45,198,9,0,2,0,9,0,5,5,6,x,s,s,第一年初,500,辆车全部用于低负荷运输,第二年初：还有,450,辆完好的车，也全部用于低负荷运输,第三年初：还有,405,辆完好的车，全部用于超负荷运输,第四年初：还有,238.5,辆完好的车，全部用于超负荷运输,第五年初：还有,198.45,辆完好的车，全部用于超负荷运输,到第五年末，即第六年初，还剩余,138.15,辆完好的车,实现最大利润,74,3,1,1,s,f,亿元,思考：某公司有,1000,辆运输卡车，在超负荷运

10、输（即每天,满载行驶,500km,以上）情况下，年利润为,25,万元,辆，这时,卡车的年损坏率为,0.3,在低负荷下运输（即每天行驶,300km,以下）情况下，年利润为,16,万元,辆。年损坏率为,0.1,现要制定一个,5,年计划，问每年年初应如何分配完好车,辆在两种不同的负荷下运输的卡车数量，使在第,5,年年末,剩余的完好卡车数量为,500,台，并且使在,5,年内的总利润最,大,第,1,年,第,2,年,第,3,年,第,4,年,1000,1,s,投,x,1,辆,超,负荷车,状态,2,s,1,1,2,2,0,9,0,x,s,s,2,2,3,2,0,9,0,x,s,s,3,3,4,2,0,9,0,

11、x,s,s,3,s,4,s,5,s,状态,状态,4,4,x,g,3,3,x,g,1,1,x,g,2,2,x,g,投,x,2,辆,超,负荷车,投,x,3,辆,超,负荷车,投,x,4,辆,超,负荷车,第,5,年,投,x,4,辆,超,负荷车,5,5,x,g,状态,状态,500,6,s,4,4,5,2,0,9,0,x,s,s,1,0,1,3,0,1,1,k,k,k,k,x,s,x,s,k,k,x,s,2,0,9,0,16,25,k,k,k,k,k,x,s,x,x,g,k,k,x,s,9,16,5,4,3,2,1,k,第,1,年,第,2,年,第,3,年,第,4,年,1000,1,s,投,x,1,辆,超,

12、负荷车,状态,2,s,1,1,2,2,0,9,0,x,s,s,2,2,3,2,0,9,0,x,s,s,3,3,4,2,0,9,0,x,s,s,3,s,4,s,5,s,状态,状态,4,4,x,g,3,3,x,g,1,1,x,g,2,2,x,g,投,x,2,辆,超,负荷车,投,x,3,辆,超,负荷车,投,x,4,辆,超,负荷车,第,5,年,投,x,5,辆,超,负荷车,5,5,x,g,状态,状态,500,6,s,4,4,5,2,0,9,0,x,s,s,逆序递推式为,0,1,2,3,4,5,max,6,6,1,1,0,s,f,k,s,f,x,g,s,f,k,k,k,k,s,x,k,k,k,k,第,1,

13、年,第,2,年,第,3,年,第,4,年,1000,1,s,投,x,1,辆,超,负荷车,状态,2,s,1,1,2,2,0,9,0,x,s,s,2,2,3,2,0,9,0,x,s,s,3,3,4,2,0,9,0,x,s,s,3,s,4,s,5,s,状态,状态,4,4,x,g,3,3,x,g,1,1,x,g,2,2,x,g,投,x,2,辆,超,负荷车,投,x,3,辆,超,负荷车,投,x,4,辆,超,负荷车,第,5,年,投,x,4,辆,超,负荷车,5,5,x,g,状态,状态,500,6,s,4,4,5,2,0,9,0,x,s,s,1,k=5,时,max,6,6,5,5,0,5,5,5,5,s,f,x,

14、g,s,f,s,x,注意到此时,0,6,6,s,f,max,5,5,0,5,5,x,g,s,x,9,16,max,5,5,0,5,5,x,s,s,x,500,2,0,9,0,5,5,6,x,s,s,2500,5,4,5,5,s,x,22500,5,56,9,16,max,5,5,5,2500,5,4,5,5,s,x,s,s,x,2500,5,4,5,5,s,x,2,k=4,时,max,5,5,4,4,0,4,4,4,4,s,f,x,g,s,f,s,x,22500,5,56,9,16,max,5,4,4,0,4,4,s,x,s,s,x,22500,2,0,9,0,5,56,9,16,max,4,

15、4,4,4,0,4,4,x,s,x,s,s,x,22500,3,2,85,66,max,4,4,0,4,4,x,s,s,x,22500,85,66,4,s,0,4,x,22500,85,66,4,4,4,s,s,f,3,k=3,时,max,4,4,3,3,0,3,3,3,3,s,f,x,g,s,f,s,x,22500,85,66,9,16,max,4,3,3,0,3,3,s,x,s,s,x,22500,2,0,9,0,85,66,9,16,max,3,3,3,3,0,3,3,x,s,x,s,s,x,22500,37,4,165,76,max,3,3,0,3,3,x,s,s,x,不难得到,0,3

16、,x,22500,165,76,3,3,3,s,s,f,4,k=2,时,max,3,3,2,2,0,2,2,2,2,s,f,x,g,s,f,s,x,22500,2,0,9,0,165,76,9,16,max,2,2,2,2,0,2,2,x,s,x,s,s,x,22500,233,6,5485,84,max,2,2,0,2,2,x,s,s,x,0,2,x,22500,5485,84,2,2,2,s,s,f,5,k=1,时,max,1000,2,2,1,1,0,1,1,1,1,1,s,f,x,g,f,s,f,s,x,22500,5485,84,9,16,max,2,1,1,1000,0,1,s,x

17、,s,x,22500,2,0,9,0,5485,84,9,16,max,1,1,1,1,1000,0,1,x,s,x,s,x,22500,9097,7,09365,76,max,1,1,1000,0,1,x,s,x,0,1,x,65,53593,22500,1000,09365,76,22500,09365,76,1,1,1,s,s,f,万元,0,1,x,时，由状态转移方程,k,k,k,x,s,s,2,0,9,0,1,900,1000,9,0,2,0,9,0,1,1,2,x,s,s,由,0,2,x,且,810,900,9,0,2,0,9,0,2,2,3,x,s,s,再由,3,3,s,x,且,5

18、67,810,2,0,810,9,0,2,0,9,0,3,3,4,x,s,s,4,4,s,x,9,396,567,2,0,567,9,0,2,0,9,0,4,4,5,x,s,s,2500,5,4,5,5,s,x,500,79,142,21,357,2500,05,1786,2,0,21,357,2500,9,396,5,4,2,0,9,396,9,0,2,0,9,0,5,5,6,x,s,s,第一年初,1000,辆车全部用于低负荷运输,第二年初：还有,900,辆完好的车，也全部用于低负荷运输,第三年初：还有,810,辆完好的车，全部用于超负荷运输,第四年初：还有,567,辆完好的车，全部用于超负

19、荷运输,第五年初：还有,396.9,辆完好的车，全部用于超负荷运输,到第五年末，即第六年初，还剩余,500,辆完好的车,实现最大利润,65,53593,1,1,s,f,万元,背,包,问,题,一般的提法为：一旅行者携带背包去登山。已知他,所能承受的背包重量的极限为,a,千克,现有,n,种物,品可供他选择装入背包。第,i,种物品的单位重量为,千克,其价值（可以是表明本物品对登山者的重,要性指标）是携带数量,的函数,i=1,2,n,问旅行者应如何选择携带物品的件数，以,使总价值最大,i,a,i,i,x,g,i,x,此模型解决的是运输工具包括卫星的最优装载问题,其数学模型为,设,为第,i,种物品装入的

20、件数，则背包问题可归结为,如下形式的整数规划模型,i,x,n,i,i,i,x,g,z,1,max,2,1,0,1,n,i,x,a,x,a,i,n,i,i,i,整数,下面从一个例子来分析动态规划建模,例,有一辆最大货运量为,10 t,的卡车，用以装载,3,种,货物，每种货物的单位重量及相应单位价值如下表,所示。应如何装载可使总价值最大,货物编号,i,1,2,3,单位重量,t,3,4,5,单位价值,c,i,4,5,6,设第,种货物装载的件数为,i,x,3,2,1,i,i,则问题可表为,3,2,1,6,5,4,m,ax,x,x,x,z,3,2,1,0,10,5,4,3,3,2,1,i,x,x,x,x

21、,i,整数,阶段,k,将可装入物品按,1,2,3,的顺序排序，每,段装入一种物品，共划分,3,个阶段，即,k=1,2,3,状态变量,在第,k,段开始时，背包中允许装入前,k,种,物品的总重量,1,k,s,决策变量,装入第,k,种物品的件数,k,x,状态转移方程,k,k,k,k,x,a,s,s,1,最优指标函数,在背包中允许装入物品的总,重量不超过,t,采取最优策略只装前,k,种物品时的,最大使用价值,1,k,k,s,f,1,k,s,货物,1,货物,2,货物,3,10,4,s,3,4,3,5,x,s,s,2,3,2,4,x,s,s,1,2,1,3,x,s,s,1,1,1,4,x,x,g,2,2,

22、2,5,x,x,g,3,3,3,6,x,x,g,2,4,x,3,5,x,1,3,x,由此可得动态规划的顺序递推方程为,0,3,2,1,max,1,0,1,1,0,1,1,s,f,k,x,a,s,f,x,g,s,f,k,k,k,k,k,k,s,x,a,k,k,k,k,k,货物,1,货物,2,货物,3,10,4,s,3,4,3,5,x,s,s,2,3,2,4,x,s,s,1,2,1,3,x,s,s,1,1,1,4,x,x,g,2,2,2,5,x,x,g,3,3,3,6,x,x,g,2,4,x,3,5,x,1,3,x,K=1,时,max,1,0,1,1,3,0,2,1,1,2,1,s,f,x,g,s

23、,f,x,s,x,为整数,4,max,1,3,0,1,2,1,x,x,s,x,为整数,货物,1,货物,2,货物,3,10,4,s,3,4,3,5,x,s,s,2,3,2,4,x,s,s,1,2,1,3,x,s,s,1,1,1,4,x,x,g,2,2,2,5,x,x,g,3,3,3,6,x,x,g,2,4,x,3,5,x,1,3,x,K=1,时,max,1,0,1,1,3,0,2,1,1,2,1,s,f,x,g,s,f,x,s,x,为整数,4,max,1,3,0,1,2,1,x,x,s,x,为整数,注意到,10,1,0,2,s,例如,7,2,s,时,4,max,7,1,7,3,0,1,1,1,x

24、,f,x,x,为整数,4,max,1,2,1,0,1,x,x,8,8,4,0,max,2,1,x,其它计算结果见下表,1,x,2,s,1,4,x,2,1,s,f,1,x,0 1 2 3,0,1,2,3,4,5,6,7,8,9,10,4,0,4,0,4,0,4,0,4,1,4,0,4,1,4,0,4,1,4,0,4,1,4,2,4,0 4,1 4,2,4,0 4,1 4,2,4,0 4,1 4,2 4,3,4,0 4,1 4,2 4,3,0,0,0,4,4,4,8,8,8,12,12,0,0,0,1,1,1,2,2,2,3,3,货物,1,货物,2,货物,3,10,4,s,3,4,3,5,x,s,

25、s,2,3,2,4,x,s,s,1,2,1,3,x,s,s,1,1,1,4,x,x,g,2,2,2,5,x,x,g,3,3,3,6,x,x,g,2,4,x,3,5,x,1,3,x,K=2,时,max,2,1,2,2,4,0,3,2,2,3,2,s,f,x,g,s,f,x,s,x,为整数,4,5,max,2,3,1,2,4,0,2,3,2,x,s,f,x,x,s,x,为整数,其中,10,1,0,3,s,例如,10,3,s,时,4,10,5,max,10,2,1,2,10,4,0,2,3,2,2,2,x,f,x,f,s,f,x,x,为整数,4,10,5,max,2,1,2,2,1,0,2,x,f,

26、x,x,0,10,6,5,10,0,m,ax,1,1,1,f,f,f,0,10,6,5,10,0,m,ax,1,1,1,f,f,f,13,0,10,8,5,12,0,max,1,2,x,1,x,2,s,1,4,x,2,1,s,f,1,x,0 1 2 3,0,1,2,3,4,5,6,7,8,9,10,4,0,4,0,4,0,4,0,4,1,4,0,4,1,4,0,4,1,4,0,4,1,4,2,4,0 4,1 4,2,4,0 4,1 4,2,4,0 4,1 4,2 4,3,4,0 4,1 4,2 4,3,0,0,0,4,4,4,8,8,8,12,12,0,0,0,1,1,1,2,2,2,3,3,

27、其它计算结果见下表,2,x,3,s,4,5,2,3,1,2,x,s,f,x,3,2,s,f,2,x,0 1 2,0,1,2,3,4,5,6,7,8,9,10,5,0,0,5,0,0,5,0,0,5,0,4,5,0,4,5,0,4,5,1,0,5,0,8,5,1,0,5,0,8,5,1,4,5,0,8,5,1,4,5,0,12,5,1,4,5,0,12 5,1,8 5,2,0,0,0,0,4,4,5,8,9,9,12,13,0,0,0,0,0,1,0,1,1,0,1,货物,1,货物,2,货物,3,10,4,s,3,4,3,5,x,s,s,2,3,2,4,x,s,s,1,2,1,3,x,s,s,1

28、,1,1,4,x,x,g,2,2,2,5,x,x,g,3,3,3,6,x,x,g,2,4,x,3,5,x,1,3,x,K=3,时,max,10,3,2,3,3,5,0,3,4,3,3,4,3,s,f,x,g,f,s,f,x,s,x,为整数,5,10,6,max,3,2,3,10,5,0,3,3,x,f,x,x,x,为整数,5,10,6,max,3,2,3,2,1,0,3,x,f,x,x,0,12,5,6,10,0,m,ax,2,2,2,f,f,f,0,12,5,6,10,0,m,ax,2,2,2,f,f,f,13,0,12,5,6,13,0,max,0,3,x,2,x,3,s,4,5,2,3,

29、1,2,x,s,f,x,3,2,s,f,2,x,0 1 2,0,1,2,3,4,5,6,7,8,9,10,5,0,0,5,0,0,5,0,0,5,0,4,5,0,4,5,0,4,5,1,0,5,0,8,5,1,0,5,0,8,5,1,4,5,0,8,5,1,4,5,0,12,5,1,4,5,0,12 5,1,8 5,2,0,0,0,0,4,4,5,8,9,9,12,13,0,0,0,0,0,1,0,1,1,0,1,从,0,3,x,再由状态转移方程,10,0,10,5,3,4,3,x,s,s,货物,1,货物,2,货物,3,10,4,s,3,4,3,5,x,s,s,2,3,2,4,x,s,s,1,

30、2,1,3,x,s,s,1,1,1,4,x,x,g,2,2,2,5,x,x,g,3,3,3,6,x,x,g,2,4,x,3,5,x,1,3,x,2,x,3,s,4,5,2,3,1,2,x,s,f,x,3,2,s,f,2,x,0 1 2,0,1,2,3,4,5,6,7,8,9,10,5,0,0,5,0,0,5,0,0,5,0,4,5,0,4,5,0,4,5,1,0,5,0,8,5,1,0,5,0,8,5,1,4,5,0,8,5,1,4,5,0,12,5,1,4,5,0,12 5,1,8 5,2,0,0,0,0,4,4,5,8,9,9,12,13,0,0,0,0,0,1,0,1,1,0,1,1,2

31、,x,再由状态转移方程,6,4,10,4,2,3,2,x,s,s,2,1,x,最大装载价值为,13,10,3,f,1,x,2,s,1,4,x,2,1,s,f,1,x,0 1 2 3,0,1,2,3,4,5,6,7,8,9,10,4,0,4,0,4,0,4,0,4,1,4,0,4,1,4,0,4,1,4,0,4,1,4,2,4,0 4,1 4,2,4,0 4,1 4,2,4,0 4,1 4,2 4,3,4,0 4,1 4,2 4,3,0,0,0,4,4,4,8,8,8,12,12,0,0,0,1,1,1,2,2,2,3,3,总结：今后解背包问题应先从,k=3,入手,k=3,时,max,10,3,

32、2,3,3,5,0,3,4,3,3,4,3,s,f,x,g,f,s,f,x,s,x,为整数,5,10,6,max,3,2,3,10,5,0,3,3,x,f,x,x,x,为整数,5,10,6,max,3,2,3,2,1,0,3,x,f,x,x,0,12,5,6,10,0,m,ax,2,2,2,f,f,f,下面应有重点地从,k=2,中求解三个最优函数值,10,2,f,5,2,f,0,2,f,K=2,时,max,2,1,2,2,4,0,3,2,2,3,2,s,f,x,g,s,f,x,s,x,为整数,4,5,max,2,3,1,2,4,0,2,3,2,x,s,f,x,x,s,x,为整数,4,10,5,

33、max,10,2,1,2,10,4,0,2,3,2,2,2,x,f,x,f,s,f,x,x,为整数,4,10,5,max,2,1,2,2,1,0,2,x,f,x,x,2,10,6,5,10,0,m,ax,1,1,1,f,f,f,4,5,5,max,5,2,1,2,5,4,0,2,3,2,2,2,x,f,x,f,s,f,x,x,为整数,4,5,5,max,2,1,2,1,0,2,x,f,x,x,1,5,5,0,m,ax,1,1,f,f,4,0,5,max,0,2,1,2,0,4,0,2,3,2,2,2,x,f,x,f,s,f,x,x,为整数,0,0,max,4,0,5,max,1,2,1,2,0

34、,2,f,x,f,x,x,所以从第一阶段应有重点地求以下四个数,0,1,f,1,1,f,6,1,f,10,1,f,max,1,0,1,1,3,0,2,1,1,2,1,s,f,x,g,s,f,x,s,x,为整数,K=1,时,4,max,1,3,0,1,2,1,x,x,s,x,为整数,4,max,0,1,0,3,0,1,1,1,x,f,x,x,为整数,0,4,max,1,0,1,x,x,4,max,1,1,1,3,0,1,1,1,x,f,x,x,为整数,0,4,max,1,0,1,x,x,0,1,x,0,1,x,2,1,f,5,1,f,4,max,6,1,6,3,0,1,1,1,x,f,x,x,为

35、整数,8,8,4,0,max,4,max,1,2,1,0,1,x,x,2,1,x,4,max,10,1,10,3,0,1,1,1,x,f,x,x,为整数,12,12,8,4,0,max,4,max,1,3,2,1,0,1,x,x,3,1,x,由此逐一逆推代回上式,4,max,5,1,5,3,0,1,1,1,x,f,x,x,为整数,4,4,0,max,4,max,1,1,0,1,x,x,1,1,x,4,max,2,1,2,3,0,1,1,1,x,f,x,x,为整数,0,4,max,1,0,1,x,x,0,1,x,0,2,f,0,0,0,max,4,0,5,max,1,2,1,2,0,2,f,x,

36、f,x,x,0,0,1,f,0,2,x,1,5,5,0,m,ax,5,1,1,2,f,f,f,5,0,5,4,0,max,1,2,x,0,1,1,f,0,1,x,4,max,6,1,6,3,0,1,1,1,x,f,x,x,为整数,8,8,4,0,max,4,max,1,2,1,0,1,x,x,2,1,x,4,max,10,1,10,3,0,1,1,1,x,f,x,x,为整数,12,12,8,4,0,max,4,max,1,3,2,1,0,1,x,x,3,1,x,4,max,5,1,5,3,0,1,1,1,x,f,x,x,为整数,4,4,0,max,4,max,1,1,0,1,x,x,1,1,x

37、,4,max,2,1,2,3,0,1,1,1,x,f,x,x,为整数,0,4,max,1,0,1,x,x,0,1,x,由此逐一逆推代回上式,4,max,6,1,6,3,0,1,1,1,x,f,x,x,为整数,8,8,4,0,max,4,max,1,2,1,0,1,x,x,2,1,x,4,max,10,1,10,3,0,1,1,1,x,f,x,x,为整数,12,12,8,4,0,max,4,max,1,3,2,1,0,1,x,x,3,1,x,4,max,5,1,5,3,0,1,1,1,x,f,x,x,为整数,4,4,0,max,4,max,1,1,0,1,x,x,1,1,x,4,max,2,1,

38、2,3,0,1,1,1,x,f,x,x,为整数,0,4,max,1,0,1,x,x,0,1,x,由此逐一逆推代回上式,2,10,6,5,10,0,m,ax,10,1,1,1,2,f,f,f,f,13,0,10,8,5,12,0,max,1,2,x,0,12,5,6,10,0,m,ax,10,2,2,2,3,f,f,f,f,13,0,12,5,6,13,0,max,0,3,x,最后,最优策略,0,3,x,再由状态转移方程,10,0,10,5,3,4,3,x,s,s,1,2,x,再由状态转移方程,6,4,10,4,2,3,2,x,s,s,2,1,x,最大装载价值为,13,10,3,f,用动态规划方

39、法求解,3,2,1,0,10,3,4,2,3,2,1,i,x,x,x,x,i,且为整数,2,3,2,1,2,9,4,max,x,x,x,F,解：我们用背包问题顺序解的思路,人为的划分三个阶段,k=1,2,3,阶段指标函数及其他分配情况如下图,1,2,3,1,1,1,4,x,x,g,2,2,2,9,x,x,g,2,3,3,3,2,x,x,g,3,3,x,2,4,x,1,2,x,1,2,1,2,x,s,s,2,3,2,4,x,s,s,3,4,3,3,x,s,s,10,4,s,1,2,3,1,1,1,4,x,x,g,2,2,2,9,x,x,g,2,3,3,3,2,x,x,g,3,3,x,2,4,x,

40、1,2,x,1,2,1,2,x,s,s,2,3,2,4,x,s,s,3,4,3,3,x,s,s,10,4,s,动态规划的顺序递推方程为,0,3,2,1,max,1,0,1,1,0,1,1,s,f,k,x,a,s,f,x,g,s,f,k,k,k,k,k,k,s,x,a,k,k,k,k,k,max,10,3,2,3,3,5,0,3,4,3,4,3,s,f,x,g,f,s,f,s,x,3,10,2,max,3,2,2,3,10,3,0,3,x,f,x,x,3,10,2,max,3,2,2,3,3,10,1,0,3,x,f,x,x,1,18,4,8,7,2,10,0,m,ax,2,2,2,2,f,f,

41、f,f,max,2,1,2,2,4,0,3,2,3,2,s,f,x,g,s,f,s,x,4,max,2,3,1,2,2,4,0,3,2,x,s,f,x,g,s,x,10,2,f,4,10,9,max,2,1,2,4,10,1,0,2,x,f,x,x,1,2,3,1,1,1,4,x,x,g,2,2,2,9,x,x,g,2,3,3,3,2,x,x,g,3,3,x,2,4,x,1,2,x,1,2,1,2,x,s,s,2,3,2,4,x,s,s,3,4,3,3,x,s,s,10,4,s,10,2,f,4,10,9,max,2,1,2,4,10,1,0,2,x,f,x,x,4,10,9,max,2,1,

42、2,2,1,0,2,x,f,x,x,2,18,6,9,10,0,m,ax,1,1,1,f,f,f,7,2,f,4,7,9,max,2,1,2,7,4,0,2,x,f,x,x,4,7,9,max,2,1,2,1,0,2,x,f,x,x,3,9,7,0,m,ax,1,1,f,f,4,2,f,4,4,9,max,2,1,2,4,4,0,2,x,f,x,x,4,4,9,max,2,1,2,1,0,2,x,f,x,x,0,9,4,0,m,ax,1,1,f,f,1,2,f,4,1,9,max,2,1,2,1,4,0,2,x,f,x,x,4,1,9,max,2,1,2,0,2,x,f,x,x,1,1,f,1

43、,2,3,1,1,1,4,x,x,g,2,2,2,9,x,x,g,2,3,3,3,2,x,x,g,3,3,x,2,4,x,1,2,x,1,2,1,2,x,s,s,2,3,2,4,x,s,s,3,4,3,3,x,s,s,10,4,s,max,1,0,1,1,2,0,2,1,2,1,s,f,x,g,s,f,s,x,4,max,1,2,0,2,1,x,s,x,0,1,f,4,max,1,0,2,0,1,x,x,0,4,max,1,0,1,x,x,0,1,x,1,1,f,0,4,max,1,0,1,x,x,4,max,1,0,2,0,1,x,x,0,1,x,2,1,f,4,max,1,2,2,0,1,

44、x,x,4,max,1,1,0,1,x,x,4,4,0,max,1,1,x,3,1,f,4,max,1,3,2,0,1,x,x,4,max,1,1,0,1,x,x,4,4,0,max,1,1,x,4,1,f,4,max,1,4,2,0,1,x,x,4,max,1,2,1,0,1,x,x,8,8,4,0,max,2,1,x,6,1,f,4,max,1,6,2,0,1,x,x,4,max,1,3,2,1,0,1,x,x,12,12,8,4,0,max,3,1,x,7,1,f,4,max,1,7,2,0,1,x,x,4,max,1,3,2,1,0,1,x,x,12,12,8,4,0,max,3,1,

45、x,0,0,1,f,0,1,1,f,4,2,1,f,4,3,1,f,8,4,1,f,12,6,1,f,20,10,1,f,1,2,f,0,1,1,f,4,2,f,0,9,4,0,m,ax,1,1,f,f,9,0,9,8,0,max,10,1,f,4,max,1,10,2,0,1,x,x,4,max,1,5,4,2,1,0,1,x,x,12,12,8,4,0,max,20,20,16,12,8,4,0,max,5,1,x,12,7,1,f,4,1,9,max,2,1,2,0,2,x,f,x,x,0,2,x,4,4,9,max,2,1,2,1,0,2,x,f,x,x,1,2,x,7,2,f,3,9

46、,7,0,m,ax,1,1,f,f,4,7,9,max,2,1,2,1,0,2,x,f,x,x,10,2,f,2,18,6,9,10,0,m,ax,1,1,1,f,f,f,0,0,1,f,0,1,1,f,4,2,1,f,4,3,1,f,8,4,1,f,12,6,1,f,20,10,1,f,12,7,1,f,7,2,f,3,9,7,0,m,ax,1,1,f,f,4,7,9,max,2,1,2,1,0,2,x,f,x,x,13,4,9,12,0,max,1,2,x,4,10,9,max,2,1,2,2,1,0,2,x,f,x,x,22,4,18,12,9,20,0,max,2,2,x,3,10,2

47、,max,10,3,2,2,3,3,2,1,0,3,4,3,3,x,f,x,f,s,f,x,1,18,4,8,7,2,10,0,m,ax,2,2,2,2,f,f,f,f,22,0,18,9,8,13,2,22,0,max,0,3,x,10,0,10,3,3,4,3,x,s,s,0,2,x,1,2,x,1,2,x,2,2,x,22,10,2,3,2,f,s,f,9,4,2,3,2,f,s,f,13,7,2,3,2,f,s,f,0,1,2,3,2,f,s,f,2,2,x,4,2,1,2,1,f,s,f,1,1,x,2,8,10,4,2,3,2,x,s,s,10,0,10,3,3,4,3,x,s,s

48、,2,2,x,1,1,x,最优决策为,1,1,x,2,2,x,0,3,x,所对应的最优解为,22,10,3,4,3,f,s,f,例,二维背包,有一辆最大货运量为,13t,最大容量为,10,件的卡车，用以装载,3,种货物，每种货物的单位重量及相,应单位价值如下表所示。应如何装载可使总价值最大,货物编号,i,1,2,3,单位重量,t,1,3,6,单位价值,c,i,4,5,8,解：设装载第,i,种货物的件数为,i=1,2,3,，则问题可表述为,13,6,3,10,3,2,1,3,2,1,x,x,x,x,x,x,t,s,3,2,1,8,5,4,m,ax,x,x,x,z,N,x,i,x,i,i,3,2,

49、1,0,i,x,1,2,3,1,1,1,4,x,x,g,2,2,2,5,x,x,g,3,3,3,8,x,x,g,3,6,x,2,3,x,1,x,1,2,1,x,s,s,2,3,2,x,s,s,3,4,3,x,s,s,10,4,s,关于件数的约束,k,k,k,x,s,s,1,关于重量的约束,k,k,k,k,x,a,u,u,1,3,2,1,k,3,2,1,k,13,4,u,3,4,3,6,x,s,u,2,3,2,3,x,u,u,1,2,1,x,u,u,基本方程式,0,3,2,1,max,1,1,0,1,1,1,0,0,1,1,1,1,u,s,f,k,x,a,u,x,s,f,x,g,u,s,f,k,

50、k,k,k,k,k,k,k,u,x,a,s,x,k,k,k,k,k,k,k,k,1,1,a,3,2,a,6,3,a,1,2,3,1,1,1,4,x,x,g,2,2,2,5,x,x,g,3,3,3,8,x,x,g,3,6,x,2,3,x,1,x,1,2,1,x,s,s,2,3,2,x,s,s,3,4,3,x,s,s,10,4,s,13,4,u,3,4,3,6,x,s,u,2,3,2,3,x,u,u,1,2,1,x,u,u,0,3,2,1,max,1,1,0,1,1,1,min,0,1,1,1,1,u,s,f,k,x,a,u,x,s,f,x,g,u,s,f,k,k,k,k,k,k,k,k,a,u,

51、s,x,k,k,k,k,k,k,k,1,1,a,3,2,a,6,3,a,问题就是求,6,13,10,max,13,10,3,3,2,3,3,13,6,0,10,0,3,4,4,3,3,3,x,x,f,x,g,f,u,s,f,x,x,1,2,3,1,1,1,4,x,x,g,2,2,2,5,x,x,g,3,3,3,8,x,x,g,3,6,x,2,3,x,1,x,1,2,1,x,s,s,2,3,2,x,s,s,3,4,3,x,s,s,10,4,s,13,4,u,3,4,3,6,x,u,u,2,3,2,3,x,u,u,1,2,1,x,u,u,6,13,10,max,3,3,2,3,3,6,13,10,

52、min,1,0,3,x,x,f,x,g,x,6,13,10,8,max,3,3,2,3,2,1,0,3,x,x,f,x,x,1,1,a,3,2,a,6,3,a,6,13,10,8,max,3,3,2,3,2,1,0,3,x,x,f,x,x,1,8,16,7,9,8,13,10,0,m,ax,2,2,2,f,f,f,max,2,2,1,2,2,3,0,0,3,3,2,3,2,3,2,u,s,f,x,g,u,s,f,u,x,s,x,3,max,2,3,2,3,1,2,2,3,min,1,0,3,3,2,x,u,x,s,f,x,g,u,s,x,3,13,10,5,max,13,10,2,2,1,2,

53、3,13,10,min,1,0,2,2,x,x,f,x,f,x,3,13,10,5,max,2,2,1,2,4,1,0,2,x,x,f,x,x,1,6,20,4,7,15,7,8,10,10,9,5,13,10,m,ax,1,1,1,1,1,f,f,f,f,f,3,7,9,5,max,7,9,2,2,1,2,3,7,9,min,1,0,2,2,x,x,f,x,f,x,3,7,9,5,max,2,2,1,2,2,1,0,2,x,x,f,x,x,1,7,10,4,8,5,7,9,m,ax,1,1,1,f,f,f,3,1,8,5,max,1,8,2,2,1,2,3,1,8,min,1,0,2,2,x

54、,x,f,x,f,x,3,1,8,5,max,2,2,1,2,0,2,x,x,f,x,x,1,8,0,m,ax,1,f,max,1,1,0,1,1,min,0,2,2,1,2,2,1,u,s,f,x,g,u,s,f,u,s,x,4,max,1,min,0,2,2,1,x,u,s,x,1,2,3,1,1,1,4,x,x,g,2,2,2,5,x,x,g,3,3,3,8,x,x,g,3,6,x,2,3,x,1,x,1,2,1,x,s,s,2,3,2,x,s,s,3,4,3,x,s,s,10,4,s,13,4,u,3,4,3,6,x,s,u,2,3,2,3,x,u,u,1,2,1,x,u,u,13,1

55、0,1,f,10,9,1,f,7,8,1,f,4,7,1,f,1,6,1,f,7,9,1,f,4,8,1,f,1,7,1,f,1,8,1,f,13,10,1,f,4,max,1,13,10,min,0,1,x,x,4,max,1,10,0,1,x,x,40,40,36,32,28,24,20,16,12,8,4,0,max,10,1,x,1,1,a,3,2,a,6,3,a,同理可求得,36,10,9,1,f,9,1,x,28,7,8,1,f,7,1,x,16,4,7,1,f,4,1,x,4,1,6,1,f,1,1,x,28,7,9,1,f,7,1,x,16,4,8,1,f,4,1,x,4,1,

56、7,1,f,1,1,x,4,1,8,1,f,1,1,x,1,8,16,7,9,8,13,10,0,m,ax,13,10,2,2,2,2,f,f,f,f,40,13,10,2,f,41,4,20,16,15,28,10,36,5,40,max,1,2,x,1,7,10,4,8,5,7,9,m,ax,7,9,1,1,1,2,f,f,f,f,28,14,21,28,max,0,2,x,3,2,x,4,4,m,ax,1,8,0,m,ax,1,8,1,2,f,f,0,2,x,1,8,16,7,9,8,13,10,0,m,ax,13,10,2,2,2,3,f,f,f,f,41,13,10,2,f,28,7

57、,9,2,f,4,1,8,2,f,41,4,16,28,8,41,max,0,3,x,10,0,10,3,4,3,x,s,s,13,0,13,6,3,4,3,x,u,u,41,13,10,2,3,3,2,f,u,s,f,1,2,x,9,1,10,2,3,2,x,s,s,10,3,13,3,2,3,2,x,u,u,3,2,x,7,3,10,2,3,2,x,s,s,4,9,13,3,2,3,2,x,u,u,9,1,x,1,2,x,0,3,x,所以最优决策方案为,最优装载价值为,41,max,z,36,10,9,1,2,2,1,f,u,s,f,9,1,x,10,9,2,2,u,s,4,7,2,2,u

58、,s,16,4,7,1,2,2,1,f,u,s,f,4,1,x,4,1,x,3,2,x,0,3,x,8,5,4,m,ax,3,2,1,x,x,x,z,1,动态规划与静态规划,动态规划研究的“多阶段决策问题”基,本上都和时间有关，所得的决策序列是在变,化的状态中迭代产生的，故有“动态”的含,义,而一般的线性规划和非线性规划所研究,的问题，通常都与时间无关，故又称为“静,态”规划,7.4,连续型动态规划问题,例、用动态规划方法求解下面的问题,2,1,2,3,1,2,3,1,2,3,max,0,Z,x,x,x,x,x,x,c,x,x,x,但对某些“静态”问题，可以人为地引,入时间因素，把它变成一个多阶段决策问题,从而用动态规划的方法加以解决,分析,1,阶段,可把对三