当前位置：文档之家 › 运筹08(第八章动态规划)

运筹08(第八章动态规划)

  • 格式：ppt
  • 大小：2.15 MB
  • 文档页数：58

下载文档原格式

  / 58

合集下载

OR8

OR8
部位
解： 把对每一个部位派出 巡逻队数量的决策，看成 是一个阶段，可归结成4 个阶段的决策问题。
2 3 4
A 18 14 10
B 38 35Biblioteka 31C 24 22 21D 34 31 25
2007/08
--20--
--第8章 动态规划--
一、建立模型
（1）阶段变量：k=1, 2, 3, 4 （2）状态变量：xk——第k阶段可用于分配的巡逻队数量； （3）决策变量：uk——第k阶段派出的巡逻队数量； 允许决策集合D(xk)={2, 3, 4} （4）状态转移律：xk+1=xk－uk ； （5）阶段指标函数：vk(uk)——预期损失函数，如表示； （6）基本方程：fk ( xk )= min{vk(uk)+ fk+1(xk+1)} （7）边界条件：f5 ( x5 )=0
3+ 3 3+ 4
=6，u3 * (C3) = C3D1
3）k=2， f2(x2)=min{v2(x2，u2) + f3(x3)}， B1C1+ f3(C1) f2(x2=B1)= min B1C2+ f3(C2) B1C3+ f3(C3) B2C1+ f3(C1) f2(x2=B2)= min B2C2+ f3(C2) B2C3+ f3(C3) = min = min 7+4 5+7 6+6 3+4 2+7 4+6 =7， u2 * (B2) = B2C1 =11，u2 * (B1) = B1C1
2007/08 --8--
--第8章 动态规划--
（3）决策（decision）：指在某阶段从给定的状态出发，决策者从面 临的若干种不同的方案中所做出的选择。 决策变量uk(xk) ∈Dk(xk)——允许决策集合， uk(xk)取值范围。 要点： ① 决策变量是对活动过程控制的手段； ② 决策变量取值可以是连续型的，也可以是离散型的； ③ 允许决策集合相当于可行域。 （4）策略（policy）与子策略（subpolicy）：各阶段决策组成的序列 总体称为策略；从某一阶段开始到过程最终的决策序列称为子策 略。 n 阶段策略可记为 {u1(x1), u2(x2) , … , un(xn)}， 子策略可记为 {uk(xk), uk+1(xk+1) , … , un(xn)}。 （5）状态转移律：状态参数变化的规律。从第k阶段的某一状态值xk 出发，当决策变量uk的取值确定之后，下一阶段的状态值xk+1按 某种规律T(xk , uk)确定。 第k+1阶段状态是第k阶段状态xk和变量uk的函数 xk+1 = T(xk , uk)， 又称状态转移方程。

动态规划

动态规划

多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状 态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化 问题的方法为动态规划方法 。
任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适 用动态规划的问题必须满足最优化原理和无后效性 。
动态规划
运筹学的分支
01 原理
03 局限性
目录
02 分类
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年 代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理， 从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域， 并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了 显著的效果 。
最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成 的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足 最优化原理又称其具有最优子结构性质 。
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来 的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又 称为无后效性 。
状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因 素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点 。

运筹学教案动态规划

运筹学教案动态规划

运筹学教案动态规划一、教学目标1. 了解动态规划的基本概念及其在运筹学中的应用。

2. 掌握动态规划的基本原理和方法，能够解决实际问题。

3. 学会使用动态规划解决最优化问题，提高解决问题的效率。

二、教学内容1. 动态规划的基本概念动态规划的定义动态规划与分治法的区别2. 动态规划的基本原理最优解的性质状态转移方程边界条件3. 动态规划的方法递推法迭代法表格法4. 动态规划的应用背包问题最长公共子序列最短路径问题三、教学方法1. 讲授法：讲解动态规划的基本概念、原理和方法。

2. 案例分析法：分析实际问题，引导学生运用动态规划解决问题。

3. 编程实践法：让学生动手编写代码，加深对动态规划方法的理解。

四、教学准备1. 教材：《运筹学导论》或相关教材。

2. 课件：动态规划的基本概念、原理、方法及应用案例。

3. 编程环境：为学生提供编程实践的平台，如Python、C++等。

五、教学过程1. 引入：通过一个实际问题，引出动态规划的概念。

2. 讲解：讲解动态规划的基本原理和方法。

