[管理学]运筹学 动态规划

《[管理学]运筹学 动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章动态规划动态规划简介多阶段决策过程最优化多阶段决策过程，是指一类特殊的过程，它们可以按时间顺序分解成若干个相互联系的阶段，称为“时段”，在每个时段都要做决策，全部过程的决策是一个决策序列。多阶段决策问题也称为序贯决策问题。多阶段决策问题的目标是要达到整个活动过程的总体最优。在每个阶段进行决策时不应仅考虑本阶段最优，尤其应考虑对最终目标的影响，从而做出对全局来说最优的决策。动态规划是符合这种要求的一种决策方法。第1阶段第2阶段第n阶段决策决策决策多阶段决策过程图示动态规划的基本概念AB1B2C1C2C3

2、C4D1D2D3E1E2F452368775845348435621343阶段:k=1,2,3,4,512345基本概念（续一）AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435621343状态：各阶段开始时的客观条件。表示状态的变量称为状态变量，常用sk表示第k阶段的状态变量，第k阶段所有状态变量的集合记为Sk。动态规划考虑的状态应该具有“无后效性”基本概念（续二）决策：当一个阶段的状态取定了后，就可以作出不同决定（或选择），从而确定下一阶段的状态，这种决定称为决策。表示

3、决策的变量称为决策变量，uk(sk)就表示第k阶段当状态为sk时的决策变量。决策变量的取值常常限制在一定的范围内，这一范围称为允许决策集合，常用记号Dk(sk)表示第k阶段状态为sk时的允许状态集合。基本概念（续三）各阶段的决策确定后，整个过程各阶段的决策就构成一个决策序列，称为策略，用p1,n{u1(s1),u2(s2),…,un(sn)}表示。此外还常常需要考虑后部子策略pk,n{uk(sk),…,un(sn)}。动态规划要求的就是使整个问题达到最优的策略。基本概念（续四）状态转移方程：动态规划中一个阶

4、段的状态常常是上一阶段的状态和决策的结果。如果给定了第k阶段的状态sk，和第k阶段的决策uk(sk)，则第k+1阶段的状态sk+1也就完全确定了，这一关系可用下面的方程表示sk+1=Tk(sk,uk)称之为状态转移方程，它表示了由第k阶段到第k+1阶段状态转移的规律基本概念（续五）指标函数：用于衡量决策或策略优劣的数量指标称为指标函数。阶段指标函数：它通常是指在第k阶段，从状态sk出发，采用决策uk时的效益，记为d(sk,uk)。过程指标函数：它通常表示在第k阶段时的状态为sk时，采用后部子策略pk,n的效

5、益值，记为Vk,n(sk,pk,n)。最优指标函数记为fk(sk)，表示第k阶段的状态为sk时，采用了最优后部子策略p*k,n的指标函数值，Vk,n(sk,pk,n)与fk(sk)的关系是特别地，f1(s1)就是从初始状态s1到全过程结束的整体最优函数。对最短路线问题阶段指标函数就是两点间的距离。后部子过程pk,n的指标函数Vk,n(sk,pk,n)就是在第k阶段位于点sk时到终点的距离，而fk(sk)就是到终点的最短距离。最短路线问题，就是要求f1(A)以及相应的路线。最短路线问题的解AB1B2C1C2C

6、3C4D1D2D3E1E2F452368775845348435621343第一步，从k=5开始，状态变量s5可以取两种状态E1，E2，从它们到终点F的距离分别为4，3。即f5(E1)=4,f5(E2)=3动态规划最通常的解法，就是逆序递推的方式求解。第二步，k=4，状态变量s4可以取三个值D1，D2，D3。于是AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435621343AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435621343k=3

7、AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435621343k=2AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435621343k=1最优路线为：A→B1→C2→D2→E2→F从起点A到终点F的最短路程为17。动态规划的最优化原理动态规划方法基于R.Bellman等人提出的最优化原理，它可表述为：“一个过程的最优化策略具有这样的性质：无论初始状态与初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略”。最短路线问题的

8、标号法AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435621343(0)(4)(3)(7)(5)(5)(12)(10)(8)(9)(13)(15)(17)最短路线问题的标号法（续）AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435621343（0）（4）（5）（6）（7）（10）（12）（11）（12）（14）（14）（14）（17）