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

《运筹学》第五章习题

1．思考题

（1）试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。

（2）动态规划的阶段如何划分？

（3）试述用动态规划求解最短路问题的方法和步骤。

（4）试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值

函数、边界函数等概念。

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

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

态规划基本方程的关键步骤。

2．判断下列说法是否正确

（1）动态规划分为线性动态规划和非线性动态规划。

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

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

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

互独立性。

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

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

B11C14

3532

36D11

5BC

A242E

69

4

447D2

B2C32

35

而引起的。

3．计算下图所示的从A到E的最短路问题

4

BD

11

23

4

3C5

1

3

3

1D1E

A2B2312

4

13C2

52

B5

3D

3

3

4．计算下图所示的从A到E的最短路问题

5．计算从A到B、C、D的最短路线。已知各线段的长度如下图所示。

4109

EFGB

1