3. 案例分析：分析实际问题，展示动态规划的应用。

4. 编程实践：让学生动手解决实际问题，巩固动态规划方法。

5. 总结：对本节课的内容进行总结，强调动态规划的关键要点。

6. 作业布置：布置相关练习题，巩固所学知识。

六、教学评估1. 课堂讲解：评估学生对动态规划基本概念、原理和方法的理解程度。

2. 案例分析：评估学生运用动态规划解决实际问题的能力。

3. 编程实践：评估学生动手实现动态规划算法的能力。

4. 课后作业：评估学生对课堂所学知识的掌握情况。

七、教学拓展1. 研究动态规划与其他优化方法的联系与区别。

2. 探讨动态规划在运筹学其他领域的应用，如库存管理、生产计划等。

3. 了解动态规划在、数据挖掘等领域的应用。

八、教学反思1. 反思本节课的教学内容、方法和过程，确保符合教学目标。

2. 考虑学生的反馈，调整教学方法和节奏，提高教学效果。

3. 探讨如何将动态规划与其他运筹学方法相结合，提高解决问题的综合能力。

运筹学课件--动态规划

运筹学课件--动态规划
J 表示留在左岸的仆人人数
初始状态s1是T(3,3)
结束状态sn是 T(0,0)
可达状态有哪些?(3,J) (2,2) (1,1) (0,J) J 3 2 1 0
2013-6-9
A
1
运筹学课件
2
3
I
阶段指标——每阶段选定决策xk后所产生的效益，记
vk= vk(Sk， xk)。
指标函数——各阶段的总效益，记相应于Pkn的指标函数
2013-6-9 运筹学课件
动态规划模型的分类： 以“时间”角度可分成：
离散型和连续型。
从信息确定与否可分成：
确定型和随机型。
从目标函数的个数可分成： 单目标型和多目标型。
2013-6-9 运筹学课件
8.2基本概念与方程
1.基本概念
阶段（Stage）——分步求解的过程，用阶段变量k表示，k=1，，n 状态（State）——每阶段初可能的情形或位置，用状态变 量Sk表示。 按状态的取值是离散或连续，将动态规划问题分为
当 k 3，f Max f v
3 0
3 3
3
4
Max 3x 5s 13.6(0.9s 0.2x )
0
3 3
3
3
3
3
Max 0.28x 17.24s
0
3 3
3
3

x s , f 17.52s ,即第3年初将全部完好机器都 投入高负荷。
指标函数vkn=
v

5
表示第k至5年的总产量；
1
递推公式：f Max f v
6

f 0, k 5, ,1
2013-6-9
运筹学课件

运筹学教材编写组《运筹学》课后习题-动态规划的基本方法(圣才出品)

运筹学教材编写组《运筹学》课后习题-动态规划的基本方法(圣才出品)
由此，可得出三条最优的运输路线：
（1） A → B2 →C1 → D1 → E ；（2） A → B3 →C1 → D1 → E ； （3） A → B3 →C2 → D2 → E 。
8.3 计算从 A 到 B、C 和 D 的最短路线。已知各段路线的长度如图 8-2 所示。
图 8-2
解：设阶段变量 k = 1, 2,3, 4 ,依次表示 4 个阶段选择路线的过程；状态变量 sk 表示第 k 阶段初所处的位置；决策变量 xk 表示第 k 阶段初可能选择的路线；最优值函数 fk (sk ) 表示 从起点 A 到第 k 阶段状态 sk 的最短距离，则有
xn =sn
n
xn
，或 fn+1(sn+1) = 0
n
（2）设状态变量为 sk = ai xi (k = 1, 2, n) ，状态转移方程为 sk+1 = sk − ak xk ，最 i=k
n
优值函数 fk (sk ) 表示在 sk 状态下从第 k 阶段到第 n 阶段使 z = ci xi2 最小的值，则动态规 i=k
划的基本方程为：
3 / 11
圣才电子书 十万种考研考证电子书、题库视频学习平台

