三、动态规划的应用举例

1、三、动态规划的应用举例(一)定价问题例27考虑为某新产品定价，该产品的单价从每件5元、6元、7元、8元这四个价 格中选取其中之一，每年年初允许变动价格，但幅度不能超过1元。该公司预计该产品 畅销只有五年，五年后将被淘汰，另据销售情况的预测，在价格不同的情况下个年的预 计利润如表3-32。表3-32预计利润额(单位：万元)单价第一年第二年第三年第四年第五年5元10121520256元121316202471615151414解：1.画出多阶段决策图，如图3-10。图中圆圈内的数字表示各年不同定价下的利润。出一H15图 3-102.确定参数根据题意，可划分为五个阶段，每阶

2、段之末进行价格策略。k阶段的状态变量sk取为本年制定的价格，状态的可能集合为：S广(5,6,7,8)。据每年年初允许价格变动的幅度不能超过1元，故决策变量与上一阶段的价格有关，当上阶段的价格为，.时，则u (s ) = (s -1, s , s )，且(s ) E Sk kk k k+1k k k 状态转移方程sk+i = uk (sk)最优指标函数的递推公式f (s ) = maxd (s ,u ) + f (s )k kk k kk+1 k+1uk式中，fk(七)从第k阶段开始到最后阶段为止的最大总收益，dk第k阶段的收益值，在本例中dk仅与sk有关。3.进行各阶段的计算设人(S6)=0,

3、人(7)=18,人(8)二14。这时，当 k =5 时，S5=5,6,7,8,所以人(5)二25,人(6)二24,当 k =4 时，S4=5,6,7,8,f (s ) = max d (s , u ) + f (s )4444455f (5) = ma叩55)顼5(5) = ma2。+ 孔=45 4d 4(56) + f (6)J20 + 24J所以u (5)=5；4d4(65) f (6) = max d (66) + f (6)所以u4(6)=5；d 4(76)+ 以6)f =max =max 、20+18,18 + 24、 =max 8 +14,=42=45所以u (7)=6；4f (8

4、) = maxjd4(87) + f5| = ma/4 + % 32 4 d 4(88) + f (8) J14 + 14j所以u4 (8)=7。当 k =3 时，S3=5,6,7,8，这时|15 + 45f (5) = max，= 603115+45|七=5或者6；|16 + 45 f (6) = max16 + 45316 + 42 = 61七=5或者6；|16 + 45 f (7) = max16 + 42316 + 32 = 61u3(7)=6；f(8)= max：5 ： 42 = 57，u3 (8)=7。315 + 32J3当 k =2 时，S2=5,6,7,8，这时，12 + 60

5、件)=m叫 12 + 61 73，七=6；|13 + 6。f (6) = max 13 + 61，= 74 ,n6)=6 或者 7；213+612|14 + 61|fJ7) = maxj14 + 61，= 75 ,u2(7)=6 或者 7；14 + 5715 + 61f2(8) = maX检 + 57 = 76，七(8)=7。当 k =1 时，S1=5,6,7,8,这时10 + 73f1=m叫10 + 74，= 84，ui(5)=6；|12+73|f (6) = max12 + 74，= 87，u (6)二7；|12 + 75|14+74|f =max 14 + 75，= 90，u (7)二8

6、；1 1、14 + 7616 + 75f1(8) = max16 + 76，= 92，气二8。所以，最优策略是，第一年定价8元，第二年定价8元，第三年定价7元，第四年 定价6元，第五年定价5元，总利润是92万元。本例也可以利用图上标号法，图3-10圆圈上方的数字就是在各阶段各状态下的最优 收益值。双实线表示最优定价策略路线。（二）资源分配问题例28某公司准备将五台加工中心分配给所属的甲、乙、丙、丁四个工厂。各工厂 获得该设备后，可以取得的利润估算如表3-33所示。试问，应如何分配这些设备，使公 司的总利润最大？表3-33预计利润（单位：万元）设备数甲乙丙丁0000016354277106310

7、91111412121112515131112解：1.按动态规划要求确定以下参数： 将分配问题按工厂甲、乙、丙、丁顺序分为四个阶段。各阶段的状态参数s取为在各阶段可能分配设备的总台数或者说，七是分配给 第k个工厂以后（含第k个工厂）的各工厂的设备总数。U是分配给辨个工厂的设备台数。状态转移方程s =s -u (s )k+1k k k最优指标函数fk（S）是从第k阶段开始到最后阶段为止的最大利润指标函数 递推关系式:k ) + f+1(Sk Juk f4(Sk) = 02.下面进行分阶段的计算当k =4时，S（0,1,2,3,4,5） , S4取不同值时，九（S4）的计算如表12-3所示。表 3

8、-34Sud (s , u )Eu*(s )000001144122662331111344121245512125当阵3时，是将s 3 MV,5）台设备分配给丙和丁两个工厂。这时，对于每个S 3值都有一个最优分配方案，使这两个工厂的总利润为最大。即f (s ) = maxd (S , u ) + f (S )3333344u3=maxd (s ,u ) + f (s -u )333433u3当S3取不同值时，九(S3)的计算如表3-35。当k =2,S2=(0,1,2,3,4,5)；当S2取不同值时，九(S2)的计算如表3-36。当k =1时，Si=5,/i（Si）的计算如表3-37。表 3

9、-35Sud (s , u )333f4(S3 u3)d 3+ f4u*(s )f3( s 3)0000000105441500662154921001021000111132510614214311011001212151116142106162163114154110110012121512175210e2117221411415511011表 3-36sud (s , u )f3( s2 u2 )d2 + f3u*( s )f2()0000000100550513030010100102135827070014140141310133275123909001616131417142710

10、172173951441201200212101316192714212215391019412517513013表 3-37sud (s , u )f2(5 - 1)d1 +f2u*(s )fi(S i)002121161723123271421531010204125175150153.从第一个阶段开始寻找最优决策序列，其步骤如下： 由u*(5) = 1,可知应分配给甲工厂1台设备，剩下4台设备待以后分配。 由*(4) = 1或2,可知分配给乙工厂有两个最优方案，1台或2台。当分配给乙 2工厂1台时，剩余3台待以后分配；当分配给乙工厂2台时，将剩余2台设备待分配。 由*(3) 二 2，可知应分