第六章 动态规划.ppt

1、1、第六章动态规划、动态规划作为运营计划学的重要分支，是解决多阶段决策过程优化的非常有效的方法。 1951年，美国数学家贝尔曼(R . Bellman )等，根据多阶段的意思判定问题特征，把多阶段的意思判定问题变换为一系列相互关系的单阶段的意思判定问题，一个阶段一个阶段地解决了。 贝尔曼等人研究解决了很多实际问题之后，提出了解决这样的问题的所谓“最优性原理”，通常被称为“贝尔曼最优化原理”，制定了解决最优化问题的新方法的动态计划(Dynamic Programming )。 2、动态规划方法在工程技术、企业管理、工农业生产和军事等部门广泛应用，取得了显着效果。 在经济管理方面，动态规划可以用于

2、解决最佳路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等，是现代企业管理中的重要决策方法。 许多实际问题采用动态规划方法处理，比线性规划和非线性规划更有效。 特别是对于离散的问题，因为不能解析数学使用其技术，所以动态规划的方法成为非常有效的工具。 3、需要特别指出的是，动态规划是解决某些问题的一种方法，也是分析问题的一种方法，并不是特别的算法(线性规划是算法)。 因此，不像线性规划那样有标准的数学公式和明确定义的规则，必须具体分析具体的问题来处理。 因此，在学习动态规划时，除了正确理解基本概念和方法外，还应该用丰富的想象力建立模型，用创造

3、性的技术解决。 正如贝尔曼本主儿所说，“动态规划的优化原理不过是基本原理，它为某些不真实自我发挥创造性思维提供了巨大空间！ 4、本部分主要研究离散决策过程，介绍动态规划的基本概念、理论和方法，并通过一些典型的应用题来说明其应用。 动态规划面向多层次的决策判定问题。 所谓多阶段的意思判定问题，是指活动的过程，分为多个阶段，有必要在各个阶段进行决策。 这个决定不仅决定了这个阶段的利益，还决定了下一阶段的初期状态。 每个阶段的决策确定后，就会得到一个称为战略的决策序列。 多阶段的意思判定问题是寻求策略，使各阶段的利益的合计达到最佳。 5、第一节多阶段的意思判定问题，在生产经营活动中，可以把几个问题的

4、决策过程分为几个相互关联的阶段，每个阶段都需要作出决策，整个过程变得最佳。 由于每一阶段的决策制定后，所有过程的决策都是由这些个阶段的决策构成的一个决策序列，因此多阶段的决策判定问题也被称为循序渐进的决策判定问题。 动态规划方法与“时间”有着密切的关系，随着时间的推移决定各时间段的决策，生成一个决策序列就是“动态”的意思。 但是，也可以处理与时间无关的静态问题，如果人为地在问题中导入“期间”的要素，就可以将其变为多阶段的意思判定问题。 本章对该处理方法进行说明。 6、动态规划求解多阶段决策判定问题的特征往往是多阶段决策过程的发展由状态的一系列变换实现的。 一般来说，系统的某个阶段的状态转移除了

5、这个阶段的状态和决策，还可能与系统过去经历的状态和决策有关。 因此，问题的解决是复杂的。 用动态规划方法求解的是特殊的多层次决策判定问题，即“回味无穷”的多层次决策过程。所谓没有后发性，也被称为马尔可夫性，意味着系统从某个阶段发展，这一阶段所处的状态及其后续的决策来决定，与系统过去经历的状态和决策(历史)无关。 7、为了说明动态规划的基本思维方法和特征，以下图为例，探讨求最短路问题的方法。 确定从a到e的最短路径8，第一种方法称为全列举法或穷举法。 其基本思想是列举所有可能发生的方案和结果，将它们一一比较，寻求最佳方案。 在这里，从a到e的路程分为四个阶段。 第一、第二阶段的行走方法有三种，第

