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

运筹学-动态规划


第16章 动态规划
动态规划是运筹学的一个分支,它是解决 多阶段决策过程最优化的一种数学方法。 该方法由美国数学家贝尔曼 (R.E.Bellman)等人在20世纪50年代初 提出的

§1 多阶段决策问题
多阶段决策问题例子:
例16-1 最短路径问题:求图16-1中从A到F的最短路径。

将问题可分为五个阶段 第一阶段:从到A或B; 第二阶段:从B到C; 第三阶段:从C到D; 第四阶段:从D到E;

第五阶段:从E到F;
每个阶段都要作出一个决策,决定向哪个点前进一 步。各阶段的决策有机的联系着,本阶段的决策影响 着下一阶段的决策,以至于影响整体效果,决策者在 做决策时,不应尽考虑本阶段最优,还应考虑对最终 目标的影响。各阶段的决策形成一个决策序列,通常 称之为一个策略,不同的策略,其效果也不同。现在 的问题就是要在允许的策略中,求出A到F的距离最 短的策略。

例16-2机器负荷分配问题:某种机器能在高低两种不同的 负荷下工作,在高负荷下有 u 台机器进行生产时,产品的 产量 s ? 8u ,工作一年后完好的机器数为 0.7u ,在低负荷 下有台 v 机器进行生产时,产品的产量 s ? 5v ,工作一年 后完好的机器数为 0.9v 。试制订一个五年计划,决定在每 年年初如何分配完好的机器在两种不同负荷下生产的数量, 才能使在五年内产品的产量为最高?
可将该问题按年划分为五个阶段:第一阶段即第一年;第二阶 段即第二年;第三阶段即第三年;第四阶段即第四年;第五阶 段即第五年。设开始时完好机器数量为x1 ,第 k年能投入生产的机器数为xk,第 k年高负荷下工作的机器 数为 uk 台,效益为 Rk ,则

xk ?1 ? 0.7 xk ? 0.9( xk ? uk ), Rk ? 8uk ? 5( xk ? uk ) , 0 ? uk ? xk
Rk 最大。 原问题就是确定uk ,k=1,2,3,4,5,使 ? k ?1
5

例16-3部件的生产计划问题:某车间每月底要为下一个月 提供出一定数量的部件给组装车间,各月份中生产这种部 件所需工时不同,生产出来多余的部件可以存入库中,但 库房的最高贮量为H=9,求某6个月中每月生产多少部件, 才能使消耗的总工时最少?最小工时是多少?各月的需求 量与单位工时如下表:
月份 k 需求量 1 8 11 2 5 18 3 3 13 4 2 17 5 7 20 6 4 10

dk

单位工时

ak

将该问题按月份划分为六个阶段, Sk为第k月开始时的库存, uk为第k 的生产量 。

uk

sk
K

dk
图 7-2

sk?1 ? sk ?uk ?dk

设 f k ( sk 为当第 k 月开始时库为sk 直至第6月止,生产部件 ) (a k uk ? f k ?1 ( sk ?1 )) 累计工时的最小值,则 f k ( sk ) ? min u 。f1 (s1 )即为要求的最小工时。
k

例16-4 原料分配问题:利用已有的12吨原料制造 A、B 两种产品,已知每制造一吨 A产品需要原 料4吨,每制造一吨 B 产品需要原料2吨,而两种产 品在市场上的价格分别为每吨8千元和1万元,求如 何安排生产计划能使总效益最大?
可将分配 A 、 B 两产品的产量看作两个阶段:第一 阶段:确定生产 A 产品多少吨;第二阶段:确定生 产B产品多少吨。求出使总效益最大的决策序列。

例 16-5 人员派谴问题:向三个售货区域派谴 四名推销员,各区人数及效益如下表:
人数
区域 1 2 3 0 0 0 0 1 16 16 10

增加效益数
2 25 17 14 3 30 21 16 4 32 22 17

问如何派谴人员能使总效益最高? 该问题可按区域分为三个阶段:第一阶段:确定向 1区派几名推销员;第二阶段:确定向2区派几名推 销员;第三阶段:确定向3区派几名推销员。求出 使总效益最大的策略。

例16-6货物装载问题:某海轮的总装载能力为 w 千 吨(不妨设w=0,1,2, ?,18千吨)需装载四种货物, 规定海轮上每种货物不超过 2 件,各种货物的单位重 量,单位运费如下表,问怎样装这些货物,才能使总 运费最大?
货物种类 1 2 3 4
表8-6

单位重量 5 1 3 4

每件运费 9 1 4 7

将该问题按四种货物分为四个阶段,第k阶段确定第k种货 物的装运件数。设Rk为第 k 种货物的运费。求出使 最大的装运策略。

?R
k ?1

4

k

§2 动态规划的基本概念与基本原理
2.1 动态规划的基本概念 1. 阶段(Stage) 将问题恰当地划分成若干相互联系的阶段,通常用 为阶段变量。可按时间顺序或空间特征划分阶段。

k



2. 状态变量(State Variable) 描述过程状态的变量,可以用一个数,一组数或一个向量来 描述,常用 sk 表示第 k 阶段的状态变量。 不可控变量。
最短路问题中,每 个阶段状态表示该 阶段初始点的集合。 状态集合用Sk表示, S1={B1,B2}

3.决策变量(Decision Variable) 某阶段状态给定以后,由该状态演变到下一阶段某状态的选择称 为决策,决策变量是描述决策的变量,常用 uk ( s k ) 或 d k ( s k ) 表示, 它是第 k 阶段状态处于 sk 时的决策变量。 决策变量的取值往往在一定的范围之内,用 D k ( s k ) 表示允许决 策集合, 则有 u k ( s k ) ? D k ( s k ) 。 例如, 例 8-2 中的 D1 ( s1 ) ? {0,1,2,?, s1 } 。 若由第 k 阶段的状态变量 s k 和决策变量 u k 可确定出第 k ? 1 阶段 的 状 态 变 量 s k ?1 , 则 称 此 规 律 为 状 态 转 移 方 程 , 一 般 形 式 为

s k ?1 ? Tk ( s k , uk ) 。
例如,例 8-2 中的状态转移方程为 s k ? 1 ? 0.7 uk ? 0.9( s k ? uk )

4.策略(Policy) 由过程的第一阶段开始到最后一阶段为止称为问题的全 过程,由各阶段的决策 uk ( s k ) (i=1,2,…,n)构成的策略序列 称 为 全 过 程 策 略 ( 简 称 策 略 ) 记 为 P 1, n , 即

P1,n ( s1 ) ? ?u1 ( s1 ), u2 ( s 2 ),? , un ( s n )?

由第 k 阶段开始到最后一阶段为止的过程,称为 k 子过 程,其策略称为 k 子过程策略(简称子策略)记为

Pk ,n ( s k ) ? ?uk ( s k ),? , un ( s n )?

在实际问题中, 可供选择的策略有一定的范围, 称之为允 许策略集合,从中找出的效果最佳的策略称为最优策略。

5.指标函数(Return Function)

指标函数(最大收益函数-Maximum Return Function ,或最小成 本函数-Minimum Cost Function)是反映策略优劣的一种数量指标 ,它是一个定义在全过程和所有后部子过程上的函数。
记V1,n (s1 , p1,n ) -表示初始状态为s1 采取策略p1,n时全过程的指标函数
Vk ,n ? Vk ,n (sk , pk ,n )-第k阶段状态为sk

采取策略pk,n时后部子过程的指标函数

动态规划的方法就是在允许策略中寻求最优策略。指标函数 的最优值,记为 f k (sk )

f k (sk ) ?

pk ,n ?Pk ,n ( sk )

opt

Vk ,n (sk , pk ,n )
n

指标函数应具有可分离性,一般的形式有:

(1)Vk ,n ? ? v j (s j , u j ),(2)Vk ,n ? ? v j (s j , u j )
j ?k j ?k

n

6.最优策略和最优轨线
* 使指标函数 Vk ,n (sk , pk ,n )达到最优值的策略 pk ,n

称为后部子过程中的最优策略。
* 使指标函数 V1,n ? V1,n (s1, p1,n ) 达到最优的策略 p1,n

称为全过程中的最优策略。
* * * * 按最优策略 p1 和状态转移方程 s ? T ( s , u ,n k ?1 k k )得出的状态序列

* * * {s1 , s2 ,..., sn ?1}称为最优轨线。

16.2 动态规划的基本定理和基本方程
现在结合解决最短路线问题来介绍动态规划方法的 基本思想,最短路线有一个重要特性: 如果由起点A经过P点和H点而到达终点G是一条最 短路线,则由点P出发经过H点到达终点G的这条子 路线,对于从点P出发到达终点的所有可能选择的不 同路线来说,必定也是最短路线。 A P H G

一般地:

