《运筹学》第五章习题
1．思考题
（1）试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。

（2）动态规划的阶段如何划分？
（3）试述用动态规划求解最短路问题的方法和步骤。

（4）试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值函数、边界函数等概念。

（5）试述建立动态规划模型的基本方法。

（6）试述动态规划方法的基本思想、动态规划的基本方程的结构及正确写出动态规划基本方程的关键步骤。

2．判断下列说法是否正确
（1）动态规划分为线性动态规划和非线性动态规划。

（2）动态规划只是用来解决和时间有关的问题。

（3）对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。

（4）在用动态规划的解题时，定义状态时应保证各个阶段中所做的决策的相互独立性。

（5）在动态规划模型中，问题的阶段等于问题的子问题的数目。

（6）动态规划计算中的“维数障碍”，主要是由于问题中阶段数的急剧增加
而引起的。

3．计算下图所示的从A 到E 的最短路问题
4．计算下图所示的从A 到E 的最短路问题
5．计算从A 到B、C、D 的最短路线。

已知各线段的长度如下图所示。

6．设某油田要向一炼油厂用管道供应油料，管道铺设途中要经过八个城镇，各
城镇间的路程如下图所示，选择怎样的路线铺设，才使总路程最短？
7．用动态规划求解下列各题
（1）．2
22211295max x x x x z -+-=；
⎩⎨
⎧≥≤+0,52
121x x x x ；
（2）．
3
3
221max x x x z =
⎩⎨
⎧≥≤++0,,6321
321x x x x x x ；
8．某人外出旅游，需将3种物品装入背包，但背包重量有限制，总重量不超过
10千克。

物品重量及其价值等数据见下表。

试问每种物品装多少件，使整个 背包的价值最大？
913 千克。

物品重量及其价值的关系如表所示。

试问如何装这些物品，使整个背包 价值最大？
10 量和相应单位价值如下表所示，应如何装载可使总价值最大？
30
30
11 底交货量，该厂的生产能力为每月600件，该厂仓库的存货能力为300件，又 每生产100件产品的费用为1000元。

在进行生产的月份，工厂要固定支出3000 元开工费。

仓库保管费用为每100件500元。

假定开始时和计划期末库存量都 是零。

试问应在各个月各生产多少件货物，才能既满足交货任务又使总费用最 少？
12
使用资金的效益也不同。

具体数据见下表。

为使此集团获得最大收益，试问 每个子公司各投资多少单位资金？（表内数字为投资所获收益）
13
荷下进行生产时，每台机器每年可收入50万元，机器损坏率为70% ，在低 负荷下进行生产时，每台机器每年可收入30万元，机器损坏率为30% ，估 计五年后有新的机器出现，旧的机器将全部淘汰。

要求制定一个五年计划， 在每年开始时，决定如何分配完好的机器在两种不同的负荷下生产的数量， 使在五年内总产值最高。

并计算每年初完好机器台数。

14．某工厂购近100台设备，准备生产A 、B 两种产品。

如果生产产品A ，每台
设备每年可收入10万元，但机器损坏率为65 %，如果生产产品B ，每台设 备每年可收入7万元，机器损坏率为40% ，三年后的设备完好情况不计，试 问应如何安排每年的生产，使三年的总收入最大？又如果要求三年后有20台 机器是完好的，则应如何安排每年的生产，使三年的总收入最大？
15．某工厂有5个单位的能源要供给3个车间，供给方案及各车间获得能源后所 产生的效益在下表给出，问应如何分配这些能源，使工厂的总收益最大？
《运筹学》第五章习题解答
2．解：（1）X （2）X （3）X （4）√ （5）√（6）X 。

3．解：最短路线为
E D C B A −→−−→−−→−−→−2
221113，最短路程为8。

4．解：最短路线为
E D C B A −→−−→−−→−−→−3121122，最短路程为8。

5．解：分别求出各最短路线和最短路程为：
B G F E A −→−−→−−→−−→−5
252313，最短路程为16 ；
C G F E A −→−−→−−→−−→−10252313，或
C G F E A −→−−→−−→−−→−8372313，最短路程为21 ；
D G F
E A −→−−→−−→−−→−7372313，最短路程为20 。

6．解：最短铺设路线有两条，分别是：
炼油厂油田−→−−→−−→−−→−40110120240D C B ，最短路程为110。

炼油厂油田−→−−→−−→−−→−40110130330D C B ，最短路程为110。

7．解：(1) 最优解为：
8131
;49,2521===
z x x ； （2）最优解为：108;
3,1,2321====z x x x 。

8．解：最优解装第一种物品2件，第二种物品1件，不装第三种物品，整个背
包的最大价值为13。

9．解：最优解为装 Ａ、Ｂ、Ｅ各一件，重 13千克, 最大价值为13.5元. 10．最优解为装第一种货物1件，第四种货物2 件，最大价值为23千元。

11
12．解：最优投资方案为，第一子公司投资2个单位资金，其它两个子公司各投 资1个单位资金。

总收益为9个单位。

13．解：最优生产计划为：前3年全部完好的机器都在低负荷下进行生产，最后 两年全部完好的机器都在高负荷下进行生产。

最高产值为：43997.5万元。

每年年初完好机器台数为：
作的时间为整个工作时间的 1/2。

其余依次类推。

14．解：最优生产安排：第一年生产产品B ，第二年、第三年生产产品A 。

三年
最大总收入为1510万元。

若要求三年后完好机器数为20台，则最优生产安排：第一年、第二年完好机 器全部生产产品B ，第三年29.6台完好机器生产产品B , 6.4 台机器生产产品 A (有一台机器一年中60%的时间生产B , 40% 的时间生产产品 A )。

三年最 大总收入为1391.2万元。

15．解：最优分配方案有三个：
（1）第一车间分配2个能源，第二车间2个，第三车间1个； （2）第一车间分配1个能源，第二车间3个，第三车间1个； （3）第一车间分配1个能源，第二车间4个，第三车间0个。

最大总收益都是17个单位。