文档介绍：动态规划问题
摘要:该问题属于动态规划问题,本文从问题的提出到问题假设与分析,然后得到模型,最后求解,得出最优的购买方案使得总生产能力最大。本文还从
关键字:动态规划  最优采购方案最优解
问题的提出
某厂计划用220万元资金,购买生产同一种产品的四种型号的设备A,B,C,D,这四种型号的设备设计生产能力Ki(吨)和价格Pi(万元/台)如表1所示,每种型号的设备应购买多少台,使总生产能力最大。
(1)    建立动态规划模型,并用动态规划求出问题的最优解。
(2)    若设备的实际生产能力达不到设计能力,则可能会影响设备购置计划的最优性。求A设备的生产能力K1=150吨在什么范围内变化,不会影响整个设备计划的最优性?
表格1
设备型号
A B C D
生产能力
价格
150 75 80 85
70 75 80 85
模型建立
问题分析:
资金的总数是确定的,关键是用确定数目的资金买四种不同生产能力的设备,合理地安排设备采购的数目使总生产能力最大。
决策变量:
由于共有四种设备,可以用xi表示分别买进四种不同设备的数目;用z表示总的生产能力。
决策目标:
使总的生产能力最大,目标为:
max z=150x1+75x2+80x3+85x4
约束条件:
由于资金的总数是一定的应有:
70x1+75x2+80x3+85x4
《
《220
设备的数目不能为负,且必须为整数;
Xi《0 且为整数(i=1,2,3,4)
模型求解:
(1)
用动态规划方法求解:
按模型中变量的个数可以分为四个阶段,设状态变量为s0,s1,s2,s3,s4,记s4《220;取s1,s2,s3,s4为各阶段的决策变量;
各阶段指标函数按加法结合,令最优值函数fk(xk)表示第k阶段的结束状态为sk,从1阶段至k阶段的最大值。
设70x1=s1, s1+75x2=s2, s2+80x3=s3, s3+85x4=s4《220;
则有x1=s1/70,0《x2《s2/75, 0《x3《s3/80, 0《x4《s4/85。
于是用顺推方法从前到后依次有
f1(s1)= max(150x1)=15/7s1(x1=s1/70)及最优解x1*=s1/70;
f2(s2)= max[75x2+f1(s1)]=max[75x2+15/7(s2-75x2)](0《x2《s2/75)
得到f2(s2)=15/7s2及相应的最优解x2*=0;
f3(s3)= max[80x3+f2(s2)]=max[80x3+15/7(s3-80x3)](0《x3《s3/80)
得到f3(s3)=15/7s3及相应的最优解x3*=0;
f4(s4)= max[85x4+ f3(s3)]=max[85x4+15/7(s4-85x4)](0《x4《s2/85)
得到f4(s4)=15/7s4及相应的最优解x4*=0;
由于s4不知道,故须再对s4求一次极值,即
maxf4(x4)=max(15/7s4) (0《s4《220)
显然,当s4=220时取最优解,但由于按反推求得的x1=22/7,不是整数,故s4应取s4=210,使fk(xk)取最优值(k=1,2,3,4),按反推求得x1*=3,x2*=0,x3*=0,x4*=0。