? 贝尔曼(R.E.Bellman)最优性原理如下: ? 作为整个过程的最优策略具有这样的性 质: ? 即无论过去的状态和决策如何,对于先 前决策所形成的状态而言,其后的所有 决策应构成最优策略。

人们逐步认识到:

对于不同类型问题所建立的严格定义的动态规划模 型,必须对相应的最优性原理给以必要的验证。即是说, 最优性原理不是对任何决策过程都普遍成立的。而且, “最优性原理”与动态规划基本方程并不是无条件等 价的,两者之间也不存在确定的蕴含关系。
反映动态规划基本方程的是最优性定理,它是策 略最优性的充要条件。 最优性原理仅仅是策略最优性的必要条件,它是 最优性定理的推论。

动态规划的基本方程或者最优性定理作为动态规划的 理论基础。

动态规划的最优性定理:设阶段数为n的多阶段决 策过程,其阶段编号为k=1,…,n,初始状态为s1 * * * * ,允许策略 P1,n ? (u1 , u2 ,...,un ) 是最优策略的充要条件是对任一个k,1<k<n 和,s1∈S1有
? V1,n ( s1 , p ) ? opt ?V1,k ?1 ( s1 , p1,k ?1 ) ? p1 , k ? 1?P1 , k ? 1 ( s1 ) ?
* 1, n

以~ sk 为起始点有一个允许子 策略集合,记为 Pk ,n (~ sk ) 其中 p ? ( p , p ), ~ s ? T (s , u )
1,n 1,k ?1 k ,n k k ?1 k ?1 k ?1

? ~ opt Vk ,n ( sk , pk ,n )? pk , n ?Pk , n ( ~ sk ) ?

?k 是由给定初始状态s1和子策略p1,k ?1确定的第k阶段状态。 s

当V是效益函数时,opt取max;当V是损失函数时, opt取min。

由上述最优性定理得到推论:
定理16.2.2 * 若允许策略p1 的k ,1 ? k ? n, 它的 , n 是最优策略,则对任意
* * * 子策略pk ,n 对于以sk ? Tk ?1 ( sk , u k到n的子过程 ?1 k ?1 )为起点的

* * 来说,必是最优策略( 注意:k阶段状态sk 是由s1和p1 , k ?1确定的)

此推论就是前面所说R.Bellman等人于20世纪50 年代提出的的动态规划的“最优性原理”。它 仅仅是最优策略的必要条件。即一个最优策略 的子策略总是最优的。

16.2.2 基本方程: 由最优性定理
? V1,n ( s1 , p ) ? opt ?V1,k ?1 ( s1 , p1,k ?1 ) ? p1 , k ? 1?P1 , k ? 1 ( s1 ) ?
* 1, n

? ~ opt Vk ,n ( sk , pk ,n )? pk , n ?Pk , n ( ~ sk ) ?

我们有
f k (sk ) ? Vk ,n (sk , p ) ?
* k ,n

pk . n ?Pk ,n ( sk )

opt

?V

k

(sk , u,k ) ? Vk ?1,n (sk ?1 , pk ?1,n )

?

? ? ? opt ?Vk (sk , u,k ) ? opt Vk ?1,n (sk ?1 , pk ?1,n )? u k ?u k ( sk ) ? pk ?1,n ?Pk ?1,n ( sk ?1 ) ?
? opt Vk ( sk , u,k ) ? f k ?1 ( sk ?1 )
uk ?uk ( sk )

指标 函数 定义

?

?

得到基本方程

f k ( sk ) ? opt Vk ( sk , u,k ) ? f k ?1 ( sk ?1 )
uk ?uk ( sk )

?

?

终端f n?1 ( sn?1 ) ? 0

16.3 逆序解法和顺序解法
在最短路线问题中,若找到了A→B1→C2→D1→E2→F是 由A到F的最短路线,则D1→E2→F应该是由D1出发到F点的 所有可能选择的不同路线中的最短路线。

此特性用反证法易证。因为如果不是这样,则从点P 到F点有另一条距离更短的路线存在,把它和原来最短路 线由A点到达P点的那部分连接起来,就会得到一条由A点 到F点的新路线,它比原来那条最短路线的距离还要短些。 这与假设矛盾,是不可能的。

根据最短路线这一特性,寻找最短路线的方法,就是 从最后一段开始,用由后向逐步递推的方法,求出各点到 F点的最短路线,最后求得由A点到F点的最短路线。 所以,动态规划的方法是从终点逐段向始点方向寻 找最短路线的一种方法。如图16-3表示。 行进方向 ︱ 1︱ 2 ︱ 3 ︱ 4 ︱5 ︱ 始点 终点 动态规划寻优途径 图 16—3

下面按照动态规划的方法,将例1从最后一段 开始计算,由后向前逐步推移至A点。

例 16-1 用动态规划求解最短路问题

令f k ( s k )表示从 s k 到F的最短距离 , d k ( s k , uk ( s k ))表示从 s k 到uk ( s k )的距离

k ? 5, f 5 ( E 1 ) ? 4 f5 (E2 ) ? 3

u5 ( E 1 ) ? F u5 ( E 2 ) ? F

? d 4 ( D1 , E 1 ) ? f 5 ( E 1 ) ? ? 3 ? 4? k ? 4, f 4 ( D1 ) ? m in? ? ? m in? ? ? 7 u4 ( D1 ) ? E1 ? 5 ? 3? ?d 4 ( D1 , E 2 ) ? f 5 ( E 2 )? ? d 4 ( D2 , E 1 ) ? f 5 ( E 1 ) ? ? 6 ? 4? u4 ( D2 ) ? E 2 f 4 ( D2 ) ? m in? ? ? m in? ??5 ? 2 ? 3? ? d 4 ( D 2 , E 2 ) ? f 5 ( E 2 )?

f 4 ( D1 ) ? 7
f 4 ( D3 ) ?

f 4 ( D2 ) ? 5

? d 4 ( D3 , E 1 ) ? f 5 ( E 1 ) ? m in? ? d ( D , E ) ? f ( E ) g 5 2 ? 4 3 2 ? ?1 ? 4 ? ? m in? ??5 ? 3 ? 3?

u4 ( D3 ) ? E1
? d 3 (C 1 , D1 ) ? f 3 (C 1 ) ? min? ? d 3 (C 1 , D 2 ) ? ? d 3 (C 2 , D1 ) ? f 3 (C 2 ) ? min? ? d 3 (C 2 , D 2 ) ? ? d 3 (C 3 , D 2 ) ? f 3 (C 3 ) ? min? ? d 3 (C 3 , D 3 ) ? f 4 ( D1 ) ? ?5 ? 7 ? ? ? min? ? ? 12 f 4 ( D 2 )? ?8 ? 5? f 4 ( D1 ) ? ?4 ? 7 ? ? ? min? ? ? 10 f 4 ( D 2 )? ? 5 ? 5? f 4 ( D 2 )? ? 3 ? 5? ? ? min? ??8 f 4 ( D 3 )? ? 4 ? 5?

u3 (C1 ) ? D1 u3 (C 2 ) ? D2 u3 (C 3 ) ? D2

? d 3 (C 1 , D1 ) ? f 3 (C 1 ) ? min? ? d 3 (C 1 , D 2 ) ? ? d 3 (C 2 , D1 ) ? f 3 (C 2 ) ? min? ? d 3 (C 2 , D 2 ) ?

f 4 ( D1 ) ? ?5 ? 7 ? ? ? min? ? ? 12 f 4 ( D 2 )? ?8 ? 5? f 4 ( D1 ) ? ?4 ? 7 ? ? ? min? ? ? 10 f 4 ( D 2 )? ? 5 ? 5?

u3 (C1 ) ? D1 u3 (C 2 ) ? D2 u3 (C 3 ) ? D2

? d 3 (C 3 , D 2 ) ? f 4 ( D 2 )? ? 3 ? 5? f 3 (C 3 ) ? min? ? ? min? ??8 ? 4 ? 5? ? d 3 (C 3 , D 3 ) ? f 4 ( D 3 )?

? d 3 ( C 4 , D 2 ) ? f 4 ( D 2 )? ? 8 ? 5? f 3 (C 4 ) ? min? ? ? min? ??9 ? 4 ? 5? ? d 3 ( C 4 , D 3 ) ? f 4 ( D 3 )?

u3 (C4 ) ? D3

? d 2 ( B1 , C 1 ) ? f 3 (C 1 ) ? 2 ? 12 ? ? f 2 ( B1 ) ? m i n?d 2 ( B1 , C 2 ) ? f 3 (C 2 ) ? m i n? 3 ? 10 ? 13 ? d ( B , C ) ? f (C ) ? 6?8 3 3 ? ? 2 1 3 ? d 2 ( B 2 , C 2 ) ? f 3 (C 2 ) ?8 ? 10 ? ? f 2 ( B 2 ) ? m i n?d 2 ( B 2 , C 3 ) ? f 3 (C 3 ) ? m i n? 7 ? 8 ? 15 ? d ( B , C ) ? f (C ) ?7?9 3 4 ? ? 2 2 4 ? d 1 ( A, B1 ) ? f 2 ( B1 ) ? ?4 ? 13? f 1 ( A) ? m i n? ? ? m i n? ? ? 17 ?5 ? 15? ?d 1 ( A, B 2 ) ? f 2 ( B 2 )?

