第四章 动态规划
1 引言
1.1 动态规划的发展及研究内容
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。
例 1 最短路线问题
图 1 是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由 A 到G 距离最短（或费用最省）的路线。
用 lingo 求解例 1 最短路线问题。
model:
Title Dynamic Programming;
sets:
vertex/A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G/:L;
road(vertex,vertex)/A B1,A B2,B1 C1,B1 C2,B1 c3,B2 C2,B2 C3,B2 C4,
C1 D1,C1 D2,C2 D1,C2 D2,C3 D2,C3 D3,C4 D2,C4 D3,
D1 E1,D1 E2,D2 E2,D2 E3,D3 E2,D3 E3,
E1 F1,E1 F2,E2 F1,E2 F2,E3 F1,E3 F2,F1 G,F2 G/????;
endsets
data:
D=5 3 1 3 6 8 7 6
6 8 3 5 3 3 8 4
2 2 1 2 3 3
3 5 5 2 6 6 4 3;
L=0,;
enddata
@for(vertex(i)|i#GT#1:L(i)aaa@qq.com(road(j,i):L(j)+D(j,i)));
end
例2 生产计划问题
工厂生产某种产品，每单位（千件）的成本为 1（千元），每次开工的固定成本为 3（千元），工厂每季度的最大生产能力为 6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为 2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为 0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。
1.2 决策过程的分类
根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-time decision process）和连续时间决策过程（continuous-time decision process）；根据过程的演变是确定的还是随机的，分为确定性决策过程（deterministic decision process）和随机性决策过程（stochastic decision process），其中应用最广的是确定性多阶段决策过程。
2 基本概念、基本方程和计算方法
2.1 动态规划的基本概念和基本方程
一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。
2.1.1 阶段
阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k = 1,2,L,n 表示。在例 1 中由 A出发为 k = 1，由 B (i = 1,2) i 出发为 k = 2 ，依此下去从 F (i =1,2) i 出发为 k = 6 ，共n = 6个阶段。在例 2 中按照第一、二、三、四季度分为k = 1,2,3,4，共四个阶段。
2.1.2 状态
状态（state）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量（state variable）。变量允许取值的范围称允许状态集合(set of admissible states)。用 k x 表示第k 阶段的状态变量，它可以是一个数或一个向量。
用 Xk 表示第 k 阶段的允许状态集合。在例 1 中 x2 可取 B1 ,B2 ，或将 Bi 定义为i(i = 1,2) ，则 x2 = 1或2 ，而 X2={1,2} 。
n 个阶段的决策过程有n +1个状态变量， n+1 x 表示 n x 演变的结果。在例 1 中 7 x 取 G ，或定义为1，即 x7 = 1。
根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。
状态变量简称为状态。
2.1.3 决策
当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）。
描述决策的变量称决策变量（decision variable），变量允许取值的范围称允许决策集合（set of admissible decisions）。用 uk (xk) 表示第k 阶段处于状态 k x 时的决策变量，它是 xk 的函数，用 Uk (xk)表示 xk的允许决策集合。在例 1 中 u2(B1) 可取 C1 ,C2 或C3 ，可记作 u2(1) =1,2,3 ，而 U2(1) = {1,2,3} 。
决策变量简称决策。
2.1.4 策略
2.1.5. 状态转移方程
2.1.6. 指标函数和最优值函数
2.1.7 最优策略和最优轨线
2.1.8 递归方程
3 逆序解法的计算框图
4 动态规划与静态规划的关系
5 若干典型问题的动态规划模型
5.1 最短路线问题
5.2 生产计划问题
5.3 资源分配问题
一种或几种资源（包括资金）分配给若干用户，或投资于几家企业，以获得最大的效益。资源分配问题（resource allocating Problem）可以是多阶段决策过程，也可以是静态规划问题，都能构造动态规划模型求解。