第8章 动态规划

第8章动态规划8.1在设备负荷分配问题中，n=10，a=0.7，b=0.85，g=15，h=10，期初有设备1000台。试利用公式(8.7)确定10期的设备最优负荷方案。【解】由公式100()ntntiiiighaagba得(g-h)/g(b-a)＝0.2222，a0＋a1＋a2＝1+0.7＋0.49＝2.19＜2.222＜a0+a1＋a2＋a3＝2.533，n－t－1＝2，t=7，则1~6年低负荷运行，7~10年为高负荷运行。各年年初投入设备数如下表。年份12345678910设备台数1000850723614522444377264184.81298.2如图8－4，求A到F的最短路线及最短距离。【解】A到F的最短距离为13；最短路线A→B2→C3→D2→E2→F及A→C2→D2→E2→F8.3求解下列非线性规划(1)123123max0,1,2,3jZxxxxxxCxj(2)22123123123min,,0ZxxxxxxCxxx（3）2123123123max2310,,0Zxxxxxxxxx(4)123123max42100,1,2,3jZxxxxxxxj(5)123123max24100,1,2,3jZxxxxxxxj（6）221123123123max228,,0Zxxxxxxxxxx【解】（1）设s3=x3,s3+x2=s2，s2+x1=s1=C则有x3=s3，0≤x2≤s2，0≤x1≤s1=C用逆推法，从后向前依次有k＝3，333333()max()xsfsxs及最优解x3*=s3k＝2，22222222233222222000()max[()max[()]max(,)xsxsxsfsxfxxsxhsx由222222120,2hsxxsx则＝222220,hx＝－故2212xs为极大值点。所以22222222111()244fssss及最优解x2*=s2k=1时，1111112111221111110001()max[()]max()max(,)4xsxsxsfsxfsxsxhsx，由221111111(43)04hssxxx，得*1113xs故23111111111()()12327fsssss已知知x1+x2+x3=C，因而按计算的顺序推算，可得各阶段的最优决策和最优解如下*113xC，311()27fCc由s2=s1－x1*=2C/3，*222211,()39xCfsC由s3=s2－x2*=C/3，*33311,()33xCfsC最优解为：31111(,,);33327TXCCCzC【解】（2）设s3=x3,s3+x2=s2，s2+x1=s1=C则有x3=s3，0≤x2≤s2，0≤x1≤s1=C用逆推法，从后向前依次有k＝3，2333333()min()xsfsxs及最优解x3*=s3k＝2，22222222223322222202200()min[()min[()]min(,)xsxsxsfsxfxxsxhsx由2222221420,2hsxxsx则＝2222xh=40,故x2=221s为极小值点。因而有2*2222211(),22fssxsk＝1时，1111211111111001()min[()min(,)2xsxsfsxsxhsx由111110hsxx知*1111111,()2xsfss得到最优解1(1,1/2,1/2);2TXCzC【解】(3)设s3=x3,s3+x2=s2，s2+x1=s1=10则有x3=s3，0≤x2≤s2，0≤x1≤s1=10用逆推法，从后向前依次有k＝3时，3323333()max()xsfsxs及最优解x3=s3k＝2时，222222222222200()max[3()]max(,)xsxsfsxsxhsx222222332202hsxxsx时而222222320,2hxsx故不是一个极大值点。讨论端点：当x2=0时2222()fss＝,x2=s2时222()3fss如果s23时,2222()fssk＝1时，111121111111100()max[2()]max(,)xsxsfsxsxhsx11111122201hsxxsx时21122120,1hxsx故不是一个极大值点同理有,x1=0,f1（s1）=s12=100，x1=s1,f1（s1）=2s1=20(舍去)得到最优解(0,0,10);100Xz【解】(4)设s3=x3,2s3+4x2=s2，s2+x1=s1=10则有x3=s3，0≤x2≤s2/4，0≤x1≤s1=10用逆推法，从后向前依次有k＝1，333333()max()xsfsxs及最优解x3*=s3k＝2，22222222222204041()max[(2)max(,)2xsxsfsxsxhsx由22xh=21s2-4x2=0,则x2=81s2222240hx,故2218xs为极大值点。则2222()32sfs及最优解x2*=s2/8k＝1，1111211111111001()max[()]max(,)32xsxsfsxsxhsx22*1111111111(43)0,323hssxxxsx，故31111()216fss得到最优解(10/3,5/6,5/3);125/27TXz【解】(5)按问题中变量的个数分为三个阶段s1，s2，s3，且s3≤10，x1，x2，x3为各阶段的决策变量，各阶段指标函数相乘。设s1=2x1,s1+4x2=s2，s2+x3=s3≤10，则有x1=s1/2，0≤x2≤s2/4，0≤x3≤s3=10用顺推法，从前向后依次有k＝1，111111/2()max()2xssfsx及最优化解x1*=s1/2k＝2，2222222222220/40/41()max[(4)max(,)2xsxsfsxsxhsx由22221402hsxx,则*2218xs222240hx,故2218xs为极大值点。则32221()32fssk＝3，3333233333333001()max[()]max(,)32xsxsfsxsxhsx由22*3333333311(43)0,323hssxxxsx故33331()216fss，由于s3≤10，则s3=10时取最大值，x3＝10/3，s2=s3－x3＝20/3，x2＝5/6，s1=s2－4x2＝10/3，x1＝5/3得到最优解(5/3,5/6,10/3);125/27TXz【解】（6）设s1=x1,s1+x2=s2，s2+x3=s3=8k＝1，1122111111()max(2)2xsfsxxss及最优化解x1*=s1k＝2，222222222222222200()max[2()2()]max(,)xsxsfsxsxsxhsx2222622,hxsx222260hxx2*=0时，f2（s2）=s22+2s2,x2*=s2时，f2（s2）=2s22故2222222()max{2,2}fssssk＝3，①当x2*=0时，23333333333033033()max[()2()]max(,)xsxsfsxsxsxhsx同样得x3*=0时，f3（s3）=s32+2s3x3*=s3时，f3（s3）=s3所以，f3（s3）=s32+2s3=80②当x2*=s2时，f3（s3）=330maxsx[x3+2（s3-x3）2]同样得x3*=0时，f3（s3）=2s32=128x3*=s3时，f3（s3）=s3=8所以，f3（s3）=2s32=128最优解为(0,8,0);128Xz8.4用动态规划求解下列线性规划问题。12121212max242624,0Zxxxxxxxx【解】设s2=x2,s2+2x1=s1≤6则有0≤x2=s2≤4，0≤x1≤s1/2用逆推法，从后向前依次有222()4fss及最优解x2*=s2111111122110/20/2()max[2()]max[46]xsxsfsxfssx由s2=s1－2x1≤4，s1≤6，取s1＝6，111110/2()max[246]xsfsx又1≤x1≤2，取x1＝1，11()18fs最优解(1,4);18TXz8.510吨集装箱最多只能装9吨，现有3种货物供装载，每种货物的单位重量及相应单位价值如表8.24所示。应该如何装载货物使总价值最大。表8.24货物编号123单位加工时间234单位价值345【解】设装载第I种货物的件数为xi（i=1,2,3）则问题可表为：123123123max3452349,,0zxxxxxxxxx且为整数利用背包问题的前向动态规划计算，建立动态规划模型。由于决策变量离散型值，所以可用列表法求解。当R=1时，121210/2()max(3)xsfsx。计算结果如下：s20123456789f1（s2）003366991212x1*0011223344当R=2时，f2（s3）=4/210maxsx[4x2+f1（s3-3x2）]计算结果如下：s30123456789x20000101010120120120123C2+f2003346467978910812101112131112f2（s3）0034679101213x2*0001010101当R=3时，f3（9）=230maxx[5x3+f2（9-4x3）]（x3为整数）=220maxx[f2（9），5+f2（5），10+f2（1）]=max[13，12，10]=138.6有一辆货车载重量为10吨，用来装载货物A、B时成本分别为5元/吨和4元/吨。现在已知每吨货物的运价与该货物的重量有如下线性关系：A：P1=10-2x1，B：P2=12-3x2其中x1、x2分别为货物A、B的重量。如果要求货物满载，A和B各装载多少，才能使总利润最大【解】A：P1=15-x1，B：P2=18-2x2由题意可得各种货物利润函数为21111112222222()(155)10()(1824)142gxxxxxgxxxxx原问题的数学模型归结为2211221212max(10)(142)10,0zxxxxxxxx最优解：x1=6，x2=4；z＝488.7现有一面粉加工厂，每星期上五天班。生产成本和需求量见表8-25。表8-25星期(k)12345需求量(dk)单位：袋1020253030每袋生产成本(ck)8691210面粉加工没有生产准备成本，每袋面粉的存储费为hk＝0.5元/袋，按天交货，分别比较下列两种方案的最优性，求成本最小的方案。（1）星期一早上和星期五晚的存储量为零，不允许缺货，仓库容量为S=40袋；（2）其它条件不变，星期一初存量为8。【解】动态规划求解过程如下：阶段k：日期，k=1,2,…,6状态变量sk：第k天早上（发货以前）的冷库存量决策变量xk：第k天的生产量状态转移方程：sk+1=sk+xk－dk；决策允许集合：400,0)(kkkkkkkdxsxxsD阶段指标：vk(sk，xk)=ckxk+0.5sk终端条件：f6(s6)=0,s6=0；递推方程：)(),(min)(),(min)(1)(11)(kkkkkkkkskDkxkkkkkkskD