u2 ( B1 ) ? C 2

u2 ( B2 ) ? C 3
u1 ( A) ? B1

f 1 ( A) ? ? d 1 ( A, B1 ) ? f 2 ( B1 ) ? m in? ? d ( A , B ) ? f ( B ) 2 2 2 ? ? 1 ?4 ? 13? ? m in? ? ? 17 ?5 ? 15?

u1 ( A) ? B1
即从A到F的最短距离为17,再按计算 顺序反推得到最优决策序列{uk},即:

u1 ( A) ? B1 , u2 ( B1 ) ? C 2 , u3 (C 2 ) ? D2 , u4 ( D2 ) ? E 2 , u5 ( E2 ) ? F .

最优路线为: A

B1 C2

D2

E2

F

f k ( s k ) ? min ?d k ( s k , uk ( s k )) ? f k ?1 ( uk ( s k ))?, k ? 5,4,...,1; f 6 ( F ) ? 0
uk ( x )

从计算过程,第k段与第k+1段有如下关系:

计算效率分析:
对上面 5个阶段的最短路径问题, 容易计算这种方法进行 了22次加法运算,12次比较运算,比穷举法计算量小。 其次,动态规划的计算不仅得到从A到F的最短距离,而 且得到中间任一点到F的最短距离

一般来说,第k段与第k+1段的递推关系为:
f k ( sk ) ? opt
uk ?Dk ( sk )

?v k ( sk , uk ( sk )) ?
f n?1 ( s n ?1 ) ? 0

f k ?1 ( uk ( s k ))?, k ? n, n ? 1, ,...,1;

边界条件为

上述递推关系式称为动态规划的基本方程。

现将动态规划方法的基本思想总结下: ① 动态规划方法的关键是写出基本的递推关系式 和恰当的边界条件。因而要把把原问题分成许多互 相联系的子问题,每个问题的求解中,均利用它后 面一个子问题的最优结果,依次进行,最前面一个 子问题的最优解,就是原问题的最优解。

?v k ( s k , uk ( s k )) ? f k ?1 (uk ( s k ))? ② 在递推方程: f k ( s k ) ? min u (s )
k k

中决策 uk ( s k )的结果,既影响 v k ( sk , uk ( sk )) ,又影响后阶段 的最优决策。 一般多阶段决策过程的最优策略和某一阶段的最优决策 一般是不同的,最优策略是从全局来考虑的。动态规划的方 法是把当前阶段和未来阶段分开,但又把当前效益和未来效 益结合起来考虑的一种最优化方法。

③ 各阶段的最优决策 uk ( sk ) 都是初始状态的函数, 若初始状态 s 1 已知,则整个问题的最优策略由其经 过的各阶段的状态可逐步转移求得。

f k ( s k ) ? min ?d k ( s k , uk ( s k )) ? f k ?1 ( uk ( s k ))?, k ? n, n ? 1, ,...,1;
uk ?Dk ( sk )

边界条件为

f n?1 ( s n?1 ) ? 0

上面的解法中以A为起点,F为终点,但从F到A的解 法: 即当初始状态s1已知,从k=n从后往前推算,求得 各阶段的最优决策和最优指标函数,最后算出f(s1) 的解法称为逆序解法,

由于线路网络的两端都是固定的,且线 路上的数字是表示两点间的距离,则从A 点计算到F点和从F点计算到A点的最短路 线是相同的 .
以A为起点,F为终点从A到F的解法,称为顺序解法。

16.3逆序解法与顺序解法
逆序解法(后向动态规划方法) 顺序解法(前向动态规划方法) 顺序解法的寻优方向与过程的行进方向相同, 计算时从第一段开始逐段向后递推,计算后一 阶段要用到前一阶段的求优结果,最后一段计 算的结果就是全过程的最优结果。

一般地说,当初始状态给定时可用逆序 解法,当终止状态给定时可用顺序解法。

?

两种解法区别

1.状态转移方式不同
逆序: sk+1=Tk(sk ,uk) 顺序: sk=Tk(sk+1,uk)

2.指标函数的定义不同

2.2.2.基本方程形式不同
当指标函数为阶段指标和形式,

逆推解法

顺推解法

2.2.3、基本方程分段求解时的几种常见算法
连续型:解析方法或线性规划方法 ? 解法 ? 连续变量的离散化解法 ? 高维问题的降维法及疏密格子点法 难! 没有固定的方法 具体模型具体分析 离散型:分段穷举法

要求:经验 、技巧、灵活

§16.3

逆推解法和顺推解法

例16.3.2 某公司拟将某种设备6套,分配给所属的A、B、C三 个用户。各用户获得此设备后,预测可创造的利润如下表所示, 问这6套设备应如何分配给这3个用户,使得所创造的总利润为 最大?
用户 设备套数 A用户 B用户 C用户

0 1 2 3 4 5 6

0 4 9 12 14 16 19

0 3 8 11 15 17 18

0 5 10 12 14 16 17

解:将问题按用户个数分为三个阶段,A、B、C三个用户分别编
号为1、2、3。
设sk=分配给第k个用户至第3个用户的设备套数,k=1、2、3。 uk=分配给第k个用户的设备套数。

用逆推解法:
已知s1=6,状态转移方程为:

s2 ? T1 (s1 , u1 ) ? s1 ? u1
s4 ? T2 (s3 , u3 ) ? s3 ? u3

s3 ? T2 (s2 , u2 ) ? s2 ? u2

fk (sk )表示第k阶段设备套数为sk , 采取最优策略可获的最大利润。
基本方程为

f k (sk ) ? max ?vk (sk , uk ) ? f k ?1 (sk ?1 )? , k ? 3, 2,,1;
uk ?Dk ( sk )

边界条件为:f 4 ( s4 ) ? 0

当k ? 3,时,f3 ( s3 ) ? max {v3 ( s3 , u3 ) ? f 4 ( s4 )} ? v3 ( s3 , u3 ),

s3 (s3 ? 0,1, 2,3, 4,5,6)
显然将s3套设备都分配给第3个用户时,也就是u3=s3时,第3阶 段的指标值(即第3个用户的盈利)为最大。
其数值计算见下表。

0?u3 ? s3

当k ? 3,时,f3 ( s3 ) ? max {v3 ( s3 , u3 ) ? f 4 ( s4 )} ? v3 ( s3 , u3 ),
0?u3 ? s3

当k ? 2,时,f 2 ( s2 ) ? max {v2 ( s2 , u2 ) ? f3 ( s3 )} s ? T (s , u ) ? s ? u 0?u2 ? s2 3 2 2 2 2 2

s 2 u2
0 1 2 3

v2 (u2 ) ? f3 (s3 )
0 0 0+5 0+10 0+12 3+0 3+5 3+10 8+0 8+5 11+0 1 2 3 4 5 6

f 2 (s2 )
0 5 10 13 0 0 0

u2

1,2

4
5 6

0+14
0+16 0+17

3+12
3+14 3+16

8+10
8+12 8+14

11+5
11+10 11+12

15+10
15+5 15+10 17+0 17+5

18
21 18+0 25

2
3 4

当k ? 3,时,f3 ( s3 ) ? max {v3 ( s3 , u3 ) ? f 4 ( s4 )} ? v3 ( s3 , u3 ),
0?u3 ? s3

当k ? 2,时,f 2 ( s2 ) ? max {v2 ( s2 , u2 ) ? f3 ( s3 )} s ? s ? u 3 2 2 0?u2 ? s2

0 5 10 13 18 21 25

0 0 0
1,2

0 0 0

当k ? 1时,s1 ? 6,
f1 (6) ? max[v1 (u1 ) ? f 2 (6 ? u1 )],
0 ? x1 ? s1

u1 0 1 v1 (u1 ) 0 4
3 4
14+10

2 9 6

3 4 5 6 12 14 16 19
* f1 (s1 ) u1

s1 6

u

* 1

v1 (6, u1 ) ? f 2 (6 ? u1 )

0
0+25

1

2

5
16+5

4+21 9+18 12+13

19+0

27

2

再由后往前推,得到分配方案:

u*1 ? 2,

s2 ? s1 ? u*1 ? 6 ? 2 ? 4;
s3 ? s2 ? u*2 ? 4 ? 2 ? 2

* 当s3 ? 2 ? u3 ? 2; 从而得到最优策略u*1 ? 2, u*2 ? 2, u*3 ? 2,

* 当s2 ? 4时,u2 ? 2;

最大利润为27.

§3 动态规划模型的建立与求解

