《运筹学-动态规划.ppt》由会员分享，可在线阅读，更多相关《运筹学-动态规划.ppt（20页珍藏版）》请在三一办公上搜索。
1、第九章：动态规划应用举例,第一节：资源分配问题 所谓分配问题，就是将数量一定的一种或若干种资源（例如原材料，资金，机器设备，劳力，食品等等），恰当地分配给若干个使用者，使效益函数为最优。,1.1 一维资源分配问题(离散）设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi),问应如何分配，才能使生产n种产品的总收入最大？,静态规划,这是一个具有n个阶段的动态规划问题。K=1,2,n决策变量uk表示分配给生产第k种产品的原料数量，即uk=xk；设状态变量sk表示为分配给用于生产第k种产品至第n种产品的原料数量；状态转移方程：sk+1=sk-uk=sk-
2、xk决策集合：Dk(sk)=uk|0uk=xksk最优值函数fk(sk)表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收益，动态规划的递推关系为：,动态规划五要素,例1 某大型公司拟将某种高效率的设备5台分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为公司提供的盈利如表。问这五台设备如何分配给各工厂，才能使公司得到的盈利最大。,解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。用k表示，即阶段变量决策变量uk表示分配给第k个工厂的设备台数，即uk=xk；设状态变量sk表示为分配给第k个工厂至第3工厂的设备台数；状态转移方程：sk+1=sk-uk=s
3、k-xk决策集合：Dk(sk)=uk|0uk=xksk最优值函数fk(sk)表示以数量为sk的设备台数分配给第k个工厂至第3个工厂所得到的最大总收益，动态规划的递推关系为：,即：（用逆推法）当阶段k=3时，0s35，0 x3s3，有,x3(s3),结果列于下表：,当阶段k=2时，s3=s2-x2，0s25，0 x2s2，有,结果列于下表：,当阶段k=1时，s2=s1-x1，s1=5，0 x1s1，有,结果可写成表格的形式,然后按计算表格的顺序反推，可知最优分配方案有两个：由于x1*=0，根据s2=s1-x1*=5-0=5，查表知x2*=2，由s3=s2-x2*=5-2=3，故x3*=s3=3。
4、即得甲工厂分配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，使总收入最大？,此问题的静态规划问题模型为：,动态规划的逆推关系方程为：,最后求得的f1(s1)即为所求问题的最大收入。,例2 机器负荷分配问题 某种
5、机器可在高低两种不同负荷下进行生产，设机器在高负荷情况下的产量函数为g=8u1，其中u1是投入生产的机器数量，年完好率为 a=0.7，在低负荷情况下的产量函数为h=5y，其中y是投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好机器的数量为1000台，试问每年如何安排机器在高低两种负荷下的生产，可使5年内生产的产品总产量最高。,允许决策集合0uksk,解：设阶段数k表示年度。状态变量sk为第k年度初拥有的完好机器台数。决策变量uk为第k年度中分配高负荷下生产的机器台数。故低负荷下生产的机器台数是sk-uk。状态转移方程,第k年度产量为,指标函数为,递推方程为,依次类推可得，,练习：每年年初的完好机器数。作业：如规定在第五年结束时完好机器数为500台，该如何安排生产？,
