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

1、例1求解下列整数规划的最优解:max Z 4xi 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的值（k 1,2,3）.状态转移方程：s $ 3x-i, s3 s2 4x2.阶段指标：U1（S!,X1） 4X1,U2（S2,X2） 5X2,U3（S3, X3） 6x3.基本方程；fk(Sk)f4(S4)maxu kSk0 X3

2、 w.ak0.Sk, xkfk 1 Sk 1k 3,2,1其中a13, a?4, a35.（1）用逆序法求解：当k3时，f3 S3max 6x3 f4s4max 6x30W X3-0W X3W-55而S30,1,2,3,4,5,6,7,8,9,10 . x表示不超过x的最大整数。因此，当S30,1,2,3,4时,x3 0 ；当S3 5,6,7,8,9时，x3可取0或1 ;当S3 10时，x3可取0,1,2,由此确定f3现将有关数据列入表中000010002000306004060050661606126170661806619061100122当k 2时，有2 s2max 5x2s 20 x2

3、243 s3max 5x2 f3 s, 4x2s 20 x2 24而 S20,1,2,3,4,5,6,7,8,9,10 。所以当 S20,1,2,3 时，x?0 ;当 s 4,5,6,7 时,X20或1 ；当S2 8,9,10时X20,1,2。由此确定f2 s。现将有关数据列入表中表5x2f3（S2 4X2）f3（S3）*X3S301200+000010+000120+05+000230+05+000340+05+010+051050+65+010+060560+660670+65+010+060780+65+6102090+65+61115100+1212010当k 1时,有fi Simax

4、 4xi f2 $ max 4为 f2 s 3xiS1S100 Xi 三33而Si10,故Xi只能取0,1,2,3,由此确定fi Si。现将有关数据列入表中。表S14f2 S 3x1fi *XiS2、 0123100+124+68+512+01324按 计 算 顺 序 反 推， 由 表 可 知 ， 当Xi2时,f i(Si)取得最大值13.又由S2 4查表4.2得X21,及S30,再由表4.1查得x30因此,最优解为x 32,x31, x30,最优解 maxZ 13.例5用动态规划方法解下列非线性规划问题max z x1 xf x3x1 x2 x3 cxi 0 i 1,2,3解：解决这一类静态

5、规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k=1, 2, 3设状态变量为 Si， S2， S3， S4并记SiW c取问题中的变量Xi，X2，X3为决策变量状态转移方程为：S3=X3Sa+X2=S2S2+Xi=Si c允许决策集合为：X3=S30 X2 S20 Xi Si各阶段指标函数为：Vi ( Xi) =XiV2 ( X2) =X22V3 ( X3) =X3，各指标函数以乘积方式结合，最优指标函数fk (Sk)表示从第k阶段初始状态Sk出发到第1)k 3,2,13阶段所得到的最大值，则动态规划基本方程为：fk(

6、Sk)max vk(Xk) fk i(SkXk Dk(Sk)f4(S4)1用逆序解法由后向前依次求解：k=3 时,f3(S3)X3mDaXS3)V3(X3) f4(S4)max(x3)X3 S3S3X3 =S3k=2 时,f 2 ( S2 )X2maxs2)v2(x2)f3(S3)max (x；0 X2 S2S3 )2max X2 (S20 X2 S2X2)2令 h2( S2，X2)=X2 ( S2 - X2)用经典解析法求极值点:dh2dx22x2s2解得:X223S2X2=0 (舍)d2h2dx：2S26x2d2h2dx；X22宁22S2所以X223S2是极大值点。f2(S2)(|S2)2