3.1动态规划模型的建立 (1) 划分阶段 根据问题的性质识别出问题的多阶段特性,并按时间或空 间顺序,将过程划分为相互联系的阶段。 (2) 正确选择状态变量 sk ,使它既能描述过程的状态又 要满足无后效性,并确定其取值范围。 状态变量应满足以下条件: (i ) 能用来描述过程的演变特征; (ii ) 满足无后效性,即某状态给定后,则以后过程的发展 不会再受前面各阶段状态的影响; (iii) 可知性。各阶段状态变量的值,直接或间接是可以知 道的。

(1) 确定决策变量 u k 及每段的允许决策集合 Dk ( s k ) 。 (2) 写出状态转移方程 s k ? 1 ? Tk ( s k , uk ) (3) 确定指标函数,指标函数应具有三个性质: (i) 它是定义在全过程和所有后部子过程上的数量函数。

(ii ) 满足递推关系: Vk ,n ( s k , uk , s k ?1 , uk ? 1 , ? , s n ? 1 )
? ? [ s k , uk ,Vk ?1,n ( s k ?1 , ? , s n?1 )]

(iii ) ? [ s k , u k ,V k ? 1,n ( s k ?1 ,? , s n ? 1 )] 对于 Vk ?1,n 来说是严
格单调的。 常见的指标函数是取各阶段指标之和形式:

Vk , n ? ? v j ( s j , u j ) 它显然满足以上三个性质。
j?k

n

指标函数是策略的函数,记为 Vk ,n ( s k , p k , n ( s k )) ,故递推关系又 可写成

V k , n ( s k , p k , n ) ? V k ( s k , u k ) ? V k ? 1. n ( s k ? 1 , p k ? 1 , n )
对于最优策略的指标函数值为
* f k ( s k ) ? opt V k ,n ( s k , p k ,n ( s k )) ? Vk ,n ( s k , p k , n ( s k ))

这里 p k ,n ( s k ) 是 k 阶段状态为 s k 的后部子过程的最优子策略。 (6)最后建立动态规划的基本方程。一般形式为:

*

? f k ( s k ) ? opt ?v k ( s k , uk ) ? f k ?1 ( s k ?1 )? uk ?Dk ( s k ) ? ? k ? n, n ? 1,? ,2,1 ? ? f (s ) ? 0 ? ? n?1 n?1 式中 opt 可根据题意取 min 或 max,v k ( s k , uk ) 为第 k

阶段的指标函数。

第4节 动态规划与静态规划的关系
动态规划- 多阶段决策问题方法,与时间或空间有关,具
有“动态”含义。分为离散确定、离散随机、连续确定、连 续随机性4种决策过程模型。
线性规划和非线性规划-

通常是与时间无关的,故又称它们为静态规划。对于某些 静态的问题,也可以人为地引入时间因素,把它看作是按阶 段进行的一个动态规划问题,这就使得动态规划成为求解一 些线性、非线性规划的有效方法

4.1逆序解法
由于动态规划方法有逆序解法和顺序解法之分, 其关键在于正确写出动态规划的递推关系式,故递 推方式有逆推和顺推两种形式。 一般地说,

当初始状态s1给定时,用逆推解法比较方便;
当终止状态sn+1给定时,用顺推解法比较方便。

对于指标函数是和式 情形,基本方程 为: ? f k ( sk ) ? opt ?v ( sk , uk ) ? f k ?1 ( sk ?1 )? u k ? Dk ( s k ) ? ? f n ? 1 ( sn ? 1 ) ? 0 ? ? sk ?1 ? Tk ( sk , uk ) ? ?
一般先从阶段n开始求解

f n ( sn ) ? opt
第k阶段可由

xn ?Dn ( sn )

?v( sn , xk )?
求解得到。

f k ( sk ) ? opt

uk ?Dk ( sk )

?v( sk , uk ) ? f k ?1 ( sk ?1 )?

最后求解得到f1(s1).

对指标函数为乘积形式其基本方程为
? f k ( sk ) ? opt ?v ( sk , uk ) ? f k ?1 ( sk ?1 )? uk ?Dk ( sk ) ? ? f n ?1 ( sn ?1 ) ? 1 ? ? sk ?1 ? Tk ( sk , uk ) ? ?
求解步骤是一样的。

4.2顺序解法
设指标函数是和式情形

计算步骤和逆序相反,先计算f1(s2),…,最后得到fn(sn+1) 一般已知状态sn或sn+1。

例16.4.1

某公司拥有资金 10 万元,若投资于项目 i (i

=1,2,3) 的投资额为 xi 时,其收益分别为 g1(x1)=4x1 , g2(x2)=9x2 , g3(x3)=2x32 ,问应如何分配投资数额才能使

总收益最大?
解: 这是一个与时间无明显关系的静态最优化问题, 可列出其静态模型为:

max z ? 4 x1 ? 9 x2 ? 2 x ? x1 ? x2 ? x3 ? 10 s.t.? ? xi ? 0, i ? 1,2,3.

2 3

max z ? 4x1 ? 9x2 ? 2x ? x1 ? x 2 ? x3 ? 10 满足 ? ? xi ? 0 (i ? 1,2,3)
2 3

我们可以人为地赋予它“时段”的概念,

用动态规划方法求解
解:(解法1)首先用逆序构造动态规划模型。

1.分阶段:设阶段变量 k 表示依次对第 k 个
项目投资,因此,阶段总数 n = 3。

(k=1,2,3)

2. 状态变量:用 sk 表示第 k 段初拥有

的可以分配给第 k 到第3个项目的资金
额 (单位:万元) 。 3. 决策变量:用 xk 表示对第

max z ? 4 x1 ? 9 x2 ? 2 x32 ? x1 ? x2 ? x3 ? 10 s.t.? ? xi ? 0, i ? 1,2,3.

k 个项目投资 的资金数量
(单位:万元)。

4 .状态转移方程为: s k ?1 ? s k ? x k
5.决策变量的取值: 0 ? xk ? sk

max z ? 4 x1 ? 9 x2 ? 2 x

2 3

6. 基本方程为:

? x1 ? x2 ? x3 ? 10 s.t.? ? xi ? 0, i ? 1,2,3.

最优指标函数 fk(sk) 表示第 k 阶段,初始 状态为 sk 时,从第 k 到第 3 个项目采取最优 策略所获最大收益

f ( s ) ? max { g ( x ) ? f ( s )} ? k k k k k ? 1 k ? 1 ? 0 ? xk ? s k ? ? ? f 4 (s4 ) ? 0

k ? 3,2,1

当 k=3 时:

f 3 (s 3 ) ? max {2 x }
0? x 3 ?s 3 2 3

max z ? 4 x1 ? 9 x2 ? 2 x32 ? x1 ? x2 ? x3 ? 10 s.t.? ? xi ? 0, i ? 1,2,3.

取 x ? s3 得
f 3 (s 3 ) ? max {2x } ? 2s
0? x 3 ?s 3 2 3 2 3

? 3

当 k=2 时:

f 2 (s 2 ) ? max {9x 2 ? f 3 (s3 )} ? max {9x 2 ? 2s }
0? x 2 ?s 2

0? x 2 ?s 2

2 3

? max {9x 2 ? 2(s 2 ? x 2 ) }
2 0? x 2 ?s 2

令 h 2 (s 2 , x 2 ) ? 9x 2 ? 2 ? (s 2 ? x 2 )

2

令 h2 (s2 , x2 ) ? 9x2 ? 2 ? (s2 ? x2 ) , f 2 (s2 ) ? 0max ? x ?s
2

h2 ( s2 , x2 )
2

dh2 由 ? 9 ? 4 ? ( s2 ? x2 ) ? (?1) ? 0 dx2

9 ? x2 ? s2 ? 4

2

d 2 h2 而 ?4?0 2 dx2

9 所以x2 ? s2 ? 是极小点 4 2 极大值只可能在[0 ,s2]端点取得, f 2 (0) ? 2s2 或f 2 (s2 ) ? 9s2
当 s2 ? 9 2, f 2 (0) ? f 2 (s2 ) 当 s2 ? 9 2, f 2 (0) ?

? x ? 0, f 2 (s2 ) ? x ? s , 2
2 2 * 2 * 2

? 2 ? 2

f2 (s2 ) ? 9s2

当s2 ? 9 / 2, f 2 ( s2 ) ? 2s , x ? 0; 当s2 ? 9 / 2, f 2 ( s2 ) ? 9s2 , x ? s2 .

f1 ( s1 ) ? max {4 x1 ? f 2 ( s2 )}
0? x1 ? s1

max z ? 4 x1 ? 9 x2 ? 2 x ? x1 ? x2 ? x3 ? 10 s.t.? ? xi ? 0, i ? 1,2,3.

2 3

当s2 ? 9 / 2, f 2 ( s2 ) ? 2s , x ? 0;
2 2 * 2 * 当s2 ? 9 / 2, f 2 ( s2 ) ? 9s2 , x2 ? s2 .

