动态规划

第七章 动态规划

习题七

7.1计算如图所示的从A到E的最短路线及其长度（单位：km）：

（1） 用逆推解法； （2） 用标号法。 3 B1 4 D1 2 3 4 C1 3 A 2 B2 1 1 5 D2 1 E 3 3 C2 4 2 5 3 1 B3 5 3 D3

7.2 用动态规划方法求解下列问题

（1） max z ＝x12x2 x33

x1＋x2＋x3 ≤6

xj≥0 （j＝1,2,3）

（2）min z ＝ 3x12＋4x22 ＋x32

x1x2 x3 ≥ 9

xj ≥0 （j＝1,2,3）

7.3 利用动态规划方法证明平均值不等式：

(x1?x2???xn)?(x1x2?xn)n

n设xi ≥0，i＝1，2，?，n。

7.4 考虑一个有m个产地和n个销地的运输问题。设ai（i＝1，2，?，m）为产地i可发运的物资数，bj（j＝1，2，?，n）为销地j所需要的物资数。又从产地i到销地j发运xij单位物资所需的费用为hij（xij），试将此问题建立动态规划的模型。

7.5 某公司在今后三年的每一年的开头将资金投入A或B项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。

投 资 回 收 概 率 A 0 0.4

2000 0.6

B 1000 0.9

2000 0.1

１８９

1第七章 动态规划

7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大? 工厂i＝l 工厂i＝2 工厂i＝3 mij 1 2 3 4 c(投资) 0 1 2 — R(收益) 0 5 6 — c(投资) 0 2 3 4 R(收益) 0 8 9 12 c(投资) 0 1 — — R(收益) 0 3 — — 7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用

为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。

7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。

货物代号 重量（吨） 容积（立方米） 价值（千元）

1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6

若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。

7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。

巡逻队数 预期事故次数仓库

1 2 3 4

2 18 38 14 34 3 16 36 12 31 4 12 30 11 25

7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，

１９０

第七章 动态规划

有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。

季度j 生产能力aj（吨） 生产成本dj（万元/吨） 需求量bj（吨） 1 30 15.6 20 2 40 14.0 25 3 25 15.3 30 4 10 14.8 15 （1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品xj吨，第j季度初存贮的产品为yj吨，显然y1＝0）

（2）请建立此问题的动态规划模型。（均不用求解）

复习思考题

7.11 举例说明什么是多阶段的决策过程及具有多阶段决策问题的特性。

7.12 解释下列概念：(a)状态；(b)决策；(c)最优策略；(d)状态转移方程；(e)指标函数和最优值函数。

7.13 建立动态规划模型时应注意哪几点，它们在模型中的作用是什么?

7.14 试述动态规划方法的基本思想，动态规划基本方程的结构及方程中各个符号的含义及正确写出动态规划基本方程的关键因素。

7.15 试述动态规划的最优化原理，以及它同动态规划基本方程之间的关系。

7.16 试述动态规划方法与逆推解法和顺推解法之间的联系及应注意之处。

7.17 判断下列说法是否正确

(1)在动态规划模型中，问题的阶段数等于问题中的子问题的数目；

(2)动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性； (3)动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策；

(4)对一个动态规划问题，应用顺推或逆推解法可能会得出不同的最优解；

(5)动态规划计算中的“维数障碍”主要是由于问题中阶段数的急剧增加而引起； (6)假如一个线性规划问题含有5个变量和3个约束，则用动态规划方法求解时

１９１

第七章 动态规划

将划分为3个阶段，每个阶段的状态将由一个5维的向量组成。

7.18 对静态规划的模型(如线性规划、非线性规划、整数规划等)，一般可以采用动态规划的方法求解，对此你能否评说一下各自的优缺点。

7.19 在动态规划中，定义状态时要保证各阶段决策的相互独立性，试述“货郎担”问题中状态是如何定义的，以及为什么要这样来定义。

7.20 什么是动态规划算法中的维数灾难，试举出本章有关问题中，在什么情况下会出现维数灾难。

１９２

本文来源：https://www.bwwdw.com/article/l4z7.html