动态规划模型

1、第2讲 动态规划模型动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家贝尔曼（R.Bellman）等人，根据一类多阶段决策问题的特点，提出了解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新方法动态规划。动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题。下面，以最短路径问题为例，说明动态规划的基本思想方法和特点。（一）、最短路径问题1、 问题提出如图1-10所示（P56），从地要铺设一条管道到地，中间必须经过五个中间站，第一站可以在两地中任

2、选一个，类似的，第二、三、四、五站可供选择的地点分别是连接两点间的距离用图上两点连线上的数字表示，两点间没有连线的表示相应两点不能铺设管道，现要选择一条从到的铺管线路，使总距离最短。2、问题分析解决最短路径问题，最容易想到的方法是穷举法，即列出所有可能发生的方案和结果，再针对题目的要求对它们一一进行比较，求出最优方案。这种方法，在变量（或节点）的数目较小时有效；在变量数目很大时，计算量将会变得十分庞大，行不通。因此，需要根据问题的特性，寻求一种简便的算法。最短路径问题有一个特性：如果最短路径在第站通过点，则这一线路在由出发到达终点的那一部分线路，对于从点终点的所有可能选择的不同线路来说，必定也

3、是距离最短的。这就是最优性原理。这就启发我们从最后一段开始，采用从后向前逐步递推的方法，求出各点到的最短线路，最后求得从到的最短线路。（归结为一句话：最有策略的子策略仍然是最优策略）3、问题求解为求解方便，将整个过程分为6个阶段，用表示。（1）时，设表示由到的最短距离，表示由到的最短距离，有 ，（2）时，从出发，有两种选择，到或，如果表示到的最短距离，表示到的距离，则再用表示相应的选择或决策，则。得到由出发到的最短线路是。从出发，也有两种选择，到或，如果的定义与中相似，则。得到由出发到的最短线路是。从出发，同样有 。得到由出发到的最短线路是。（3）时，分别以为出发点来计算，有，由出发的最短线路

4、是。 ，由出发的最短线路是 ，由出发的最短线路是。（4）时，分别以为出发点来计算，有，由出发的最短线路是。，由出发的最短线路是。，由出发的最短线路是。，由出发的最短线路是。（5）时，分别以为出发点来计算，有，由出发的最短线路是。，由出发的最短线路是。 （6）时，出发点只有，有，由出发的最短线路是，距离为18。综上所述，动态规划方法的基本思想是，把一个复杂的问题分解为一系列同一类型更容易求解的子问题，使计算过程单一化，便于应用计算机。求解过程分为两个阶段，先按照整体最优的思想逆序地求出各个可能状态的最优决策。然后，再顺序地求出整个问题的最优策略和最优路线。由于把最优化应用到每个子问题上，于是，就

5、系统地删去了所有中间非最优的方案组合，使计算工作量比直接枚举法大大减少。（二）、基本概念和基本方程1、动态规划的基本概念（1）阶段和阶段变量用动态规划求解多阶段决策系统问题时，要根据具体情况，将系统适当地分成若干个阶段，以便分阶段决策。通常阶段是按照决策进行的时间或空间上的先后次序划分的，描述阶段的变量称为阶段变量。由系统的最后阶段向初始阶段求最优解的过程，称为动态规划的逆推解法。（2）状态和状态变量状态表示系统在某阶段所处的“起点”位置或状态。各阶段的状态可用状态变量来描述，阶段的状态变量记为。第阶段所有可能状态的全体，可用状态集合来描述。上例中（3）决策、决策变量和策略从一个阶段的某个状态

6、出发，到达下一阶段，都有若干种选择。把过程从一个状态演变到下一阶段某一状态所作的选择或决定称为决策。描述决策的变量称为决策变量，记为。表示从第阶段的状态出发所作的决策。并用表示第阶段从出发的所有决策的集合。由每阶段的决策组成的决策序列称为全过程策略或策略，表示为。由系统的第阶段出发到终点的决策过程称为全过程的后部子过程，相应的策略称为子策略。表示为。对于每一实际的多阶段决策过程，可供选择的策略有一定的范围限制，这个范围称为允许集合。允许集合中达到最优效果的策略称为最优策略。（4）状态转移方程由第阶段的状态，采用决策变到第阶段的状态的过程称为状态转移，并记为 该式表达了从阶段到阶段的状态转移规律

