第4节一般数学模型的动态规划解法详解.ppt

例1 某公司有资金10万元，若投资于项目i(i=1,2,3)的投资额为xi时，其收益分别为g1(x1)=4x1,g2(x2)= 9x2 , g3(x3)=2x32,问应如何分配投资数额才能使总收益最大？;为了应用动态规划方法求解，人为地赋予它“时段” 的概念，将投资项目排序，首先考虑对项目1投资，然后考虑对项目2投资……，即把问题划分为3个阶段，每个阶段只决定对一个项目应投资的金额。;u1为可分配用于第一种项目的最大资金，则第一阶段时有：;于是有;;要讨论s2的具体情况:;;另取;2.连续变量的离散化解法:; 由于sk与xk都是连续变量，当各阶段指标gk(xk)，没有特殊性质而较为复杂时，要求出fk(sk)比较困难，因而求全过程的最优策略也就相当不容易，这时常常采用把连续变量离散化的方法求其数值解，具体做法如下：;（3）按逆序方法，逐步递推求出fn(sn),…, f1(s1)，最后求出最优资金分配方案。;动态规划基本方程为：;计算结果如??表;计算结果表明，最优决策为：;练 习; 背包问题的一般提法是：一位旅行者携带背包去登山、已知他所能承受的背包重量限度为a千克，现有n种物品可供他选择装入背包。第i种物品的单件重量为ai干克、其价值(可以是表明本物品对登山的重要性的数量指标)是携带数量xi的函数ci(xi) (i＝1,2,…n),问旅行者应如何选择携带各种物品的件数，以使总价值最大？ 其他如车、船、飞机、潜艇、人造卫星等工具的最优装载问题，机床加工中零件最优加工、下料问题、投资决策问题，均等同于背包问题。;背包问题的动态规划模型;例3: 有一辆最大货运量为10吨的卡车，用以装载3种货物．每种货物的单位重量及相应单位价值如表所示。应如何装载可使总价值最大?;建立动态规划模型，由于决策变量取离散值，故可利用列表法求解;当k=2时，;三、生产经营问题的动态规划解法 ;试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第j+1个月的库存量是第j个月可销售量与该月用户需求量之差；而第i个月的可销售量是本月初库存量与产量之和。 ;(5)最优指标函数：fk(sk)表示第k月状态为sk时，采用最佳策略生产，从本月到计划结束（第4个月末）的生产与存贮最低费用。 (6)基本方程：;当k=3时，;当k=2时，;当k=1时，;本 章 小 结