动态规划应用举例.ppt

《动态规划应用举例.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章：动态规划应用举例第一节：资源分配问题分配问题：将数量一定的一种或若干种资源（例如原材料，资金，机器设备，劳力，食品等等），恰当地分配给若干个使用者，使效益函数最优。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

2、0uk=xksk}最

3、优值函数fk(sk)表示数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收益，动态规划的递推关系为：例1某大型公司拟将某种高效率的设备5台分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为公司提供的盈利如表。问这五台设备如何分配给各工厂，才能使公司得到的盈利最大。解：将问题按工厂分为三个阶段，甲乙丙分别编号为1，2，3。用k表示，即阶段变量决策变量uk表示分配给第k个工厂的设备台数，即uk=xk；设状态变量sk表示为分配给第k个工厂至第3工厂的设备台数；状态转移方程：sk+1=sk-uk=sk-xk决策集合：Dk(sk)={uk

4、0uk=xksk}最优值函数fk(s

5、k)表示数量为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-

6、x1*=5-2=3，查表知x2*=2，由s3=s2-x2*=3-2=1，故x3*=s3=1。即得甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。以上两个分配方案所得到的总盈利均为21万元。问题：如果原设备台数是4台，求最优分配方案？如果原设备台数是3台，求最优分配方案？1.2资源连续分配问题:一般问题的提法是如此进行n年，如何确定投入A的资源量u1、…、un，使总收入最大？资源数量s1A种生产数量u1投入收益g(u1)年终资源回收率aB种生产数量s1-u1收益h(s1-u1)年终资源回收率b第一年资源数量s2=au1+b(s1-u1)第二年A种生产数量u2投入;收益g(u2);年终资源回收率a

7、B种生产数量s2-u2;收益h(s2-u2);年终资源回收率b到n年此问题的静态规划问题模型为：动态规划的逆推关系方程为：最后求得的f1(s1)即为所求问题的最大收入。例2机器负荷分配问题某种机器可在高低两种不同负荷下进行生产，设机器在高负荷情况下的产量函数为g=8x，其中x是投入生产的机器数量，年完好率为a=0.7，在低负荷情况下的产量函数为h=5y，其中y是投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好机器的数量为1000台，试问每年如何安排机器在高低两种负荷下的生产，可使5年内生产的产品总产量最高。允许决策集合0uksk解：设阶段数k表示年度。状态变量sk为第k年

8、度初拥有的完好机器台数。决策变量uk为第k年度中分配高负荷下生产的机器台数。故低负荷下生产的机器台数是sk-uk。状态转移方程第k年度产量为指标函数为递推方程为当时当时依次类推可得，相应的相应的相应的因此最优策略为最高产量为23700。第二节生产与存贮问题所谓生产与库存问题就是一个生产部门，如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。很多问题可以化成此类问题来解决。生产与库存问题本身就是一个多阶段决策过程。设某一生产部门，生产周期分为n个阶段，已知最初库存量为x1，阶段市场的需求为dk，生产的固定成本为K，单位产品的消耗费用为L，单位

9、产品的阶段库存费用为h，仓库容量为M，阶段生产能力为B。问如何安排各阶段产量，使计划周期内的费用总和最小。状态变量xk选为阶段k的初始库存量，x1已知，xn+1=0。阶段k的库存量即不能超过库存容量M，也不能超过阶段k至阶段n的需求总量，即决策变量uk选为阶段k的产量。阶段产量必须不超过生产能力和第k阶段到第n阶段的总需求减去第k阶段初的库存量，同时要大于该阶段的需求和库存量之差，即状态转移方程为