第三节 态规划.docVIP

§12.4 动态规划 [学习目标] 能建立动态规划问题的数学模型； 会表述动态规划问题的一般形式； 会求解简单的动态规划问题。 动态规划是解决多阶段决策过程最优化的一种方法。这种方法把困难的多阶段决策问题变换成一系列互相联系比较容易的单阶段问题，解决了这一系列比较容易的单阶段问题，也就解决了这困难的多阶段决策问题。 多阶段决策问题，是指这样一类活动的过程，在它的每个阶段都需要做出决策，并且一个阶段的决策确定以后，常影响下一个阶段的决策，从而影响整个过程决策的效果。多阶段决策问题就是要在允许的各阶段的决策范围内，选择一个最优决策，使整个系统在预定的标准下达到最佳的效果。 有时阶段可以用时间表示，在各个时间段，采用不同决策，它随时间而变动，这就有“动态”的含意。动态规划就是要在时间的推移过程中，在每个时间阶段选择适当的决策，以便整个系统达到最优。 用动态规划可以解决管理中的最短路问题、装载问题、库存问题、资源分配、生产过程最优化问题。 近几十年来，动态规划在理论、方法和应用等方面取得了突出的进展，并在工程技术、经济、工业生产与管理、军事工程等领域得到广泛的应用。下面我们先看一个简单的例子。 一、引例：最短线路问题 如图形5.5，从地要铺设一条管道到地，、中间必须经过五个中间站。第一可以在两地中任选取一个，类似地，第二、三、四、五站可供选择的地点分别是。连接两点间的管道的距离用图3-7上的数字表示，两点间没有连线的相应两点间不能铺设管道，现要选择一条从到的铺管线路，使总距离最短。 解 最短线路问题有一个特性，如果最短线路在第k 站通过，则这一线路在由出发到达终点的所有可能选择的不同线路来说，必定也是距离最短的。最短线路的这一特性，启发我们从最后一段开始，用从后向前逐渐递推的方法，示出各点到的最短线路，最后球得从到的最短线路。 时，设表示由到的最短距离，表示由到的最短距离，显然 =4， =3 k=5时，（1）从出发，有两种选择，到或，如果表示由到的最短距离，）表示到的距离，表示相应的选择或决策，则 最短路线是。 （2）从出发，出有两种选择，即到到。 的定义与（1）中相似，则 最短路线是。 （3）从出发，同样有 ，最短路线是。 时，分别以为出发点来计算 ，最短路线是 ，最短路线是 ，最短路线是。 时，分别以为出发点计算，即有 ，最短路线是。 ，最短路线是。 ,最短路线是。 ,最短路线是。 时：分别为出发点计算，即有 ,最短路线是。 ,最短路线是。 时：出发点只有。 ,最短路线是，最短距离为18。本例直观地揭示了动态规划的基本思想。 二、动态规划法求解的数学描述： 讨论动态规划中最优目标函数的建立，一般要用下列术语和步骤： 阶段 用动态规划求解多阶段决策系统问题时，要根据具体情况，将系统适当地分成若干个阶段，以便分阶段求解，一般是根据时间与空间的自然特征去划分阶段，描述阶段的变量称为阶段变量。上例分六个阶段，是一个六阶段的决策过程。例中由系统的最后阶段向初始阶段求最优解的过程称为动态规划的逆推解法。 状态 状态表示系统在某一阶段开始时所处的自然状况或客观条件。上例中第一阶段有一个状态，即。第二阶段有两个状态，即，等。过程的状态可用状态变量来描述，某个阶段所有可能状态的全体可用状态集合来描述，如，，。 3.决策 某一阶段的状态确定以后，从该状态演变到下一阶段某一状态所作的选择称为决策。第阶段的决策与第个阶段的状态有关，通常用表示第阶段处于状态时的决策变量，而这个决策又决定了第阶段的状态。如上例中在第阶段用表示处于状态时的决策变量。决策变量限制的范围称为允许决策集合。用表示第阶段从出发的决策集合。 4. 策略 由每阶段的决策组成的决策函数序列称为全过程策略或简称策略，用表示。即 由系统的第阶段开始到终点的决策过程称为全过程的后部子过程，相应的策略称为后部子过程策略。用表示子过程策略。即 对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合