4 5
14
5 8 4
18
13
22
7
36
5
28
8
23
6
11
6
38
5
30
9
17
7
10
3
8
12
8
第7章
7
6
6
4
动态规划
7.3
7.3. 2 资源分配问题
离散确定型典例
例3 某厂为扩大生产能力，拟定购某种成套设备4~6套,以分配给
其所辖三个分厂使用。预计各分厂分得不同套数的设备后每年创造的
利润如下表所示。该厂应订购几套设备并如何分配，才能使每年预计 创利总额最大？
积函数
和函数
6
fk(sk,xk) = vi(si,xi)
i= k
n n
fk(sk,xk) = vi(si,xi)
i= k
第7章
动态规划
7.2
七、最优解
基本概念
(1) 最优指标函数 fk*(sk) = opt {fk(sk, pk(sk))}, k=1,2,…,n pk∈Pk (2) 最优策略 能使上式成立的子策略pk*称为最优子策略，记为 pk* (sk) = { xk*(sk),… ,xn*(sn)} 特别当k=1时,称为最优策略，记为 p1* (s1) = { x1*(s1),… ,xk*(sk),… ,xn*(sn)} (3) 最优决策 构成最优策略的决策称为最优决策，记为xk*。 (4) 最优值：最优策略对应的最优指标 f *1
xk∈Xk
k = n, n-1, …, 2, 1
积
f*n+1(sn+1) = 1 f*k(sk) = opt {vk(sk,xk) ×fk+1*(sk+1)}
xk∈Xk
k = n, n-1, …, 2, 1
8
第7章
动态规划
7.2
1°建立模型
基本概念
7.2. 3 动态规划的基本方法
(1) 划分阶段，设定 k (2) 设定状态变量 sk (3) 设定决策变量 xk (4) 建立状态转移方程 (5) 确定指标函数 vk，fk* (6) 建立函数基本方程
2°递推(逆推)求解
3°得出(顺推)结论
9
第7章
动态规划
7.2
一、按阶段变量k划分
基本概念
7.2. 4 动态规划的基本类型
(1) 定期型: k = 1, 2, … , n (2) 不定期型: k = 1, 2, … , n (解前未知) (3) 无期型: k = 1, 2, … , n , …
二、按状态变量sk划分
离散型 连续型
10
确定型 随机型
第7章
动态规划
7.3
7.3.1 定价问题
离散确定型典例
例2 某厂要确定一种新产品在今后五年内的价格，并已拟定只在 5、6、7、8 元这四种单价中进行选择。 据预测， 今后五年不同价格下 每年盈利如表所示, 但是各相邻年度价格增减不超过 1 元。问今后五年 内每年定价各为多少,可预期五年总利润最大？
一、阶段
基本概念
把所研究的问题恰当的划分成若干个相互联系的阶段。用 k = 1，2，…，n 表示阶段序号，称为阶段变量。
二、状态
状态表示某段的初始条件。用sk表示第k段的状态，称为第k段 sk∈Sk 状态变量。
三、决策
是指人们对某一阶段活动中各种不同的行为或方案或途径等的 一种选择。
用xk表示第k段的决策，称为第k段决策变量。由于决策随状态
p 1 ( s1 ) , 有
而
p1(s1) = { x1(s1),x2(s2),… ,xn(sn)} ∈P1 pk(sk) = { xk(sk),xk+1(sk+1),… ,xn(sn)} ∈Pk
称为第k子过程策略，简称子策略。
5
第7章
动态规划
7.2
六、指标函数
基本概念
(1) 阶段指标函数 用vk(sk,xk)表示第k段处于sk状态且所作决策为xk∈P1 时的指标，则它就是第k段指标函数，简记为vk。 (2) 过程指标函数 用fk(sk,xk)表示第k子过程的指标函数。 它是各vk的累积效应。 常用函数：
盈利：万元
套数
分厂
0 0 0 0
第7章
1 3 4 2
2 5 6 5
3 6 7 9
4 7 8 8
5 6 9 8
6 5 10 7
1 2 3
13
动态规划
7.3
解 1. 建立DP模型
离散确定型典例
以 k = 1，2，3 表示给三个分厂分配的顺序。 设 sk = 在给k分厂分配时尚余的套数； xk = 分给k分厂的套数； 可知状态方程为 sk+1 = sk - xk vk ( sk, xk ) = 从现有sk套设备中分给k分厂xk套 设备后的预计创利额； fk ( sk, xk ) = 将现有sk套设备从 k - 3 分配后 (其中k分厂分得xk套)的预计创利额之和；
而变,所以决策变量xk是状态变量sk的函数,记为 xk= xk(sk) ∈Xk
4
第7章
动态规划
7.2
四、状态转移方程
基本概念
sk+1与sk,xk之间必须能够建立一种明确的数量对应关系，记为 Tk(sk,xk), 即有 sk+1 = Tk(sk,xk)
这种明确的数量关系称为状态转移方程。
五、策略
由各阶段决策xk构成的决策序列,称为全过程策略,简称策略,记为
第7章
动态规划
7.1 引言 7.2 基本概念 7.3 离散确定型典例 7.4 其他典例
1
第7章
动态规划
7.1
7.1. 1 多阶段决策问题
阶段、决策、策略
引言
7.1. 2 动态规划的基本特性
一、多阶段决策问题的基本特性
Q = S1
S2
…
Sk
Sk+1
…
Sn S’n
T
反证法容易得证。
S’k+1
…
若 {S2 , … , Sk , Sk+1 , … , Sn , T} 全程最优 则 {Sk+1 , … , Sn , T} 子程最优
7
第7章
动态规划
7.2
基本概念
7.2.2 动态规划的基本方程
一、最优化原理 作为一个全过程最优策略具有这样的性质： 无论过去的状态和决策如何，对前面所形成的状态而言， 余下的诸决策必构成最优策略。 二、函数基本方程
和
f*n+1(sn+1) = 0 f*k(sk) = opt {vk(sk,xk)+fk+1*(sk+1)}
2
第7章
动态规划
7.1
二、 动态规划方法的基本思路 例1 最短路问题 —— 标号法
引言
11
11 2 4 Q 3
7 A1 4 6 73 A2 2 4 8 41 A 5
3
4
1 B1 4 7 6 B2 3 63 3 B3 2 3 3 C1 3
0
T
4
C2
4
阶段
3
1
第7章
4
动态规划
Байду номын сангаас.2
7.2.1 动态规划的基本概念
盈利：万元
价格 (元 )
年
1 9 7 6 8
第7章
2 2 5 5 7
动态规划
3 4 8 9 6
4 5 6 7 6
5 8 4 3 4
5 6 7 8
11
7.3
年 1 9
35
离散确定型典例
2 2
28
p1* = { 8, 8 , 7, 6 , 5 } (元)
价格 5 6 7
37 24
3 4
f *1 = 38 万元