fk (sk )
=
min
0xk sk ak
{ck
xk2
+
f k +1 (sk
− ak xk )}
fn+1(sn − anxn ) = 0(k = n, n −1, 2,1)
8.5 用递推方法求解下列问题。
=
max {2
0x3 10
x32
+
f2 (s2 )} =
max {2
0x3 10

运筹学教案动态规划

运筹学教案动态规划

运筹学教案动态规划一、引言1.1 课程背景本课程旨在帮助学生掌握运筹学中的动态规划方法，培养学生解决实际问题的能力。

1.2 课程目标通过本课程的学习，学生将能够：（1）理解动态规划的基本概念和原理；（2）掌握动态规划解决问题的方法和步骤；（3）能够应用动态规划解决实际问题。

二、动态规划基本概念2.1 定义动态规划（Dynamic Programming，DP）是一种求解最优化问题的方法，它将复杂问题分解为简单子问题，并通过求解子问题的最优解来得到原问题的最优解。

2.2 特点（1）最优子结构：问题的最优解包含其子问题的最优解；（2）重叠子问题：问题中含有重复子问题；（3）无后效性：一旦某个给定子问题的解确定了，就不会再改变；（4）子问题划分：问题可以分解为若干个子问题，且子问题之间是相互独立的。

三、动态规划解决问题步骤3.1 定义状态状态是指某一阶段问题的一个描述，可以用一组变量来表示。

3.2 建立状态转移方程状态转移方程是描述从一个状态到另一个状态的转换关系。

3.3 确定边界条件边界条件是指初始状态和最终状态的取值。

3.4 求解最优解根据状态转移方程和边界条件，求解最优解。

四、动态规划应用实例4.1 0-1背包问题问题描述：给定n个物品，每个物品有一个重量和一个价值，背包的最大容量为W，如何选择装入背包的物品，使得背包内物品的总价值最大。

4.2 最长公共子序列问题描述：给定两个序列，求它们的最长公共子序列。

4.3 最短路径问题问题描述：给定一个加权无向图，求从源点到其他各顶点的最短路径。

5.1 动态规划的基本概念和原理5.2 动态规划解决问题的步骤5.3 动态规划在实际问题中的应用教学方法：本课程采用讲授、案例分析、上机实践相结合的教学方法，帮助学生深入理解和掌握动态规划方法。

教学评估：课程结束后，通过课堂讨论、上机考试等方式对学生的学习情况进行评估。

六、动态规划算法设计6.1 动态规划算法框架介绍动态规划算法的基本框架，包括状态定义、状态转移方程、边界条件、计算顺序等。

第8章 动态规划《管理运筹学》PPT课件

Vk,n (sk , uk , , sn1) fk [sk , uk ,Vk 1,n (sk 1, uk 1, , 1)] ③函数 fk (sk , uk ,Vk 1,n ) 对于变量 Vk1,n 要严格单调。
8.2 动态规划模型建立
下面以投资问题为例介绍动态规划的建模条件。
【例8-2】 某公司现有资金20万元，若投资于三个
8.1 动态规划基础知识
（5）状态转移方程：状态转移方程是确定过程由一
个状态转移到另一个状态的演变过程。动态规划中某一状
态以及该状态下的决策，与下一状态之间具有一定的函数
关系，称这种函数关系的表达式为状态转移方程。如果第
k段的状态为 sk ，该阶段的决策为
的状态就可以用下式来表示：
uk
sk
，则第k+1段
阶段的指标函数，是该阶段最优的指标函数。
8.2 动态规划模型建立
建立动态规划模型，就是在分析实际问题的基础上建 立该问题的动态规划基本方程。成功地应用动态规划方法 的关键，在于识别问题的多阶段特征，将问题分解成为可 用递推关系式联系起来的若干子问题，或者说正确地建立 具体问题的基本方程，这需要经验与技巧。而正确建立基 本递推关系方程的关键又在于正确选择状态变量，保证各 阶段的状态变量具有递推的状态转移关系。
第8章 动态规划
动态规划(DYnamic Programming，缩写为DP)方法 ，是本世纪50年代初期由美国数学家贝尔曼(Richard E ，Bellman)等人提出，后来逐渐发展起来的数学分支， 它是一种解决多阶段决策过程最优化问题的数学规划法 。动态规划的数学模型和求解方法比较灵活，对于连续 的或离散的，线性的或非线性的，确定性的或随机性的 模型，只要能构成多阶段决策过程，便可用动态规划方 法求其最优解。因而在自然科学、社会科学、工程技术 等许多领域具有广泛的用途，甚至一定程度上比线性规 划（LP）、非线性规划（NLP）有成效，特别是对于某 些离散型问题，解析数学无法适用，动态规划方法就成 为非常有用的求解工具。

运筹与优化--动态规划.ppt


2.2. 动态 规划的基本思想和基本方程
最短路线有一个重要特性：如果L是允许策略集
合P中从始点A到终点E的最短路线,M是L中的一点,则
从M沿L到E的路是从M到E的最短路线.
寻找最短路线的方法,可以从最后一段开始,由后
向前逐步递推,求出各点到后一点的最短路线,最后求
得始点到终点的最短路线.所以,动态规划的方法是从
终点逐段向始点方向寻找最短路线的一种方法. 如图
所示:
行进方向
始点 1 2 3
n 终点
寻优途径
例1、最短路径问题
2
A5
1
B1
12 14
10
6
B2 10
4 13
B3
12 11
C1
3
9
6
C2
5 8
C3
10
求从A到E的最短路径
D1
5
E
D2 2
2
A5
1
B1
12 14
10
6
B2 10
4 13
B3
12 11
B1 12 14
2 f2(B2)=110 4
6
5
B2 10
4
1
13
B3
12 11
f2(B3)=19
f3(C1)=8
C1
3
9
f3(C2)=7
6
C2
5 8
C3
10
f3(C3)=12
f4(D1)=5
D1
5 f5(E)=0
E
D2 2
f4(D2)=2
状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态 A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1

运筹学第八章动态规划

□状态转移律为： xk+1 = uk( xk )
B1 C2
（5）策略（policy）和子策略（subpolicy）
□策略：由依次进行的n个阶段决策构成的决策序列就构成一个
策略，用 p1n{ u1(x1), u2(x2), …, un(xn) } 表示。
7
B1 5
6
2
3
1
C1 4
6
D1 3
A5
3
B2
15
□状态集合：状态变量 xk 的取值集合称为状态集合，状态集合 实际上是关于状态的约束条件。
□通常用Sk表示状态集合，xkSk。
□第1阶段 S1={A}；
x1
x2
□第2阶段具有3个状
态B1、B2和B3，故
S2={B1, B2, B3}。 □……
x3
x4
x5
16
（3）决策（decision）
□当过程处于某一阶段的某状态时，可以做出不同的决定，从而
第八章 动态规划
1
引言
□动态规划是解决多阶段决策过程最优化的一种方法。 □该方法是由美国数学家贝尔曼（R. E. Bellman）等人在20世 纪50年代初提出的。并成功地解决了生产管理、工程技术等方 面的许多问题，从而建立了运筹学的一个新的分支，即动态规 划。Bellman在1957年出版了《Dynamic Programming》一 书，是动态规划领域中的第一本著作。
其中 opt 可根据具体情况取max 或min。
□例1中，如 f3( C2 ) = 3+略 p1n ◎最优值：最优指标 f1(A)
□从第2阶段的状态 B1出发，如我们决 定选择C2（也即确 定了下一阶段的状 态）。
B1 C2

运筹学动态规划

许多问题用动态规划的方法去处理，常比 线性规划或非线性规划方法更有效。特别对于 离散性的问题。
特别注意：动态规划是求解某类问题的一种 方法，是考察问题的一种途径，而不是一种算法 （如线性规划是一种算法）。
因而，动态规划没有标准的数学表达式和明 确定义的一组规则，而必须对具体问题进行具体 分析处理．
动态规划
8.1 多阶段决策过程及实例 8.2 动态规划的基本概念和
基本方程 8.3 动态规划的最优性定理 8.4 动态规划与静态规划关系
综述
动态规划是运筹学的一个分支，是解决多 阶段决策过程最优化问题的一种数学方法。
该方法是由美国数学家贝尔曼(R.Bellman)等 人在本世纪50年代初提出的。
他们针对多阶段决策问题的特点，把多阶段 决策问题变换为一系列互相联系单阶段问题，然 后逐个加以解决。
1
2
3
始点
5
B1
6 3
A
4 B2 4 6
2
5
B3 6
C1
1 2
2
C2 2
3
C3
3
4 终点
D1 2
D2 3
E
4
D3
2、状态
5
B1
6 3
A 4 B246
25
B3 6
C1
1 2
2
C2 2
C3 3 3
D1 2
D2 3 E 4
D3
各个阶段开始时所处的自然状况和客观条件称为
状态,描述了研究问题过程的状况(称不可控因素).
一些与时间没有关系的静态规划（如线性 规划，非线性规划）问题，只要人为地引进 “时间”因素，也可把它视为多阶段决策问题， 用动态规划方法去处理。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2013-7-22 20
三、最优化原理 作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状 态和决策如何，对该状态来说，以后的所有决 策必定构成最优子策略。就是说，最优策略的 任意子策略都是最优的。
2013-7-22
21
用逆序法列表 k=n=5 时，f5(v10)＝0 k=4，递推方程为
阶段2
本阶段始点 （状态）
B1 B2 B3 B4
本阶段各终点（决策）
C1 2+12=14 4+12=16 4+12=16 7+12=19 C2 1+11=12 7+11=18 8+11=19 5+11=16 C3 6+11=17 2+11=13 3+11=14 1+11=12
到E的最 短距离 12 13 14 12
C1 C2 C3
8+10=18 6+6=12 7+10=17 5+6=11 1+10=11 6+6=12
12 11 11
D2 D2 D1
分析得知：如果经过C1，则最短路为C1-D2-E； 如果经过C2，则最短路为C2-D2-E； 如果经过C3，则最短路为C3-D1-E。
2013-7-22 6
第二阶段：有4个始点B1,B2,B3,B4 ，终点有C1,C2,C3 。对始点 和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短 路径问题： 表-3
xk Dk ( sk )
(8-4)
2013-7-22
18
连乘形式(vj≠0) ： VK VK ( sk , xk , xk 1 , , xn )
vk ( sk , xk ) VK ( sk＋1 , xk 1 , , xn ) v j ( s j , x j ) Vn
j =k n 1
2013-7-22 19
对于可加性指标函数，上式可以写为
f k ( sk )
d k Dk ( sk )
opt
{vk ( sk , xk } f k 1 ( sk 1 )}
k 1,2,, n
上式中“ opt”表示“ max”或“ min”。对于可乘性指标函数， 上式可以写为
f k ( sk )
动态规划求解可分为三个步骤：分解、求解与合并。
2013-7-22 12
例2 资源分配问题 设有某种机器数台，用于完成两类工作A，B。由于机 器使用后有一定的损坏率，所以每年初的机器数量是变化 的；A、B两项工作产生的收益也不同。如何合理的分配机 器的使用，可使得三年的总收益最大? 假设第k年年初完好机器数是SK，用于A生产的机器数 是XK，则用于B生产的机器数是（SK- XK）；
f k ( sk )
d k Dk ( sk )
opt
{Vk ,n ( sk , Pk ,n )}
（Opt＝optimization 表示“max”或“min”
2013-7-22
17
动态规划要求过程指标满足递推关系 ，即
Vk (sk , xk , xk 1,, xn ) Vk [v(sk , xk ),Vk 1 (sk 1, xk 1,, xn )]
每个阶段都要进行决策,目的是使整个过程的决策 达到最优效果
2013-7-22
10
动态规划问题具有以下基本特征
1. 问题具有多阶段决策的特征。阶段可以按时间划 分，也可以按空间划分。
2. 每一阶段都有相应的“状态”与之对应。 3. 每一阶段都面临一个决策，选择不同的决策将 会导致下一阶段不同的状态，同时，不同的决策将会 导致这一阶段不同的目标函数值。 4. 每一阶段的最优解问题可以递归地归结为下一 阶段各个可能状态的最优解问题，各子问题与原问题 具有完全相同的结构。能否构造这样的递推归结，是 解决动态规划问题的关键。这种递推归结的过程，称 为“ 不变嵌入”。
12 B1 4 14 A 3 2 B3 3 2 6 1 11 7 2 4 8 3 1 12 C1 6 7 5 D2 6 6 6 8 10 D1 10
13 4 B2
0 E
C2
C3
11 1
14 7 5
B4
12
以上过程，仅用了22次加法，计算效率远高于穷举法。
2013-7-22 9
动态规划是用来解决多阶段决策过程最优化的一种 方法。 多阶段决策：是动态决策问题的一种特殊形式； 系统的动态过程可以按照时间等进程分为状态相互 联系 而又相互区别的各个阶段；
2013-7-22
4
讨论：
1、求从A到E的最短路径问题，可以转化为四个性质完全
相同，但规模较小的子问题，即分别从Di 、Ci、Bi、A到 E的最短路径问题。 第四阶段：两个始点D1和D2，终点只有一个； 阶段4
本阶段始点 （状态） 本阶段各终点（决策） 到E的最短距离 本阶段最优终点 （最优决策)
连和形式：
(8-2)
VK VK (sk , xk , xk 1 ,, xn ) vk (sk , xk）＋VK (sk＋1 , xk 1 ,, xn ) v j (s j , x j） Vn
n 1 j k
(8-3)
最优指标函数是
f k (sk ) Opt {vk (sk , xk } f k 1 (sk 1 )}, k 1,2,, n
xk Dk ( sk )
opt
{vk ( sk , xk } f k 1 ( sk 1 )}
k 1,2,, n
上式称为动态规划最优指标的递推方程，是动态规划的基本方 程。 终端条件：为了使以上的递推方程有递推的起点，必须要 设定最优指标的终端条件，即确定最后一个状态n下最优指标 fn(sn)的值。
B 2 1 1 6 4 A 3 2 3 B2 7 2 C2 7 5 6 E
C 1
6Hale Waihona Puke 84D 1
10
4
B3 7 3
8 C3 1
1 6
D 2
5
4
2013-7-22 3
用穷举法的计算量:
如果从A到E的站点有k个，除A、E之外每站有3个位置则
总共有3k-1×2条路径； 计算各路径长度总共要进行 (k+1) 3k-1×2次加法以及 3k-1×2-1次比较。随着 k 的值增加时，需要进行的加法和比 较的次数将迅速增加； 例如当 k=20时，加法次数为 4.2550833966227×1015 次， 比较 1.3726075472977×1014 次。若用1亿次/秒的计算机计 算需要约508天。
运筹学
OPERATIONS RESEARCH
2013-7-22
1
第八章
§1
动态规划
多阶段决策最优化问题举例
§2
§3
基本概念、基本方程与最优化原理
离散确定性动态规划求解
§4
§5
离散随机性动态规划求解
一般数学规划模型的动态规划解法
2013-7-22
2
§1 多阶段决策过程最优化问题举例
例1 最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最 短路径。
f 4 ( s 4 ) min {v 4 ( s 4 , x4 ) f 5 ( s5 )}
2013-7-22 11
5 . 状态具有无后效性 当某阶段状态确定后，此阶 段以后过程的发展不受此阶段以前各阶段状态的影响。
动态规划基本原理是将一个问题的最优解转化为求子问题的最 优解，研究的对象是决策过程的最优化，其变量是流动的时间 或变动的状态，最后到达整个系统最优。 基本原理一方面说明原问题的最优解中包含了子问题的最优解， 另一方面给出了一种求解问题的思路，将一个难以直接解决的 大问题，分割成一些规模较小的相同子问题，每一个子问题只 解一次，并将结果保存起来以后直接引用，避免每次碰到时都 要重复计算，以便各个击破，分而治之，即分治法，是一种解 决最优化问题的算法策略。
从k阶段状态sk出发，选择决策xk所产生的第k阶段指 标，称为k阶段指标函数,记为vk(sk,xk)。
2013-7-22 16
过程指标函数 从k阶段状态sk出发，选择决策xk,xk+1,…,xn所产生的过 程指标，称为k子过程指标函数或简称过程指标函数， 记为 Vk(sk,xk,xk+1,…,xn)或Vk，n为阶段数。 最优指标函数 从k阶段状态sk出发，对所有的子策略，最优的过程指 标函数称为最优指标函数，记为fk(sk)，通常取Vk的最 大值或最小值。
E
10 6 10 6
D1 D2
E E
分析得知：从D1和D2到E的最短路径唯一。
2013-7-22 5
第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点 和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路 径问题： 表-2 阶段3
本阶段始点 本阶段各终点（决策） （状态） D1 D2 本阶段最优终点 到E的最短距离 （最优决策)
表10-4
阶段1 本阶段始 点(状态) B1 A 4+12=16 本阶段各终点（决策） B2 3+13=16 B3 3+14=17 B4 2+12=14 到E的最 短距离 14 本阶段最优终 点(最优决策)
B4
最后，可以得到：从A到E的最短路径为A B4 C3 D1 E
2013-7-22
8
以上计算过程及结果，可用图2表示，可以看到，以上方法不 仅 得到了从A到D的最短路径，同时，也得到了从图中任一点到E 的最短路径。
本阶段最优终点 （最优决策)
C2 C3 C3 C3
分析得知：如果经过B1，则走B1-C2-D2-E； 如果经过B2，则走B2-C3-D1-E； 如果经过B3，则走B3-C3-D1-E； 如果经过B4，则走B4-C3-D1-E。