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

例1 求解下列整数规划得最优解：解 （1）建立动态规划模型：阶段变量：将给每一个变量赋值瞧成一个阶段，划分为3个阶段，且阶段变量k=1,2,3、设状态变量表示从第阶段到第3阶段约束右端最大值，则设决策变量表示第阶段赋给变量得值、状态转移方程：阶段指标：基本方程；其中（1） 用逆序法求解：当时，而表示不超过得最大整数。因此，当时，；当时，可取0或1；当时，可取0，1，2，由此确定现将有关数据列入表4、1中表4、1中、012012345678910000000000006666661200000666661200000111112当时，有而。所以当时，；当时，；当时。由此确定。现将有关数据列入表4、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 用动态规划方法解下列非线性规划问题解： 解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。按问题得变量个数划分阶段，把它瞧作一个三阶段决策问题，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（舍）所以就是极大值点。由于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，最优指标函数fk（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*01234560123456000000010111812716411252021282272643031383274041485051600018276412800,111112表6、3 计算结果fx1s1x12 f2(s1x1)f1(s1)x1*012345660164427981612503601082由表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，x3*=3，f1(s1)=108。上面讨论得问题仅有一个约束条件。对具有多个约束条件得问题，同样可以用动态规划方法求解，但这时就是一个多维动态规划问题，解法上比较繁琐一些。例7 某公司打算在3个不同得地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量得销售点每月可得到得利润如表6、4所示。试问在各地区如何设置销售点可使每月总利润最大。表6、4 利润值地区销售点01234123000161210251714302116322217解： 如前所述，建立动态规划数学模型：将问题分为3个阶段，k=1，2，3；决策变量xk表示分配给第k个地区得销售点数；状态变量为sk表示分配给第k个至第3个地区得销售点总数；状态转移方程：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+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，每单位产品成本为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，当skdk时，至少应生产dksk，故xk得下限为max（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,60,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、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、52123*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，即第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=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*=600s3，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件，不进货，可获得最大总利润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%假设需求就是按一定速度均匀发生得，订货不需时间，但订货只能在月初办理一次，每次订货得采购费（与采购数量无关）为10美元。月存贮费按每月月底鞋得存量计，每双0、2美元。由于订货不需时间，所以销售季节外得其她月份得存贮量为“0”。试确定最佳得进货方案，以使总得销售费用最小。解：阶段：将销售季节6个月中得每一个月作为一个阶段，即；状态变量：第阶段得状态变量代表第个月初鞋得存量；决策变量：决策变量代表第个月得采购批量；状态转移律：（就是第个月得需求量）；边界条件：，；阶段指标函数：代表第个月所发生得全部费用，即与采购数量无关得采购费、与采购数量成正比得购置费与存贮费、其中：；最优指标函数：最优指标函数具有如下递推形式当时（3月）：表6、16 时计算结果S601020x620100f6（S6）86480当时（2月）：表6、17 时计算结果x5S501020304050020418816450164101721681424014220134136122301223086989008640505205050404当时（1月）：表6、18 时计算结果x4S4010203040500302304403021028228228630、4028220250262264252202503021223024423021810212401641922122101961700164501441741781761520144601261401441320126当时（12月）：表6、19 时计算结果x3S30102030405004204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284当时（11月）：表6、20 时计算结果x2S2010203040500500504474468504681046247245444645240446当时（10月）：表6、21 时计算结果x1S101020304050060660840606利用状态转移律，按上述计算得逆序可推算出最优策略：10月份采购4箱（40双），11月份采购5箱（50双），12月份不采购，1月份采购4箱（40双），2月份采购5箱（50双），3月份不采购；最小得销售费用为606美元。例13 某工厂生产三种产品，各产品重量与利润关系如表6、24所示，现将此三种产品运往市场销售，运输能力总重量不超过6吨，问如何安排运输使总利润最大？表6、24重量与利润关系表种类123单位重量（吨）234单位利润（元）80130180解： 设xi为装载第i种货物得件数，i=1，2，3，该问题数学模型为：按前述方法建立动态规划模型；k=3时，计算结果如表6、25所示。表6、25 k=3时计算结果fx3s3c3(x3)f3(s3)x3*010,1,2,34,5,600180018001k=2时，计算结果如表6、26所示。表6、26 k=2时计算结果fx2s2c2(x2)+ f3(s23 x2)f2(s2)x2*0120,1,234,560+00+00+1800+180130+0130+0130+0260+001301802600102k=1时，计算结果如表6、27所示。表6、27 k=1时计算结果fx1s1c1(x1)+ f2(s12 x1)f1(s1)x1*012360+26080+180160+0240+02600,1反向追踪得最优方案：x1*=0，x2*=2，x3*=0；最优方案：x1*=1，x2*=0，x3*=1最大总利润为260元。