《运筹学》 第五章习题及 答案

1、运筹学第五章习题 1思考题 （1）试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。 （2）动态规划的阶段如何划分？ （3）试述用动态规划求解最短路问题的方法和步骤。 （4）试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值 函 数、边界函数等概念。 （5）试述建立动态规划模型的基本方法。 （6）试述动态规划方法的基本思想、动态规划的基本方程的结构及正确写出动 态 规划基本方程的关键步骤。2判断下列说法是否正确 （1）动态规划分为线性动态规划和非线性动态规划。（2）动态规划只是用来解决和时间有关的问题。（3）对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优

2、解。（4）在用动态规划的解题时，定义状态时应保证各个阶段中所做的决策的相 互独立性。 （5）在动态规划模型中，问题的阶段等于问题的子问题的数目。（6）动态规划计算中的“维数障碍”，主要是由于问题中阶段数的急剧增加 而引起的。45AB1B2B3C1C2C3D1D2E3541633442942675123计算下图所示的从 A 到 E 的最短路问题1434113222433553A3B1B2B3C1C2D1D2D3E3154计算下图所示的从 A 到 E 的最短路问题5计算从 A 到 B、C、D 的最短路线。已知各线段的长度如下图所示。13ABCD107848712658373246589101015

3、7E1E2E3F1F2F3G1G2G330501040606030B1油田厂B2B3C1C2C3D1D22030702040205030204050 6设某油田要向一炼油厂用管道供应油料，管道铺设途中要经过八个城镇，各 城镇间的路程如下图所示，选择怎样的路线铺设，才使总路程最短？3030 7用动态规划求解下列各题 （1）； ； （2） ； 8某人外出旅游，需将3种物品装入背包，但背包重量有限制，总重量不超过10千克。物品重量及其价值等数据见下表。试问每种物品装多少件，使整个背包的价值最大？ 物品编号123单位重量（千克）345单位价值456物品件数9某人外出旅游，需将五件物品装入背包，但包裹重

4、量有限制，总质量不超过13 千克。物品重量及其价值的关系如表所示。试问如何装这些物品，使整个背包 价值最大？物 品重量（千克）价值（元）A79B54C43D32E10.510有一辆最大装载量为17吨的货车，现有4种货物要装运，每种货物的单位重 量和相应单位价值如下表所示，应如何装载可使总价值最大？ 货 物 编 号1234单位重量（吨）5436单位价值（千元）7535811某工厂根据市场需求预测今后4个月的交货任务如下表所示，表中数字为月 底交货量，该厂的生产能力为每月600件，该厂仓库的存货能力为300件，又 每生产100件产品的费用为1000元。在进行生产的月份，工厂要固定支出3000 元开

5、工费。仓库保管费用为每100件500元。假定开始时和计划期末库存量都 是零。试问应在各个月各生产多少件货物，才能既满足交货任务又使总费用最 少？ 月 份1234需求（百件）232412某集团公司有4个单位的资金，要向下属三个子公司投资。由于条件不同，使用资金的效益也不同。具体数据见下表。为使此集团获得最大收益，试问每个子公司各投资多少单位资金？（表内数字为投资所获收益） 资金子公司0123410145620235730346613某公司有500台完好的机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，每台机器每年可收入50万元，机器损坏率为70% ，在低负荷下进行生产时，每台机器每

6、年可收入30万元，机器损坏率为30% ，估计五年后有新的机器出现，旧的机器将全部淘汰。要求制定一个五年计划，在每年开始时，决定如何分配完好的机器在两种不同的负荷下生产的数量，使在五年内总产值最高。并计算每年初完好机器台数。14某工厂购近100台设备，准备生产A、B两种产品。如果生产产品A，每台设备每年可收入10万元，但机器损坏率为65 %，如果生产产品B ，每台设备每年可收入7万元，机器损坏率为40% ，三年后的设备完好情况不计，试问应如何安排每年的生产，使三年的总收入最大？又如果要求三年后有20台机器是完好的，则应如何安排每年的生产，使三年的总收入最大？15某工厂有5个单位的能源要供给3个车

7、间，供给方案及各车间获得能源后所 产生的效益在下表给出，问应如何分配这些能源，使工厂的总收益最大？ 能 源车间012341056208912303注：表中的“”表示没有此方案。运筹学第五章习题解答2解：（1）X（2）X（3）X（4） （5）（6）X 。3解：最短路线为，最短路程为8。4解：最短路线为，最短路程为8。5解：分别求出各最短路线和最短路程为： ，最短路程为16 ； ，或 ，最短路程为21 ； ，最短路程为20 。6解：最短铺设路线有两条，分别是： ，最短路程为110。 ，最短路程为110。7解：(1) 最优解为：； （2）最优解为：。8解：最优解装第一种物品2件，第二种物品1件，不装

8、第三种物品，整个背 包的最大价值为13。9解：最优解为装 、各一件，重 13千克, 最大价值为13.5元.10最优解为装第一种货物1件，第四种货物2 件，最大价值为23千元。11解：每月最佳生产货物数量为：月 份1234生产货物量（百件）2504 总最低费用为21千元。12解：最优投资方案为，第一子公司投资2个单位资金，其它两个子公司各投 资1个单位资金。总收益为9个单位。13解：最优生产计划为：前3年全部完好的机器都在低负荷下进行生产，最后 两年全部完好的机器都在高负荷下进行生产。最高产值为：43997.5万元。 每年年初完好机器台数为： 第i年初12345第5年底完好机器数500350245171.552.5315.435计算公式5000.73500.72450.7175.10.352.530.3注：在台数中出现小数，如第四年为171.5，表示有一台机器在第四年度中正常工 作的时间为整个工作时间的 1/2。其余依次类推。14解：最优生产安排：第一年生产产品B，第二年、第三年生产产品A。三年最大总收入为1510万元。 若要求三年后完好机器数为20台，则最优生产安排：第一年、第二年完好机 器全部生产产品B，第三年29.6台完好机器生产产品B , 6.4 台机器生产产品 A (有一台机器一年中60%的时间生产B , 40% 的时间生