2022年动态规划[参 .pdf

第 7 章动态规划1、某公司打算向它的三个营业区增设6 个销售店，每个营业区至少增设1 个。各营业区每年增加的利润与增设的销售店个数有关，具体关系如表1 所示。试规划各营业区应增设销售店的个数，以使公司总利润增加额最大。表 1 增设销售店个数营业区 A营业区 B营业区 C1 100（万元）120（万元）150（万元）2 160 150 165 3 190 170 175 4 200 180 190 解：阶段：将每个营业区作为一个阶段，即k=1,2,3 状态变量：第k 阶段的状态变量kS代表从第 k 各营业区到第3 个营业区的店数决策变量：Kx代表第 k 个营业区的销售店数状态转移律：1KKKSSx边界条件：1S=6 4S=0 允许决策集合0KKKKKDSxxS和递推关系式)()(max)(10kkkkkSxkkxSfxgSfkk)1,2,3(k0)(44Sf当3k时：)(max0)(max)(330330333333xgxgSfSxSx于是有下表2，表中3x表示第三个阶段的最优决策。表 2（单位：万元）3S0 1 2 3 4 3x0 1 2 3 4)(33Sf0 150 165 175 190 当2k时：名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 12 页 -)()(max)(2232202222xSfxgSfSx于是有表 3。表 3（单位：万元）x2S2g2（x2）+f3（s2-x2）)(22Sf2x0 1 2 3 4 0 0+0 0 0 1 0+150 120+0 150 1 2 0+165 120+150 150+0 150 1 3 0+175 120+165 150+150 170+0 300 2 4 0+190 120+175 150+165 170+150 180+0 320 3 5 0+190 120+190 150+175 170+165 180+150 335 3 当1k时：)()(max)(1121101111xSfxgSfSx于是有表 4。表 4 x1S1g1（x1）+f2（s1 x1）)(11Sf1x0 1 2 3 4 6 0+345 100+375 160+320 190+300 200+270 490 3 故最优分配方案为：A 区建 3 个销售店，B 区建 2个销售店，C 区建 1 个销售店，总利润为 490 万元。2、某工厂有100 台机器，拟分4 个周期使用，在每一周期有两种生产任务，据经验把机器投入第一种生产任务，则在一个周期中将有六分之一的机器报废，投入第二种生产任务，则有十分之一的机器报废。如果投入第一种生产任务每台机器可收益1 万元，投入第二种生产任务每台机器可收益0.5 万元。问怎样分配机器在4 个周期内的使用才能使总收益最大？解：阶段：将每个周期作为一个阶段，即k=1,2,3，4 状态变量：第k 阶段的状态变量kS代表第 k 个周期初拥有的完好机器数决策变量：决策变量kx为第k周期分配与第一种任务的机器数量，于是kkxS该周期分配在第二种任务的机器数量。状态转移律：15/60.9()0.91/15KKKKKKSSSxSx允许决策集合0KKKKKDSxxS令最优函数：1max0.50.50.91/15KKKkKKKkKKxDSfSSxfSx名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 12 页 -边界条件：55fS=0 当 k=4 时：444444550()max 0.50.5()xSfSSxfS44440max 0.50.5xSSx因)(44Sf是关于4x的单调递增函数，故取44Sx，相应有444()fSS；依次类推，可求得：当3k时：33Sx，333()11/6fSS当2k时：22xS，222()91/36fSS当1k时：11xS，111(100)671/216310.65fSS计算表明，每一期都将全部机器投入第一种任务中，其中1S100，2S=83，3S=69，4S=58 3、某公司生产一种产品，估计该产品在未来四个月的销售量分别为300、400、350 和 250件。生产该产品每批的固定费用为600 元，每件的变动费用为5 元，存储费用为每件每月2元。假定第一个月月初的库存为100 件，第四个月月底的存货为50 件。试求该公司在这四个月内的最优生产计划。解：阶段：将今后4 个月中的每一个月作为一个阶段，即1,2,3,4k；状态变量：第k阶段的状态变量kS代表第k个月初产品存储量；决策变量：决策变量kx代表第k个月的生产量；状态转移律：kkkkdxSS1（kd是第k个月的销售量）；边界条件：1100S，550S，55()0fS；固定生产费用0,k0C600,k0和存贮费122()kkkkkZSSxd变动生产费用k G5最优指标函数：最优指标函数具有如下递推形式名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 12 页 -11()min()kkkkkkkxfSCGZfS1()min52()kkkkkkkkkkkkxfSCxSxdfSxd当4k时：表 1 S40 50 100 150 200 250 300 X4300 250 200 150 100 50 0 F4（S4）2200 1950 1700 1450 1200 950 100 当 K=3 时：3333333344()min52xfSCxSxdfS表 2 x3 S30 50 100 150 200 250 300 350 400 450 3x)(33Sf0 4550 4650 4750 350 4550 50 4300 4400 4500 4600 300 4300 100 4050 4150 4250 4350 4450 250 4050 150 3800 3900 4000 4100 4200 4300 200 3800 200 3550 3650 3750 3850 3950 4050 3550 150，450 3550 250 3300 3400 3500 3600 3700 3800 3300 100，400 3300 300 3050 3150 3250 3350 3450 3550 3050 50，350 3050 350 2200 2900 3000 3100 3200 3300 2800 0 2200 400 2050 2250 2850 2950 3050 2550 2050 当 K=2 时：表 3 S30 50 100 150 200 250 300 350 400 450 2x)(22Sf0 7150 7250 400 7150 50 6900 7000 7100 350 6900 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 12 页 -100 6650 6750 6850 6950 300 6650 150 6400 6500 6600 6700 6800 250 6400 200 6150 6250 6350 6450 6550 6650 200 6150 当 K=1 时:表 4 x1 S10 50 100 150 200 250 300 350 400 450 1x)(11Sf100 8750 8850 8950 9050 9150 9250 200 8750 利用状态转移律，按上述计算的逆序可推算出最优策略为：第1 个月生产 200 件，第 2个月生产 400 件，第 3 个月生产 350 件，最后一个月生产300 件。4、用动态规划求解下述规划问题（1）51maxiimz（2）22112maxxxxz1051iim6322221xx0im)5,4,3,2,1(i0,21xx解：（1）解：阶段：将问题的变量数作为阶段，即3,2,1k，4，5；决策变量：决策变量kx；状态变量：状态变量kS代表第k阶段的约束右端项，即从kx到5x占有的份额；状态转移律：kkkxSS1；边界条件：110S，66()1fS；允许决策集合：kkSx0当 k=5 时：555555555665500()max()max|xSxSxSfSxfSxS当 k=4 时：44444445544400()max()max()xSxSfSxfSxSx名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 12 页 -设444()hx Sx，于是令44420dhdxSx可得44/2xS又因2242d hdx0，所以：44/2xS是44()fS的极大值点于是：1442214444()|xSfSS当 k=3 时：333323334433300()max()max()/4xSxSfSxfSxSx3323/31/27|xSS当 k=2 时：222232223322200()max()max()/27xSxSfSxfSxSx122441222256()|xSfSS当 k=1 时：1111411112211125600()max()max()xSxSfSxfSxSx同理：1115411112114(10)32|52565xSfSSS2111028SSx12242xS322826SSx33/32xS3434SSx*44/22xS*544SSx=2*552xS故最优解为：(2,2,2,2,2)TX最优值为：32z（2）解：阶段：将问题的变量数作为阶段，即k=1,2；决策变量：决策变量kx；状态变量：状态变量kS代表第k阶段的约束右端项;状态转移律：22112SSx；名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 12 页 -边界条件：16S，33()0fS；阶段指标：211111,2VS xxx2222,VSxx基本方程：110()max,()kkkkkkkkkkSxafSVSxfS1,2,3k其中：12a23a当 k=2 时：22222222233200()max()max SSxxaafSxfSx关于2x的单调增函数，故*22222()33SSfSx当 k=1 时：12211112202()max 2()SxfSxxfS12221121102max 2(2)SxxxfSx=12221111022max 23SxSxxx5、某公司经销A、B、C 三种产品，由于运输能力的限制，该公司每月只能把6 吨的产品运回公司进行销售。产品A、B、C 的单件重量分别为20、30 和 40 公斤；进货的批量分别为50、40 和 20 件；单位产品利润分别为80、130 和 150 元。试确定该公司每月A、B、C 三种产品的最佳进货量，以使总利润最大。6、某公司需要在近四周内采购一批原料，估计在未来四周内的价格可能有60、80、90 和100 四种状态，各状态发生的概率分别为0.2、0.3、0.3 和 0.2，试求各周应以什么样的价格购入原料，才能使采购价格期望值最小。解：阶段：将每一周作为一个阶段，即4,3,2,1k；决策变量：决策变量kx代表第k周是否决定采购，1kx代表第k周决定采购，0kx名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 12 页 -代表第k周决定等待；状态变量：状态变量kS代表第k周原材料的市场价格；中间变量：ky代表第k周决定等待，而在以后采取最佳子策略时的采购价格期望值；最优指标函数：是否采购决定于目前市场价格与等待价格期望值的相对大小，如果前者大于后者，应决定等待；如果前者小于后者，则应决定采购。于是：,min)(kkkkySSf边界条件：对于第4 周，因为没有继续等待的余地，所以：444)(SSf即：44(60)60fS、80)80(44Sf44(90)90fS44(100)100fS111111()0.2(60)0.3(80)0.3(90)0.2(100)kkkkkkkyE fSffff1;()0;()kkkkkkkfSSxfSy当4k时：只有采购一种选择44(60)60fS、80)80(44Sf44(90)90fS44(100)100fS当3k时：30.2 600.3 800.3 900.2 10083y于是：33333333360;6080;80()min,min,8383;9083;100SSfSSySSS即第三周的最佳决策为：3331;60,800;90,100SxS当2k时：20.2600.3 800.3 830.2 8377.5y于是：22222222260;6077.5;80()min,min,77.577.5;9077.5;100SSfSSySSS名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 12 页 -即第二周的最佳决策为：2221;600;80,90,100SxS当1k时：10.2 600.3 77.50.3 77.50.2 77.574y于是：22111112260;6074;80()min,min,7474;9074;100SSfSSySSS即第一周的最佳决策为：1111;600;80,90,100SxS由以上计算可知，最佳的采购策略为：第一周,第二周只有价格是60 时才采购，否则就等待；第三周只要价格不超过80 就要采购，否则继续等待；如果已经等待到了第四周，那么无论什么价格都只有采购，别无选择。7、某工厂生产一种精密仪器，今后四个月的订单分别为2、3、4 台。已知生产费用C（万元）同生产量x 的关系为：2061604292466xxxxCxxx当当当当又若生产出来的产品当月销售不出去，其库存费用为每台每月0.2 万元。设在第一个月月初及第四个月月末该产品无库存，试确定在满足需求的条件下，使该工厂生产与库存总费用最小的生产方案。解：阶段：将今后4 个月中的每一个月作为一个阶段，即1,2,3,4k；状态变量：第k阶段的状态变量kS代表第k个月存储量；决策变量：决策变量kx代表第k个月的生产量；状态转移律：kkkkdxSS1（kd是第k个月的销售量）；名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 12 页 -边界条件：150SS，55()0fS；生产费用kC和存贮费kZ)(2.0kkkkdxSZ最优指标函数：最优指标函数具有如下递推形式11()min()kkkkkkkxfSCZfS1()min0.2()kkkkkkkkkkkxfSCSxdfSxd当4k时：表 1 S40 1 2 3 4 X44 3 2 1 0 F4（S4）16 135 10 55 0 当 K=3 时：表 2 x5 S50 1 2 3 4 5 6 3x)(33Sf0 35 34.7 6 34.7 1 32 31.7 31.4 6 31.4 2 29.5 29.7 29.4 27.1 6 27.1 3 26 27.2 26.4 25.1 21.8 6 21.8 4 21.5 23.7 23.9 22.1 19.8 22 5 19.8 5 16 19.2 20.4 19.6 16.8 20 0 16 6 13.7 15.9 16.1 14.3 0 13.7 7 10.4 11.6 10.8 0 10.4 当 K=2 时：表 3 x3 S30 1 2 3 4 5 6 2x)(22Sf0 48.2 47.6 46.5 43.4 6 43.4 1 44.7 45.1 43.5 41.4 41.6 5 41.4 2 40.2 41.6 41 38.4 39.6 38 6 38 3 34.7 37.1 37.5 35.9 36.6 36 35.9 0 34.7 4 31.6 33 32.4 34.1 33 33.9 32.8 0 31.6 当 K=1 时:名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 12 页 -表 4 x1 S10 1 2 3 4 5 1x)(11Sf0 53.4 55.1 54.4 53.4 2,6 53.4 利用状态转移律，按上述计算的逆序可推算出最优策略有两种：（1）第1 个月生产2台，第 2 个月和第 3 个月生产 6 台，最后一个月不生产;(2)第 1 个月生产6，第 2 个月不生产，第 3 个月生产6 台，最后一个月生产2 台。总费用为53.4 万元。8、某研发部（乙方）拟承担一种新产品的研发任务，甲方提供研发经费10 万元。为适应市场竞争的需要，合同要求乙方应在三个月内向甲方交付一台合格样品，否则乙方将退还甲方10 万元的研发费。据估计，研发时投产1 台即合格的概率为0.35，投产一批的准备费用为0.25 万元，每台的研发费用为1 万元。若投产一批而未得到合格样品，可再投产一批，但每批的研发周期是一个月。试分析该研发部应否接受此研发任务，如果接受应该采用怎样的研发策略。解：阶段：将每个试制周期（1 个月）作为一个阶段，即3,2,1k；决策变量：决策变量kx代表第k阶段投产试制的台数；状态变量：状态变量kS代表第k阶段初是否已获得合格样品，尚无合格样品时1kS，已获得合格样品时0kS；允许决策集合：0;01;,3,2,1)(kkkkSSSD状态转移律：1(1)(0.65)kxkP S，1(0)1(0.65)kxkP S；边界条件：11S，44(1)10fS，0)0(44Sf，；阶段指标函数：0.2;0()0;0kkkkkxxCxx最优指标函数：0)0(kkSf1111()(1)min()(0.65)(1)1(0.65)(0)kkkkkxxkkkkkkkkxDSfSCxfSfS211()min()(0.65)(1)kkkxkkkkxDSCxfS当3k时：0)0(33Sf名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 12 页 -3333333344()(1)min()(0.65)(1)xxDSfSCxfS表 1 x3 S30 1 2 3 4 5 3x)(33Sf0 0 0 1 10 7.75 6.48 6 6.04 4.88 3 6 当2k时：0)0(22Sf2222222233()(1)min()(0.65)(1)xxDSfSCxfS表 2 x2 S20 1 2 3 2x)(22Sf0 0 0 1 6 5.15 4.78 4.9 2 4.78 当1k时：1111111122()(1)min()(0.65)(1)xxDSfSCxfS表 3 x1 S10 1 2 3 1x)(11Sf1 4.78 4.36 4.27 4.56 2 4.27 即该公司的最佳试制计划为：第一个月初投产试制2 台；如果在第二个月初无合格样品出现，再投产试制2；如果在第三个月初仍然无合格样品出现，再投产试制3。按此最佳试制方案最小期望总费用是4.27 元。名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 12 页 -