假定 s2 ? 9 / 2 这时取 f 2 ( s2 ) ? 9s2
{9s1 ? 5 x1} ? 9s1 f1 (10) ? max {4x1 ? 9s1 ? 9x1}? 0max ? x ?10

但此时 s 2 ? s1 ? x1 ? 10 ? 0 ? 10 ? 9 2
矛盾,所以舍去 sk < 9/2

0?x1 ?10

1

假定 s2 ? 9/ 2, 这时取
0? x1 ?10

f2 (s2 ) ? 2s

2 2

f1 (10) ? max{4 x1 ? 2( s1 ? x1 ) }
2

f1 (10) ? max{4 x1 ? 2( s1 ? x1 ) }
2 0? x1 ?10



h1 ( s1 , x1 ) ? 4 x1 ? 2 ? ( s1 ? x1 )

2

dh1 d h1 由 ? 4 ? 4 ? ( s1 ? x1 ) ? (?1) ? 0 而 2 ? 1 ? 0 dx1 dx1 解得驻点x1 ? s1 ?1? x1 ? s1 ?1是极小值
故 极大值只能在 [0,10] 的端点取得,比较[0,10]两

2

个端点的函数值

?当x1 ? 0 时,f1 (10) ? 200; 当x1 ? 10时,f1 (10) ? 40 ? ? * ? x1 ? 0, s2 ? s1 ? x1 ? 10 ? 0 ? 10 ? 9/ 2, x2 ? 0,
? ? x3 ? s3 ? 10

即全部资金投于第3个项目

(解法2) 用顺序解法
1. 阶段划分: (同上) 和决策变量

2. 状态变量: 用 sk 表示可用于第1到第 k-1
个项目投资的金额,即对第 k 个项目到第3

个项目投资后的剩余资金数量。
3. 决策变量: (同上)

4. 状态转移方程:

s4 ? 10
k ?1, 2 , 3

sk ? sk ?1 ? xk

5. 决策变量的取值范围:

0 ? xk ? sk ?1
6. 最优指标函数:

k ? 1, 2 , 3

令 fk(sk+1) 表示从第1到第 k 阶段投资额 sk+1 为时, 第1到第 k 项目所获的最大收益,此时顺序解法的 基本方程为:

f ( s ) ? max { g ( x ) ? f ( s )} ? k k ? 1 k k k ? 1 k ? 0? xk ? sk ?1 ? ? ? f 0 (s1 ) ? 0

k ? 1,2,3

当 k=1 时,有

f1 ( s2 ) ? max { g1 ( x1 ) ? f 0 ( s1 )}
0? x1 ? s2

? max {4 x1 } ? 4 s2
0? x1 ? s2

x ? s2

? 1

当 k=2 时,有

f 2 ( s3 ) ? max [9 x 2 ? f1 ( s 2 )]
0 ? x 2 ? s3

? max [9 x 2 ? 4s 2 ]

? max [9 x 2 ? 4( s3 ? x 2 )]
0 ? x 2 ? s3

0 ? x 2 ? s3

? max [5 x 2 ? 4s3 ]
0 ? x 2 ? s3

? 9s3
当 k=3 时,有
0? x3 ? s4 2 3

x ? s3
* 2

f 3 (s 4 ) ? max [2 x ? f 2 ( s3 )]
? max [2 x ? 9(s 4 ? x3 )]
0? x3 ? s4 2 3



h( s4 , x3 ) ? 2 x ? 9 ? ( s4 ? x3 )
2 3



dh ? 4 x3 ? 9 ? 0 dx3

?

极大值应在[0,s4] =[ 0,10 ] 端点取得

d h ?4 2 dx3

2

? x3 = 9/4 为极小点。

?

当 x3 ? 0 时 当 x3 ? 10时
? 3

x ? 10
* 3

f3 (10) ? 90 f3 (10) ? 200

再由状态转移方程逆推:

s3 ? s4 ? x ? 10 ? 10 ? 0

得 x ?0

? 2

s2 ? s3 ? x ? 0
得 x ? s2 ? 0
? 1

? 2

第4节 动态规划和静态规划的关系
例16.4.2 用逆推解法求解下面问题
max z ? x 1 ? x 2 2 ? x3 ?x 1 ? x 2 ? x 3 ? c (c ? 0) ? ?x i ? 0, i ? 1,2.3

解 : 按变量个数划分为三阶段决策问题。 设状态变量为s1,s2,s3,s4,并记s1=c;取问题中的变量x1,x2,x3为 决策变量;各阶段指标函数按乘积方式结合。令最优值函数fk(sk) 设 则有

表示为第k阶段的初始状态为sk,从k阶段到3阶段所得到的最大值。

0 ? s4 ? s3 ? x3

s3 ? s2 -x2

s2 ? s1 ? x1 , s1 ? c

x3 ? s3

0 ? x1 ? s2

0 ? x1 ? s1 ? c
k ? 1, 2,3

基本方程

{vk ( xk ) ? f k ?1 ( sk ?1 )} ? ? f k ( sk ) ? 0max ? xk ? sk ? ? ? f 4 ( s4 ) ? 1

第4节

动态规划和静态规划的关系

用逆推解法,从后向前依次有

f3 ( s3 ) ? max( x3 ) ? s3
x3 ? s3

max z ? x 1 ? x 2 2 ? x3 ?x 1 ? x 2 ? x 3 ? c (c ? 0) ? ?x i ? 0, i ? 1,2.3

* 最优解为 x3 ? s3

s3 ? s2 ? x2

2 2 ? ? ? f 2 (s2 ) ? max ? x f ( s ) ? max x 2 3 3 ? 2 ( s2 ? x2 ) ? ? max h2 ( x2 , x2 ) ? ? 0? x2 ? s2 0? x2 ? s2 0? x2 ? s2

由 由

dh2 2 ? 2 x2 s2 ? 3x2 ?0 dx2
d 2 h2 ? 2s2 ? 6 x2 2 dx2
d 2 h2 2 dx2


2 x2 ? s2 3

x2 ?

2 s2 3



x2 ? 0 (舍去)
2 s2为极大值点。 3

? ?2 s 2 ? 0
* 2

? x2 ?

所以

f 2 ( s2 ) ?

4 3 s2 27

最优解

2 x ? s2 3

第4节 动态规划和静态规划的关系

f1 ( s1 ) ? max[ x1 ? f 2 ( s2 )]
0? x1 ? s1

max z ? x 1 ? x 2 2 ? x3 ?x 1 ? x 2 ? x 3 ? c (c ? 0) ? ?x i ? 0, i ? 1,2.3

4 ? max[ x1 ? ( s1 ? x1 )3 ] 0? x1 ? s1 27 ? max h1 ( x1 , s1 )
1 利用微分法易知 x ? s1 4
* 1

0? x1 ? s1

1 4 f1 ( s1 ) ? s1 64

4 3 f 2 ( s2 ) ? s2 27

1 4 c * 由于已知 s1 ? c, f1 (c) ? c , x1 ? 64 4 而按计算的顺序反推算,可得各阶段的最优决策和最优值。

s1 ? c

s2 ? s1 ? x ? c ? c / 4 ? 3c / 4,
* 1 * 2 * 3

s3 ? s2 ? x ? c / 4,

1 4 c x ? s3 ? c / 4, max z ? f1 (c) ? 64

2 c x ? s2 ? , 3 2
* 2

例16.4.3

用动态规划顺推解法解下面问题
2 2 max F ? 4 x12 ? x2 ? 2 x3 ? 12

?3 x1 ? 2 x2 ? x3 ? 9 ? ? xi ? 0, i ? 1, 2,3

解:按问题中变量的个数分为三个阶段。设状态变量为 s1、s2、s3、s4

并记s4 ? 9, 取x1、x2、x3 为各阶段的决策变量;
各阶段指标函数按加法方式结合。令最优值函数 fk (sk ?1 ) 表示第k阶段的结束状态为sk+1,从1阶段至k阶段的最大值。

设 则有

s1 ? s2 ? 3x1, s2 ? s3 ? 2x2 , s3 ? s4 ? x3 , s4 ? 9
x1 ? s2 / 3, 0 ? x2 ? s3 / 2, 0 ? x3 ? s4

用顺推方法,从前向后依次有
4 2 1 * f1 ( s2 ) ? max (4 x ) ? s2 及最优解 x1 ? s2 x1 ? s2 / 3 9 3
2 1

2 2 max F ? 4 x12 ? x2 ? 2 x3 ? 12

?3 x1 ? 2 x2 ? x3 ? 9 ? ? xi ? 0, i ? 1, 2,3

? 2 4 2? ? f 2 (s3 ) ? max ? ? x ? f ( s ) ? max ? x ? ( s ? 2 x ) ? max h2 ( s3 , x2 ) 1 2 ? 2 3 2 ? 0? x2 ? s3 / 2 ? 0? x2 ? s3 / 2 ? 9 ? ? 0? x2 ? s3 / 2
2 2

