优化模型动态规划.ppt.ppt

第八章动态规划问题及求解
多阶段决策问题
动态规划是解决这样一类最优化问题的专门计算方法,这类问题允许把它的过程(求解)分解为一系列的单级过程(步骤)。
最优化原理:达到系统某种状态的过程无论是怎样的,以这个状态为初始状态的剩余过程的求解仍是最优的规划。也就是说,当系统处于第
个状态时,只要最优
规划剩余的
个过程,便可逐步求出
时的
最优解。
为了方便讨论动态规划的求解过程,我们把动态规划
问题化分为下面几个过程:
阶段(stage):把问题恰当的分为若干个相互联系
的阶段;
(State):它是表示某段的出发位置,是某支路
的起点,又是前一段某支路的终点。第
个阶段的状态
变量
应该包含前各阶段决策过程的全部信息,且之后
作出的决策与之前的状态和决策无关。
(Decision):是指某阶段初从给定的状态出发
决策者所作出的选择,决策变量
表示第
个阶段
状态为
时对方案的选择。决策允许范围记为
,
(Policy):即决策序列。
个阶段动态规划问题
的策略可记为
,当
时,
表示从
阶段开始到最后的决策
序列。
:表明后一阶段和前一阶段之间的
阶段状态和决策给定之后,第
关系。当第
阶段状态就确定了,记为
:阶段指标函数----对应于某一阶段状态和从该
状态出发的决策的某种指标度量。第
阶段指标函数记
为
;过程指标函数----从某阶段开始到最后
过程的指标度量。记为
,最优策略值记为
:过程指标函数是各阶段指标函数
的函数。
动态规划问题的解法
,负责4个要害部位,对每个部位可分别派2到4人巡逻,由于巡逻人数不同,各部位预期在一段时间内可能造成的损失也不一样,具体数字见下表。问该卫队应往各部位分别派多少人巡逻才能使预期损失最小?
A
B
C
D
2人
3人
4人
18
14
10
38
35
31
24
22
21
34
31
25
把12人派往4个部位看作4个阶段(k=1,2,3,4),每个阶段初可派遣的人数是前面阶段决策的结果,也是本阶段决策的依据。用表示第
个阶段的状态变量,用
表示第
个阶段的决策变量(即在该阶段派出的
人数,显然
),各阶段可允许的决策集合
状态转移方程为
用
表示第
个阶段派出的巡逻人数为
时,在该部位的预期损失值
过程指标函数
由于
用
表示从第
个阶段到结束时预期损失值,
(1)先考虑D部位
(2)先考虑C,D部位
由于
,所以
(3)先考虑B,C,D部位
由于
,所以
(4)先考虑A,B,C,D部位
由于
,所以
由此可见,A,B,C,D四个部位应分别派4人,2人,
2人,4人,预期损失值为97。

解:从A到G分六个阶段:A->B,B->C,C->D,D->
E,E->F,F->G
(1)第六阶段F->G最短路
例2
(2)第五阶段E->G最短路
(3)第四阶段D->G最短路
(4)第三阶段C->G最短路
(5)第二阶段B->G最短路
(6)第一阶段A->G最短路
所以最短路是:A->B1->C2->D1->E2->F2->G,
最短路长为18。