下载文档原格式
运筹学动态规划第7章动态规划动态规划是Bellman 在1957年提出的解多阶决策问题的方法，在那个时期，线性规划很流行，它是研究静态问题的，而Bellman 提出的解多阶决策问题的方法适用于动态问题，相对于线性规划研究静态问题，取名动态规划。
动态规划方法应用范围非常广泛，方法也比较简单。
动态规划是将一个多阶决策问题分解为一系列的互相嵌套的一步决策问题，序贯求解使问题得到简化。
动态规划问题按照问题的性质可以分为确定性的和随机性的，按决策变量的和状态变量的取值可以分为离散型的和连续型的。
此外还有依据时间变量连续取值还是离散取值又分为连续时间动态规划问题和离散时间动态规划问题。
本章重点讨论离散时间确定性动态规划问题，包括状态变量和决策变量连续取值和离散取值两种情况。
7.1解多阶决策问题的动态规划法1.多阶决策问题的例(1)最优路径问题—多阶决策问题的例为了直观，先从最优路径问题谈起，它可以看作一个多阶决策过程。
通过最优路径问题的解可以看到用动态规划法解多阶决策问题的基本思想。
考虑图7-1所示的最优路径问题。
一汽车由S 点出发到终点F ，P 和Q 是一些可以通过的点。
图中两点间标出的数字是汽车走这一段路所需的时间(单位为小时)。
最优路径问题是确定一个路径，使汽车沿这条路径由S 点出发达到F 点所用时间最短。
最优路径问题可以看作一个多阶决策问题，由S 到城市甲是第1个阶段，第1个结点P 1或第2个结点Q 1做为第1阶段可以通过的两个站点，由城市甲到城市乙是第2阶段，这个阶段是从P 1或Q 1到P 2或Q 2，由城市乙到城市丙是第3阶段，这个阶段是从P 2或Q 2到P 3或Q 3，由城市丙的P 3或Q 3到F 做为第四阶段。
（2）最优路径问题的解对最优路径问题，存在一个非常明显的原理，即最优路径的一部分还是最优路径。
换句话说，如果SQ P Q F 123是所求的最优路径，那么，汽车从这一路径上的任何一点，例如P 2，出发到F 的最优路径必为P Q F 23。
习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）：
（1） 用逆推解法；2用标号法。
7.2 用动态规划方法求解下列问题
（1） max z ＝x 12x 2 x 33
x 1＋x 2＋x 3 ≤6
x j ≥0 （j ＝1,2,3）
（2）min z ＝ 3x 12＋4x 22 ＋x 32
x 1x 2 x 3 ≥ 9
x j ≥0 （j ＝1,2,3）
7.3 利用动态规划方法证明平均值不等式：
n n n x x x n
x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。
7.4 考虑一个有m 个产地和n 个销地的运输问题。
设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。
又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。
7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。
每年至多做一项投资，每次只能投入1000万元。
求出三年后所拥有的期望金额达到最大的投资方案。
投 资 回 收 概 率
A 0 0.4
2000 0.6
B 1000 0.9
2000 0.1
7.6 某公司有三个工厂，它们都可以考虑改造扩建。
每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。
现公司有资金5千万元，问应如何分配投资使公司的总收益最大?
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生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨）
1 30 15.6 20
2 40 14.0 25
3 25 15.3 30
4 10 14.8 15
（1）请建立此问题的线性规划模型。
（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。
（均不用求解）。