8 得x2 ? s3 7 因该点不在允许决策集合内,故无须判别。因而 h2 (s3 , x2 ) 的最大值必在两个端点上选取。而 4 2 ? s3 ? 2 h2 (0) ? s3 , h2 ? ? ? ? s3 4 9 ?2? 所以 h2 (s3 , x2 ) 的最大值点在 x2 ? 0 处,故得到
4 2 f 2 ( s3 ) ? s3 9
* 相应的最优解 x2 ?0

dh2 14 16 由 ? x2 ? s3 ? 0 dx2 9 9

f3 ( s4 ) ? max {2 x ? 12 ? f 2 ( s3 )}
0? x3 ? s4
2 3

2 3

2 2 max F ? 4 x12 ? x2 ? 2 x3 ? 12

4 ? max {2 x ? 12 ? ( s4 ? x3 ) 2 } 0? x3 ? s4 9 ? max h3 ( s4 , x3 )
0? x3 ? s4

?3 x1 ? 2 x2 ? x3 ? 9 ? ? xi ? 0, i ? 1, 2,3

d h 3 44 8 2 ? ? x3 ? s3 ? 0 ? x3 ? s4 d x3 9 9 11

4 2 f 2 ( s3 ) ? s3 9
d 2 h3 44 又 2 ? ?0 dx3 9

4 2 2 ? 12 故该点为极小值点, h3 (0) ? s4 ? 12, h3 ( s4 ) ? 2 s4 9

h3 (s4 , x3 )的最大值点为:x ? s4
* 3

2 f3 (s4 ) ? 2s4 ?12

? s4 ? 9, 故max F= f3 (s4 ) ? 2 ? 92 ?12 ? 174
反推得到最优解:
* x3 ? 9,

s1 ? s2 ? 3x1, s2 ? s3 ? 2x2 , s3 ? s4 ? x3 , s4 ? 9 * x2 ? 0, x1* ? s2 ? 0. 3

例题16.4.4(背包问题) 设有一辆汽车,最多可载7吨。今欲装载甲、乙、丙 三种货物,每件货物的重量和价值如下表所示,问应 如何装载可使总价值最大? 甲 乙 丙 1 2 3 每件重量(t) 2 5 8 每件价值 解:设甲、乙、丙的装载量分别为x1、x2、x3,则问 题的数学模型为:
max f ? 2 x1 ? 5 x2 ? 8 x3 ? x1 ? 2 x2 ? 3 x3 ? 7 ? ? xi ? 0且为整数,i ? 1, 2,3

max f ? 2 x1 ? 5 x2 ? 8 x3 ? x1 ? 2 x2 ? 3 x3 ? 7 ? ? xi ? 0且为整数,i ? 1, 2,3
解: 用逆序解法来解。分为三阶段,状态变量为s1,s2,s3,s4. 决策变量为原x1,x2,x3.转移方程为:

求f1 (7).

s1 ? 7, s2 ? s1 ? x1, s3 ? s2 ? 2 x2 , s4 ? s3 ? 3x3.
max ?2 x1 ? f 2 (7 ? x1 )? f1 (7) ? max ?2 x1 ? f 2 ( s2 )? ? 0 ? x ?7
0? x1 ? 7 x1 ? 0,整数
x1 ? 0,整数
1

?0 ? f 2 (7), 2 ? f 2 (6), 4 ? f 2 (5), 6 ? f 2 (4), ? ? max ? ? ?8 ? f 2 (3),10 ? f 2 (2),12 ? f 2 (1),14 ? f 2 (0) ?

?0 ? f 2 (7), 2 ? f 2 (6), 4 ? f 2 (5), 6 ? f 2 (4), ? f1 (7) ? max ? ? 8 ? f (3),10 ? f (2),12 ? f (1),14 ? f (0) ? 2 2 2 2 ?

由此看到,要计算f1(7) ,必须先计算出 f2 (7), f2 (6),..., f2 (0)
f 2 (7) ? max ?5 x2 ? f3 (7 ? 2 x2 )?
0? 7 ? 2 x2 x2 ? 0,整数

max f ? 2 x1 ? 5 x2 ? 8 x3 ? x1 ? 2 x2 ? 3x3 ? 7 ? ? xi ? 0且为整数,i ? 1, 2,3

? max ?5 x2 ? f3 (7 ? 2 x2 )?
x2 ? 0,1,2,3

? max ?0 ? f3 (7),5 ? f3 (5),10 ? f3 (3),15 ? f3 (1)?
f 2 (6) ? max ?5 x2 ? f3 (6 ? 2 x2 )? ? max ?5 x2 ? f3 (6 ? 2 x2 )?
0? 6 ? 2 x2 x2 ? 0,整数
x2 ? 0,1,2,3

? max ?0 ? f3 (6),5 ? f3 (4),10 ? f3 (2),15 ? f3 (0)?
依次类推得到:

f 2 ( s2 ) ? max ?5 x2 ? f3 ( s2 ? 2 x2 )?
f 2 (5) ? max ?5 x2 ? f3 (5 ? 2 x2 )?
0?5? 2 x2 x2 ? 0,整数

0? s2 ? 2 x2 x2 ? 0,整数

max f ? 2 x1 ? 5 x2 ? 8 x3 ? x1 ? 2 x2 ? 3 x3 ? 7 ? ? xi ? 0且为整数,i ? 1, 2,3

? max ?0 ? f3 (5),5 ? f3 (3),10 ? f3 (1)?

f2 (4) ? max ?0 ? f3 (4),5 ? f3 (2),10 ? f3 (0)? f2 (3) ? max ?0 ? f3 (3),5 ? f3 (1)? f2 (1) ? max ?0 ? f3 (1)? f2 (2) ? max ?0 ? f3 (2),5 ? f3 (0)?

f2 (0) ? f3 (0) ? 0 f3 (7), f3 (6),.., f3 (1), f3 (0)

由此看到,要计算f1(7) ,必须先计算出

从而
f3 (7) ? max ?8 x3? ? 16,
0? 7 ?3 x3 x3 ? 0,整数

max f ? 2 x1 ? 5 x2 ? 8 x3

x ?2
* 3 * x3 ?2 * x3 ?1 * x3 ?1

f3 (6) ? max ?8 x3? ? 16, f3 (5) ? max ?8 x3 ? ? 8,
0?5?3 x3 x3 ? 0,整数 0? 6 ?3 x3 x3 ? 0,整数

? x1 ? 2 x2 ? 3 x3 ? 7 ? ? xi ? 0且为整数,i ? 1, 2,3

f3 (4) ? max ?8 x3 ? ? 8,
0? 4 ?3 x3 x3 ? 0,整数

f3 (3) ? max ?8 x3 ? ? 8, f3 (2) ? max ?8 x3 ? ? 0,
0? 2 ?3 x3 x3 ? 0,整数 0? 4 ?3 x3 x3 ? 0,整数

x ?1
* 3 * x3 ? 0;

f3 (1) ? max ?8 x3 ? ? 0 ? f3 (0),
0?1?3 x3 x3 ? 0,整数

x ? 0;
* 3

由上述各f3(s3)的值,可以计算各f2(s3)的值。

f2 (7) ? max ?0 ? f3 (7),5 ? f3 (5),10 ? f3 (3),15 ? f3 (1)?

? max ?0 ?16,5 ? 8,10 ? 8,15 ? 0? ? 18, x2 ? 2
f2 (6) ? max ?0 ? f3 (6),5 ? f3 (4),10 ? f3 (2),15 ? f3 (0)?

? max ?0 ?16,5 ? 8,10 ? 0,15 ? 0? ? 16, x2 ? 0
f2 (5) ? 13, x2 ? 1; f 2 (2) ? 5, x2 ? 1; f 2 (4) ? 10, x2 ? 2; f2 (1) ? f2 (0) ? 0, x2 ? 0;

经计算得

f2 (3) ? 8, x2 ? 0;

?0 ? f 2 (7), 2 ? f 2 (6), 4 ? f 2 (5), 6 ? f 2 (4) ? f1 (7) ? max ? ? ?8 ? f 2 (3),10 ? f 2 (2),12 ? f 2 (1),14 ? f 2 (0) ?
? 18, x1 ? 0, 或x1 ? 1;

?0 ? f 2 (7), 2 ? f 2 (6), 4 ? f 2 (5), 6 ? f 2 (4) ? f1 (7) ? max ? ? ?8 ? f 2 (3),10 ? f 2 (2),12 ? f 2 (1),14 ? f 2 (0) ?

? 18, x1 ? 0, 或x1 ? 1;
反推得到最优解:

max f ? 2 x1 ? 5 x2 ? 8 x3 ? x1 ? 2 x2 ? 3 x3 ? 7 ? ? xi ? 0且为整数,i ? 1, 2,3