7、(S2 討专X2k=1 时,fi(Si)xmaxjmxi) f2(s2)拧蕉化4 327S2)max x10 X, S4327 (s Xi)令 hi(S,X)4Xi 27(sXi)3dh idxXi)3Xi(s Xi)2( i )解得:Xi=Si (舍)1Xi S4id2hii2应 27(Sxi)2(1)i2护Xi)22424Xi)27(Sixj(2xi Si)d2hdx；所以XiXi927s20i- Si是极大值点。4i4 /i .3Si(SiSi )4 27464由于Si未知，所以对Si再求极值，fi(Si)丄Si4Ximax fi (si) max( si)0 Si c0 Si c 64

8、显然Si=c时,f i ( Si)取得最大值fi (Si)i 4 c64反向追踪得各阶段最优决策及最优值:*iifi(Si)Si=cxiSic44*3*2if2(S2)S2SiXic4X23S2c2*1*if36)S3S2X2c4X3S3 i4c所以最优解为*:xii *c,X2i *c, X3i * i-c,z4 c0 si c 64例6用动态规划方法解下列非线性规划问题i c 644 3S2271S3c34i 3 c i6max z2XiX2XiXj3X36i,2,3X3j解：按变量个数将原问题分为三个阶段，阶段变量 k=i，2, 3;X20选择Xk为决策变量;状态变量Sk表示第k阶段至第

9、3阶段决策变量之和;取小区间长度 =i，小区间数目m=6/i=6，状态变量Sk的取值点为:Sk 0,i,2,3,4,5,6 k 2Si6状态转移方程：Sk+i =Sk Xk ；允许决策集合：Dk （Sk） = Xk|O XkW skk=l, 2, 3Xk, Sk均在分割点上取值；阶段指标函数分别为：gi（Xi）=xjg2（X2） =X2 ga（X3）=X33，最优指标函数f k（Sk）表示从第k阶段状态Sk出发到第3阶段所得到的最大值，动 态规划的基本方程为：fg omaXkg） fkiE）k 3,2,1f4（S4）1k=3 时，f3（S3）maX（X3） SS3及X3取值点较多，计算结果以表

10、格形式给出，见表所示。表计算结果S3X3f 3（ S3）*X301234560001011128823276427341256445216125562166表计算结果*X2 f 3（S2 X2）f 2（ S2）*X20123456表计算结果2X1f 2（ S1 X1）f 1（S1）*X10123456601 X 644X 279X 816X 125X 036 X 01082由表知，x；=2, Si=6,则 S2=Si x=62=4,查表得：x；=1,则 S3= S2-x；=4* 、 、 _ * * *仁3,查表得：X3=3，所以最优解为：Xi =2, X2=1, X3=3, fi（Si）=10

11、8。00101 X 0201 X 12X 0301 X 82X 13 X 0401 X 272X 83 X 1501 X 642X 273 X 8601 X 1252X 643 X 270000,1114X 0814X 15 X 02714X 85 X 16X 06411282上面讨论的问题仅有一个约束条件。对具有多个约束条件的问题，同样可以 用动态规划方法求解，但这时是一个多维动态规划问题，解法上比较繁琐一些。例7某公司打算在3个不同的地区设置4个销售点，根据市场部门估计， 在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。表利润值地区销售

12、点01234101625303220121721223010141617解：如前所述，建立动态规划数学模型:将问题分为3个阶段，k=1, 2, 3；决策变量Xk表示分配给第k个地区的销售点数；状态变量为Sk表示分配给第k个至第3个地区的销售点总数；状态转移方程：Sk+i=Sk Xk,其中Si=4；允许决策集合：Dk (Sk) = Xk|0 Xkdk时，Xk可以为0,当Skdk时，至少 应生产dk Sk,故Xk的下限为max (0, dk Sk)每期最大生产能力为 6, Xk最大不超过6,由于期末库存为0, Xk还应小于本期至4期需求之和减去本期的库存sk，6)，故有:44量， dj sk，所以

