动态规划例1求解下列整数规划的最优解

1、例1求解下列整数规划的最优解:max Z 4x-i 5x2 6x33xi 4x2 5x3 w 10 s t Xj > 0 j 1,2,3 ,Xj为整数解（1）建立动态规划模型:阶段变量：将给每一个变量Xj赋值看成一个阶段，划分为3个阶段，且阶段变量k=1,2,3.设状态变量Sk表示从第k阶段到第3阶段约束右端最大值，则 Sj 10.设决策变量Xk表示第k阶段赋给变量Xk的值（k1,2,3).状态转移方程：S2 Si 3X1 , S3 S2 4X2.阶段指标:U1（S1,X1） 4为，比（勺，2） 5X2,U3（S3, X3） 6X3.基本方程;fk(Sk)0<max2uk Sk,X

2、kaki k 1k 3,2,1Sk 1其中 a13, a?4,83f4（S4）5.0.用逆序法求解:3时，maxS3 0< X3 -3 56X3f4 S4maxS30< X3W6X3,0,1,2,3,4,5,6,7,8,9,10 . x表示不超过x的最大整数。因此，当 S30,1,2,3,4 时,x30 ;当Sj5,6,7,8,9时，x3可取0或1 ;当&10时，x3可取0,1,2,由此确定f3 S3现将有关数据列入表4.1中表4.1中.、逬6X3f4(S4)f3（S3）*X30120000100020003000400050661606617066180661906611

3、00612122S2max5x2max 5x2 f3 s2 4x20< x2 <2当k 2时，有而 S20,1,2,3,4,5,6,7,8,9,10 。所以当 s2 Q.1,2,3 时，x20 ;当 s 4,5,6,7 时,X20或1;当S28,9,10时X20,1,2。由此确定f2s。现将有关数据列入表4.2中.表4.2S2 5X2 彳3(S24X2)f3(S3)*X3S301200+000010+000120+000230+000340+05+051050+65+060560+65+060670+65+060780+65+010+0102090+65+610+01115100+

4、125+610+012010当k 1时,有f1 S|max 4为 f2 s，max 4为 f2 S| 3x1S1S10= X1 w0= X1 w1313而S,10,故X1只能取0,1,2,3，由此确定f1 §。现将有关数据列入表4.3中。表 4.34%f2 s 3%f1 Si*X1S2 0123100+124+68+512+01324按 计 算 顺 序 反 推， 由 表 4.3 可 知，当x12时,f 1(s1)取得最大值13.又由S24查表4.2得x21,及0,再由表4.1查得x30因此,最优解为x 3 2,x3 1, x3 0,最优解 maxZ 13.例5用动态规划方法解下列非线

5、性规划问题2max z xi x2 x3x2 x3 cXi 0 i 1,2,3解：解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k=1，2，3设状态变量为S1，&，S3，S4并记S1< c取问题中的变量X1，X2，X3为决策变量状态转移方程为：S3=X3S3+X2=S2S2+ X1 = S1 < c允许决策集合为：X3=S30 < X2< S20< X1< S1各阶段指标函数为：V1 (X1)=X1 V2 ( X2)=X22 V3 ( X3) =X3，各指标函

6、数以乘积方式结合，最优指标函数 fk ( Sk)表示从第k阶段初始状态Sk出发到第 3阶段所得到的最大值，则动态规划基本方程为：fk(Sk)maX、Vk(Xk) fk1(Sk1)k 3,2,1Xk Dk(Sk)f4(S4)1用逆序解法由后向前依次求解：k=3 时，f 3 (S3 )max "3(x3)X3 D3G3)f4(S4 )max(X3)冷S3S3X3 = S3k=2 时，f2(S2)max MX?)f36)max (x；S3)2max x2 (s2 x2 )沁 D2(S2)0 X2 S20 X2S2令h22(S2，X2)=X2( S2 X2)用经典解析法求极值点:dh22x2

