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

1、例1 求解下列整数规划的最优解：解 （1）建立动态规划模型：阶段变量：将给每一个变量赋值看成一个阶段，划分为3个阶段，且阶段变量k=1,2,3.设状态变量表示从第阶段到第3阶段约束右端最大值，则设决策变量表示第阶段赋给变量的值.状态转移方程：阶段指标：基本方程；其中（1） 用逆序法求解：当时，而表示不超过的最大整数。因此，当时，；当时，可取0或1；当时，可取0，1，2，由此确定现将有关数据列入表4.1中表4.1中.012012345678910000000000006666661200000666661200000111112当时，有而。所以当时，；当时，；当时。由此确定。现将有关数据列入表4

2、.2中.表4.2 0120123456789100+00+00+00+00+00+60+60+60+60+60+125+05+05+05+05+05+65+610+010+010+00000566610111200001000210012305670510当时,有而故只能取0,1,2,3,由此确定。现将有关数据列入表4.3中。表 4.30123100+124+68+512+01324按计算顺序反推，由表4.3可知,当及例5 用动态规划方法解下列非线性规划问题解： 解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。按问题的变量个数划分阶段，把它看作一个三阶段决策问

3、题，k=1，2，3设状态变量为s1，s2，s3，s4并记s1c取问题中的变量x1，x2，x3为决策变量状态转移方程为：s3=x3s3+x2=s2s2+x1=s1c允许决策集合为：x3=s30x2s20x1s1各阶段指标函数为：v1（x1）=x1v2（x2）=x22v3（x3）=x3，各指标函数以乘积方式结合，最优指标函数fk（sk）表示从第k阶段初始状态sk出发到第3阶段所得到的最大值，则动态规划基本方程为：用逆序解法由后向前依次求解：k=3时，x3*=s3k=2时，令h2（s2，x2）=x22（s2x2）用经典解析法求极值点：解得：x2=0（舍）所以是极大值点。k=1时，令解得：x1=s1（

4、舍）所以是极大值点。由于s1未知，所以对s1再求极值，显然s1=c时，f1（s1）取得最大值反向追踪得各阶段最优决策及最优值：s1=c所以最优解为：例6 用动态规划方法解下列非线性规划问题解： 按变量个数将原问题分为三个阶段，阶段变量k=1，2，3；选择xk为决策变量；状态变量sk表示第k阶段至第3阶段决策变量之和；取小区间长度=1，小区间数目m=6/1=6，状态变量sk的取值点为：状态转移方程：sk+1=skxk；允许决策集合：Dk（sk）=xk|0xkskk=1，2，3xk，sk均在分割点上取值；阶段指标函数分别为：g1（x1）=x12g2（x2）=x2g3（x3）=x33，最优指标函数f

5、k（sk）表示从第k阶段状态sk出发到第3阶段所得到的最大值，动态规划的基本方程为：k=3时，s3及x3取值点较多，计算结果以表格形式给出，见表6.1-6.3所示。表6.1 计算结果fx3s3x3f3(s3)x3*01234560123456018276412521601827641252160123456表6.2 计算结果fx2s2x2 f3(s2x2)f2(s2)x2*0123456012345600000001×01×11×81×271×641×1252×02×12×82×272×

6、;643×03×13×83×274×04×14×85×05×16×00018276412800,111112表6.3 计算结果fx1s1x12 f2(s1x1)f1(s1)x1*0123456601×644×279×816×125×036×01082由表6.3知，x1*=2，s1=6，则s2= s1x1*=62=4，查表6.2得：x2*=1，则s3= s2x2*=41=3，查表6.1得：x3*=3，所以最优解为：x1*=2，x2*=1，

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

8、的销售点总数；状态转移方程：sk+1=skxk，其中s1=4；允许决策集合：Dk（sk）=xk|0xksk阶段指标函数：gk（xk）表示xk个销售点分配给第k个地区所获得的利润；最优指标函数fk（sk）表示将数量为sk的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：数值计算如表所示。表6.5 k=3时计算结果fx3s3g3（x3）f3(s3)x3*012340123401014161701014161701234表6.6 k=2时计算结果fx2s2g2(x2)+f3(s2x2)f2(s2)x2*012340123400+100+140+160+1712+012+1012+

9、1412+1617+017+1017+1421+021+1022+001222273101122,3表6.7 k=1时计算结果fx1s1g1(x1)+f2(s1x1)f1(s1)x1*0123440+3116+2725+2230+1232+0472所以最优解为：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1个地区设置2个销售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。例9 （生产库存问题）某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2，3，2，4单位，假设每批产品固定成本为3千元，若不生产为0，每

10、单位产品成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。解: 以每个时期作为一个阶段，该问题分为4个阶段，k=1，2，3，4；决策变量xk表示第k阶段生产的产品数；状态变量sk表示第k阶段初的库存量；以dk表示第k阶段的需求，则状态转移方程：sk+1=sk+xkdk；k=4，3，2，1由于期初及期末库存为0，所以s1=0，s5=0；允许决策集合Dk（sk）的确定：当skdk时，xk可以为0，当sk<dk时，至少应生产dksk，故xk的下限为m

