动态规划习题详解.doc

《动态规划习题详解.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼(R．Bellman)等人在本世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支——动态规划。他的名著《动态规划》于1957年出版，该书是动态规划的第一本著作。动态规划是现代企业管理中的一种重要决策方法，在工程技术、经济管理、工农业生产及军事及其它部们都有广泛的应用，并且获得了显著的效果。动态规划可用于解决最优路径问题、资源分配

2、问题、生产计划与库存问题、投资分配问题、装载问题、设备更新与维修问题、排序问题及生产过程的最优控制等。由于它所具有独特的解题思路，在处理某些优化问题时，常常比线性规划或非线性规划方法更有效。第一节动态规划的基本方法多阶段决策的实际问题很多，下面通过具体例子，说明什么是动态规划模型及其求解方法。例1：最短路线问题某工厂需要把一批货物从城市A运到城市E，中间可经过B1、B2、B3、C1、C2、C3、D1、D2等城市，各城市之间的交通线和距离如下图所示，问应该选择一条什么路线，使得从A到E的距离最短？C1B163D1845B2A564EC29872D363

3、671C3B3837下面引进几个动态规划的基本概念和相关符号。(1)阶段(Stage)把所给问题的过程，按时间和空间特征划分成若干个相互联系的阶段，以便按次序去求每个阶段的解，阶段总数一般用字母n表示，用字母k表示阶段变量。如例l中(最短路线问题)可看作是n=4阶段的动态规划问题，k=2表示处于第二阶段。(2)状态(State)状态表示每个阶段开始时系统所处的自然状况或客观条件，它描述了研究问题过程状况。描述各阶段状态的变量称为状态变量，常用字母sk表示第k阶段的状态变量，状态变量的取值范围称为状态集，用Sk表示。如例l中，第一阶段的状态为A（即出发

4、位置）。第二阶段有三个状态：B1、B2、B3，状态变量s2=B2表示第2阶段系统所处的位置是B2。第2阶段的状态集S2={B1、B2、B3}。动态规划中的状态变量应具有如下性质：当某阶段状态给定以后，在这个阶段以后过程的发展不受这个阶段以前各个阶段状态的影响。也就是说，未来系统所处的状态只与系统当前所处的状态有关，而与系统过去所处的状态无关，即过去历史只能通过当前的状态去影响它未来的发展，这种特点称为无后效性（又称马尔可夫性）。如果所选定的状态变量不具备无后效性，就不能作为状态变量来构造动态规划模型。如例1中，当某阶段的初始状态即所在的城市选定以后，

5、从这个状态以后的运货路线只与这个城市有关，不受以前的运货路线影响，所以是满足状态的无后效性的。（3）决策(Decision)当系统在某阶段处于某种状态，可以采取的行动（或决定、选择），从而确定下一阶段系统将到达的状态，称这种行动为决策。描述决策的变量，称为决策变量。常用字母uk(sk)表示第k阶段系统处于状态sk时的决策变量。决策变量的取值范围称为决策集，用Dk(sk)表示。在例l的第二阶段中，若从状态B2出发，可以做出三种不同的决策，其允许的决策集为D2(B2)={C1、C2、C3}，决策u2(B2)=C2表示第二阶段处于状态B2，选择的确行动下一

6、阶段是走到C2。（4）策略(Policy)系统从第k阶段的状态sk开始由每阶段的决策按顺序组成的决策序列{uk(sk)，uk+1(sk+1)，…，un(sn)}称为一个策略（k=1,2,…，n）,记作。在例l中，p2,4(B2)={u2(B2)=C2，u3(C2)=D1，u4(D1)=E}是一个策略，表示第二阶段从状态B2出发，沿着B2→C2→D1→E的方向走到终点。注意策略必须是一串实际可行的序列行动。（5）状态转移方程系统由这一阶段的—个状态进行决策后转变到下—阶段的另—个状态称为状态转移，状态转移既与状态有关，又与决策有关，描述状态转移关系的方

7、程称为状态转移方程，记为：sk+1=Tk(sk，uk)它的实际意义是当系统第k阶段处于状态sk做决策uk时，第k+1阶段系统转移到状态sk+1。状态转移方程在不同的问题中有不同的具体表现形式，在例l中，状态转移方程表示为：sk+1=uk(sk)。（6）阶段指标阶段效益是衡量系统阶段决策结果的一种数量指标，记为：表示系统在第k阶段处于状态sk做出决策uk时所获得的阶段效益。这里的阶段效益在不同的实际问题中有不同的意义。在例l中它表示两个中转站的距离，如表示从中转站B2走到中转站C2之间的距离为7。更一般地有。（7）指标函数指标函数是用来街量所实现过程的

8、优劣的一种数量指标，它是一个定义在全过程和所有后部子过程上的确定的数量函数，记为：它应具有可分离性，并满足递