6、三阶段的行走方法有两种，第四阶段的行走方法只有一种，因此，共有332118条可能的路线，计算各个路线的距离，最后进行比较，最佳路线为AB2 C1 D1 E，最短距离为1.9，9 在构成交通网络的节点很多的情况下，用网罗法求最佳路线的计算工作量很庞大，而且其中包含很多迭代计算的第二方法，所谓的“局部最佳路径”法，有人从a出发，不管全线最短，他只是选择现在的最短路线很明显，在此思维方法的指导下，决定的决定是AB2 C1 D1 E，全线长度是2.5，这种方法的结果往往是错误的，认为局部最佳化是整体最佳化。 1.0，第三种方法是动态规划方法。 动态规划方法求出这个最短路问题的基本思想是，如果A=S1

7、S2 Sk Sn E是a到e的最短路，则Sk到e的最短路是Sk Sn E。 首先将问题分为4个阶段，每次的选择总是考虑后继过程的综合优化，并且如果需要每个阶段的所有可能状态的最佳后继过程，则还得到整个过程的最佳路径。 为了找到所有可能状态的最佳后继过程，动态规划方法总是从过程的最后阶段考虑，与实际过程的发展顺序相反，阶段性地递归计算到第一点。、1.1、2、5、1、1.2、1.4、1.0、6、4、1.3、1.1、1.2、3、9、6、5、8、1.0、5、2、C1、C3、D1、a、B1、B3、B2、D2、e、C2、F5 (e )=0、12、4、 1.3，1.1，1.2，3，9，6，5，8，1.0，5

8、，2，C1，C3，D1，a，B1，B3，B2，D2，e，C2，f4(D1)=5，F5 (e )=0，1.3，、2，5，1，1.2，1.4，1.0，6 C1 C3、D1、a、B1、B3、B2、D2、e、C2、f4(D2)=2、f5(E)=0、f4(D2)=2、1.4、2、5、1、1.2、1.4、1.0、6、1.0、4、1.3、1.1、1.2、3、9、6、5、8 C2 f4(D2)=2，f5(E)=0，f3(C1)=8，f4(d1)=5，1.5、2，5，1，1.2，1.4，1.0，6，1.0，4，1.3，1.1，1.2，3，9，6，5，8，10，5，2，C1，C3，C3 f4(D2)=2 f5(E

9、)=0、f3(C2)=7、f4(D1)=5、f3(C2)=7、1.6、2、5、1、1.2、1.4、1.0、6、1.0、4、1.3、1.1、1.2、3、9、6、5、8、10、5、2、c f4(D2)=2 f5(E)=0，f3(C3)=12，f4(D1)=5，f3(C1)=8，f3(c2)=7，1.7，2，5，1，1.2，1.4，1.0，1.0，4，1.3，1.1，12，3，9，6，5，8，10，5 c2 f4(D2)=2，f5(E)=0，f3(C3)=12，f4(D1)=5，f2(B1)=20，f3(C2)=7，F3 (C1 )=8，1.8，2，5，1，1.2，1.4，1.0，6，1.0，4，1

10、.3，11，12，12 B1 B3，B2，D2，e，C2，f4(D2)=2，f5(E)=0，f3(C3)=12，f4(D1)=5，f2(B2)=14，f3(C2)=7，f3(C1)=8，F2 (B1 )=2.1、1.9、2 1.0，5，2，C1，C3，D1，a，B1，B3，B2，D2，e，C2，f4(D2)=2，f5(E)=0，f3(C3)=12，f4(D1)=5，f2(B3)=19，f3(C2)=7，f 5、1、1.2、1.4、1.0、6、1.0、4、1.3、1.1、1.2、3、9、6、5、8、1.0、5、2、C1、C3、D1、a、B1、B3、B2、D2、e、C2、f4(D2)=2、f5(E

11、)=0、f3(C3)=12 f1(A)=19 f2(B2)=14、f2(b1)=2.1、2、5、1.2、1.0、4、1.3、1.1、12、3、9、6、5、8、10、5、2、C1、C3、D1、a、b1、B3、B2 f5(E)=0，f3(C3)=12 f4(D1)=5，f2(B3)=19，f3(C2)=7，f3(C1)=8，f1(A)=19，f2(B2)=14，f2(B1)=21，状态最佳决定状态最佳决定状态1.0，4，1.3，1.1，1.2，3，9，6，5，8，1.0，5，2，C1，C3，D1，a，B1，B3，B2，D2，e，C2，f4(D2)=2，f5(E)=0，f3(C3)=12，f4(D1

12、)=5，f 2 f2(B2)=14 f2(B1)=21，状态最佳决定状态最佳决定状态，A (A，B2) B2 (B2，c1) c 1，2.3，、2，5，1，1.2，1.4，1.0，6，1.0，4，1.3，11，12，3，9，6，5，8，11 1.2，f4(D1)=5，f2(B3)=19，f3(C2)=7，f3(C1)=8，f1(A)=19，f2(B2)=14，f2(B1)=21，状态最佳化C1) C1 (C1，d1) d1、2.4、2、5、1、1.2、1.4、1.0、6、1.0、4、1.3、1.1、1.2、3、9、6、5、8、10、5、2、C1、C3、d 1、a1、B1、B3、B2、D2、e、