11、ax（0，dksk）每期最大生产能力为6，xk最大不超过6，由于期末库存为0，xk还应小于本期至4期需求之和减去本期的库存量，所以xk的上限为min（，6），故有：Dk（sk）=xk| max（0，dksk）xkmin（，6）阶段指标函数rk（sk，xk）表示第k期的生产费用与存贮费用之和：最优指标函数fk（sk）表示第k期库存为sk到第4期末的生产与存贮最低费用，动态规划基本方程为：先求出各状态允许状态集合及允许决策集合，如表6.8所示。表6.8 状态允许状态集合及允许决策集合s10D1(s1)2,3,4,5,6s201234D2(s2)3,4,5,62,3,4,5,61,2,3,4,5,6

12、0,1,2,3,4,5,60,1,2,3,4,5s30123456D3(s3)2,3,4,5,61,2,3,4,50,1,2,3,40,1,2,30,1,20,10s401234D4(s4)43210由基本方程计算各阶段策略，结果如下表所示。表6.9 k=4时计算结果s4x4s5f5(s5)f4(s4)012344*3*2*1*0*76.565.5200000000007*6.5*6*5.5*2* 表6.10 k=3时计算结果s3x3s4= s3+ x32f4(s4)f3(s3)023456*567890123476.565.521212.51313.511*112345*4.55.56.57

13、.58.50123476.565.5211.51212.51310.5*20*1234156780123476.565.528*11.51212.51030*1231.55.56.57.512346.565.528*11.5129.540*1226723465.528*11.5950*12.56.5345.528*8.560*3425*表6.11 k=2时计算结果s2x2s3= s2+ x23f3(s3)f2(s2)0345*6678901231110.5881717.516*171234*565.56.57.58.59.5012341110.588816.51715.5*16.517.521

14、23*45656789100123451110.588881616.515*16171830*1234561.55.56.57.58.59.510.501234561110.58888512.5*1614.515.516.517.515.540*12345267891012345610.58888512.5*1415161715表6.12 k=1时计算结果s1x1s2= x12f2(s2)f1(s1)02345*656789012341615.51512.512.52121.52220.5*21.5逆向追踪可得：x1*=5，s2=3，x2*=0，s3=0，x3*=6，s4=4，x4*=0，即第

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

16、200，s5=0；决策变量： xk表示第k月售出的货物数量，yk表示第k月购进的货物数量；状态转移方程：sk+1=sk+ykxk；允许决策集合：0xksk，0yk600（skxk）；阶段指标函数为：pkxkckyk表示k月份的利润，其中pk为第k月份的单位销售价格，ck为第k月份的单位购货成本；最优指标函数fk（sk）表示第k月初库存为sk时从第k月至第4月末的最大利润，则动态规划基本方程为：k=4时，x4*=s4y4*=0k=3时，为求出使44s35x3+4y3最大的x3，y3，须求解线性规划问题：只有两个变量x3，y3，可用图解法也可用单纯形法求解，取得最优解，x3*=0，y3*=600s

17、3，f3（s3）=40s3+2400k=2时，类似地求得：x2*=s2，y2*=600，f2（s2）=42s2+3600k=1时，类似地求得：x1*=s1，y1*=600，f1（s1）=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件，不进货，可获得最大

18、总利润13800。例11某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季节是从10月1日至3月31日。下个销售季节各月的需求预测值如表6.14所示。 表6.14 需求预测值 (单位：双)月份101112123需求402030403020该鞋店的此种鞋完全从外部生产商进货，进货价每双4美元。进货批量的基本单位是箱，每箱10双。由于存贮空间的限制，每次进货不超过5箱。对应不同的订货批量，进价享受一定的数量折扣，具体数值如表6.15所示。表6.15 数量折扣数值表进货批量1箱2箱3箱4箱5箱数量折扣4%5%10%20%25%假设需求是按一定速度均匀发生的，订货不需时间，但订货只能在月初办

19、理一次，每次订货的采购费（与采购数量无关）为10美元。月存贮费按每月月底鞋的存量计，每双0.2美元。由于订货不需时间，所以销售季节外的其他月份的存贮量为“0”。试确定最佳的进货方案，以使总的销售费用最小。解：阶段：将销售季节6个月中的每一个月作为一个阶段，即；状态变量：第阶段的状态变量代表第个月初鞋的存量；决策变量：决策变量代表第个月的采购批量；状态转移律：（是第个月的需求量）；边界条件：，；阶段指标函数：代表第个月所发生的全部费用，即与采购数量无关的采购费、与采购数量成正比的购置费和存贮费.其中：；最优指标函数：最优指标函数具有如下递推形式当时（3月）：表6.16 时计算结果S601020x

20、620100f6（S6）86480当时（2月）：表6.17 时计算结果x5S501020304050020418816450164101721681424014220134136122301223086989008640505205050404当时（1月）：表6.18 时计算结果x4S4010203040500302304403021028228228630、4028220250262264252202503021223024423021810212401641922122101961700164501441741781761520144601261401441320126当时（12月）：表6.19 时计算结果x3S30102030405004204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284当时（11月）：表6.20 时计算结果x2S201020304050050050447446850468104624724544464