[经济学]运筹学 动态规划.ppt

动态规划最优化原理： “一个过程的最优化策略具有这样的性质，即无论初始状态及初始决策如何，其以后诸决策对以初始决策所形成的状态作为初始状态的过程而言，必构成最优策略。” 构造模型的过程 1)划分阶段 2)正确选择状态变量，使它既能描述过程的状态，又要满足无后效性； 3)选择决策变量xk 4)确定状态转移方程，即在状态sk作决策xk，下一步所达到的状态的方程 sk+1=Tk(sk, xk) 5)确定最优指标函数fk（sk） 6)建立函数基本方程式 对于顺序解法，有方程 fk(sk)= opt {vk-1(sk, xk-1)+fk-1(sk-1)} k=1，2,…,n f0(s1)=0 8.3 生产与存储问题 Production and inventory problem 【解】动态规划求解过程如下。 阶段k：月份，k=1,2,…,7 状态变量sk：第k个月初的库存量 决策变量xk：第k个月的生产量 状态转移方程：sk+1=sk+xk－dk 决策允许集合: 阶段指标： 终端条件：f7(s7)=0, s7=0 递推方程： 8.3 生产与存储问题 Production and inventory problem 当k=6时，因为s7=0，有 当k=5时， 由于s5≤50，则当25－s5＜0时x5的值取“0”，决策允许集合为 8.3 生产与存储问题 Production and inventory problem k=4时， 决策允许集合为 8.3 生产与存储问题 Production and inventory problem 显然该决策不可行，x5=0，s4+x4=65＝d4+d5，s5=s6=0，x6=45，与s5≥25矛盾。因此有 k=3，当0≤s4≤40时， 8.3 生产与存储问题 Production and inventory problem 当40≤s4≤50时， 当k=2时，由 x2的决策允许集合为 8.3 生产与存储问题 Production and inventory problem 当k=1时，由 只要期初存量s1≤20，则x1的决策允许集合为 (1)期初存储量s1=0，由各阶段的最优决策xj*及状态转移方程，回朔可求出最优策略。 8.3 生产与存储问题 Production and inventory problem x1=20， s2=s1+x1－d1=0+20－20＝0， x2=80， s3=s2+x2－d2=0+80－30＝50， x3=85－50＝35， s4=s3+x3－d3=50+35－35＝50＞40， x4＝0， s5=50－0－40＝10＜25， x5＝25－s5＝15， s6=10＋15－25＝0， x6＝45。 总成本为2876 (2)期初存储量s1=10，与前面计算类似，得到x1＝10，x2＝80，x3＝35，x4＝0，x5＝15，x6＝45。 1～6月份生产、存储详细计划表见表8-10所示。 8.3 生产与存储问题 Production and inventory problem 表8-10 2876 合计 66 0 6 30 30 0 0 存储成本Hk(sk) 2810 720 270 0 560 960 300 生产成本CK(xk) 110 0 10 50 50 0 0 期初存量sk 195 45 15 0 35 80 20 产量xk 0.6 0.6 0.6 0.6 0.6 0.6 单位存储费hk 16 18 19 16 12 15 单位产品成本(ck) 195 45 25 40 35 30 20 需求量(dk) 合计 6 5 4 3 2 1 月份(k) 8.3 生产与存储问题 Production and inventory problem 8.4 背包问题 Knapsack Problem 8.4 背包问题 Knapsack Problem 背包问题数学模型为 式中： ck为第k种物品的单位价值，wk是第k种物品的单位重量或体积，W是背包的重量或体积限制。动态规划的有关要素如下。 阶段k：第k次装载第k种物品（k=1,2,…,n） 状态变量sk：第k次装载时背包还可以装载的重量(或体积) 决策变量xk：第k次装载第k种物品的件数 决策允许集合：Dk(sk)={dk|0? xk?