13、Xk的上限为min( d jj kj k4Dk (Sk) = Xk| max (0，dk Sk) xw min ( dj sk， 6) j k阶段指标函数rk (Sk，Xk)表示第k期的生产费用与存贮费用之和:k(Sk,Xk)0.5s3 xk 0.5skXk 0Xk123,4,5,6最优指标函数fk( Sk)表示第k期库存为Sk到第4期末的生产与存贮最低费用，动态规划基本方程为:fk(Sk)min k(Sk,Xk)fk1(SkJk 4,3,2,1Xk Dk(sk)f5(S5)0先求出各状态允许状态集合及允许决策集合，如表所示。表状态允许状态集合及允许决策集合S10D( s234,51),6 S

14、201234D2( s3,4,5,62,3,4,51,2,3,4,0,1,2,3,4, 0,1,2,3,2),6 5,6 5,6 4,5 S30123456D3( s3)2,3,4,5,6 1,2,3,4,5 0,1,2,3,4 0,1,2,3 0,1,2 0,10S401234D4( S4)43210 由基本方程计算各阶段策略，结果如下表所示表k =4时计算结果S4X40.5s44(S4,X4)3 X4x40O.5S4 X40S5f 5( S5)f 4( S4)047OO71*3OO*2*26OO*63*1OO*4*02OO*2表 k=3时计算结果S3X30.5s330X3)c3 X3X3

15、OO.5S3 x3 OS4= S 3+ X 3 2f 4( S4)f 3( S3)25O712361O472613583*6942*111O7211213264313*542*O*1O7*8151226261237348421O*O1*83126231234202268*416327429501342*86*0342*5表k =2时计算结果S2X2r2（S2,X2）0.5s23 X2X20.5S2 X200S3= S 2+ X 2 3f 3（S3）f 2（S2）360111747105*82816*6938172011311714*28*53864815011162613*72815*2483

16、816594817610581830*011*12128163384485586650*21*16281427381543848164958175106515表k =1时计算结果S1X10.5S|W)3 x1X10.5$x100S2=x 1 2f 2( S2)f 1( S1)250162136104721522*583*694逆向追踪可得：Xi=5, S2=3, X2 =0, S3=0, X3 =6, S4=4, X4 =0,即第 1 时期生产5个单位，第3时期生产6个单位，第2, 4时期不生产，可使总费用最小， 最小费用为千元。例10 （库存一销售问题）设某公司计划在1至4月份从事某种商品经

17、营。已知仓库最多可存储600件这种商品，已知1月初存货200 件,根据预测知1至4月份各月的单位购货成 本及销售价格如表所示，每月只能销售本月初的库存，当月进货供以后各月销售，问如何安排进货量和销售量，使该公司四个月获得利润最大(假设四月底库存为零)表单位购货成本及销售价格月份购货成本C销售价格P14045238423403944244解：按月份划分阶段，k=1, 2, 3, 4；状态变量Sk表示第k月初的库存量，Si=200, S5=0;决策变量：Xk表示第k月售出的货物数量，yk表示第k月购进的货物数量； 状态转移方程：Sk+i=Sk+ykXk ；允许决策集合：0w XkW Sk， 0w

