运筹学-动态规划.pptxVIP

第九章：动态规划应用举例第一节：资源分配问题所谓分配问题，就是将数量一定的一种或若干种资源（例如原材料，资金，机器设备，劳力，食品等等），恰当地分配给若干个使用者，使效益函数为最优。1.1一维资源分配问题(离散）设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi),问应如何分配，才能使生产n种产品的总收入最大？静态规划资源分配离散连续

010203040506这是一个具有n个阶段的动态规划问题。K=1,2,…,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某大型公司拟将某种高效率的设备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个工厂至第3个工厂所得到的最大总收益，动态规划的递推关系为：

01即：（用逆推法）当阶段k=3时，0?s3?5，0?x3?s3，有02x3(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台，求最优分配方案？如果原设备台数是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);年终资源回收率aB种生产数量s2-u2;收益h(s2-u2);年终资源回收率b到n年

动态规划的逆推关系方程为：最后求得的f1(s1)即为所求问题的最大收入。此问题的静态规划问题模型为：

某种机器可在高低两种不同负荷下进行生产，设机器在高负荷情况下的产量函数为g=8u1，其中u1是投入生产的机器数量，年完好率为a=0.7，在低负荷情况下的产量函数为h=5y，其中y是投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好机器的数量为1000台，试问每年如何安排机器在高低两种负荷下的生产，可使5年内生产的产品总产量最高。例2机器负荷分配问题?状态变量sk为第k年度初拥有的完好机器台数。?决策变量uk为第k年度中分配高负荷下生产的机器台数。故低负荷下生产的机器台数是sk-uk。?状态转移方程?允许决策集合0?uk?sk解：?设阶段数k表示年度。

第k年度产量为时递推方程为指标函数为当

当时依次类推可得，相应的相应的相应的因此最优策略为最高产量为23700。

作业：如规定在第五年结束时完好机器数为500台，该如何安排生产？练习：每年年初的完好机器数。