动态规划问题.pptx

动态规划是1951年由美国学者R. Bellman等人在解决所谓多阶段决策问题时提出的一种优化方法,
该方法在工程技术、企业管理和军事等方面多有着广泛的应用。
许多问题用动态规划方法解决,比其他常用方法如线性规划或非线性规划等方法更为有效。特别是对于离散的问题,由于目标函数或约束条件难以用解析的方式表达时,此时,动态规划方法就成为非常有效的工具。
动态规划模型的分类一般根据其状态的性质或多少来分类。动态规划有离散确定型、离散随机型、连续确定型、连续随机型、一维动态规划模型和多维动态规划模型之分。
这里主要介绍一维离散确定型动态规划模型。
第一节多阶段决策过程及其问题举例
一、多阶段决策过程
在生产决策中,若某一活动过程可以分为若干相互联系的阶段,每一阶段又需要作出决策,从而使整个过程达到最好的活动效果。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程(如图5—1所示)就称为多阶段决策过程,这种问题就称为多阶段决策问题。
1
2
n
……
状态
决策
状态
状态
状态
状态
决策
决策
图5—1
二、多阶段决策问题举例
最短路问题
如图5—2,给定一个线路网络,两点之间连线上的数字表示两点间的距离(或费用、时间等),试求一条由A到E的线路,使总距离为最短(或费用最小、时间最少等)。
B1
A
C1
B2
C3
E
D1
C4
C2
D3
D2
3
5
3
1
6
8
6
6
7
3
5
8
3
3
8
4
2
3
2
图5—2
生产与存储问题
假设某厂某车间每月底都要供应总装车间一定数量的部件,但由于生产条件的变化,该车间每月生产单位部件所耗费的工时不同,各月份的生产量于当月的月底以前,全部要存入仓库以备后用。已知总装车间各个月份的需求量以及在加工车间生产该部件每单位数量所需工时如表5—1所示。
设库存容量H=9,开始时库存量为2,期终库存量为0,现要求制定一个半年逐月生产计划,使得既满足需求和库存容量的限制,又使总耗费的工时最少。
月份k
0
1
2
3
4
5
6
月需求量dk
0
8
5
3
2
7
4
单位工时ak
11
18
13
17
20
10
第二节动态规划的基本概念与基本方程
一、动态规划的基本概念
(1)阶段
对于多阶段决策问题,按问题的特点可将其划分为若干个相互联系的阶段,阶段就是问题所处的地段或时段。描述阶段的变量称为阶段变量,通常用k表示。
,阶段为问题所处的地段,且k=1,2,3,4;
,阶段为问题所处的时段(月),且k=0,1,…,6;
(2)状态
状态就是在各阶段开始时问题的自然状况。
,各阶段的起始位置就是该问题的状态;
,各阶段开始(月初)时的库存量即为问题的状态。
描述过程状态的变量称为状态变量。
通常用Sk表示第k阶段的状态集合,用sk表示第k阶段的某一具体的状态。
,S2 ={B1,B2}={s2(1),s2(2)},S3={C1,C2,C3,C4};
,S0={2},S1={8,9},S2={5,6,7,8,9}。
对于动态规划,其状态必须满足两个条件,即:①能描述问题的过程;②满足无后效性。
所谓能描述问题的过程就是当各阶段的状态确定之后,整个问题的过程就已确定。
所谓无后效性是指如果某阶段的状态给定以后,则在这阶段以后过程的发展不受这阶段以前各状态的影响,即过程的过去历史只能通过当前的状态去影响它的未来的发展,当前的状态是以往历史的一个总结。
(3)决策
决策表示当过程处于某一阶段的某一状态时,为确定下一阶段的某一状态所作出的决定或者选择。
,决策就是一种可行路径的选择。
,决策就是月初在某一库存量情况下生产量的决定。
描述决策的变量称为决策变量。
通常用uk(sk)表示第k阶段在状态为sk时所作出的决策,用Dk(sk)表示第k阶段在状态为sk处所有可行决策构成的决策集合,显然有uk(sk)∈Dk(sk)。
,D1(A)={B1,B2}={u1(1)(A),u1(2)(A)},D2(B1)={C1,C2,C3};
,D0(2)={6,7},D1(8)={5,6,7,8,9},D1(9)={4,5,6,7,8}等。
(4)状态转移方程
描述相邻两阶段状态与决策相互关系的方程称为状态转移方程。不同的问题,这种关系的形式是不同的,对于某一具体问题,状态转移方程的形式一般也是确定的。
状态转移方程的一般形式可描述为sk+1=Tk(sk,uk),它描述了由k阶段到k+1阶段的状态转移规律,Tk