动态规划模型与实验[管理资料]
第七章 动态规划模型与实验
一个系统依据某种方式分为许多个不同的阶段,这些阶段不仅有着次序推移性,而且相互间有着依赖和影响。这种能分成阶段推移的系统叫做动态系统。动态规划是解决多阶段决策过程最优化的一种数学方法。动态规划的一个显著特点在于具有明确的阶段性,整个系统按某种方式可分为若干个不同的阶段,在每个阶段由若干种不同的方案可供选择。这样,在多阶段决策过程中,每个阶段决策的选择,不仅要依据次序来考查某阶段的效果外,而且更要顾及此决策对以后各阶段决策的影响,特别是对以后各个阶段决策的影响。系统最优决策问题要求在系统每个阶段可供的多种方案 (决策) 中,选择一个合适的决策,使整个系统达到最优的效果。整个过程分为多阶段的决策过程。各个阶段所做的决策形成确定整个系统的决策序列,称这样的决策序列为系统的一个策略。对应某一确定的策略,整个系统依据某种数量指标衡量其优劣的决策。多阶段决策过程就是在所有允许策略集合中。确定一个达到最优指标的最优策略。这种衡量系统的指标一般取最大值或最小值的策略。因此,多阶段决策过程也是一个可以构成多个变量的最优化问题。一个系统能分为多阶段的决策过程,有时需要数学技巧和艺术来划分,动态规划就是解决此类多阶段决策过程的最优化方法。
?7.1动态规划的基本原理
实际生活的问题,通过构造数学模型,具有特殊的动态系统过程,将基于某种方式把整个过程分成若干个互相联系的阶段,在其每个阶段都需要作出合适决策,从而使整个过程达到最佳效果。同时,各个阶段决策的选择依赖于该阶段的状态以及前或后阶段的变化。各个阶段决策确定后,组成一个决策序列,从而形成了整个过程具有前后关联的链状结构的多阶段决策过程,称为序贯决策过程。由此,动态规划求解首先关键在于如何将实际问题构造成能形成多阶段的系统,并且在各个阶段能作出序贯性的最佳决策,以使在序贯决策的状态推移进程中达到整个系统的最优决策。
例7.1 能分成阶段的最短路问题。图7.1是一个路线网络图,连线上的数字
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示两点之间的距离(或费用),要求寻找一条由A到E的路线,使距离最短(或费用最省)。
9 B C 115 9 5 6 D 18 7 6 7 A B C E225 4 5 8 9 5 11 D 210 B C 33
图7.1
对于这样一个比较简单的问题,可直接使用枚举法列举所有从A到E的路线,共14条,然后,根据每条路线的长度(或费用),确定出所应走的路线(费用)最短(少)。
直观的思想,如果已找到由A到E的最短路线是A—?B—?C12
—?D—?E(记作L),那么当寻求L中的任何一点(如C)到E22的最短路时,它必然是L中子路线C—?D—?E(记作L)。否则221若D到E的最短路是另一条路线L,则把AB—?C与L连—?22 122接起来,就会得到一条不同于L的从A到E的最短路。根据此特性,可以从最后一段开始,用逐步向前递推的方法,依次求出路段上各点到E的最短路,最后得到A到E的最短路。上述这种由系统的作后阶段逐段向初是始阶段求最优的过程称为动态规划的逆推解法。该过程揭示了动态规划的基础思想,为使动态规划的思想和方法数学上描述。下面先引入动态规划中基本概念与最优目标函数的建立。
(1)分阶段 把所给的系统,适当地依据具体情况分成若干个相互联系的阶段,描述阶段的变量称为阶段变量,常用k表示,并将各个阶段按顺序或逆序加以编号,如例7.1可分为5个阶段来求解,k=1,2,3,4,5。
(2)状态 状态表示系统在某一阶段所处的位置,自然状况或客观条件。一个阶段系统会存在若干个可能的状态。在例7.1中,状态就是某阶段的出发位置,它既是该阶段某之路的起点,又是前一阶段某之路的终点,一个阶段有若干个状态,第一阶段有一个状态就是初始位置A,第二阶段有三个状态,即使集合{B,B,B},一般第k123阶段的状态就是第k阶段所有始点的集合。
描述过程状态的变量称为状态变量,常用S表示第k阶段的所有k
可能状态变量的集合,其元素为s可以是数,数组或向量。如例7.1k
中第三阶段有三个状态,则s可能取三个值,即C,C,C,并且S={C,k12331C,C} 称为第三阶段的可达状态集合。 23
(3)决策 决策表示当系统处于某一阶段的某个状态时,可以作出不同的选择,确定下一阶段的状态,这种决定称为决策。描述决策的变量称为决策变量,常用d(s)表示第k阶段当状态处于s时的决kkk策变量,它是状态变量的函数。而用D(S) 表示相应的决策变量的k k
函数集,即有d(s)?D (S)。如在例7.1第二阶段中,从状态B出k kkk2发,其允许决策集合为D(B)={C,C,C},某一阶段的状态变量22123
及决策变量的值取定之后,那么下一阶段的状态随之确定。例如选取的点为C,则C是状态B在决策d(B)作用下的一个新的状态,记22121
作d(B)= C,下一阶段的状态类似地对上阶段的状态和决策变量的212
依赖关系可用状态转移方程表示:
s =T (s ,d (s ) ) (7.1)k+1kkkk
(4) 策略 由系统各阶段确定的决策所形成的决策序列称为策略。从初始状态s出发由系统的所有n个阶段的决策所形成的策略成为全1
过程策略,记为:
P(s )={d (s ),d (s ),…,d (s )} (7.2),1n11122n n
由系统的第k个阶段出发的后面n – k +1个阶段的决策过程称为全过程的后部子过程,相应的策略称为后部子过程策略,记为
P (s )={d (s ),d (s ),…,d (s )} (7.3),knkkkk+1k+1n n
所有可供选择的策略集合称为策略集合,用P表示,从允许策略集合中找出达到最优效果的策略称为最优策略。 (5)状态转移方程 状态转移方程是确定过程由一个状态到另一个状态的演变过程。若给定第k阶段状态的演变过程,并且若该阶段的决策变量d一经确定,第k+1阶段的状态变量s也就完全确定,kk+1
这种对应关系为:
s=T(s,d(s)) k+1k k k k
所描述了由第k个阶段到第k+1个阶段的状态转移规律,称为状态转移方程。T 称为第k阶段的状态转移系数。如例7.1中,状态转移方k
程为
s =d(s ) k+1 k k
(6) 阶段收益 系统某一阶段的状态一经确定,执行某一决策所得的效益称为阶段效益,它是整个系统总收益的一部份。阶段效益是阶段状态和决策变量的函数,反映该阶段的价值与目标。对第k阶段的某一状态s执行某一决策d(s)的阶段效益可用r(s ,d(s))来表k k k k k k k 示。在例7.1中的阶段效益为走完一段路程所花费的距离。
(7) 指标函数和最优值函数 系统执行某一策略所产生效果的优劣可用数量指标来衡量,这样的数量指标是整个系统总效益的反映,它是各个阶段状态和决策的函数,称为指标函数。它是定义在全进程和所有子进程上确定的数量函数,记
F(s, p ),i=n,n-1,…,1 (7.4),, knkkn
表示从阶段k的某一状态s 出发的后部子进程上的指标函数,其中k
p表示从状态s出发的一个子策略,最优策略下指标函数的指标为,knk
最优策略指标,记为
(7.5)f(s),F(s,p)optkkk,nkk,n,pPk,nk,n
其中P表示由状态S出发的所有允许子策略集合,“opt”为英文k, nk
Optimization(最优)的缩写,可以依题意取min或max。
由上述指标函数的定义,可得指标函数(例7.1的指标函数注记r(s ,d(s))表示第k 阶段中点s 到d(s)的距离)。 k k k k k k k
Fk.n(sk),r(s,d(s)),F(s)k,n,n,1,?,1kkkkk,1,nk,1
其中
s,T(s,d(s)),j,k,k,1,?,n,1 (7.6)j,1jjjj
而最优策略指标为
opt,, f(s),r(s,d(s)),f(T(s,p)),k,n,n,1,?,1 (7.7)kkkkkkk,1,nkkk,1,n{d(s)}kk
在例7.1中显然有
f(s) = 0 (7.8)n+1n+1
称为边值条件,动态规划的求解对k=n, n-1,„,1由(7.7)式求最优策略指标的过程。
一般地对多数指标函数的形式取(7.6)式,而最优策略指标取形
如(7.7)式,以求和形式出现,另一种常用形式是的各阶段的指标函数为乘积,即
n
F(s,p),r(s,d(s)),r(s,d(s)),F(s,p),k,nkk,njjjjkkkkk,1,nkk,1,n (7.9)j,k
k,n,n,1,?,1
其相应的最优策略指标为
(7.10)opt,,f(s),r(s,d(s)),f(T(s,d(s)),k,n,n,1,?,1kkkkkkk,1,nkk,1kk{d(s)}kk
对更一般的系统来说,指标函数未必是求和或乘积形式,但应具有可分离性,并满足递推关系,一般具有形式
(7.11)F(s,p),,(s,d(s),F(T(s,d(s)),p))k,nkk,nkkkk,1,nkkkkk,1,n
(7.12)optf(s),,(s,d(s),f(T(s,d(s)))kkkkkk,1kkkk{d(s)}kk
在第k阶段,指标函数最优策略指标,即最优值,称为最优值函数,即f(s)。根据上述确定的阶段编号、状态变量、决策变量、状态kk
转移方程以及指标函数,确定例7.1的最短路线,计算步骤如下:
根据最短路线特性,寻找最短路线的方法,将从最后一段开始,用由后向前逐步递推的方法,求出各点到E点的最短路线,最后求得由A点到E点的最短路线。所以,动态规划的方向是从各点逐段向始点方向寻找最短路线的一种方法,见图7.2显示
行进方向
1 2 3 4 5 始点 终点
动态规划寻优途径
图7.2 当k= 4时,由D到终点E只有一条路线,故f(D) = 6,同理,f(D) 14142
= 5。
当k= 3时,出发点有C、C、C三个,若从C出发,则有两个选择,1231一是至D,一是至D,则 12
r(C,D),f(D)5,6,,,,31141 f(C),min,min,11,,,,31r(C,D),f(D)7,5,,31242,,
其相应的决策为d(C)=D,表示由D至终点E的最短距离为11,其3111
最短路线是C?D?E。 11
同理,从C和C出发,则有 23
r(C,D),f(D)6,6,,,,32141f(C),min,min,10 ,,,,32r(C,D),f(D)5,5,,52242,,
其相应的决策为d(C) = D。 322
r(C,D),f(D)8,6,,,,33141f(C),min,min,14 ,,,,33r(C,D),f(D)11,5,,33242,,
且d(C) = D。 333
类似地,可计算当k=2时,有
f(B)= 18 d(B)= C 21212
f(B)= 19 d(B)= C 22222
f(B)= 15 d(B)= C 23232当k=1时,出发点只有一个A点,则
r(A,B),f(B)5,18,,,,1121,,,,f(A),minr(A,B),f(B),min7,17,23 ,,,,12222
,,,,9,15r(A,B),f(B)2323,,,,
且d(A)= B ,于是获得从始点A至终点E的最短距离为15。为11
使找出最短路线,再接计算的顺序推之,可求出最优决策函数序列{d},即由d(A)= B ,d(B)= C ,d(C)= D ,d(D)k1121232242= E,组成一个最优策略。那么最短路线为A?B?C?D?E。122
从上述例7.1的计算过程,可知动态规划的方法比枚举有以下优点:
(1)减少计算量,使用枚举法,要对18条路线比较,即比较运算进行18次,逐阶段累计加法为64次。使用动态规划来计算,比较运算为7次,加法运算16次,可见,动态规划方法比穷举法减少了许多计算量,而且随着规模扩大,计算量将大大地减少。
(2)丰富了计算结果,虽然枚举法执行了较多的运算,其结果只有从起点A到终点E的一个结果,用动态规划方法以较少的运算不仅得到从A至E的最优路线,而且还确定了各中间点到终点E的最优路线。
?7.2 LINGO软件计算动态规划
使用LINGO软件计算上述动态规划问题。
设:A?顶点(城市)1,B?2,B?3,B?4,C?5,C?6,12312C?7,D?8,D?9,E?点(城市)10。本例使用LINGO程序的312
编制动态规划模型如下:
MODEL:
SETS:
! Dynamic programming illustration.
We have a network of 10 cities. We
want to find the length of the shortest route
from city 1 to city 10.;
! Here is our primitive set of ten cities, where
F( i) represents the shortest path distance
from city i to the last city;
CITIES /1..10/: F;
! The derived set ROADS lists the roads that
exist between the cities (note: not all city
pairs are directly linked by a road, and roads
are assumed to be one way.);
ROADS( CITIES, CITIES)/
1,2 1,3 1,4
2,5 2,6
3,5 3,6 3,7
4,5 4,6
5,8 5,9
6,8 6,9
7,8 7,9
8,10
9,10/: D;
! D( i, j) is the distance from city i to j;
ENDSETS
DATA:
! Here are the distances that correspond to the
above links;
D =
5 7 9
9 8
11 7 4
5 10
5 7
6 5
8 11
6
5;
ENDDATA
! If you are already in City 10, then the cost to
travel to City 10 is 0;
F( @SIZE( CITIES)) = 0;
! The following is the classic dynamic programming
recursion. In words, the shortest distance from
City i to City 10 is the minimum over all
cities j reachable from i of the sum of the
distance from i to j plus the minimal distance
from j to City 10;
@FOR( CITIES( i)| i #LT# @SIZE( CITIES):
F( i) = @MIN( ROADS( i, j): D( i, j) + F( j))
);
END
程序第十行,集合CITES表示点,赋值F(i)表示从城市i到最后一个
城市的最短距离。第十五行中集合ROADS(•,•)表示连接城市间的
i弧,而数据D()表示从城市到城市的距离。动态规划的目标函i,jj
ii数,即为从城市到最后城市10的最短距离为所有从城市到城市可j达到路加上从到城市10的最短距离的和的最小值。使用SOLVE求解j
得结果如下,其中F(i)表示第i个(城市)点至最后(城市)终点E的距离。
从上述计算过程,可归纳k阶段与k+1 阶段之间的递推关系
(7.13)opt,,f(s),r(s,d(s)),f(d(s))kkkkkkk,1,nkkd,D(s)kkk
称为动态规划的基本方程,以及边值条件为:
f (s )=0n+1n+1
动态规划方法的基本思想归纳如下:
(1) 归纳出基本的递推关系式和恰当的边值条件,即基本方程。
(2) 在多阶段决策过程中,虽是独立的阶段,但又将当前阶段效益
和未来效益阶段结合起来的一种最优化方法。 (3) 在求解整个系统的最优策略时,由于初始状态是已知的,而每
阶段的决策都有该阶段的函数,所以最优策略经过的各段状态,
便可逐次变递推换得到,从而确定了最优的路线。
例如,在例7.1中,初始状态A已知,上述逐次变换如图7.3。
d(A) d(B) …… d(D)12142
(已知) A B C E 12
图7.3
从而可得最优策略为{d(A),d(B),„,d(D)},相应的最短路12142
线为A?B?C?D?E,计算过程,使用图7.4直观简明地表示,122
图中每节点处上方的方格内的数,表示该点到终点E的最短距离,用直线连接点表示该点到终点E的最短路线,未连线的点表示该点到终点E不是最短路线,(舍去),图中粗线表示由始点A到终点E的最短路线,这种由E点开始从后向前,即从终点至起点求优的过程叫做逆推解法,逆推法不仅求出A到E最优路线,而且确定了任意点到点E的最优路线,如果问题不仅要求确定从点A到点E的最优路线,并要求知道A到其它点的最优路线,可采用从始端逐步向终端求优的顺推解法。
18 11
B C 116
D 123 19 10
A B C E225 16 14
D 2
B C 33
图7.4
?7.3 顺推解法
对例7.1来说,顺推解法以A为始端,逐阶段计算各中间点到A
的最优路线,直至确定E到A的最优路线,用顺推法求解时,可以根据情况对阶段重新编号,确定各阶段的允许状态集合,各状态的允许决策集合,状态转移方程,阶段效益及指标函数,如果阶段编号,状态变量与决策变量取值保持不变,则第k阶段的状态变量应是s,k+1而不是s。这由于在顺推算法时s成为k阶段的“初始状态”,而kk+1
s成为采取某一决策后的“终止状态”。因此,相应的状态转移方程k
为
/ (7.14)s,T(s,d(s))kkk,1kk,1
它应是逆推算法中状态转移方程的逆变换,其次从初始阶段向最后阶段过渡的指标函数与最优指标应满足
/F(s,p),,(s,d(s),F(T(s,d(s)),p) (7.15)k,nkk,1k,1kk,1k,1,nkk,1kk,1k,1,1
/ (7.16)opt,,f(s),,(s,d(s)),f(T(s,d(s))),k,0,1,?,nkkk,1kk,1k,1kk,1kk,1{d(s)}kk
边值条件为
f(s),0 (7.17) 01
在例7.1中,若阶段编号,状态变量与决策变量的定值不变,则顺推解法的指标函数为
i
F(s,p),r(s,d(s)),i,1,2,?,5 ,,1,1,1kkkjjjj,1j
最优指标为
/,,f(s),r(s,d(s)),f(T(s,d(s))) minkkkk,1kk,1k,1kk,1kkd(s)kk
在图7.5中,表示顺推过程的图解,详细计算不再聱述,每个节
点处上方方格内的数表示该点到A点的最短距离,用直线连接的点表示该点到始点A的最短路线,粗线表示A到E的最短路线。
5 14
B C 1119
D 123 7 13
A B C E2218 9 11
D 2
B C 33
图7.5
注意A到D有两条最短路,即A?B?C?D,或A?B?C?D。1111231
使用LINGO软件程序编制软件本例的顺推法,只要设E?1点(城市),D?2,D?3,C?4,C?5,C?6,B?7,B?8,B?9,12123123A?10点(城市)。计算动态规划(顺推法)LINGO程序如下:
MODEL:
SETS:
! Dynamic programming illustration.
We have a network of 10 cities. We
want to find the length of the shortest route
from city 1 to city 10.;
! Here is our primitive set of ten cities, where
F( i) represents the shortest path distance
from city i to the last city;
CITIES /1..10/: F;
! The derived set ROADS lists the roads that
exist between the cities (note: not all city
pairs are directly linked by a road, and roads
are assumed to be one way.);
ROADS( CITIES, CITIES)/
1,2 1,3
2,4 2,5 2,6
3,4 3,5 3,6
4,7 4,8
5,7 5,8 5,9
6,8 6,9
7,10
8,10
9,10/: D;
! D( i, j) is the distance from city i to j;
ENDSETS
DATA:
! Here are the distances that correspond to the
above links;
D =
6 5
5 6 8
7 5 11
9 11
8 7 5
4 10
5
7
9;
ENDDATA
! If you are already in City 10, then the cost to
travel to City 10 is 0;
F( @SIZE( CITIES)) = 0;
! The following is the classic dynamic programming
recursion. In words, the shortest distance from
City i to City 10 is the minimum over all
cities j reachable from i of the sum of the
distance from i to j plus the minimal distance
from j to City 10;
@FOR( CITIES( i)| i #LT# @SIZE( CITIES):
F( i) = @MIN( ROADS( i, j): D( i, j) + F( j))
);
END
详细解释参见逆推法,使用SOLVE求解得结果如下,其中F(i)表示第i个点至起点A的距离。
归纳如下,使用动态规划解一个可分阶段的多阶段决策问题时,必须包含下面步骤。
(1)将系统划分成恰当的阶段,并编号;
sS(2)确定状态变量,状态变量集合; kk
d(s)D(S)(3)确定决策变量,以及允许决策变量集合;kkkk
S,T(s,d(s))(4)建立状态转移方程; k,1kkkk
r(s,d(s))(5)确定各阶段的阶段效益; kkkk
(6)建立指标函数
/; F(s,p),,(s,d(s),F(T(s,d(s)),p)k,nk,1k,nkkkk,1,nkkkkk,1,n
(7)为边值条件,求最优指标k,n,n,1,?,1,f(s),0n,1n,1
opt,,f(s),,(s,d(s),f(T(s,d(s)))kkkkkk,1kkkkd(s)kk
并给出相应于最优指标的状态转移方程。 (8)对k=1,2„,n,从最优指标的状态转移方程求得最优决策。
上述求解过程由图7.6所示,在选择状态变量时应能正确地反映整个多阶段决策的演变过程,同时又必须满足无后效性的要求,即某阶段的状态一旦确定,则该阶段以后过程的演变不受该阶段以前演变过程的影响,而只与该状态本身有关,状态变量应选择尽可能的明确简单。
决决dd 1 n 策策
阶段1 阶段n
S2 T(s,d) …… T(s,d) 111nnn
r(s,d) r(s,d) 111nnn
…… F(s, p) F(s, p) 1, n11, nn, nn1, n
…… f(s) f(s) 11nn
图7.6
* 动态规划的最优性原理和最优性定理
动态规划的最优性定理 设阶段数为n的多阶段决策系统,其阶段编号为k =0,1,„,n―1。
****允许策略是最优策略的重要条件是对任一个p,(d,d,?,d)nn0,,101,1
k,0
本文档为【动态规划模型与实验[管理资料]】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。