18、ykW 600 (Sk Xk)；阶段指标函数为：PkXk Ckyk表示k月份的利润，其中Pk为第k月份的单位 销售价格，Ck为第k月份的单位购货成本；最优指标函数fk (Sk)表示第k月初库存为Sk时从第k月至第4月末的最大 利润，则动态规划基本方程为：fk(sQ 0 max PkXk Ckyk fk 16 J k 4,3,2,10 xk sk0 yk 600 (Sk x)f5(S5)0f4(S4)X4 =S4 y4 =0k=4 时，max(44x4 42 y4) 44 s40 X4 S40 y4 600 (S4 X4)f3(S3)nmax39X30X30y3600 (S3X3)max39X3

19、0X30y3600 (S3X3)0max(44S3X30y3600 (S3X3)40 y3 f4(S4)40 y344( S3 y X3)5x3 4y3)为求出使44S3 5X3+4y3最大的X3, y3,须求解线性规划问题:max z 44s3 5x3 4y3X3 S3X3 y3600 S3X3,y30只有两个变量X3, y3,可用图解法也可用单纯形法求解，取得最优解，X3*=0,y 3* =600 S3, f 3(S3)=40S3+2400k=2 时,f2(S2 )maX42X2 38y2 f3(S3)0 X2 S20 y2 600 (S2 X2)maX42X2 38y2 40(S2 y2

20、 X2 ) 24000 X2 S20 y2 600 (S2 X2 )maX(40S2 2X2 2y2 2400)0 X2 S20 y2 600 (S2 X2 )类似地求得: X2*=S2, y2*=600, f 2(S2)=42S2+3600k=1 时，f1(S1)maX0 X1 S10 y1 600 (S1maX0 X1 S10 y1 600 ( S1maX 0 X1 S1 0 y1 600 ( S145X1X1)45X1X1 )(42S1X1)40y140y13X1f2(S2)42(S1 y1 X1) 36002y1 3600)类似地求得: X1*=S1, y1*=600, f1(S1)=

21、45S1+4800=13800逆向追踪得各月最优购货量及销售量:X1*=S1=200y1*=600；X2*=S2=S1+ y1* X1*=600y2*=600；X3 =0y3 =600S3=600(S2+ y2 X2 )=0X4*=S4=(S3+ y3* X3*)=600y4*=0即1 月份销售 200件,进货 600件, 2月份销售 600件,进货 600件, 3月 份销售量及进货量均为 0, 4 月份销售 600 件,不进货,可获得最大总利润 13800。例 11 某鞋店销售一种雪地防潮鞋,以往的销售经历表明,此种鞋的销售季 节是从 10月1 日至3月31 日。下个销售季节各月的需求预测值

22、如表所示。表需求预测值（单位：双）月份101112123需求402030403020该鞋店的此种鞋完全从外部生产商进货， 进货价每双4美元。进货批量的基 本单位是箱，每箱10双。由于存贮空间的限制，每次进货不超过 5箱。对应不 同的订货批量，进价享受一定的数量折扣，具体数值如表所示。表数量折扣数值表进货批量1箱2箱3箱4箱5箱数量折扣4%5%10%20%25%假设需求是按一定速度均匀发生的， 订货不需时间，但订货只能在月初办理 一次，每次订货的采购费（与采购数量无关）为 10美元。月存贮费按每月月底 鞋的存量计，每双美元。由于订货不需时间，所以销售季节外的其他月份的存贮 量为“ 0”。试确定最

23、佳的进货方案，以使总的销售费用最小。解：阶段：将销售季节6个月中的每一个月作为一个阶段，即k 1,2,6 ；状态变量：第k阶段的状态变量Sk代表第k个月初鞋的存量；决策变量：决策变量Xk代表第k个月的采购批量；状态转移律：Sk 1 Sk xk dk （ dk是第k个月的需求量）；边界条件：S1 S70， f7（S7）0 ；阶段指标函数：rk（Sk，Xk）代表第k个月所发生的全部费用，即与采购数量无 关的采购费Ck、与采购数量成正比的购置费 Gk和存贮费Zk.其中：0, xk 0 Ck ； Gk px xk ； Z k 0-2（Sk xk d k ）10, Xk 0最优指标函数：最优指标函数具有

24、如下递推形式fk（Sk） min Ck G k Zk f k 1 （Sk 1）Xkmin Ck Gk 0.2（Sk xk dk） fk 1 （Sk Xk dk）Xk当k 6时（3月）:表 k 6时计算结果01020X620100f6 ( S6)86480当k 5时（2月）:表k 5时计算结果X501020304050X5f 5( S5 )020418816450164101721681424014220134136122301223086989008640505205050404当k 4时（1月）:表 k 4时计算结果X4S01020304050X4f4（S4）0302304403021028

25、228228630、4028220250262264252202503021223024423021810212401641922122101961700164501441741781761520144601261401441320126当k 3时（12月）:表k 3时计算结果01020304050X3f 3( S3 )04204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284当k 2时（11月）:表 k 2时计算结果 X201020304050X2f 2 ( S2 )0500504474468504681046247245444645240446当k 1时（10