第八章 动态规划

三、动态规划模型的建立
用动态规划解决实际问题，就要建立动态规划模 型，为此需要解决如下问题：

1. 划分阶段 2. 确定状态变量和决策变量以及相应的取值范围 3. 建立状态转移方程 4. 确定指标函数，建立动态规划的基本方程 5. 确定边界条件

1. 划分阶段 按照时间、空间、变量划分为若干阶段。 建立动态规划模型要求每个阶段问题具有同一模式。 2. 确定状态变量和决策变量以及相应的取值范围 决策过程可用状态演变描述。状态必须包含表示系统情况和确定决 策所需要的全部信息，反映过程的演变特征。无后效性。找出状态 变量在各阶段的取值范围。决策变量由系统最优化的目的所决定。
f 3 (C3 ) min{ 5 f 4 ( D2 )} min{ 5 3} 8
最小费用路线为 C3 D2 E 相应的最优决策 u3 (C3 ) D2
3．第2阶段，同上。 如果现处于B1，到达终点E的最小费用为：
3 f 3 (C1 ) 3 11 f 2 ( B1 ) min min 12 4 f ( C ) 4 8 3 3
第2阶段的状态 3 B1 C1 4 4 B2 1 11 B3 6 6 4 C2 9 7 12 5 C3 8 D2 D1 5 3 E
第1阶段的状态 4 A
3
第1阶段
第2阶段
第3阶段
第4阶段
s1状态A ，s2?
S1={A}，S2={B1、B2、B3}，S3={C1、C2、C3}，S4={D1、D2}。
3）决策 决策是某阶段状态给定之后，从该状态演变到下一阶
最小费用路线为 B1 C3 D2 E 相应的最优决策 u2 ( B1 ) C3 如果现处于B2，则到达终点E的最小费用为：
4 f 3 (C1 ) 4 11 f 2 ( B2 ) m in4 f 3 (C 2 ) m in4 12 15 6 f (C ) 6 12 3 3
划分阶段 把对某一种新产品增加研制费用作为一个阶段，将整个过程分
为三个阶段。对甲产品增加研制费用记为第1阶段、对乙产品增加研制费 用记为第2阶段、对丙产品增加研制费用记为第3阶段。K=1,2,3。
状态变量 把有可能提供的研制费用作为状态变量，记为sk，它的取值范
围是：0、1、2
决策变量 把给第k种新产品的研制费用的数量作为决策变量 uk，它由决策
* f k (sk ) Vk ,n (sk , pk Vk ,n (sk , pk ,n ) , n ) optimum pk , n
第2阶段的状态 B1 第1阶段的状态 4 A 3 11 4 B2 1 B3 6 6 4 3 4 C1 9 7 D1 8 D2 5 3 E
C2
12 5
C3
第1阶段
略。
第2阶段的状态 3
B1
第1阶段的状态 4 A 3 11 第1阶段
4
C1
9
7 D1 8 D2 5 3 E
4
B2 1 B3 6 6 第2阶段
4
C2
12
5
C3 第3阶段 第4阶段
pA,E{A,B2,C3,D2,E}就是一个策略。 pB2,E{B2,C3,D2,E}就是一个子策略。
5）状态转移方程
它是确定过程由某一阶段的一个状态到下一阶段另一状态 的演变过程，用sk+1=Tk(sk,uk)表示。该方程描述了由第k阶段 到第k+1阶段的状态转移规律。因此又称其为状态转移函数。
第八章 动态规划


第一节 动态规划原理和模型
第二节 一维动态规划求解方法

第三节 动态规划在经济和管理中的应用
第一节 动态规划原理和模型

一、引例与动态规划的基本概念 二、动态规划的原理 三、动态规划模型的建立
一、动态规划的基本概念

动态规划是50年初由美国数学家R.Bellman等人提出 的解决多阶段决策过程优化问题的“最优化原理” 基础上建立起来的。
1 1
4 2

在每一阶段的求解，都利用了第k阶段和第k+1 阶 段的如下关系：
f k( s k ) min{d k ( s k , u k ) f k 1 ( s k 1 )} f 5 ( s5 ) 0 k 4,3,2,1
这种关系称为动态规划的基本方程。 所谓最优化原理是：一个过程的最优决策具有这 样的性质：无论初始状态及初始决策如何，对于 先前决策所形成的状态而言，其以后的所有决策 应构成最优策略。
第2阶段
第3阶段
第4阶段
V2,4(B1)：表示在第2阶段，状态为B1时，从B1到E的距离。
f2(B1)则表示从B1到E的最短距离。
二、动态规划的原理
在例8.1中，整个运输路程分为四个阶段，见图 8.2。下面给出求解的全过程。这里我们采用倒推 的方法，即从终点（E）到起点（A）。