7、s2 3xf 0解得：X22一 S2X2=0 (舍)dx23d2h2d2h22s2 6x222s20dxfdxfX2- S23所以X23 s2是极大值点f 2 ( s2 )22243(3S2) (S2 3S2)习S2* 2X2S23k=1 时,fi(Si)max vi(xi) f2(S2)max (xiX Di (S )0 Xi S4 3.27S2)max x10 Xi S|习(sixi)3 43令hi(S，Xi) xi 27(Si xi)dh idx27(si xi)31 2 2 Xi(S x i) ( 1 )解得:XiXi= Si (舍)d2h -dx：27(sXi)2(1)2|(S xi

8、 )227xi(sXi)%27Xi)(2xi3)d2hdx：Xi?S 2027i所以Xi4 Si是极大值点4s)3 64Si44644fi(Si)Si(Si427由于Si未知，所以对&再求极值,Xii;Si4 max f i (s-i) max( s ) 0 s c0 Si c 64显然Si=c时，fi ( Si)取得最大值fi (Si)i c 64S 1 =cXi4s 1c4f i(S)164* 3*21f2(S2)4S2S ixicX2S2c27432*1f 3 (S3)S3S2X2cX3S3cS344所以最优解为：Xi*c,X2*c, X31 * c,z4 c42464反向追踪得

9、各阶段最优决策及最优值:例6用动态规划方法解下列非线性规划问题I c 4c43S2i 3 c i6max z2XiX23X3XiX2X36Xj0j1 ,2,3解：按变量个数将原问题分为三个阶段，阶段变量k=1 , 2, 3;选择Xk为决策变量；状态变量sk表示第k阶段至第3阶段决策变量之和； 取小区间长度 =1，小区间数目m=6/1=6，状态变量Sk的取值点为：sk 0,1,2,3,4,5,6 k 2Si 6状态转移方程：Sk+1 = S< Xk ；允许决策集合：Dk (Sk) = Xk|0<XkWSkk=1 , 2, 3X<, Sk均在分割点上取值；阶段指标函数分别为：gl

10、(Xi)=X12g2(X2)=X2g3(X3 )=X33 ,最优指标函数fk (sQ表示从第k阶段状态S<出发到第3阶段所得到的最大值， 动态规划的基本方程为：fk(sQmaXgk(Xk) fk1(Sk1)k 3,2,10 Xk Skf4(S4)1k=3 时，弘3)maX(X：) s3S3及X3取值点较多，计算结果以表格形式给出，见表6.1-6.3所示。表6.1计算结果*S3X3f3(S3)*X301234560000111128823272734646445125125562162166表6.2计算结果*X2 f3(S2 X2)f2(S2)*S20123456X20000101 X00

11、0,1201 X12X011301 X82X13 X081401 X272X83 X14 X0271501 X642X273 X84 X15X0641601 X1252X643 X274 X85X16X01282表6.3计算结果02 -X1 f2(S1 X1)f1(S1)*X10123456601 X644X279 X816 X125 X036 X01082* * r *由表 6.3 知，xi =2 , si=6，贝U S2= si - xi =6 2=4，查表 6.2 得：X2=1，则 S3= S2 X2 =4 仁3，查表 6.1 得：X3 =3，所以最优解为：xi =2，X2 =1，X3

12、=3，fi(Si)=108。上面讨论的问题仅有一个约束条件。对具有多个约束条件的问题，同样可以 用动态规划方法求解，但这时是一个多维动态规划问题，解法上比较繁琐一些。例7某公司打算在3个不同的地区设置4个销售点，根据市场部门估计， 在不同地区设置不同数量的销售点每月可得到的利润如表6.4所示。试问在各地区如何设置销售点可使每月总利润最大。表6.4利润值地区销售点01234101625303220121721223010141617解：如前所述，建立动态规划数学模型：将问题分为3个阶段，k=1，2, 3；决策变量Xk表示分配给第k个地区的销售点数；状态变量为Sk表示分配给第k个至第3个地区的销售

13、点总数；状态转移方程：Sk+1 = Sk Xk，其中Si=4 ；允许决策集合：Dk ( Sk) = Xk|0< Xk< Sk阶段指标函数：gk (Xk)表示Xk个销售点分配给第k个地区所获得的利润； 最优指标函数fk (Sk)表示将数量为*的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：fk(Sk) 0maxgk(Xk) fki6 xQk 3,2,10 Xk Skf4(S4)0数值计算如表所示。表6.5 k=3时计算结果S3g3 （x）f3（S）X3012340000110101214142316163417174表6.6 k=2时计算结果Xx>S2、g

14、2（X2）+ f3（S2 X2）f2（9）X201234000010+1012+012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312,3表6.7k=1时计算结果7g*X1）+f2（S1 为）f1（S）X10123440+3116+2725+2230+1232+0472所以最优解为：xi =2，X2 =1，X3=1，fi=47，即在第1个地区设置2个销 售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润 47。例9 (生产一库存冋题)某工厂要对一种产品制定今后四个时期的生产计划，据估计在今

15、后四个时期 内，市场对该产品的需求量分别为 2，3, 2，4单位，假设每批产品固定成本为3千元，若不生产为0，每单位产品成本为1千元，每个时期最大生产能力不超 过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前 提下总成本最小。解：以每个时期作为一个阶段，该问题分为 4个阶段，k=1，2, 3, 4；决策变量Xk表示第k阶段生产的产品数；状态变量Sk表示第k阶段初的库存量；以dk表示第k阶段的需求，则状态转移方程：Sk+i = *+Xk dk； k=4，3，2，1 由于期初及期末库存为0，所以Si=0，

16、S5=0 ;允许决策集合Dk (sQ的确定：当s<>dk时，xk可以为0,当s<vdk时，至少 应生产dk Sk，故Xk的下限为max (0，dk s<)每期最大生产能力为6，Xk最大 不超过6，由于期末库存为0，Xk还应小于本期至4期需求之和减去本期的库存44量， d j Sk，所以x<的上限为min ( d j Sk，6)，故有：j kj k4Dk ( s<) = xk| max (0，dk s<)< Xk< min (dj Sk，6)j k阶段指标函数rk (sk，xk)表示第k期的生产费用与存贮费用之和：k(Sk,Xk)0.5skX

17、k0.5skXk 0Xk123,4,5,6最优指标函数fk ( Sk)表示第k期库存为Sk到第4期末的生产与存贮最低费 用，动态规划基本方程为：fk(Sk)min、rk(Sk,Xk) fk1(Sk1)k 4,3,2,1k Dk(sk)f5 (S5)0先求出各状态允许状态集合及允许决策集合，如表6.8所示。表6.8状态允许状态集合及允许决策集合S0D1(s1)234,5,6孚01234D2(s2)345,62,3,4,5,61,2,3,4,5,60,1,2,3,4,5,60,1,2,3,4,5 S30123456D3(S3)234,5,61,2,3,4,5 .0,1,2,3,4 0,1,2,3

18、0,1,2 0,10 S401234D4(s43210 由基本方程计算各阶段策略，结果如下表所示。表6.9 k=4时计算结果S4x0.5®4（S4,X4）c3 x4X400.5s4 x40S5f5（S5）f4（S）04700713*6.5006.5*2*2600*631*5.5005.5*4*0200*2表6.10k=3时计算结果S3X330X3）0.5s33 X30.5S3X30X30S4=Ss+ X3- 2f4（S4）f3（S3）2507123616.512.504726135835.513.56*94211*14.50711.525.516.512136.52612.547.5

19、35.5135*8.54210.5*0107*81516.511.522626123735.512.54842100*1.516.58*315.52611.526.535.51237.5429.5*02268*41635.511.5274295*012.56.5345.52*88.56*0342*5表6.11k=2时计算结果S2X22（"2）0.5s23 x20.5s2X20X20S3=S2+ X 一 3f3（S）f2（S）360111747110.517.50*58281669381725.501116.536.5110.51714*7.52815.5*58.53816.569.5

20、4817.5150111626110.516.53*72815*248381659481761058180*1.501112.5*15.5110.51626.52814.5337.53815.548.54816.559.55817.5610.56515.50*2110.512.5*16281427381543848164958175106515表6.12k=1时计算结果S1X10.5S|3 x1X10.5s!x100S2= X1 2f2（S2）f1(S1)250162136115.521.504721522*58312.520.5*69412.521.5逆向追踪可得：xi=5, S2=3, X

21、2 =0, S3=0 , xa =6 , S4=4 , X4=0，即第 1 时期 生产5个单位，第3时期生产6个单位，第2, 4时期不生产，可使总费用最小， 最小费用为20.5千元。例10 （库存一销售问题）设某公司计划在1至4月份从事某种商品经营。已知仓库最多可存储600件这种商品，已知1月初存货200件，根据预测知1至4月份各月的单位购货 成本及销售价格如表6.13所示，每月只能销售本月初的库存，当月进货供以后 各月销售，问如何安排进货量和销售量，使该公司四个月获得利润最大(假设四 月底库存为零)。表6.13单位购货成本及销售价格月份购货成本C销售价格P140452384234039442

22、44解：按月份划分阶段，k=1，2，3，4 ；状态变量Sk表示第k月初的库存量，&=200，S5=0 ；决策变量：xk表示第k月售出的货物数量，yk表示第k月购进的货物数量； 状态转移方程：Sk+1 = S+yk Xk；允许决策集合：0W XkW Sk， 0W ykW 600 ( Sk Xk)；阶段指标函数为：pkXk dyk表示k月份的利润，其中pk为第k月份的单位 销售价格，d为第k月份的单位购货成本；最优指标函数fk (Sk)表示第k月初库存为Sk时从第k月至第4月末的最大 利润，则动态规划基本方程为：fk(Sk)0 max PkXk CkYk0 xk sk0 yk 600 (S

23、k x<)fk 1(sk 1)f5(S5)0k 4,3,2,1k=4 时,f4(S4)max(44x442 y4)44 S4X4 = S4y4 =0k=3 时,f36) nmax39X30X3S30y3600 (S3X3)max39X30X3§0y3600 (S3X3)0max(44S3X3S30y3600 (S3X3)0 X4 S40 y4 600 (S4X4)40 y3f4(S4)40 y3 44( S3 y X3)5X3 4y3)为求出使44& 5x3+4y3最大的X3，y3，须求解线性规划问题:max z 44s3 5x3 4y3X3 S3X3 y 600 S3

24、X3, y30只有两个变量X3, y3,可用图解法也可用单纯形法求解， 取得最优解，X3=0 ,y3 =600 S3,=40 S3+2400k=2 时,max 42x2 38 y20 X2 S20 y2 600 (S2 X2)max42x2 38 y20 X2 S20 y2 600 (S2 X2)max(40s2 2x20 X2 S220 y2 600 (S2 X2)f3(S3)40(s2 y2 x2) 24002y22400)类似地求得：X2*= S2，y2*=600，f2（ S2）=42&+3600f2(S2)k=1 时,fi(Si)max 45%40y10 Xi S|0 yi 6

25、00 (Si Xi)max45xi 40yi 42( si yi xi) 36000 xi Si0 yi 600 (S| xi )0 x max (42 Sj 3xi 2yi 3600)0 yi 600 (S| Xi )类似地求得:xi = si，yi =600，fi( si)=45si+4800=i3800逆向追踪得各月最优购货量及销售量:yi =600 ;y2 =600 ;Xi = Si =200X2 =S2=Si+ yi xi =600X3 =0y3 =600 S3=600 ( S2+ y2 X2) =0* * * *xi =S4= (S3+ y3 X3 ) =600y4 =0即i月份销

26、售200件，进货600件，2月份销售600件，进货600件，3月 份销售量及进货量均为0,4月份销售600件，不进货，可获得最大总利润i3800。例ii某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季 节是从i0月i日至3月3i日。下个销售季节各月的需求预测值如表6.i4所示表6.i4需求预测值仲位：双）月份ioiii2i23需求402030403020该鞋店的此种鞋完全从外部生产商进货， 进货价每双4美元。进货批量的基本单位是箱，每箱10双。由于存贮空间的限制，每次进货不超过5箱。对应不同的订货批量，进价享受一定的数量折扣，具体数值如表6.15所示。表6.15数量折扣数值表进货批

27、量1箱2箱3箱4箱5箱数量折扣4%5%10%20%25%假设需求是按一定速度均匀发生的， 订货不需时间，但订货只能在月初办理 一次，每次订货的采购费（与采购数量无关）为 10美元。月存贮费按每月月底 鞋的存量计，每双0.2美元。由于订货不需时间，所以销售季节外的其他月份的 存贮量为0”。试确定最佳的进货方案，以使总的销售费用最小。解：阶段：将销售季节6个月中的每一个月作为一个阶段，即 k 1,2,6 ；状态变量：第k阶段的状态变量Sk代表第k个月初鞋的存量；决策变量：决策变量Xk代表第k个月的采购批量；状态转移律：Sk 1 Sk Xk dk （ dk是第k个月的需求量）；边界条件：S S70,

28、 f7（S7）0 ；阶段指标函数：rk（Sk,Xk）代表第k个月所发生的全部费用，即与采购数量无 关的采购费Ck、与采购数量成正比的购置费 Gk和存贮费Zk.其中：0, Xk 0 Ck ； Gk px xk ； Z k 0.2（Sk xk dk）10, xk 0最优指标函数：最优指标函数具有如下递推形式fk（Sk） min Ck Gk Zk f k 1 （Sk 1）xkminCk Gk 02（Sk Xk dk） fk 1 （Sk Xk dk ）Xk当k 6时（3月）：表6.16 k 6时计算结果01020X620100f6 （ Ss）86480当k 5时（2月）:表6.17 k5时计算结果X5

29、01020304050X5f 5( S5 )020418816450164101721681424014220134136122301223086989008640505205050404当k 4时（1月）:表6.18 k 4时计算结果X01020304050X4f4（S4）0302304403021028228228630、4028220250262264252202503021223024423021810212401641922122101961700164501441741781761520144601261401441320126当k 3时（12月）:表6.19 k 3时计算结果XX301020304050X3f 3( S3 )04204224145041410388402392384503842035037037236233250332303