英文版动态规划

第三章：动态规划3.1 动态规划的基本概念一、动态决策问题：决策过程具有阶段性和时序性(与时间有关)的决策问题。

即决策过程可划分为明显的阶段。

二、什么叫动态规划(D.P.–Dynamic Program)：多阶段决策问题最优化的一种方法。

广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。

三、动态规划(D.P.)的起源：1951年,(美)数学家R.Bellman等提出最优化原理，从而建立动态规划，名著《动态规划》于1957年出版。

四、动态决策问题分类：1、按数据给出的形式分为：•离散型动态决策问题。

•连续型动态决策问题。

2、按决策过程演变的性质分为：•确定型动态决策问题。

•随机型动态决策问题。

五1、阶段(stage)n ：作出决策的若干轮次。

n = 1、2、3、4、5。

2、状态(state)S n ：每一阶段的出发位置。

构成状态集，记为S nS 1={A}，S 2={B 1,B 2,B 3}，S 3={C 1,C 2,C 3}，S 4={D 1,D 2,D 3}，S 5={E 1,E 2}。

阶段的起点。

3、决策(decision)X n ：从一个阶段某状态演变到下一个阶段某状态的选择。

构成决策集，记为D n (S n )。

阶段的终点。

D 1(S 1)={X 1(A)}={B 1,B 2,B 3}= S 2，D 2(S 2)={X 2(B 1),X 2(B 2),X 2(B 3)}={C 1,C 2,C 3}=S 3，D 3(S 3)={X 3(C 1),X 3(C 2),X 3(C 3)}={D 1,D 2,D 3}=S 4，D 4(S 4)={X 4(D 1),X 4(D 2),X 4(D 3)}={E 1,E 2}=S 5D 5(S 5)={X 5(E 1),X 5(E 2)}={F;F}={F}。

4、策略(policy)：全过程中各个阶段的决策Xn 组成的有序总体{Xn }。

如 A àB2àC1àD1àE2àF5、子策略(sub-policy)：剩下的n个阶段构成n子过程，相应的决策系列叫n子策略。

9
优化值间的递归式
LOGO
虽然不知道优化解是否放物品1 虽然不知道优化解是否放物品1，但从优化原理我们 能建立优化值间的递归式 设f(i, y)为以背包容量y，放物品i,…,n,得到的优化效 y)为以背包容量y 放物品i,…,n,得到的 为以背包容量 得到的优化效 益值，以下递归关系成立: 益值，以下递归关系成立: f(1,c)=max{ f(2,c), f(2,c-w1)+p1 } 不放物品1、放 f(2,c不放物品1 物品1 物品1 先求子问题的优化值(递归) 再从2种可能性中求 先求子问题的优化值(递归)，再从2种可能性中求 出最优的。 出最优的。 须对任意给定容量y 任意i,…,n 种物品求解子问题。 须对任意给定容量y，任意i,…,n 种物品求解子问题。
14
动态规划算法思想
LOGO
动态规划方法采用最优原则来建立用于计算最优 动态规划方法采用最优原则来建立用于计算最优 解的递归式 ； 不管前面的决策如何，此后的决策必须是基于当 不管前面的决策如何， 前状态的最优决策 ； 有些问题的某些递归式若不能保持最优原则，不 有些问题的某些递归式若不能保持最优原则， 可使用动态规划方法 。
因此最优解 f(1,116 )=max{f(2,116)，f(2,116-w1)+p1} )=max{f(2,116)，f(2,116=max{f(2,116)， =max{f(2,116)，f(2,16)+20 } =max{33， =max{33，38}=38
13
0/1背包问题：例15-4 （解续2） 背包问题： 15f(1,c =f(2,c f(1,c) =f(2,c)=>x1=0；否则x1=1，c=c-w1。 =0；否则x =1，c=cx2: f(2,c)=f(3,c)=> x2=0 否则x2=1，c=c-w2 否则x =1，c=cxi: f(i,c)=f(i+1,c)=> xi=0 否则xi=1，c=c-wi 否则x =1，c=c该例中, 该例中, x=[1, 1, 0]

此问题的解决可分为n个阶段，在这n个阶段上需分别确定用于生产第1， 2，…，n种产品的原料的数量.设在第 i个阶段时，原料的数量还有y， g i，剩下的数量为 ( xi ) x i (0 ≤ x i ≤ y ) 以数量 去生产第 i 种产品，获利
y − xi 的原料将用于生产其它产品.如此，得到多阶段决策问题.
最优化原理是动态规划的理论基础.
2011-3-10
7
运筹学
Operations Research
例1（续）解：令 u k ( S )：决策变量，即当前处 于状态S，还有k个阶段才能 到达E，下一个阶段所选择的点;
d ( S , uk ( S ))：状态S到下一个阶段所选择的 点u k ( S )的距离;
运筹学
Operations Research
§6 动态规划
Dynamic programming
2011-3-10
1
运筹学
Operations Research
动态规划(dynamic programming)是求解多阶段决策问题的一个运筹学分支. 多阶段决策问题（multistage decision problem）：在现实生活中,有一些活 动过程，因其特殊性,可分为若干个互相联系的阶段.在每一阶段都要做 出决策,而且前一个阶段的决策常会对后一个阶段的决策产生影响.应如 何在每一阶段做出一个决策，以使得整个决策过程（策略）最优，是为 多阶段决策问题. 在多阶段决策问题中,各个阶段所做出的决策一般来说是和时间有关的,它 既依赖于当前状态（status）,又随即引起状态的转移.于是，一个前后关联 的链状决策序列在这种“动态”的变化中产生, 故称解决此种问题的方法 为动态规划.
u 2 (C 3 ) = D2

j 1
i 1 2 3 4 5 6
2
3
4
5
6
可以表示为： n=6，p=(30, 35, 15, 5, 10, 20, 25)
2016年1月16日星期六
第3章 动态规划
22
1 2 3 4 5 6 0 15750 7875 9375 11875 15125 0 2625 4375 7125 10500 0 750 2500 5375 0 1000 0 3500 5000 0
8
T(n)
n/2
T(n/4) T(n/4) T(n/4)
=
n
n/2 n/2 n/2
T(n/4)
T(n/4)
T(n/4) T(n/4) T(n/4)T(n/4)T(n/4) T(n/4)
避免大重复计算
2016年1月16日星期六
第3章 动态规划
9
动态规划的实质 动态规划的实质是分治思想和解决冗余。
1) 一种将问题实例分解为更小的、相似的子问题。 2) 存储子问题的解而避免计算重复的子问题。 主要特点: 问题分解；采用表格技术，用多项式 算法代替指数算法；空间换取时间
• 虽然动态规划主要用于求解以时间划分阶段的动 态过程的优化问题，但是一些与时间无关的静态 规划(如线性规划、非线性规划)，只要人为地引 进时间因素，把它视为多阶段决策过程，也可以 用动态规划方法方便地求解。 • 应用广泛：经济管理、生产调度、工程技术和最 优控制。例如最短路线、库存管理、资源分配、 设备更新、排序、装载等问题，用动态规划方法 比用其它方法求解更为方便。
第3章 动态规划
23
m[4][4] m[5][6] p3 p4 p6 0 5000 1250 m[4][6] min m[4][5] m[6][6] p3 p5 p6 0 1000 2500 min{6250 ,3500 } 3500