[高等教育]运筹学2.pptVIP

第七章：动态规划应用举例 建立动态规划模型的一般步骤： 1 划分阶段。即按时间和空间的先后顺序适当地划分为满足递推关系的若干个阶段。 2 正确选择状态变量。（可知性和无后效性） 3 根据状态变量和决策变量的含义，正确写出状态转移方程 Sk+1=Tk(sk,uk) 4 明确指标函数Vk.n、最优指标函数fk(sk)及k阶段指标Vk(sk,us)的含义。 5 正确列出最优指标函数的递推关系及边界条件。 * 所谓分配问题，就是将数量一定的一种或若干种资源（例如原材料，资金，机器设备，劳力，食品等等），恰当地分配给若干个使用者，使效益函数为最优。 1.1 多元投资分配问题(离散） 设有某种原料，总数量为a，用于生产n种产品。若分配数量xI用于生产第i种产品，其收益为gi(xi),问应如何分配，才能使生产n种产品的总收入最大？ 静态规划 资源分配 离 散 连 续 第一节：资源分配问题 决策变量uk表示分配给生产第k种产品的原料数量，即uk=xk； 设状态变量sk表示为分配给用于生产第k种产品至第n种产品的原料数量； 状态转移方程： sk+1=sk-uk=sk-xk 决策集合：Dk(sk)={uk|0?uk=xk?sk} 最优值函数fk(sk)表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收益，动态规划的递推关系为： 动态规划 五要素 ?直接求解动态规划 ?求解静态规划 例1 某公司有资金10万元，若投资于项目i（i=1，2，3）的投资额为xi时，其效益分别为 ，问如何分配投资数额才能使总效益最大 解：可列出静态规划问题的模型如下 分阶段：（考虑效益函数的形式）分三个阶段，即k=1，2，3。 确定决策变量x k：通常可以取静态规划中的变量为决策变量，即决 定给第 k个项目投资的资金数。 确定状态变量S k：状态变量与决策变量有密切关系，状态变量一般为累计量或随递推过程变化的量。既第k阶段可以投资于第k项到第3项目的资金数量。 状态转移方程： 决策 指标函数 最优指标函数fk(sk):当可投资金额为sk时，投资第k项到第3项所得的最大收益数。 基本方程 当阶段k=3时，有 最优决策为 最优目标函数 Sk+1=sk-xk 当阶段k=2时，有 是凹函数，最大值点只能在[0，s2]端点上取得，即 当 当 当 时， 时， 时， 此时 此时 当阶段k=1时，有 2阶导数大于0 当 当 时 时 矛盾，舍去。 是凹函数，故比较[0,10]的端点 （最优决策） 因为 所以 最优投资方案是全部资金投于第3个项目，可得最大收益200万元。 S29/2 S29/2 2阶导数0 例2 某大型公司拟将某种高效率的设备5台分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为公司提供的盈利如表。问这五台设备如何分配给各工厂，才能使公司得到的盈利最大。 解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。用k表示，即阶段变量 决策变量uk表示分配给第k个工厂的设备台数，即uk=xk； 设状态变量sk表示为分配给第k个工厂至第3工厂的设备台数； 状态转移方程： sk+1=sk-uk=sk-xk 决策集合：Dk(sk)={uk|0?uk=xk?sk} 最优值函数fk(sk)表示以数量为sk的设备台数分配给第k个工厂至第n个工厂所得到的最大总收益，动态规划的递推关系为： 即：（用逆推法） 当阶段k=3时，0?s3?5， 0?x3?s3，有 x3(s3) 结果列于下表： 当阶段k=2时， s3=s2-x2， 0?s2?5， 0?x2?s2，有 结果列于下表： 当阶段k=1时， s2=s1-x1， s1=5， 0?x1?s1，有 结果可写成表格的形式 然后按计算表格的顺序反推，可知最优分配方案有两个： 由于x1*=0，根据s2=s1-x1*=5-0=5，查表知x2*=2，由s3=s2-x2*=5-2=3，故x3*=s3=3。即得甲工厂分配0台，乙工厂分配2台，丙工厂分配3台。 由于x1*=2，根据s2=s1-x1*=5-2=3，查表知x2*=2，由s3=s2-x2*=3-2=1，故x3*=s3=1。即得甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。 以上两个分配方案所得到的总盈利均为21万元。 问题：如果原设备台数是4台，求最优分配方案？ 如果原