第6章-动态规划.ppt

第三部分 动态规划
第一章 动态规划的基本方法
§1 动态规划的研究对象
特征：包含有随时同变化的因素和变量，整个过程可以分为若干个相互联系的阶段，而且每个阶段都要做出决策。
1
应用：
企业管理：动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等。
2
多阶段决策过程及实例
在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干相互联系的阶段。在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果，因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成了一个决策系列，因而也就确定了整个过程的一条活动路线，这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程（如图1所示）就称为多阶段决策过程，也称序贯决策过程，这种问题就称为多阶段决策问题。
3
n
状态
1
决策
2
决策
决策
状态
状态
状态
状态
图1 链状结构的多阶段过程
4
多阶段决策问题很多，现举例如下：
例1：最短路问题
如图2，给定一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），试求一条由A到G的铺管线路，使总距离为最短（或总费用最小）。
5
A
B2
3
B1
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
F1
F2
G
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
4
2
2
2
1
3
3
5
5
2
6
6
4
3
图2
6
例2：机器负荷分配问题
某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为
这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终时完好的机器就为au，0<a<1。在低负荷下进行生产时，产品的年产量和投入生产的机器数量u2的关系为
7
这时，机器的年完好率为b，0<b<1 。
假定开始生产时完好的机器数量为s，要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高？
8
§2 动态规划的基本概念
一、阶段和阶段变量
在多阶段决策过程中，为了表示决策和过程的发展而引入阶段的概念，一个阶段就是需要作出决策的子问题。通常阶段是按照决策进行的时间或空间上的先后顺序划分的，用阶段变量k表示。
9
二、状态和状态变量 状态表示某一阶段初所处的位置或状况，通常一个阶段包含若干个状态，描述状态的变量称为状态变量。常用sk表示第k阶段的某一状态。所有状态变量组成的集合，称为状态变量集合。常用Sk表示第k阶段的状态变量集合。三、决策和决策变量 决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。描述决策的变量，称为决策变量。常用xk（sk）表示第k阶段当状态处于sk时的决策变量，在实际问题中，决策变量的取值往往限制在某一范围内，此范围称为允许决策集合，通常用Dk（sK）表示第k阶段的允许决策集合，显然有：
10