第五节动态规划 动态规划是运筹学的一个分支,它是解决多 阶段决策过程最优化的一种数学方法.大约产生 于50年代.1951年美国数学家贝尔曼 (R. Bellman)等人,根据一类多阶段决策问题的 特点,把多阶段决策问题变换为一系列互相联系 单阶段问题,然后逐个加以解决。与此同时,他 提出了解决这类问题的“最优性原理”,研究了 许多实际问题,从而创建了解决最优化问题的 种新的方法--动态规划.他的名著“动态规划” 于1957年出版,该书是动态规划的第一本著作
第五节 动态规划 动态规划是运筹学的一个分支，它是解决多 阶段决策过程最优化的一种数学方法．大约产生 于50年代．1951年美国数学家贝尔曼 (R．Bellman)等人，根据一类多阶段 决策问题的 特点，把多阶段决策问题变换为一系列互相联系 单阶段问题，然后逐个加以解决。与此同时，他 提出了解决这类问题的“最优性原理”，研究了 许多实际问题，从而创建了解决最优化问题的一 种新的方法——动态规划．他的名著“动态规划” 于1957年出版，该书是动态规划的第一本著作．
动态规划模型的分类,根据多阶段决策过程的时间参量是离散的还是连续 的变量:;过程分为离散决策过程和连续决策过程.根据决策过程的演变是确定 性的还是随杋性的,过程又可分为确定性决策过程和随机性决策过程.组合起 来就有离散确定性、离散随杋性、连续确定性、连续随杋性四种决策过程模 型.本部分主要研究离散决策过程,介绍动态规划的基本概念、理论和方法 并通过几个典型的问题来说明它的应用,这些都是整个动态规划的基本内容 根据多阶段决策过程的 根据决策过程的 时间参量 演变 确定性 随机性 离散 连续 决策过程 决策过程 决策过程 决策过程 离散确定性)离散确定性 续确定性 连续随机性 决策过程 决策过程 决策过程 决策过程
动态规划模型的分类，根据多阶段决策过程的时间参量是离散的还是连续 的变量；过程分为离散决策过程和连续决策过程．根据决策过程的演变是确定 性的还是随机性的，过程又可分为确定性决策过程和随机性决策过程．组合起 来就有离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模 型．本部分主要研究离散决策过程，介绍动态规划的基本概念、理论和方法， 并通过几个典型的问题来说明它的应用，这些都是整个动态规划的基本内容． 离散 决策过程 连续 决策过程 根据多阶段决策过程的 时间参量 根据决策过程的 演变 确定性 决策过程 随机性 决策过程 离散确定性 决策过程 离散确定性 决策过程 连续确定性 决策过程 连续随机性 决策过程
1多阶段决策过程及实例 有一批军用物资需要从A地调运到E地,如下图所示,请求出 条从A到E的一条线路,使总的运输距离最短。图中线条上的数字为距离。 80ky A B2 4 A地 B地 C地 D地 E地
引例——有一批军用物资需要从A 地调运到E地，如下图所示，请求出一 条从 A 到 E 的一条线路，使总的运输距离最短。图中线条上的数字为距离。 A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 10 12 9 4 5 8 9 7 7 3 4 11 1 多阶段决策过程及实例 B 地 C 地 D 地 E 地 A 地
①0 (B2 18 在生产和科学实验中,有一类活动的过程,由于它的特殊性,可将过程分为若干个 互相联系的阶段,在它的每一个阶段都需要作出决策,才能使整个过程达到最好的活动 效果.因此,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响 到以后的决策 如果一个问题的过程可以化分为若干个互相联系的阶段,而且每个阶段都需要作出 决策,而且当每个阶段的决策都确定之后,整个问题也就确定了,那么,这个问题就叫 做一个多阶段决策问题。动态规划就是解决这类问题的一个重要的数学方法
在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个 互相联系的阶段，在它的每一个阶段都需要作出决策，才能使整个过程达到最好的活动 效果．因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响 到以后的决策。 A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 10 12 9 4 5 8 9 7 7 3 4 11 如果一个问题的过程可以化分为若干个互相联系的阶段，而且每个阶段都需要作出 决策，而且当每个阶段的决策都确定之后，整个问题也就确定了，那么，这个问题就叫 做一个多阶段决策问题。动态规划就是解决这类问题的一个重要的数学方法
10 12 A B2 18 B 如上图所示的线路网络,求A到E点的最短路线问题是动态规划中一个较为直 观的典型例子,现通过讨论它的解法,来说明动态规划方法的基本思想,并阐述它的 基本概念 如上图可知,从A点到E点可以分为4个阶段.从A到B为第一阶段,从B到C为第二 阶段.从D到E为第四阶段
如上图所示的线路网络，求 A 到 E 点的最短路线问题是动态规划中一个较为直 观的典型例子．现通过讨论它的解法，来说明动态规划方法的基本思想，并阐述它的 基本概念。． A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 10 12 9 4 5 8 9 7 7 3 4 11 如上图可知，从A点到E点可以分为4个阶段．从A到B为第一阶段，从B到C为第二 阶段…从D到E为第四阶段
10 12 A B2 18 在第一阶段,A为起点,终点有B1,B2,B3三个,因而这时走的路线有三个选择, 分别是走B1,B2,B3 如果选择走B2的决策,则B2就是第一阶段在我们决策之下的结果.它既是第一阶段 路线的终点,又是第二阶段路线的始点。 在第二阶段,再从B2点出发,对应于B2点就有一个可供选择的终点集合{C1,C2 C3}; 如果选择由B2走至C2为第二阶段的决策,则C2就是第二阶段的终点,同时又是第三 阶段的始点 同理递推下去,可看到:各个阶段的决策不同,调运的路线就不同.很明显,当某 阶段的始点给定时,它直接影响着后面各阶段的行进路线和整个路线的长短,而后面各阶
在第一阶段，A为起点，终点有B1，B2，B3三个，因而这时走的路线有三个选择， 分别是走B1，B2，B3。 如果选择走B2的决策，则B2就是第 一阶段在我们决策之下的结果．它既是第一阶段 路线的终点，又是第二阶段路线的始点。 在第二阶段，再从B2点出发，对应于B2点就有一个可供选择的终点集合{C1，C2， C3}； 如果选择由B2走至C2为第二阶段的决策，则C2 就是第二阶段的终点，同时又是第三 阶段的始点． 同理递推下去，可看到：各个阶段的决策不同，调运的路线就不同．很明显，当某一 阶段的始点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶 段的路线的发展不受这点以前各阶段路线的影响．故此问题的要求是：在各个阶段选取一 A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 10 12 9 4 5 8 9 7 7 3 4 11
10 12 A B2 18 如何解决这个问题呢? 可以采取穷举法.即把由A到E所有可能的每一条路线的距离都算出来,然后互相比 较找出最短者,相应地得出了最短路线.这样,由A到E一共有3X3X2Ⅹ1=18条不同的 路线,比较这18条不同的路线的距离值,才找出最短路线 显然,这样作计算是相当繁的.如果当段数很多,各段的不同选择也很多时,这种解 法的计算将变得极其繁杂,甚至在电子计算机上计算都是不现实的
如何解决这个问题呢? 可以采取穷举法．即把由A到E所有可能的每一条路线的距 离都算出来，然后互相比 较找出最短者，相应地得出了最短路线．这样，由A到E一共有3 X 3 X 2 X 1＝18条不同的 路线，比较这18条不同的路线的距离值，才找出最短路线。 显然，这样作计算是相当繁的．如果当段数很多，各段的不同选择也很多时，这种解 法的计算将变得极其繁杂，甚至在电子计算机上计算都是不现实的． A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 10 12 9 4 5 8 9 7 7 3 4 11
2用动态规划的方法来求解以上最短路间题 (1) 顺序 16N解法 12 A 3(B2) E 18 E地 A地 B地 C地 D地 求解得到的结果内容丰
A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 10 12 9 4 5 8 9 7 7 3 4 11 12 0 4 3 5 14 14 16 17 19 2 用动态规划的方法来求解以上最短路问题 B 地 C 地 D 地 E 地 A 地 （1） 顺序 解法 求解得到的结果内容丰富
(2) 逆序 3解法 12 0 E 18 l0′ D地 A地 E地 B地 C地
（ 2 ） 逆序 解法 A B2 C2 E B1 B3 C1 C3 D1 D2 4 35 8 10 12 14 18 10 12 9 4 5 8 97 7 34 11 0 B 地 C 地 D 地 E 地 A 地 34 7 11 10 15 18 19 19
3动态规划的基本概念 8 1O 12 (1)阶段 把所给问题的过程,恰当地分为若干个相互联系的阶段,以便能按一定的次序去 求解 阶段的划分,一般是根据时间和空间的自然特征来划分。 描述阶段的变量称为阶段变量,常用k表示.如例1可分为4个阶段来求解,k=1、2、 3、4
3 动态规划的基本概念 (1)阶段 把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去 求解． 阶段的划分，一般是根据时间和空间的 自然特征来划分。 描述阶段的变量称为阶段变量，常用 k 表示．如例1可分为4个阶段来求解，k＝1、2、 3、4。 A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 12 10 9 4 5 8 9 7 7 3 4 11