13、C1 f2(B3)=19，f3(C2)=7，f3(C1)=8，f1(A)=19，f2(B2)=14，f2(B1)=21，状态最佳决定状态最佳决定状态，A (A，B2) B2 (B2， C1) C1 (C1) D1) D1 (D1，E) E的从a到e的最短路径是1.9，路径是AB 2C1 D1 E，如前所述，整个枚举法能够找到最佳方案，但不是好的算法，局部最佳法则以完全错误的方式，只有动态规划是科学有效的算法其基本思想是将比较复杂的问题分解成一系列同类型的更容易解决的子问题，使计算机更容易应用。 整体求解过程分为两个阶段，首先根据整体的最佳思想，反求各子问题所有可能状态的最佳决定和最佳路径值，然

14、后依次求问题整体的最佳策略和最佳路径。 在计算过程中，从系统上去除了所有中间的非最佳方案组合，使计算工作量比贫困法大幅减少。2.6、第二节动态规划的基本概念和基本原理的多阶段决策过程：整个决策过程可以按时间和空间的顺序分解为几个相互关系的阶段，每个阶段都需要做出决策，所有过程的决策都是一个决策序列。 优化多阶段决策过程的目标：实现整个活动过程的总体效果，而不是单个阶段的最佳简单总和。为了使用动态规划方法解决多阶段的决策判定问题，首先要把实际问题写在动态规划模型上，然后给云同步下一步描述和定义，以便于今后的描述和讨论： 2.7，1，为了确定和展示阶段决策过程的发展顺序一个阶段是必须作出决策的子问

15、题，阶段通常被划分为作出决策的时间序列或空间特征的优先级。 描述阶段的变量被称为阶段变量，通常用k表示的阶段变量的阶段数等于从多个阶段的决策过程开始到结束所需的决策数。 例如，上述最短路的问题是四阶段决策过程。 进程在2.8、2、状态(state )各个阶段开始时所处的自然或客观条件。 反映物态变化的量称为状态变量，并且可以由一个数、一组数和向量来描述。 状态变量必须包含在指定阶段行政许可定所有决策所需的信息。 它描述工艺特点“没有事后有效性”，即当前阶段的状态应该给出时间节点，该阶段以后的过程的进化与该阶段在先的各阶段的状态无关。 用sk表示“状态变量”。2.9，一般的状态变量的值有一定的范围或容许集合，被称为可能的状态定径套。 可能的状态定径套实际上是对状态的约束。 通常，可能的状态定径套由相应的阶段状态sk的大写字母sk表示，不管可能的状态定径套是离散的值的集合还是连续的值的取得区间，由于具体问题，比如，在上述最短路径问题中，在第一阶段状态为a，状态变量s1的状态集合S1=A的第二阶段，在B1、B2、B3 状态变量s2的状态集合S2=B1、B2、B3 .3.0、3、决定(decision )在某个阶段的状态决定后，通过进行不同的决定或选择，能够将迁移到下一个阶段的某个状态的决定或