运筹学习题解答(chap8)公开课教案课件.doc

《运筹学习题解答(chap8)公开课教案课件.doc》由会员分享，可在线阅读，更多相关《运筹学习题解答(chap8)公开课教案课件.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章 动态规划一、用逆序法求解下列问题1、P237, 8.1 有600万元资金用于三个工厂的更新改造，投资数以百万元为单位取整数，已知工厂II的投资不超过300万元，工厂I和III的投资均不少于100万元，又不超过400万元，已知各工厂投资更新改造后，每年可增加的效益如下表，试用动态规划方法确定投资分配方案，使预期效益为最大。(单位：万元)工厂投资0100200300400I-361114II051012-III-481115解：该问题可分为3个阶段，分别为分配资金给、三个厂。设k为阶段变量，第k个阶段给第k个厂分配设备；是第k个阶段的状态变量，表示可分配给第k个厂到第3个厂的设备数；是第k

2、个阶段的决策变量，表示分配给第k个厂的设备数； 状态转移方程：，并且。指标函数： 下面按照逆序解法求解。第三阶段：万，, X3S3100200300400100441002004882003004811113004004811151540050048111515400 第二阶段：万。 X2S201002003002000+85+4102003000+115+810+4142004000+155+1110+812+4182005000+155+1510+1112+821200 第1阶段：万。 X1S11002003004006003+216+1811+1414+1025300 按照与计算相反的顺

3、序可推知有一个最优解：，最大利润为25万。2、P237, 8.2 如图，要铺设一条从A到E的输油管线，箭线旁数字为各点间相应距离（km）一个运筹学小组正研究讨论线路选择，使得总距离为最短。甲提出用求最短距离的Dijkstra 算法求解；乙认为这个问题也可用动态规划方法求解，但丙丁认为从A到E经B1、D1的线路，与经B2、C1、D2的线路阶段数不等，故动态规划行不通；丙提出建立整数规划模型求解，甲乙对此持怀疑的态度；丁设想用破圈法或避圈法找出图中最小部分树，树图中A-E的唯一链即为A至E铺设管道的最佳选择，对此甲和乙不同意。因此除对甲的意见一致外，其余均有分歧。请说明乙丙丁的方法是否可行，并说明

4、依据。3、P238, 8.3 某公司根据市场调查，今后四个时期的产品需求量如下表所示。据此公司确定每个时期的生产数量，以满足上述要求。已知每件生产费用C（万元）同生产数量的关系：又若生产出来的产品当期卖不出去，其库存费用每件每期0.5万元。设在第一时期初及第四时期末均无库存，试决定在满足市场需求条件下，使该公司生产加库存总费用最小的方案。解：该问题可分为4个阶段，分别为四个时期的生产阶段，设k为阶段变量， k=1,2,3,4。；是第k个阶段的状态变量，表示第k个阶段到第4个阶段的需求量；是第k个阶段的决策变量，表示第k个阶段的产量； 状态转移方程：，并且。指标函数： 下面按照逆序解法求解。第三

5、阶段：万，,4、P238,8.4 某项工程有3个设计方案。据现有条件，这些方案不能按期完成的概率分别为0.40,0.60,0.80，即三个方案均完不成的概率为，为使这三个方案中至少完成一个的概率尽可能大，决定追加2万元投资。当使用追加投资后，上述方案完不成的概率见下表。问应如何分配追加投资，使其中至少有一个方案完成的概率为最大？追加投资（万元）各方案完不成的概率12300.400.600.8010.200.400.5020.150.200.30解：设给第k个方案分配资金为第k个阶段；是第k个阶段的状态变量，表示可分配给第k个到第3个阶段的投资额；是第k个阶段的决策变量，表示分配给第k个阶段的投

6、资额；状态转移方程：，并且。阶段指标函数：，示第k阶段投资后，本方案完成的概率；过程指标函数：优化方程：k-3阶段至少有一个完成的最大概率 下面按照逆序解法求解。第三阶段：万，, X3S3至少完成一个概率01200.20.2010.20.50.5120.20.50.70.72 第二阶段：万。 X2S201200.520.52010.70.680.7020.820.80.840.842 第1阶段：万。 X1S101220.9360.940.9280.941 按照与计算相反的顺序可推知有一个最优解：，最大完成概率为0.94。状态转移方程：，并且。指标函数： 下面按照逆序解法求解。第三阶段：万，,4

7、、P238,8.4 某项工程有3个设计方案。据现有条件，这些方案不能按期完成的概率分别为0.40,0.60,0.80，即三个方案均完不成的概率为，为使这三个方案中至少完成一个的概率尽可能大，决定追加2万元投资。当使用追加投资后，上述方案完不成的概率见下表。问应如何分配追加投资，使其中至少有一个方案完成的概率为最大？追加投资（万元）各方案完不成的概率12300.400.600.8010.200.400.5020.150.200.30解：设给第k个方案分配资金为第k个阶段；是第k个阶段的状态变量，表示可分配给第k个到第3个阶段的投资额；是第k个阶段的决策变量，表示分配给第k个阶段的投资额；状态转移方程：，并且。阶段指标函数：，示第k阶段投资后，本方案完成的概率；过程指标函数：优化方程：k-3阶段至少有一个完成的最大概率 下面按照逆序解法求解。第三阶段：万，, X3S3至少完成一个概率01200.20.2010.20.50.5120.20.50.70.72 第二阶段：万。 X2S201200.520.52010.70.680.7020.820.80.840.842 第1阶段：万。 X1S101220.9360.940.9280.941 按照与计算相反的顺序可推知有一个最优解：，最大完成概率为0.94。