7、，故称为状态转移方程。（5）阶段效益多阶段决策过程中，在阶段的状态执行决策转到状态，不仅带来系统状态的转移，而且也将对整个决策的结果或效益产生影响。用表示在第阶段中，从状态出发，采取策略，转移到的效益，称为阶段效益。（6）最优策略与最优效益对于多阶段决策问题，自然都存在很多策略，而且每个策略都对应一种结果，把这些结果统称为效益。根据不同的实际问题，效益可以是利润、距离、产量或资源的消耗量等。显然一个多阶段决策问题的效益（决策的目的）是各阶段效益的和，使整体效益达到最优的策略，称为最优策略；相应于最优策略的整体效益称为最优效益。同（3）中子策略的定义类似，可以将最优效益定义在全过程上，也可以定义

8、在后部子过程上。如果统一用表示从阶段的状态出发到终点的最优效益，那么目的就是求。（7）最优性原理对于无后效性的多阶段决策过程，最优策略具有最基本的性质：无论初始状态和初始决策如何，对于前面的决策所造成的某一状态而言，余下的决策必是最优子策略。无后效性是指系统从某个阶段往后的发展，完全由本阶段所处的状态及其往后的决策决定，与系统以前的状态和决策无关，即当前状态就是过程往后发展的初始条件。2、动态规划的基本方程及一般模型建立动态规划模型，需要进行以下几方面的工作：（1）选择阶段变量；（2）选择状态变量。状态变量必须能正确描述整个过程的演变特性，又要满足无后效性的原则；（3）选择决策变量；（4）列出

9、状态转移方程；（5）列出动态规划基本方程：对于极小化问题 称为动态规划基本方程。给出终端条件，即可由后向前逐步推出，得到最优效益。整个递推关系可表示为这就是动态规划模型。（三）、应用举例问题1（机器负荷分配问题）某机器可以在高低两种不同的负荷下进行生产。在高负荷下生产时，产品产量，为投入生产的机器数量，机器的年折损率为，即年初完好的机器数量为，年终就只剩下台是完好的，其余均需维修或报废。在低负荷下生产，产品年产量，其中为投入生产的机器数量，机器的年折损率为。设开始时，完好的机器数为台，要求制订一个五年计划，在每年开始时决定如何重新分配完好机器在两种不同负荷下工作的数量，使产品五年的总产量最高。

10、模型建立 这是一个典型的多阶段决策问题，用阶段变量表示年度。（1）状态变量是第年初拥有的完好机器数量，它也是年度末的完好机器数量。（2）决策变量为第年度中分配在高负荷下生产的机器数量。于是是该年度分配在低负荷下生产的机器数量。这里与前面的例子不同的是均取连续变量以利于求解。的非整数值可以理解为：如表示一台机器在该年度正常工作时间只占60%；表示一台机器在该年度的30%时间里在高负荷下工作。（3）由状态采取决策后的状态转移方程为 （4）第年度产品产量是（阶段效益函数） （5）若用表示第年初从出发，采用最优策略，到第5年末产品的最大值。则由最优化原理，得动态方程（即所求模型）为其终端条件为。 模型

11、求解及结果 利用动态规划的逆推解法，计算过程如下：时， =因为是关于的单调增加函数，且，故最优决策是，此时；类似可以依次求出时，取，则；时：，取，则；时：，取，则；时：，取，则； 由此可知，最优策略为，即开始两年将完好机器全部投入低负荷生产，后三年将完好机器全部投入高负荷生产，这时最高产量为（台） 利用状态转移方程可以求出每年年初的完好机器数量：，。问题2 在问题1中增加限制条件，要求在第五年末完好的机器数量为500台，即台。问这时如何安排生产，使产品五年总产量最高？分析与求解 问题1中始端状态是给定的，而终端状态没有限制，这是一种破坏性生产，在几年后产品停产、换型或设备更新的情况下是可行的。但若需2生产，这样的方法是不可取的，因此，通常对终端是有要求的。由状态转移方程得即，这说明第五年的决策变量由唯一确定，即决策集合退化为一点，只有一种决策，所以时 利用递推关系，得时： = 显然最优决策为