《基本动态规划》由会员分享，可在线阅读，更多相关《基本动态规划（4页珍藏版）》请在金锄头文库上搜索。
1、动态规划问题动态规划问题摘要：摘要：该问题属于动态规划问题，本文从问题的提出到问题假设与分析，然后 得到模型，最后求解，得出最优的购买方案使得总生产能力最大。本文还从关键字：关键字：动态规划 最优采购方案 最优解问题的提出问题的提出某厂计划用 220 万元资金，购买生产同一种产品的四种型号的设备 A,B,C,D,这四种型号的设备设计生产能力 Ki（吨）和价格 Pi（万元/台）如表 1 所示，每种型号的设备应购买多少台，使总生产能力最大。（1） 建立动态规划模型，并用动态规划求出问题的最优解。（2） 若设备的实际生产能力达不到设计能力，则可能会影响设备购置计划的最优性。求 A 设备的生产能力 K
2、1=150 吨在什么范围内变化，不会影响整个设备计划的最优性?表格 1模型建立模型建立问题分析问题分析：资金的总数是确定的，关键是用确定数目的资金买四种不同生产能力的设备，合理地安排设备采购的数目使总生产能力最大。决策变量决策变量: :由于共有四种设备，可以用 xi 表示分别买进四种不同设备的数目；用 z 表示总的生产能力。决策目标决策目标：设备型号A B C D 生产能力 价格150 75 80 8570 75 80 85使总的生产能力最大，目标为：max z=150x1+75x2+80x3+85x4约束条件约束条件：由于资金的总数是一定的应有：70x1+75x2+80x3+85x4220设
3、备的数目不能为负，且必须为整数；Xi0 且为整数(i=1,2,3,4)模型求解模型求解：(1)用动态规划方法求解:按模型中变量的个数可以分为四个阶段，设状态变量为 s0,s1,s2,s3,s4,s0,s1,s2,s3,s4,记s4220;取s1,s2,s3,s4s1,s2,s3,s4为各阶段的决策变量；各阶段指标函数按加法结合，令最优值函数 fk(xk)fk(xk)表示第 k 阶段的结束状态为 sk，从 1 阶段至 k 阶段的最大值。设 70x1=s1, s1+75x2=s2, s2+80x3=s3, s3+85x4=s4220; 则有 x1=s1/70，0x2s2/75, 0x3s3/80,
4、 0x4s4/85。于是用顺推方法从前到后依次有f1(s1)= max(150x1）=15/7s1(x1=s1/70)及最优解 x1*=s1/70；f2(s2)= max75x2+f1(s1)=max75x2+15/7(s2-75x2)（0x2s2/75）得到 f2(s2)=15/7s2 及相应的最优解 x2*=0；f3(s3)= max80x3+f2(s2)=max80x3+15/7(s3-80x3)（0x3s3/80）得到 f3(s3)=15/7s3 及相应的最优解 x3*=0；f4(s4)= max85x4+ f3(s3)=max85x4+15/7(s4-85x4)（0x4s2/85）得
5、到 f4(s4)=15/7s4 及相应的最优解 x4*=0；由于 s4 不知道，故须再对 s4 求一次极值，即maxf4(x4)=max(15/7s4) (0s4220)显然，当 s4=220 时取最优解，但由于按反推求得的 x1=22/7,不是整数，故s4 应取 s4=210，使 fk(xk)取最优值(k=1,2,3,4),按反推求得 x1*=3,x2*=0,x3*=0,x4*=0。因此最优方案为购买设备 A 三台，此时总生产能力最大，为 450 吨。(2)由于设备的实际生产能力达不到设计能力时，可能会影响设备购置计划的最优性，那么可以设 A 设备的生产能力为(150+c)( -150c0)
6、,那么决策目标变为：max z=(150+c)x1+75x2+80x3+85x4而约束条件不变，若要不影响整个设备计划的最优性，那么不影响各个阶段的最优性，即不影响各阶段最优解的取值，用顺推方法从前到后依次有;f1(s1)= max(150+c)x1= (15/7+c/70)s1(x1=s1/70)及最优解 x1*=s1/70不变。f2(s2)=max75x2+f1(s1)=max75x2+(15/7+c/70)(s2-75x2)=max(15/7+c/70)s2+(75-1125/7-15c/14)x2（0x2s2/75），由于不影响最优解 x2*=0的取值，那么 75-1125/7-15c
7、/140，即有 c-80，于是得到 f2(s2)= (15/7+c/70)s2。f3(s3)=max80x3+f2(s2)=max80x3+(15/7+c/70)(s3-80x3)=max(15/7+c/70)s3+(80-1200/7-8c/7)x2（0x3s3/80），由于不影响最优解 x3*=0 的取值，那么(80-1200/7-8c/7) 0，即有 c-80，于是得到 f3(s3)= (15/7+c/70)s3。f4(s4)=max85x4+f3(s3)=max85x4+(15/7+c/70)(s4-85x4)=max(15/7+c/70)s4+(85-1275/7-17c/14)x2
8、（0x4s4/85），由于不影响最优解 x4*=0的取值，那么(85-1275/7-17c/14) 0，即有 c-80，于是得到 f4(s4)= (15/7+c/70)s4。由于 s4 不知道，故须再对 s4 求一次极值，即maxf4(x4)=max(15/7+c/70)s4 (0s4220)显然，当 s4=220 时取最优解，但由于按反推求得的 x1=22/7,不是整数，故s4 应取 s4=210，使 fk(xk)取最优值(k=1,2,3,4),按反推求得 x1*=3,x2*=0,x3*=0,x4*=0。综上可知-80c0，因此 A 的生产能力应在 70 吨和至 150 吨之间。评注：评注：动态规划的方法在工程技术、企业管理、工农业生产及军事等部门中都有广泛应用。上述问题就是工业生产中应用动态规划的一个例子。在生产和管理上，遇到这种合理的安排购买与生产的例子是很常见的。参考文献参考文献:1徐玖平 胡知能 主编 运筹学 I 类 第二版 高等教育出版社