s1 ? 7, s2 ? s1 ? x1 , s3 ? s2 ? 2x2 , s4 ? s3 ? 3x3.
* * * * (1)当x1 ? 0,s2 ? s1 ? x1 ? 7; ? f 2 (7) ? 18, x2 ? 2, s3 ? s2 ? 2x2 ? 3,
* 而f3 (3) ? 8, x3 ? 1; * * * * (2)当x1 ?1 ,s2 ? s1 ? x1 ? 6; ? f2 (6) ? 16, x2 ? 0, s3 ? s2 ? 2x2 ? 6, * 而f3 (6) ? 16, x3 ? 2; * * * 故最优解为x1 ?1 ,x2 ? 0,x3 ? 2,f * ? 18,;

16.5函数迭代法
定期多阶段决策问题-阶段数为n,是固定数; 对于从一个节点到另一节点的阶段数不是固定的多 阶段决策问题,上述方法不方便求解。
7 1 1 5 3 4 2 5 1 3 2 3 3 4

如对上述问题,求节点1到节点5的最短距离,阶段数不固定。 可用函数迭代法求解。

考虑由n个节点1,2,…,n组成的网络。设f(i)(i=1,2,…,n)为由节 点i到节点n的最短距离。则有基本方程:

? f (i) ? min?cij ? f ( j )? 1? j ? n ? ? f ( n) ? 0

(16.5.1)

其中cij连接节点 i和节点j的弧长度 (费用 )。
计算f (i)的步骤为:
(1)取f1(i)为节点i经一步到达节点n的最短距离,即

? cin , i ? 1,2,...,n ? 1 f1 (i) ? ? ?0, i ? n
(2)对k=2,3,…,n,求fk(i).

? min?cij ? f k ?1 ( j )?, i ? 1,2,...,n ? 1 f k (i) ? ? 1? j ?n ?0, i ? n

(3)当对所有的i=1,2,…,n,都有:

f k ?1 (i) ? f k (i),i ? 1,2,...,n
时停止。此时有:

f (i) ? f k (i), i ? 1,2,...,n

16.6动态规划的软件求解
? (1)可用Matlab编写动态规划计算程序求解; ? (2)可用Lingo编写动态规划计算程序求解;

16.6动态规划的软件求解
例题16.6.1:下图是一个7座城市的及其相连道路的交 通图,线上的数字是对应的路长。问:应如何选择行 驶路线,才能使从A、Bj(j=1,2)、Ci(i=1,2,3)到D城市的 行驶路程最短。
B1 2 1 3 C1
1

1

3 A 4 B2 1 2 C2

D

4 C3

B1 2 1

3

C1
1

1

3 D 2 A 4 B2 1 C3 C2

4

解:利用动态规划基本方程:
f k ( xk ) ? min f 4 ( x4 ) ? 0
uk ?Dk ( xk )

?d ( xk , uk ( xk )) ? f k ?1 (uk ( xk ))?

编写Lingo程序如下:

Model: sets: cities/A,B1,B2,C1,C2,C3,D/:f; roads(cities,cities)/A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 C1,D C2,D C3,D/:w,p; endsets N=@size(cities);

data:
W=2 4 3 3 1 2 3 1 1 3 4; enddata

