第7章 动态规划

最优路径问题 资源分配问题 排序问题 投资问题 装载问题 生产计划与库存问题 生产过程的最优控制等
动态规划
模型分类
离散确定型 离散随机型 连续确定型 连续随机型
§1 多阶 段决 策过 程的 最优
化
多阶段决策问题
(Multi-Stage decision process)
决策u1 决策u2
决策uk
32
维护费
8 8 9 9 10 6 6 8 8 10 5 6 8 9 5 5 6 4 54Βιβλιοθήκη 新设备购置费 5050
52 52 55 60
旧设备折价
20 15 10 5 2 30 25 20 15 10 31 26 21 15 33 28 20 35 30
40
§1 多阶 段决 策过 程的 最优
化
3)连续生产过程的控制 问题：一般化工生产过程中，
本章 内容
多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划模型的建立与求解 动态规划在经济管理中的应用 马氏决策规划简介
创始时间 创始人
上个世纪50年代
美国数学家贝尔曼 （Richard. Bellman)
是运筹学的一个主要分支 是解决多阶段决策过程的最优化的一
种方法多阶段决策过程： 多阶段决策过程的最优化的目标： 达到整个活动过程的总体效果最优 •主要用于解决：
不过，实际中尚有许多不包含时间 因素的一类“静态”决策问题，就其本 质而言是一次决策问题，是非动态决策 问题，但是也可以人为地引入阶段的概 念当作多阶段决策问题，应用动态规划 方法加以解决。
§1 多阶 段决 策过 程的 最优
化
4）资源分配问题：便属于这类静 态问题。如：某工业部门或公司，拟对 其所属企业进行稀缺资源分配，为此需 要制定出收益最大的资源分配方案。这 种问题原本要求一次确定出对各企业的 资源分配量，它与时间因素无关，不属 动态决策，但是，我们可以人为地规定 一个资源分配的阶段和顺序，从而使其 变成一个多阶段决策问题(后面我们将 详细讨论这个问题)。

第七章– 最优控制理论
Optimal Control Theory
同济大学汽车学院：赵治国 教授 Prof. Zhiguo Zhao School of Automotive Studies, Tongji University Tel：69589117(O) E-mail: Zhiguozhao@
*
x(t ) x* (t )上的变分等于零，即 J [ x* (t )] 0
§7－3 泛函与变分的基本概念
证明：对于任意给定的
x(t ) 来说，J [ x* (t ) x(t )]是实变量 的 * * J [ x ( t )] 函数。泛函 在 x (t ) 达到极值，即函数 J [ x (t ) x(t )] 在 0 时达到极值，所以它的导数在 0 时应为零，即
二. 最优控制问题的一般提法 用数学语言描述最优控制问题，应包括以下几个方面的内容： 1. 受控系统的数学模型 用状态方程描述：x (t ) f [ x(t ), u (t ), t ] 2. 受控系统的始端和终端条件，即状态方程的边界条件 对最优控制问题始端条件通常是已知的：x(t0 ) x0 终端条件可以用一个目标集表示：
J J [ x()] J [ x(t ) x(t )] 中的 x(t ) 应理解为某一特定函数的整体，而不是对应于 的
dx(t ) J ( x (t ) t )dt 0 dt 1 5 2 J (t t )dt 0 6 2 1 e J (e 2t tet )dt 1 0 2
1 2
若 x (t ) t 有
t x ( t ) e 若 有
§7－3 泛函与变分的基本概念
2.泛函自变量的变分 泛函 J [ x (t )] 的自变量函数 x (t ) 与标称函数 x* (t )之间的差值函数

当∆t很小时，有

t t
t
Lx, u, t d t Lx, u, t t
J x, t min
*
min
uU

uU

tf
t0
Lx, u, t d t Φ xt f
tf t t

t t
t
Lx, u, t d t
Lx, u, t d t Φ xt f
P1 11
7
P2 4 2
P3 4 4
12 A 4 8 Q1
4 3 2 2 Q3 B
5 Q2
第一段：P1、Q1的前站是始发站A。显见从
A到B的最优值为12，故得最优路线为AQ1P2Q3B。
综上可见，动态规划法的特点是： 1) 与穷举算法相比，可使计算量大大减少。如
上述最优路线问题，用动态规划法只须做10次
J x, t min Lx, u, t t J xt t , t t
* * uU


(8)
* J x , t J x, t * * J x x, t t J x, t t (12) x t x * T
A城出发到B城的行车时间最短。
P1 3 A 4 Q1 1
7
P2
2
P3 4
4
6 8 2 Q2
3 3 3
2 Q3 4
2
B
现将A到B分成四段，每一段都要作一最优决 策，使总过程时间为最短。所以这是一个多段最 优决策问题。 由图2可知，所有可能的行车路线共有8条。 如果将各条路线所需的时间都一一计算出来，并 作一比较，便可求得最优路线是AQ1P2Q3B，历时 12。这种一一计算的方法称为穷举算法。这种方 法计算量大，如本例就要做3×23=24次加法和7次 比较。如果决策一个n段过程，则共需(n-1)2n-1次 加法和(2n-1-1)次比较。可见随着段数的增多，计 算量将急剧增加。

运筹学概念整理名解5、简答4、建模与模型转换2、计算5~6第1章线性规划与单纯形法(计算、建模:图解法)线性规划涉及的两个方面：使利润最大化或成本最小化线性规划问题的数学模型包含的三要素：一组决策变量：是模型中需要首确定的未知量。

一个目标函数：是关于决策变量的最优函数，max或min。

一组约束条件：是模型中决策变量受到的约束限制，包括两个部分：不等式或等式；非负取值（实际问题）。

线性规划问题(数学模型)的特点：目标函数和约束条件都是线性的。

1.解决的问题是规划问题；2解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；3解决问题的约束条件是多个决策变量的线性不等式或等式。

图解法利用几何图形求解两个变量线性规划问题的方法。

求解步骤：第一步：建立平面直角坐标系；第二步：根据约束条件画出可行域；第三步：在可行域内平移目标函数等值线，确定最优解及最优目标函数值。

LP问题的解：（原因）唯一最优解、无穷多最优解（有2个最优解，则一定是有无穷多最优解）无界解（缺少必要的约束条件）、无可行解（约束条件互相矛盾，可行域为空集）标准形式的LP模型特点：目标函数为求最大值、约束条件全部为等式、约束条件右端常数项bi全部为非负值，决策变量xj的取值为非负●线性规划模型标准化（模型转化）(1) “决策变量非负”。

若某决策变量x k为“取值无约束”(无符号限制)，令：x k= x’k–x”k，(x’k≥0, x”k≥0) 。

(2) “目标函数求最大值”。

如果极小化原问题minZ = CX，则令Z’ = – Z，转为求maxZ’ = –CX 。

注意：求解后还原。

(3) “约束条件为等式”。

对于“≤”型约束，则在“≤”左端加上一个非负松弛变量，使其为等式。

对于“≥”型约束，则在“≥”左端减去一个非负剩余变量，使其为等式。

(4) “资源限量非负”。

若某个bi < 0，则将该约束两端同乘“–1” ，以满足非负性的要求。