文档介绍：管理运筹学
谢家平博士副教授
研究领域:系统建模与优化、生产与运作管理、物流与供应链管理
讲授课程:管理运筹学、管理系统工程、生产运作管理、
供应链管理、国际物流管理、企业资源计划
单位:上海财经大学国际工商管理学院供应链管理研究中心
E-mail:jiaping_xie@
电话:55036936(H) 65903541(O)
2
第八章动态规划
动态规划Dynamic Programming
研究多阶段决策的最优化问题的方法。
多阶段决策问题含有一个描述过程时序或空间演变的阶段变量,将复杂问题划分成若干阶段,根据“最优性原理”,逐段解决而最终实现全局最优。
经济、管理、工业生产、工程技术等领域,许多问题可归结为多阶段决策问题。
一些用线性规划、非线性规划处理有困难的问题,往往可以用动态规划方便地求解。
动态规划是美国运筹学家贝尔曼()等人1959年提出的。
3
第一节多阶段决策问题
多阶段决策:
经济管理决策中,有些管理决策问题可以按时序或空间演变划分成多个阶段,呈现出明显的阶段性;
于是可把这类决策问题分解成几个相互联系的阶段,每个阶段即为一个子问题;
原有问题的求解就化为逐个求解几个简单的阶段子问题;
每个阶段的决策一旦确定,整个决策过程也随之确定,此类问题称为多阶段决策问题。
例如:
企业生产物流:可分为物料供应、生产制造、分销零售等阶段。
最短路问题:可以按空间顺序划分阶段。
一、问题的提出
4
第一节多阶段决策问题
从生产厂Q到某公司T选择那条路线,使总运费最低(路程最短)?
最短路问题
Q
T
A1
A2
A3
B1
B2
B3
C1
C1
2
4
3
7
4
6
4
2
4
4
2
5
1
4
6
3
3
3
3
4
生
产
商
某
公
司
出
口
港
进
口
港
城
市
阶段1
阶段2
阶段3
阶段4
5
第一节多阶段决策问题
这是一个多阶段决策问题,它可分为四个阶段:
第一阶段:从Q(制造厂)到A(出口港);
第二阶段:从A(出口港)到B(进口港);
第三阶段:从B(进口港)到C(城市);
第四阶段:从C(城市)到T(某公司)。
每个阶段选取的路线不同,对应从Q到T就有一系列不同的运输路线:
从始点Q到终点T共有3×3×2×1=18条不同路线
现在的问题是如何选择一条费用最小的路线?
6
第一节多阶段决策问题
最短路径:Q→ A3→ B1→ C1→T
二、动态规划的标号法
Q
T
A1
A2
A3
B1
B2
B3
C1
C2
2
4
3
7
4
6
4
2
4
4
2
5
1
4
6
3
3
3
3
4
阶段1
阶段2
阶段3
阶段4
0
3,T
4,T
4,C1
7,C2
6,C1
11,B1 ,B2
8,B1
8,B1
11,A3
7
第一节多阶段决策问题
最短路的基本特征
从始点Q到终点T 的最短路径:Q→ A3→ B1→ C1→T,则从中点A3 到终点T 的最短路径必为: A3→ B1→ C1→T, 从中点B1 到终点T 的最短路径必为:B1→ C1→T,…。
推广:从始点Q到终点T 的最短路径: Q → S1→ S2→…→ Sk→ Sk+1→…→ Sn→T,则从中点Sk 到终点T 的最短路径必为: Sk→ Sk+1→…→ Sn→T。
三、多阶段决策的基本特征
8
第二节动态规划原理
阶段(stage)
处理多阶段决策,需将全过程划为若干阶段,每个阶段进行一次抉择。
各阶段按一定顺序联接在一起组成统一的整体。
用k表示阶段变量。
阶段编号
顺序编号
逆序编号
一、动态规划的基本概念
9
第二节动态规划原理
状态(state)
状态表示过程发展中某阶段的起始状况。
过程的发展可以通过各阶段状态的演变来描述。
状态可用一个变量来描述,称为状态变量,用Sk表示。
选取的状态变量必须满足无后效性。
某阶段的状态给定后,则过程未来发展不受该阶段以前各阶段状态的影响。
第 k 阶段可能有若干状态,用Sk 表示阶段k的状态集合,
sk(i)表示第k阶段的第 i 个状态。
10
第二节动态规划原理
决策(decision)
从上一阶段某状态演变到下一阶段某状态要作一次选择,称为决策。
用变量xk(sk)表示第k阶段状态为sk时的决策,称为决策变量,简记xk
决策变量的取值被限制在某一范围内,此范围称为允许决策集合Xk(sk)