f(@size(cities))=0;
@for(cities(i)|i #lt# N:f(i)=@min(roads(i,j):W(i,j)+f(j))); @for(roads(i,j):p(i,j)=@if(f(i)# eq # W(i,j)+f(j),1,0)); end

运行得到如下结果(部分)
Variable
N F( A) F( B1) F( B2) F( C1) F( C2) F( C3) F( D)

B1 2 1

3

C1
1

1

Value
7.000000 6.000000 4.000000 3.000000 1.000000 3.000000 4.000000 0.000000
A

3 2 C2

D

4

B2 1

4 C3

P( A, B1) P( B1, C1) P( B2, C1) P( C1, D) P( C2, D) P( C3, D)

1.000000 1.000000 1.000000 1.000000 1.000000 1.000000

得到A 到D的最短距离为6,最短路径为 A-B1-C1-D。同时得到其他点到D的最短 路径和距离。

例题16.6.2(资源分配问题):假设总公司打算拿出60万元, ) 分配给下属的四个子公司,每个子公司产生的利润 gi ( xi (万 元)由下列表给出:

试给出最优决策。

解:问题的模型为:
max z ? g1 ( x1 ) ? g 2 ( x2 ) ? g3 ( x3 ) ? g 4 ( x4 ) s.t.x1 ? x2 ? x3 ? x4 ? 60 xi ? 0, i ? 1, 2,3, 4 xi ? 0,10, 20,30, 40,50, 60

max z ? g1 ( x1 ) ? g 2 ( x2 ) ? g3 ( x3 ) ? g 4 ( x4 ) s.t.x1 ? x2 ? x3 ? x4 ? 60 xi ? 0, i ? 1, 2,3, 4 xi ? 0,10, 20,30, 40,50, 60

模型简化:令g(I,j)表示给第i个公 司投资j(10万元)时的利润。
c(i, j ) ? 1表示给第i个公司投资 j (10万元)。 j ? 0,1,2,..,6.

则上述模型可改写为:

min ?? g (i, j ) ? c(i, j )
i ?1 j ? 0

4

6

s.t.? c(i, j ) ? 1, i ? 1,2,3,4.
j ?0 6

6

?? j * c(i, j ) ? 6
i ?1 j ? 0

4

model: sets: gongsi/1..4/; touzi/1..7/; lirun(gongsi,touzi):g,c;

c(i, j ) ? 1表示给第i个公司投资 j (10万元)。 j ? 0,1,2,..,6.
min ?? g (i, j ) ? c(i, j )
i ?1 j ? 0 4 6

endsets
data: g=0 20 50 65 80 85 85, 0 20 40 50 55 60 65, 0 25 60 85 100 110 115, 0 25 40 50 60 65 70; enddata

s.t.? c(i, j ) ? 1, i ? 1,2,3,4.
j ?0 6

6

?? j * c(i, j ) ? 6
i ?1 j ? 0

4

Objective value: 160.0000 Variable C( 1, 3) C( 3, 4) C( 4, 2) Value 1.000000 1.00000 1.000000

max=@sum(lirun(i,j):g(i,j)*c(i,j));
@for(gongsi(i):@sum(lirun(i,j):c(i,j))<=1); @for(lirun:@bin(c)); @sum(lirun(i,j):(j-1)*c(i,j))=6; end

即公司1投资20万元,公司3投资30 万元,公司4投资10万元,总利润 160万元

不定期多阶段决策: 定义f(i)是由i点出发至终点N的最短路程,由最优化原理可得
{cij ? f ( j )}, i ? 1, 2, ?, N ? 1 ? ? f (i) ? min j ? ? ? f (N ) ? 0

这是一个函数方程,用LINGO可以方便的解决。

!最短路问题; model: data: n=10; enddata

sets:
cities/1..n/: F; !10个城市; roads(cities,cities)/ 1,2 1,3 2,4 2,5 2,6 3,4 3,5 3,6 4,7 4,8

5,7 5,8 5,9
6,8 6,9 7,10 8,10 9,10 /: D, P;

model: data: n=5; enddata

书中例题 16.5.1
1

7 1

5

5
1

4 3

3
4 2
F( 1) F( 2) F( 3) F( 4) F( 5)

sets:
cities/1..n/: F; !5个城市; roads(cities,cities)/ 1,2 1,4 1,5 2,3 2,4 2,5 3,2 3,4 3,5 4,1 4,2 4,3 4,5 /: D, P;

3
2

3
4.000000 3.000000 1.00000 4.000000 0.000000

endsets
data: D= 1 3 7 enddata 2 3 4 2 3 1 3 3 3 5;

F(n)=0;
@for(cities(i) | i #lt# n: F(i)=@min(roads(i,j): D(i,j)+F(j));); @for(roads(i,j):

P( 1, 2) P( 2, 3) P( 3, 5) P( 4, 3)

1.000000 1.000000 1.000000 1.000000

P(i,j)=@if(F(i) #eq# D(i,j)+F(j),1,0));
end

【例16.5.2】某种设备可在高低两种不同的负荷下进行生产,设 在高负荷下投入生产的设备数量为x,产量为g=10x,设备年完好 率为a=0.75;在低负荷下投入生产的设备数量为y,产量为h=8y, 年完好率为b=0.9。假定开始生产时完好的设备数量s1=100。 制定一个五年计划,确定每年投入高、低两种负荷下生产的设 备数量,使五年内产品的总产量达到最大。 阶段k:运行年份(k=1,2,3,4,5,6),k=1表示第一年初,k=6表 示第五年末(即第六年初);
状态变量sk:第k年初完好的机器数(k=1,2,3,4,5,6),也是第k -1年末完好的机器数,其中s6表示第五年末(即第六年初)的 完好机器数,s1=100。 决策变量xk:第k年初投入高负荷运行的机器数; 状态转移方程:sk+1=0.75xk+0.9(sk-xk)

决策允许集合:Dk(sk)={xk|0?xk?sk}

阶段指标:vk(sk,xk)=10xk+8(sk-xk)
终端条件:f6(s6)=0 递推方程:

高负荷生产产量=10x, 完好率=0.75 低负荷生产产量=8y 完好率0.9

f k ( s k ) ? max ?v k ( s k , x k ) ? f k ?1 ( s k ?1 )? ? max ? 10x k ? 8( s k ? x k ) ? f k ?1 ?0.75x k ? 0.9( s k ? x k )??
0 ? xk ? s k xk ?Dk ( sk )

f5 ( s5 ) ? max ?10 x5 ? 8( s5 ? x5 ) ? f 6 ( s6 )?
0? x5 ? s5

? max ?10 x5 ? 8( s5 ? x5 )?
0? x5 ? s5 0? x5 ? s5

? max ?2 x5 ? 8s5 ? ? 10s5

* x5 ? s5时最优

f 4 ( s4 ) ? max ?10 x4 ? 8( s4 ? x4 ) ? f5 ( s5 )?
0 ? x4 ? s4

? max ?10 x4 ? 8( s4 ? x4 ) ? 10 s5 ?
0 ? x4 ? s4 0 ? x4 ? s4 0 ? x4 ? s4

? max ?10 x4 ? 8( s4 ? x4 ) ? 10(0.75 x4 ? 0.9( s4 ? x4 ))? ? max {0.5 x4 ? 17 s4 } ? 17.5s4
f3 ( s3 ) ? max ?10 x3 ? 8( s3 ? x3 ) ? f 4 ( s4 )?
0 ? x3 ? s3

* x4 ? s4时最优

? max ?10 x3 ? 8( s3 ? x3 ) ? 17.5s4 ?
0 ? x3 ? s3 0 ? x3 ? s3 0 ? x3 ? s3

? max ?10 x3 ? 8( s3 ? x3 ) ? 17.5(0.75 x3 ? 0.9( s3 ? x3 ))? ? max {?0.625 x3 ? 23.75s3} ? 23.75s3
* x3 ? 0时最优

f 2 ( s2 ) ? max ?10 x2 ? 8( s2 ? x2 ) ? f3 ( s3 )?
0 ? x2 ? s2

? max ?10 x2 ? 8( s2 ? x2 ) ? 23.75s3 ?
0 ? x2 ? s2 0 ? x2 ? s2 0 ? x2 ? s2

? max ?10 x2 ? 8( s2 ? x2 ) ? 23.75(0.75 x2 ? 0.9( s2 ? x2 ))? ? max {?1.5625 x2 ? 29.375s2 } ? 29.375s2
* x2 ? 0时最优

f1 ( s1 ) ? max ?10 x1 ? 8( s1 ? x1 ) ? f 2 ( s2 )?
0 ? x1 ? s1

? max ?10 x1 ? 8( s1 ? x1 ) ? 29.375s2 ?
0 ? x1 ? s1 0 ? x1 ? s1 0 ? x1 ? s1

? max ?10 x1 ? 8( s1 ? x1 ) ? 29.375(0.75 x1 ? 0.9( s1 ? x1 ))? ? max{?2.406 x1 ? 34.4375s1} ? 34.4375s1

* x1 ? 0时最优

因为s1=100,五年的最大总产量为f1(s1)=25.7525×100=3443.75。

由x1*= x2*= x3*=0,x4*=s4,x5*=s5,设备的最优分配策略是, 第一年至第三年将设备全部用于低负荷运行,第四年和第五年将 设备全部用于高负荷运行。每年投入高负荷运行的机器数以及每 年初完好的机器数为: s1=100 x1*=0, s2=0.75x1+0.9(s1-x1)=90

x2*=0,
x3*= 0, x4*= s4=73, x5*= s5=55,

s3=0.75x2+0.9(s2-x2)=81
s4=0.75x3+0.9(s3-x3)=73 s5=0.75x4+0.9(s4-x4)=55 s6=0.75x5+0.9(s5-x5)=41

第五年末还有41台完好设备。

一般地,设一个周期为n年,高负荷生产时设备的完好率为a, 单台产量为g;低负荷完好率为b,单台产量为h。若有t满足
n ?t ?1

?
i ?0

n ?t g ? h ai ? ? ? ai g (b ? a) i ?0

则最优设备分配策略是:从1~t-1年,年初将全部完好设备投 入低负荷运行,从t~n年,年初将全部完好设备投入高负荷运 行,总产量达到最大 . 在例15.5.2中,

n=5,a=0.75,b=0.9,g=10,h=8,(g-h)/g(b-a)=1.3333
式(8.7)的求和式是完好率a的i次方累加. 由a0=1<1.3333<a0+a1=1.75知,n-t-1=0,t=4,则1~3年低负 荷运行,4~5年为高负荷运行

16章 动态规划简介
? 作业:p466, ? 第2题 (1) (只考虑逆推解法), ? 第3题。


相关文章:
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划(Dynamic Programming) 动态规划是美国数学家Bellman创立的。Bellman50年代执教于普林 斯顿和斯坦福大学,后进入兰德(Rand)研究所...
运筹学-第3版-课件-动态规划例题_图文.ppt
运筹学-第3版-课件-动态规划例题 - 8.1 用动态规划方法求整数规划模型,而
运筹学7动态规划.ppt
运筹学7动态规划_数学_自然科学_专业资料。运筹学7动态规划 第七 章动态规划 主要内容: §7.1 多阶段决策过程的最优化 §7.2 动态规划的基本概念和基本原理 ...
运筹学-动态规划_图文.ppt
运筹学-动态规划 - 动态规划 (Dynamic programming) 动态
运筹学第10章-动态规划_图文.ppt
运筹学第10章-动态规划 - Page:1 管理运筹学 动态规划 Page:2 综 述 动态规划是解决多阶段决策过程最优 化问题的一种方法。动态规划所研究 的对象是多阶段...
运筹学(二)动态规划(1-2014)_图文.ppt
运筹学(二)动态规划(1-2014) - 运筹学(二) 动态规划 动态规划 ? 动态规划运筹学的一个分支,它是 解决多阶段决策问题的一种数学方法。大 约产生...
运筹学动态规划.ppt
运筹学动态规划_数学_自然科学_专业资料。第7章重点: 动态规划 (Dynamic Programming) 理解动态规划基本概念、最优化原理和基本方程; 通过资源分配、生产与存储和设备...
运筹学动态规划PPT_图文.ppt
运筹学动态规划PPT - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化的...
运筹学 动态规划应用.ppt
运筹学 动态规划应用_数学_自然科学_专业资料。第七章 动态规划动态规划问题的基本概念和基本原理 动态规划模型的建立与求解 应用举例 应用举例 1。背包问题 2。...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 资源分配问题 生产计划问题 背包问题 复合系统工作可靠性问题 动态规划是用...
运筹学---动态规划_图文.ppt
运筹学---动态规划 - 这是关于运筹学里的动态规划的课件ppt... 运筹学---动态规划_理学_高等教育_教育专区。这是关于运筹学里的动态规划的课件ppt 动态...
第六章(上课) 运筹学动态规划04修改_图文.ppt
第六章(上课) 运筹学动态规划04修改_理学_高等教育_教育专区。(Dynamic programming) 1 主要内容一、多阶段决策问题 二、动态规划的基本概念三、动态规划的基本...
运筹学-动态规划-13,14_图文.ppt
运筹学-动态规划-13,14 - 第五章 动态规划 ? §5.1 动态规划的基本
第七章运筹学动态规划_图文.ppt
第七章运筹学动态规划 - 动态规划 引言 □动态规划是解决多阶段决策过程最优化的
运筹学动态规划_图文.ppt
运筹学动态规划 - 运筹学 课程主要内容 第一章 第二章 第三章 第四章 第五章
运筹学(动态规划1)_图文.ppt
运筹学(动态规划1) - 1.多阶段决策过程的最优化 一、多阶段决策问题 (Mu
动态规划(运筹学讲义)_图文.ppt
动态规划(运筹学讲义) - 第八章 动态规划 Dynamic Programming §1 动态规划问题实例 动态规划的基本概念 §2 动态规划的基本概念 §3 基本原理和基本方程 动态...
运筹学教案(动态规划).ppt
运筹学运筹学隐藏>> 运筹学教案动态规划 陈安明 概述动态规划运筹学的一个分支, 动态规划运筹学的一个分支,是用于求解 多个阶段决策过程的最优化数学方法。 ...
运筹学 07 动态规划_图文.ppt
运筹学 07 动态规划 - 动态规划 Dynamic Programming 1. 2. 3. 4. 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划模型的建立与求解 动态规划...
运筹学课件(动态规划)_图文.ppt
运筹学课件(动态规划) - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化...
更多相关文章: