当前位置:首页 >> 工学 >>

动态规划算法原理与应用


动态规划算法原理 及其应用研究

系 姓

别: x 名: x

x x x

x x x

指导教员: x

2012 年 5 月 20 日

摘要: 动态规划是解决最优化问题的基本方法,本文介绍了动态规划的基本思想 和基本步骤, 并通过几个实例的分析, 研究了利用动态规划设计算法的具体途径。 关键词:动态规划 多阶段决策

1.引言
规划问题的最终目的就是确定各决策变量的取值, 以使目标函数达到极大或 极小。 在线性规划和非线性规划中, 决策变量都是以集合的形式被一次性处理的; 然而,有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多 阶段决策问题是指这样一类活动过程:它可以分解为若干个互相联系的阶段,在 每一阶段分别对应着一组可供选取的决策集合; 即构成过程的每个阶段都需要进 行一次决策的决策问题。 将各个阶段的决策综合起来构成一个决策序列,称为一 个策略。显然,由于各个阶段选取的决策不同,对应整个过程可以有一系列不同 的策略。当过程采取某个具体策略时,相应可以得到一个确定的效果,采取不同 的策略,就会得到不同的效果。多阶段的决策问题,就是要在所有可能采取的策 略中选取一个最优的策略, 以便得到最佳的效果。动态规划是一种求解多阶段决 策问题的系统技术,可以说它横跨整个规划领域(线性规划和非线性规划) 。在 多阶段决策问题中,有些问题对阶段的划分具有明显的时序性,动态规划的“动 态” 二字也由此而得名。 动态规划的主要创始人是美国数学家贝尔曼 (Bellman) 。 20 世纪 40 年代末 50 年代初,当时在兰德公司(Rand Corporation)从事研究工 作的贝尔曼首先提出了动态规划的概念。1957 年贝尔曼发表了数篇研究论文, 并出版了他的第一部著作《动态规划》 。该著作成为了当时唯一的进一步研究和 应用动态规划的理论源泉。 在贝尔曼及其助手们致力于发展和推广这一技术的同 时, 其他一些学者也对动态规划的发展做出了重大的贡献,其中最值得一提的是 爱尔思(Aris)和梅特顿(Mitten) 。爱尔思先后于 1961 年和 1964 年出版了两部 关于动态规划的著作,并于 1964 年同尼母霍思尔(Nemhauser) 、威尔德(Wild) 一道创建了处理分枝、 循环性多阶段决策系统的一般性理论。梅特顿提出了许多 对动态规划后来发展有着重要意义的基础性观点, 并且对明晰动态规划路径的数 学性质做出了巨大的贡献。 动态规划问世以来,在工程技术、经济管理等社会各个领域都有着广泛的应 用,并且获得了显著的效果。在经济管理方面,动态规划可以用来解决最优路径

问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题 以及生产过程最优控制问题等, 是经济管理中一种重要的决策技术。许多规划问 题用动态规划的方法来处理, 常比线性规划或非线性规划更有效。特别是对于离 散的问题, 由于解析数学无法发挥作用, 动态规划便成为了一种非常有用的工具。 动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态 规划; 也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规 划。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一 些与时间无关的静态规划(如线性规划、 非线性规划), 只要人为地引进时间因素, 把它视为多阶段决策过程,也可以用动态规划方法方便地求解。

2.动态规划的基本思想
一般来说, 只要问题可以划分成规模更小的子问题,并且原问题的最优解中 包含了子问题的最优解, 则可以考虑用动态规划解决。动态规划的实质是分治思 想和解决冗余, 因此, 动态规划是一种将问题实例分解为更小的、 相似的子问题, 并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。由 此可知, 动态规划法与分治法和贪心法类似, 它们都是将问题实例归纳为更小的、 相似的子问题, 并通过求解子问题产生一个全局最优解。其中贪心法的当前选择 可能要依赖已经作出的所有选择,但不依赖于有待于做出的选择和子问题。因此 贪心法自顶向下, 一步一步地作出贪心选择;而分治法中的各个子问题是独立的 (即不包含公共的子子问题),因此一旦递归地求出各子问题的解后,便可自下而 上地将子问题的解合并成问题的解。但不足的是,如果当前选择可能要依赖子问 题的解时, 则难以通过局部的贪心策略达到全局最优解;如果各子问题是不独立 的,则分治法要做许多不必要的工作,重复地解公共的子问题。解决上述问题的 办法是利用动态规划。 该方法主要应用于最优化问题,这类问题会有多种可能的 解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解。若存在 若干个取最优值的解的话,它只取其中的一个。在求解过程中,该方法也是通过 求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划 允许这些子问题不独立, 也允许其通过自身子问题的解作出选择,该方法对每一 个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算。 因此, 动态规划法所针对的问题有一个显著的特征,即它所对应的子问题树

中的子问题呈现大量的重复。 动态规划法的关键就在于, 对于重复出现的子问题, 只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不 必重新求解。

3.动态规划的基本概念
动态规划的数学描述离不开它的一些基本概念与符号, 因此有必要在介绍多 阶段决策过程的数学描述的基础上,系统地介绍动态规划的一些基本概念。 3.1 多阶段决策问题 如果一类活动过程可以分为若干个互相联系的阶段, 在每一个阶段都需作出 决策,一个阶段的决策确定以后,常常影响到下一个阶段的决策,从而就完全确 定了一个过程的活动路线,则称它为多阶段决策问题。 各个阶段的决策构成一个决策序列,称为一个策略。每一个阶段都有若干个 决策可供选择, 因而就有许多策略供我们选取,对应于一个策略可以确定活动的 效果,这个效果可以用数量来确定。策略不同,效果也不同,多阶段决策问题, 就是要在可以选择的那些策略中间,选取一个最优策略,使在预定的标准下达到 最好的效果. 3.2 动态规划问题中的术语 阶段: 把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求 解,过程不同,阶段数就可能不同.描述阶段的变量称为阶段变量。在多数情况 下,阶段变量是离散的,用 k 表示。此外,也有阶段变量是连续的情形。如果过 程可以在任何时刻作出决策, 且在任意两个不同的时刻之间允许有无穷多个决策 时,阶段变量就是连续的。 状态: 状态表示每个阶段开始面临的自然状况或客观条件,它不以人们的主 观意志为转移, 也称为不可控因素。 在上面的例子中状态就是某阶段的出发位置, 它既是该阶段某路的起点,同时又是前一阶段某支路的终点。 过程的状态通常可以用一个或一组数来描述,称为状态变量。一般,状态是 离散的,但有时为了方便也将状态取成连续的。当然,在现实生活中,由于变量 形式的限制,所有的状态都是离散的,但从分析的观点,有时将状态作为连续的 处理将会有很大的好处。此外,状态可以有多个分量(多维情形),因而用向量来 代表;而且在每个阶段的状态维数可以不同。

无后效性:我们要求状态具有下面的性质:如果给定某一阶段的状态,则在 这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定 时,整个过程也就确定了。换句话说,过程的每一次实现可以用一个状态序列表 示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,整个 线路也就完全确定。从某一阶段以后的线路开始,当这段的始点给定时,不受以 前线路(所通过的点)的影响。状态的这个性质意味着过程的历史只能通过当前 的状态去影响它的未来的发展,这个性质称为无后效性。 决策: 一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种 选择(行动)称为决策。在最优控制中,也称为控制。在许多间题中,决策可以 自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的 变量称决策变量, 因状态满足无后效性,故在每个阶段选择决策时只需考虑当前 的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。 策略: 由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决 策过程,可供选取的策略有一定的范围限制,这个范围称为允许策略集合。允许 策略集合中达到最优效果的策略称为最优策略。 给定 k 阶段状态变量 x(k)的值后,如果这一阶段的决策变量一经确定,第 k+1 阶段的状态变量 x(k+1)也就完全确定,即 x(k+1)的值随 x(k)和第 k 阶段的决 策 u(k)的值变化而变化,那么可以把这一关系看成(x(k),u(k))与 x(k+1)确定的对 应关系, x(k+1)=Tk(x(k),u(k))表示。 用 这是从 k 阶段到 k+1 阶段的状态转移规律, 称为状态转移方程。 最优性原理: 作为整个过程的最优策略,它满足:相对前面决策所形成的状 态而言,余下的子策略必然构成―最优子策略‖。

4.动态规划求解的基本步骤
动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过 对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确 定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态 规划的设计都有着一定的模式,一般要经历以下几个步骤。

初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

?????

动态规划决策过程示意图

