文档介绍：:..第四章动态规划动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼()等人在本世纪50年代初提出的。他们针对多阶段决策问题的特点,提出了解决这类问题的“最优化原理”,并成功地解决了生产管理、工程技术等方面的许多实际问题,从而建立了运筹学的一个新分支一一动态规划。他的名著《动态规划》于1957年出版,该书是动态规划的第一本著作。动态规划是现代企业管理中的一种重要决策方法,在工程技术、经济管理、工农业生产及军事及其它部们都有广泛的应用,并且获得了显著的效果。动态规划可用于解决最优路径问题、资源分配问题、生产计划与库存问题、投资分配问题、装载问题、设备更新与维修问题、排序问题及生产过程的最优控制等。由于它所具有独特的解题思路,在处理某些优化问题时,常常比线性规划或非线性规划方法更有效。第一节动态规划的基本方法多阶段决策的实际问题很多,下面通过具体例子,说明什么是动态规划模型及其求解方法。例1:最短路线问题某工厂需要把一批货物从城市A运到城市E,中间可经过B,、B2、B3、C,、C2、C3、D!、D2等城市,各城市之间的交通线和距离如下图所示,问应该选择一条什么路线,使得从A到E的距离最短?下面引进几个动态规划的基本概念和相关符号。(1)阶段(Stage)把所给问题的过程,按时间和空间特征划分成若干个相互联系的阶段,以便按次序去求每个阶段的解,阶段总数一般用字母n表示,用字母k表示阶段变量。如例1中(最短路线问题)可看作是n=4阶段的动态规划问题,k=2表示处于第二阶段。(2)状态(State)状态表示每个阶段开始时系统所处的自然状况或客观条件,它描述了研究问题过程状况。描述各阶段状态的变量称为状态变量,常用字母sk表示第k阶段的状态变量,状态变量的取值范围称为状态集,用&表示。如例1中,第一阶段的状态为A(即出发位置)。第二阶段有三个状态:、B2、B3,状态变量s2=B2表示第2阶段系统所处的位置是B2。第2阶段的状态集S2={B1、B2、B3}o动态规划中的状态变量应具有如下性质:当某阶段状态给定以后,在这个阶段以后过程的发展不受这个阶段以前各个阶段状态的影响。也就是说,未来系统所处的状态只与系统当前所处的状态有关,而与系统过去所处的状态无关,即过去历史只能通过当前的状态去影响它未来的发展,这种特点称为无后效性(又称马尔可夫性)。如果所选定的状态变量不具备无后效性,就不能作为状态变量来构造动态规划模型。如例1中,当某阶段的初始犾态即所在的城市选定以后,从这个状态以后的运货路线只与这个城市有关,不受以前的运货路线影响,所以是满足状态的无后效性的。(3)决策(Decision)当系统在某阶段处于某种状态,可以采取的行动(或决定、选择),从而确定下一阶段系统将到达的状态,称这种行动为决策。描述决策的变量,称为决策变量。常用字母Uk(sk)表示第k阶段系统处于状态&时的决策变量。决策变量的取值范围称为决策集,用仏(&)表ZK。在例1的第二阶段中,若从状态^出发,可以做出三种不同的决策,其允许的决策集*D2(B2)={Ci、C2、C3},决策112化2)=€:2表示第二阶段处于状态^,选择的确行动下一阶段是走到C2。(4)策略(Policy)系统从第k阶段的状态sk幵始由每阶段的决策按顺序组成的决策序列{uk(sk),uk+i(),…,un(s。)}称为一个策略(k=l,2,…,n),记作八;1(么)。在例1中,Pm(B2)={U2(B2)=C2,U3(C2)=DPu4(D丨)=E}是一个策略,表示第二阶段从状态^出发,沿着B2—C2—队―E的方向走到终点。注意策略必须是一串实际可行的序列行动。(5)状态转移方程系统由这一阶段的一个状态进行决策后转变到下一阶段的另一个状态称为状态转移,状态转移既与状态有关,又与决策有关,描述状态转移关系的方程称为状态转移方程,记为:Sk+i=Tk(si<,Uk)它的实际意义是当系统第k阶段处于状态做决策IU时,第k+1阶段系统转移到状态Sk*lo状态转移方程在不同的问题中有不同的具体表现形式,在例1中,状态转移方程表示为:Sk+i=Uk(Sk)o(6)阶段指标阶段效益是衡量系统阶段决策结果的一种数量指标,记为:表示系统在第k阶段处于状态sk做出决策uk时所获得的阶段效益。这里的阶段效益在不同的实际问题中有不同的意义。在例1中它表示两个中转站的距离,如v2(B2,u2(B2)=C2)=d(B2,C2)=7表示从中转站B2走到中转站C2之间的距离为7。更一般地有4 ,,人(么))二6/(人,人(5;))。(7)指标函数指标函数是用来街量所实现