1．第4阶段，即从E到D，从E出发倒推到下一站D， 它可通过D1，也可通过D2，所需费用分别为5和3。
如果现处于状态D1，到终点E的最佳路线费用： f4(D1)=5，最优策略：u4(D1)=E。 如果现处于状态D2，到终点E的最佳路线费用： f4(D2)=3，最优策略：u4(D2)=E。


第3阶段，当从E到达D后，有两个状态D1和D2； 若处于状态D1，则可到达C1或C2，则费用分别为9或 7。 若处于状态D2，则可到达C1或C2或C3，费用分别为8 或12或5。 从E经D1到达C1或C2 的费用，应加上E到达D1这段的 费用，所以费用分别为5+9=14、5+7=12； 从E经D2到达C2或C2或C3 的费用，应加上E到达D2这 段的费用，所以费用分别为3+8=11、3+12=15、 3+5=8。
段某一状态的选择。表示决策的变量称为决策变量，
用uk(sk)表示第阶段，状态为sk时的决策变量，它是 状态变量的函数。实际问题中，决策变量的选取往往 受到某些条件的影响而限制于某一范围，此范围称为 允许决策集合。
第1阶段的状态 4 A 3
第2阶段的状态 3 B1 C1 4 4 B2 1 6 6 第2阶段 4 C2
B1 4 A 4 B2 1 11 B3 6 6 4 C2 12 5 C3 3 4 C1 9 7 8 D2 D1 5 3 E
3
第1阶段
第2阶段
第3阶段
第4阶段
(2)状态 状态就是阶段的起始位置。通常一个阶段包含若干个状态。 第k阶段的状态就是该阶段所有始点的集合。描述各阶段状 态的变量称为状态变量。常用sk表示第k阶段的状态变量。状 态变量的取值集合称为状态集合，用Sk表示。
第2阶段的状态 3 B1 C1 4 4 B2 1 6 6 第2阶段 4 C2
9 7 12 5 8 D2 D1
第1阶段的状态 4 A 3
5
3 E
11
第1阶段
B3
C3 第3阶段 第4阶段
状态转移方程为 sk+1=uk(sk)
6）指标函数
指标函数是用来衡量多阶段决策过程优劣的一种数量指标。 一个n 阶段决策过程，从1到n 称为问题的原过程，对于任意 一个给定的k（1≤k≤n），从第k 阶段到第n 阶段的过程称为原 过程的一个后部子过程。 用 V1,n(s1,p1,n)表示初始状态为s1 采用策略p1,n 时，原过程的指 标函数值。 Vk,n(sk,pk,n)表示在第k 阶段，状态为sk采用策略pk,n 时，后部子 过程的指标函数值。 从第k 阶段状态 sk采用最优策略 p*k,n 到过程终止时的最佳效 益值，称为最优指标函数。记为fk(sk)。
最小费用路线为： A B C D E 相应的最优决策： u1 ( A) B1 所以，整个问题的最小费用路线为：
u (D ) E u 2 ( B1 ) C3 ， 最优策略为：{ u ( A) B ， u3 (C3 ) D2， }。
最小费用路线为 B2 C1 D2 E 相应的最优决策 u 2 ( B2 ) C1 如果现处于B3，则到达终点E的最小费用为： 1 f 3 (C1 ) 1 11 f 2 ( B3 ) min min 12 6 12 6 f 3 (C 3 )

动态规划是将一个较复杂的多阶段决策问题分解为 若干相互关联的较容易求解的子决策问题，而每一 个子决策问题都有多种选择，并且当一个子决策问 题确定以后，将影响另一个子决策问题，从而影响 到整个问题的决策。

动态规划模型分为（1）离散模型；（2）连续模 型。本章只讨论与离散模型有关原理和方法。这 对连续模型也适用。


如果现在处于C1，则到达终点E的最小费用为：
9 f 4 ( D1 ) 9 5 f 3 (C1 ) min min 11 8 3 8 f 4 ( D2 )
最小费用路线为 C1 D2 E 相应的最优决策 u3(C1)=D2。 如果现在处于C2，则到达终点E的最小费用为：
构成了一个策略。 p1,n {u1 (s1 ),, un (sn )}称为全过程的一个策略，
简称策略。 pk ,n {uk (sk ),uk 1 (sk 1 ),, un (sn )} 称为由第k阶段开始 到最后阶段止的一个子策略，简称后部子策略。
使整个问题到达最优效果的策略称为最优策略。
动态规划方法就是要从允许策略集中找出最优策
7 f 4 ( D1 ) 75 f 3 (C 2 ) min min 12 12 3 12 f 4 ( D2 )
最小费用路线为 C2 D1 E
u3 (C2 ) D1
。相应的最优决策:

如果现在处于C3，到达终点E的最小费用为：