(1)划分阶段: ,按照问题的时间或空间特征,把问题分为若干个阶段。在划 分阶段时, 注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法 求解。 (2)确定状态和状态变量: 将问题发展到各个阶段时所处于的各种客观情况用 不同的状态表示出来。当然,状态的选择要满足无后效性。 (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状 态转移就是根据上一阶段的状态和决策来导出本阶段的状态。 所以如果确定了决 策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两段各状态 之间的关系来确定决策。 (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止 条件或边界条件。 (5)程序设计实现:动态规划的主要难点在于理论上的设计,一旦设计完成, 实现部分就会非常简单。 根据上述动态规划设计的步骤,可得到大体解题框架如图所示。

动态规划设计的一般模式图

上述提供了动态规划方法的一般模式,对于简单的动态规划问题,可以按部

就班地进行动态规划的设计。下面,给出一个利用动态规划方法求解的典型例 子。 <数字三角形问题> 上图示出了一个数字三角形宝塔。数字三角形中的数字 为不超过 100 的整数。 现规定从最顶层走到最底层,每一步可沿左斜线向下或右 斜线向下走。 任务一:假设三角形行数≤10,键盘输入一个确定的整数值 M,编程确定是 否存在一条路径,使得沿着该路径所经过的数字的总和恰为 M,若存在则给出 所有路径,若不存在,则输出―NO Answer!‖字样。 任务二:假设三角形行数≤100,编程求解从最顶层走到最底层的一条路径, 使得沿着该路径所经过的数字的总和最大,输出最大值。 输人数据:由文件输入数据,任务一中文件第一行是三角形的行数 N 和整数 值 M。以后的 N 行分别是从最顶层到最底层的每一层中的数字。任务二中文件 数据格式同任务一,只是第一行中没有整数值 M。在例子中任务二的文件数据 表示如下: 输入:5 7 输出: 输出路径和最大值 38 ?? 7 或―No Answer!‖字样。 810 ?? 3 ? 8 2774 ?? 8?1?0 45265 ?? 2?7?4?4 图 3 数字三角形? 4 ? 5 ? 2 ? 6 ? 5 【分析】对于这一问题,很容易想到用枚举的方法去解决,即列举出所有路 径并记录每一条路径所经过的数字总和。 然后判断数字总和是否等于给定的整数 值 M 或寻找出最大的数字总和,这一想法很直观,而且对于任务一,由于数字 三角形的行数不大(<=10),因此其枚举量不是很大,应该能够实现。但对于任 务二,如果用枚举的方法,当三角形的行数等于 100 时,其枚举量之大是可想而 知的,显然,枚举法对于任务二的求解并不适用。其实,只要对对任务二稍加分 析,就可以得出一个结论: 如果得到一条由顶至底的某处的一条最佳路径,那么对于该路径上的每一 个中间点来说, 由顶至该中间点的路径所经过的数字和也为最大。因此该问题是 一个典型的多阶段决策最优化的问题。算法设计与分析如下:

对于任务一,合理地确认枚举的方法,可以优化问题的解法。由于从塔顶 到底层每次都只有两种走法,即左或右。设―0‖表示左,―1‖表示右,对于层数为 N 的数字塔, 从顶到底的一种走法可用一个 N-1 位的二进制数表示。 如例中二进 制数字串 1011,其对应的路径应该是:8—1—4—6。这样就可以用一个 N—l 位 的二进制数来模拟走法和确定解的范围。穷举出从 0 到 2n-1 个十进制数所对应 的 N-1 位二进制串对应的路径中的数字总和,判定其是否等于 M 而求得问题的 解。 对于任务二,采用动态规划中的顺推解法。按三角形的行划分阶段,若行数 为 n,则可把问题看做一个 n-1 个阶段的决策问题。从始点出发,依顺向求出第 一阶段、第二阶段……第 n—1 阶段中各决策点至始点的最佳路径,最终求出始 点到终点的最佳路径。 设:fk(Uk)为从第 k 阶段中的点 Uk 至三角形顶点有一条最佳路径,该路径 所经过的数字的总和最大,fk(Uk)表示为这个数字和;由于每一次决策有两个选 择,或沿左斜线向下,或沿右斜线向下,因此设: Uk1 为 k-1 阶段中某点 Uk 沿左斜线向下的点; Uk2 为 k-1 阶段中某点 Uk 沿右斜线向下的点; dk(Uk1)为 k 阶段中 Uk1 的数字;dk(Uk2)为 k 阶段中 Uk2 的数字。 因而可写出顺推关系式(状态转移方程)为: fk(Uk)=max{fk-1(Uk)+dk(Uk1),fk-1(Uk)+dk(Uk2)}(k=1,2,3,…,n) f0(U0)=0 经过一次顺推,便可分别求出由顶至底 N 个数的 N 条路径,在这 N 条路径所经 过的 N 个数字和中,最大值即为正确答案。

5.动态规划的应用实例
5.1 最短路线问题
[例 1]

美国黑金石油公司(The Black Gold Petroleum Company)最近在阿拉斯

加(Alaska)的北斯洛波(North Slope)发现了大的石油储量。为了大规模开发 这一油田, 首先必须建立相应的输运网络,使北斯洛波生产的原油能运至美国的 3 个装运港之一。在油田的集输站(结点 C)与装运港(结点 P1、P2、P3)之间 需要若干个中间站,中间站之间的联通情况如图 7-2 所示,图中线段上的数字代

表两站之间的距离(单位:10 千米) 。试确定一最佳的输运线路,使原油的输送 距离最短。 解:最短路线有一个重要性质,即如果由起点 A 经过 B 点和 C 点到达终点 D 是 一条最短路线,则由 B 点经 C 点到达终点 D 一定是 B 到 D 的最短路(贝尔曼最 优化原理) 。此性质用反证法很容易证明,因为如果不是这样,则从 B 点到 D 点 有另一条距离更短的路线存在,不妨假设为 B—P—D;从而可知路线 A—B—P —D 比原路线 A—B—C—D 距离短,这与原路线 A—B—C—D 是最短路线相矛 盾,性质得证。 根据最短路线的这一性质, 寻找最短路线的方法就是从最后阶段开始,由后向前 逐步递推求出各点到终点的最短路线,最后求得由始点到终点的最短路;即动态 规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。 按照动态规划的 方法,将此过程划分为 4 个阶段,即阶段变量 k 的位置为状态变量 S k ,按逆序算法求解。
? 1, 2, 3, 4 ;取过程在各阶段所处

10 8 M11 12
C

M31 6 4

8
P1

M21 6

7

6

9 M22 7 5 11 4

M32 7

3
P2

10 M12

9

7 M33

6

11 M23

5
P3

6 M34

3 4 k=4

k=1

k=2

k=3

图 7-2

当 k ? 4 时:由结点 M31 到达目的地有两条路线可以选择,即选择 P1 或 P2;故:
f 4 (S 4 ? M ?8 ? ) ? min ? ? ? 6 ?6 ?

31

选择 P2,由结点 M32 到达目的地有三条路线可以选择, 即选择 P1、 或 P3; P2 故:
f 4 (S 4 ?4? ? ? ? M 32 ) ? min ? 3 ? ? 3 ?7 ? ? ?

选择 P2,由结点 M33 到达目的地也有三条路线可以选择,即选择 P1、P2 或 P3; 故:
f 4 (S 4 ?7 ? ? ? ? M 33 ) ? min ? 6 ? ? 5 ?5? ? ?

选择 P3,由结点 M34 到达目的地有两条路线可以选择,即选择 P2 或 P3;故:
f 4 (S 4 ? M
34

?3? ) ? min ? ? ? 3 ?4?

选择 P2 当 k ? 3 时: 由结点 M21 到达下一阶段有三条路线可以选择, 即选择 M31、 M32 或 M33;故:
f3 (S 3 ?10 ? 6 ? ? ? ? M 21 ) ? min ? 7 ? 3 ? ? 10 ?6?5? ? ?

选择 M32 由结点 M22 到达下一阶段也有三条路线可以选择,即选择 M31、M32 或 M33;故:
f3 (S 3 ?9 ? 6 ? ? ? ? M 22 ) ? min ? 7 ? 3 ? ? 10 ?5 ? 5? ? ?

选择 M32 或 M33,由结点 M23 到达下一阶段也有三条路线可以选择,即选择 M32、M33 或 M34;故:
f3 (S 3 ?11 ? 3 ? ? ? ? M 23 ) ? min ? 4 ? 5 ? ? 9 ?6?3? ? ?

选择 M33 或 M34 当 k ? 2 时:由结点 M11 到达下一阶段有两条路线可以选择, 即选择 M21 或 M22;故:
? 8 ? 10 ? f 2 ( S 2 ? M 11 ) ? min ? ? ? 16 ? 6 ? 10 ?

选择 M22,由结点 M12,到达下一阶段也有两条路线可以选择,即选择 M22 或

M23;故:
? 9 ? 10 ? f 2 ( S 2 ? M 12 ) ? min ? ? ? 19 ? 11 ? 9 ?

选择 M22,当 k ? 1 时:由结点 C 到达下一阶段有两条路线可以选择,即选择 M11 或 M12;故:
?12 ? 16 ? f 1 ( S 1 ? C ) ? min ? ? ? 28 ?10 ? 19 ?

选择 M11,,而通过顺序(计算的反顺序)追踪(黑体标示)可以得到两条最佳 的输运线路:C—M11—M22—M32—P2;C—M11—M22—M33—P3。最短的输 送距离是 280 千米。 5.2 资源分配问题 所谓资源分配问题,就是将一定数量的一种或若干种资源(如原材料、机器 设备、资金、劳动力等)恰当地分配给若干个使用者,以使资源得到最有效地利 用。设有 m 种资源,总量分别为 bi(i = 1,2,?,m) ,用于生产 n 种产品,若用 xij 代表用于生产第 j 种产品的第 i 种资源的数量(j = 1,2,?,n) ,则生产第 j 种产品 的收益是其所获得的各种资源数量的函数,即 gj = f(x1j,x2j,?, xmj) 。由于总收 益是 n 种产品收益的和,此问题可用如下静态模型加以描述:
max z ?

?g
j ?1

n

j

?

n

x ij ? b i ( i ? 1, 2, ? , m )

j ?1

x ij ? 0

( i ? 1 , 2 , m, j ; ? ?

?, 2 n 1 ,

,

)

若 x ij 是连续变量,当 g j = f( x1 j , x 2 j ,?, 性规划模型;当 g j = f( x1 j , x 2 j ,?,
xmj

xmj

)是线性函数时,该模型是线

)是非线性函数时,该模型是非线性规
xmj

划模型。若 x ij 是离散变量或(和) g j = f( x1 j , x 2 j ,?,

)是离散函数时,此

模型用线性规划或非线性规划来求解都将是非常麻烦的。然而在此情况下,由于 这类问题的特殊结构, 可以将它看成为一个多阶段决策问题,并利用动态规划的 递推关系来求解。 本例只考虑一维资源的分配问题, 设状态变量 s k 表示分配于从第 k 个阶段至 过程最终(第 N 个阶段)的资源数量,即第 k 个阶段初资源的拥有量;决策变 量 xk 表示第 k 个阶段资源的分配量。于是有状态转移律:
S k ?1 ? S k ? x k

允许决策集合:
D k (S k ) ? {xk | 0 ? xk ? S k }

最优指标函数(动态规划的逆序递推关系式) :
f k ( S k ) ? m ax { g k ( x k ) ? f k ? 1 ( S k ? 1 )}
0 ? xk ? S k

(k ? N , N ? 1 , N ? ? , 2

,1)

f N ?1 ( S N ?1 ) ? 0

利用这一递推关系式,最后求得的 f 1 ( S 1 ) 即为所求问题的最大总收益,下面来看 一个具体的例子。

[例 2] 某公司拟将 500 万元的资本投入所属的甲、 丙三个工厂进行技术改造, 乙、 各工厂获得投资后年利润将有相应的增长,增长额如表 7-1 所示。试确定 500 万 元资本的分配方案,以使公司总的年利润增长额最大。 表 7-1 投 100 资额 万元 甲 30 乙 50 丙 40

200 万元 70 100 60

300 万 元 90 110 110

400 万元 120 110 120

500 万元 130 110 120
? 1, 2, 3

解:将问题按工厂分为三个阶段 k=1,2,3,设状态变量 S k ( k

)代表从

第 k 个工厂到第 3 个工厂的投资额,决策变量 x k 代表第 k 个工厂的投资额。于是 有状态转移率 S k ? 1 ? S k ? x k 、允许决策集合 D k ( S k ) ? { x k | 0 ? x k ? S k } 和递推关系 式:
f k ( S k ) ? m ax { g k ( x k ) ? f k ? 1 ( S k ? x k )}
0 ? xk ? S k

(k ? 3 , 2 , 1 )

f 4 (S 4 ) ? 0

当 k ? 3 时:

f 3 ( S 3 ) ? max { g 3 ( x 3 ) ? 0} ? max { g 3 ( x 3 )}
0 ? x3 ? S 3 0 ? x3 ? S 3

于是有表 7-2,表中 x 3? 表示第三个阶段的最优决策。 表 7-2
S3
x3
?

(单位:百万元) 0 1 2 0 0 1 0.4 2 0.6

3 3 1.1

4 4 1.2 2

5 5 1.

f3 (S 3 )

当 k ? 2 时: f 2 ( S 2 ) ? m ax { g 2 ( x 2 ) ? f 3 ( S 2 ? x 2 )} 。于是有表 7-3。
0 ? x2 ? S 2

表 7-3 (单位:百万元) x g2(x2)+f3(s2 - x2) 2 0 1 2 S 2 0 0+ 0 1 0+ 0.5+ 0.4 0 2 0+ 0.5+ 1.0 0.6 0.4 +0 3 0+ 0.5+ 1.0 1.1 0.6 +0.4 4 0+ 0.5+ 1.0 1.2 1.1 +0.6 5 0+ 0.5+ 1.0 1.2 1.2 +1.1 当 k ? 1 时:
f 1 ( S 1 ) ? max { g 1 ( x 1 ) ? f 2 ( S 1 ? x 1 )}
0 ? x1 ? S 1

3

4

5

f 2 (S 2 )

x2

?

0 0.5 1.0 1.1 +0 1.1 +0.4 1.1 +0.6 1.1 +0 1.1 +0.4 1+0 1. 2.1 1.6 ,2 1.4

0 1 2 2 1 2

于是: g1(x1)+f2(s1 – x1) x 0 1 2 3 1 S 1 50+2.1 0.3+1.6 0.7+ 1.4 0.9+ 1.0

4

5

f1 (S1 )

x1

?

1.2+ 0.5

1.3+0

2.1

0,2

然后按计算表格的顺序反推算,可知最优分配方案有两个: (1)甲工厂投资 200 万元,乙工厂投资 200 万元,丙工厂投资 100 万元; (2)甲工厂没有投资, 乙工厂投资 200 万元,丙工厂投资 300 万元。按最优分配方案分配投资(资源) , 年利润将增长 210 万元。 5.3 用动态规划求解非线性规划问题 非线性规划问题的求解是非常困难的;然而,对于有些非线性规划问题,如 果转化为用动态规划来求解将是十分方便的。 [例 3] 用动态规划求解
max z ? x 1 ? x 2 ? x 3
2

x 1 ? x 2 ? x 3 ? 36 x1 , x 2 , x 3 ? 0

解: 阶段:将问题的变量数作为阶段,即 k=1,2,3; 决策变量:决策变量 x k ; 状态变量: 状态变量 S 代表第 k 阶段的约束右端项, 即从 x k 到 x 3 占有的份额;
k

状态转移律: S k ? 1 ? S k ? x k ; 边界条件: S 1 ? 3 6 , f 4 ( S 4 ) ? 1 ; 允许决策集合: 0 ? x k ? S k 当 k ? 3 时:
f 3 ( S 3 ) ? max { x 3 ? f 4 ( S 4 )} ? max { x 3 } ? S 3 | x ? ? S
0 ? x3 ? S 3 0 ? x3 ? S 3
3 3

当 k ? 2 时:
f 2 ( S 2 ) ? max { x 2 ? f 3 ( S 3 )} ? max { x 2 ( S 2 ? x 2 )}
2 2 0? x2 ? S 2 0? x2 ? S 2

设h
dh dx 2

? x 2 ( S 2 ? x 2 ) , ddxh ? 2 x 2 ( S 2 ? x 2 ) ? x 2
2
2

2

? 2 x2 (S 2 ? x2 ) ? x2 ? 0
2

x2 ? 0 S

2

又因 x,所以:

d h d x2
2 2

2

|x

2

?0

? 2S2 ? 0

,x

2

? 0



f 2 (S 2 )

的极小值点 , x 2 ? 2 S 2 是 f 2 ( S 2 ) 的极大值点 3

d h d x2
2

? 2( S 2 ? x2 ) ? 2 x2 ? 2 x2 ? 2 S 2 ? 6 x2

于是:
f 2 (S 2 ) ?
4 27

S 2 | x? ? 2 S
2 3

3

2

当k

? 1 时:

f 1 ( S 1 ) ? max { x 1 ? f 2 ( S 2 )} ? max { x 1 ?
0 ? x1 ? S 1 0 ? x1 ? S 1

4 27

( S 1 ? x1 ) }
3

同上可得:
f 1 ( S 1 ? 36 ) ?
1 64

S1 ?
4

1 64

? 36

4

? 26244 | x ? ? 1 S
1 4

1 ?9

由 S 2 ? S 1 ? x 1? ? 36 ? 9 ? 27 ,有 x 由 S3
? ?

? 2

?

2 3

S2 ?

2 3

? 27 ? 18

? S 2 ? x 2 ? 2 7 ? 1 8 ? 9 ,有 x 3 ? S 3 ? 9
?

于是得到最优解 X ? ? (9,1 8, 9 ) ,最优值 z

? 26244



6. 结束语
从以上实例分析可以看出,用动态规划解决多阶段决策问题效率是很高的, 而且思路清晰简便,同时易于实现,虽然使用动态规划方法也有一定的限制,如 状态变量必须满足无后效性,并且只适用一些维数相当低的问题等。但是,可以 看到,动态规划方法的应用是很广的,已成功解决了许多实际问题,具有很强的 实用性。

参考文献
[1] 徐渝,贾涛.运筹学[M].北京:清华大学出版社, 2005. [2] 韦兰用.最优控制问题研究综述[D].吉林大学,2006. [3] 谬慧芬,邵小兵.动态规划算法的原理及应用[J].中国科技信息, 2005(21). [4] 解可新,韩立兴,林友联.最优化方法[M].天津:天津大学出版社, 1997. [5] 赵旋. 变分法、最小值原理、动态规划和最优控制[J].自动化博览,1997


赞助商链接
相关文章:
6、动态规划算法的应用
6、动态规划算法应用 - 数学与计算机学院 课程设计说明书 课程名称: 课程代码: 题目: 算法设计与分析-课程设计 7106620 动态规划算法应用 年级/专业/班: 学...
动态规划算法应用
动态规划算法应用 - 动态规划算法应用 1、实验项目: 动态规划算法运用 2、实验目的: 了解动态规划基本思想了,能用动态规划法解决实际问题 3、实验要求: 要求学生...
动态规划法
动态规划法 - 实验报告(2016/2017 学年 第二学期) 课程名称 实验名称 实验时间 指导单位 指导教师 2017 算法分析与设计 动态规划法 年 4 月 28 日...
常见动态规划算法问题策略分析
常见动态规划算法问题策略分析 - 常见动态规划算法问题 策略分析 1 目录 一、 动态规划策略 ... 1 1....
动态规划的特点及其应用
动态规划的特点及其应用 - 动态规划的特点及其应用 目录 (点击进入) §1 动态规划的本质 §1.1 多阶段决策问题 §1.2 阶段与状态 §1.3 决策和策略 §1.4...
浅谈动态规划的特点及其解题应用 算法设计
浅谈动态规划的特点及其解题应用 算法设计 - 浅谈动态规划的特点及其解题应用 魏月圆 (安徽中医学院 医药信息管理学院,安徽 合肥 230031) 摘要: 摘要:动态规划就是...
动态规划算法综述
动态规划算法综述 - 动态规划算法综述 学院:信息与电子工程学院 专业:计算机技术 学号:10076169109 姓名:李楠 1 动态规划算法综述 1 引言 动态规划 (dynamic ...
动态规划及其在资源分配中的应用
动态规划及其在资源分配中的应用摘要:在概述动态规划原理的基础上,提出了动态规划...Fk(Sk)=Max Rk(Dk)+ +Fk+Fk(Sk+1) F4(S4)=0 k=3时,计算如下: _...
动态规划算法的应用实验报告
动态规划算法应用实验报告 - 实验二 一、实验目的 动态规划算法应用 1.掌握动态规划算法的基本思想,包括最优子结构性质和基于表格的最优值计算方法。 2.熟练...
动态规划算法在TBD中的应用
动态规划算法在TBD中的应用 - 动态规划算法在 TBD 中的应用 绪论 动态规划的基本思想是把多阶段过程转化为一系列单阶段问题,利用各阶段 之间的关系,逐个求解,使...
更多相关标签: