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

运筹学动态规划


动 态 规 划
(Dynamic programming)

动态规划的基本思想 最短路径问题 资源分配问题 生产计划问题 背包问题 复合系统工作可靠性问题

动态规划是用来解决多阶段决策过程最优 化的一种数量方法。其特点在于,它可以把一 个n 维决策问题变换为几个一维最优化问题,从 而一个一个地去解决。

需指出:动态规划是求解某类问题的一种 方法,是考察问题的一种途径,而不是一种算 法。必须对具体问题进行具体分析,运用动态 规划的原理和方法,建立相应的模型,然后再 用动态规划方法去求解。

动态决策问题的特点: 系统所处的状态和时刻是进行决策的重要因素; 即在系统发展的不同时刻(或阶段)根据系统 所处的状态,不断地做出决策; 找到不同时刻的最优决策以及整个过程的最优策略。
多阶段决策问题: 在多阶段决策过程中,系统的动态过程可以按照时间 进程分为状态相互联系而又相互区别的各个阶段; 每个阶段都要进行决策,目的是使整个过程的决策 达到最优效果。

决策 状态 状态 1

决策 决策 状态 ? 状态 2 n

多阶段决策问题的典型例子:
1 . 生产决策问题:企业在生产过程中,由于需 求是随时间变化的,因此企业为了获得全年的最佳 生产效益,就要在整个生产过程中逐月或逐季度地 根据库存和需求决定生产计划。 2. 机器负荷分配问题:某种机器可以在高低两 种不同的负荷下进行生产。在高负荷下进行生产时, 产品的年产量g和投入生产的机器数量u1的关系为 g=g(u1)

这时,机器的年完好率为a,即如果年初完好机 器的数量为u,到年终完好的机器就为au, 0<a<1。
在低负荷下生产时,产品的年产量h和投入生产 的机器数量u2的关系为 h=h(u2)

相应的机器年完好率b, 0< b<1。
假定开始生产时完好的机器数量为s1。要求制 定一个五年计划,在每年开始时,决定如何重新 分配完好的机器在两种不同的负荷下生产的数量, 使在五年内产品的总产量达到最高。

3. 航天飞机飞行控制问题:由于航天飞机的 运动的环境是不断变化的,因此就要根据航天飞机 飞行在不同环境中的情况,不断地决定航天飞机的 飞行方向和速度(状态),使之能最省燃料和实现 目的(如软着落问题)。
4 .不包含时间因素的线性规划、非线性规划等 静态决策问题(本质上是一次决策问题)也可以适 当地引入阶段的概念,作为多阶段的决策问题用动 态规划方法来解决。

5 . 最短路问题:给定一个交通网络图如下,其 中两点之间的数字表示距离(或花费),试求从A点 到G点的最短距离(总费用最小)。
1 C1 3 6 3 3 6 C3 8 C4 1 2 3 8 D1 1 2 2 2 D2 E2 5 E1 3

5
A 3

B1

6
8 B2 7

C2

5

5
2

F1
3

4
G

3
4 D3

3
3 4 E3

6

6

F2

5

6

一、动态规划的基本思想
(一)、基本概念
1、阶段: 把一个问题的过程,恰当地分为若干个相互联系的 阶段,以便于按一定的次序去求解。

描述阶段的变量称为阶段变量(k)。k=1,2 ,3, …,n
一个数、 阶段的划分,一般是根据时间和空间的自然特征来进行 年、月、 一组数、 的,但要便于问题转化为多阶段决策。 路段 一个向 2、状态:表示每个阶段开始所处的自然状况或客观 量 条件。通常一个阶段有若干个状态,描述过程状态的 变量称为状态变量sk (表示第k阶段的状态变量 )。

状态变量的取值有一定的允许集合或范围,此集合 称为状态允许集合S K ={s1,s2, …, s k ,…}

3、决策:表示当过程处于某一阶段的某个状态时, 可以作出不同的决定,从而确定下一阶段的状态,这 种决定称为决策。

描述决策的变量,称为决策变量。 常用uk(sk)表示第k阶段当状态为sk时的决策变量。 决策变量是状态变量的函数。可用一个数、一组数 或一向量(多维情形)来描述。
在实际问题中决策变量的取值往往在某一范围之内, 此范围称为允许决策集合。 常用Dk(sk)表示第k阶段从状态sk出发的允许决策 集合,显然uk(sk)∈Dk(sk)。

4、多阶段决策过程 可以在各个阶段进行决策,去控制过程发展的多段过 程; 其发展是通过一系列的状态转移来实现的;
系统在某一阶段的状态转移不但与系统的当前的状态 和决策有关,而且还与系统过去的历史状态和决策有 关。

其状态转移方程如下(一般形式)

s2 ? T1 ( s1 , u1 ) s3 ? T2 ( s1 , u1 , s2 , u2 ) ?? sk ?1 ? Tk ( s1 , u1 , s2 , u2 ,?, sk , uk )
图示如下:

状态转移方程是确定 过程由一个状态到另 一个状态的演变过程。 如果第k阶段状态变量 sk的值、该阶段的决策 变量一经确定,第k+1 阶段状态变量sk+1的值 也就确定。

s1

u1 1

s2

u2 2

s3

?

sk

uk k

sk+1

能用动态规划方法求解的多阶段决策过程是一类 特殊的多阶段决策过程,即具有无后效性的多阶段 决策过程。

无后效性(马尔可夫性) 如果某阶段状态给定后,则在这个阶段以后 过程的发展不受这个阶段以前各段状态的影响; 过程的过去历史只能通过当前的状态去影响 它未来的发展; 构造动态规划模型时,要充分注意 是否满足无后效性的要求; 状态变量要满足无后效性的要求; 如果状态变量不能满足无后效性的要求,应 适当地改变状态的定义或规定方法。 状态具有无后效性的多阶段决策过程的状 态转移方程如下 动态规划中能 s2 ? T1 ( s1 , u1 ) 处理的状态转移 s3 ? T2 ( s2 , u2 ) 方程的形式。 ?? sk ?1 ? Tk ( sk , uk )

5、策略:相互连接的决策序列称为一个策略。 从第k阶段开始到第n阶段结束称为一个子策略。 Pk,n , 全策略 P1,n . 所有策略当中有最优值的策略称为最优策略。

6、状态转移方程:是确定过程由一个状态到另一 个状态的演变过程,描述了状态转移规律。

7、指标函数和最优值函数:用来衡量所实现过程优 劣的一种数量指标,为指标函数。

阶段指标函数: Vk (sk ,uk ) 表示第 k 阶段位 于sk 状态、决策为 uk 的指标值。 策略指标函数:各决策序列指标值之和。(个别情 况为乘积) 指标函数的最优值,称为最优值函数。在不同的问题 中,指标函数的含义是不同的,它可能是距离、利润、 成本、产量或资源消耗等。 动态规划模型的指标函数,应具有可分离性,并满 足递推关系。

小结: 无后效性 动态规划本质上是多阶段决策过程;
概念 : 阶段变量k﹑状态变量sk﹑决策变量uk; 方程 :状态转移方程 sk ?1 ? Tk (sk , uk ) 指标: Vk ,n ? Vk ,n (sk , uk , sk ?1, uk ?1,?, sn?1 )
效益

f k ( sk ) ? opt V k ,n ( sk , u k ,?, sn?1)
?u k ,?,u n?
Vk ,n (sk , uk , sk ?1, uk ?1,?, sn?1 )
可递推

? ? k [ sk , u k , Vk ?1, n ( sk ?1 , u k ?1 , ?, sn ?1 )]
指标函数形式: 和、 积

解多阶段决策过程问题,求出
最优策略,即最优决策序列
* * * {u1 , u2 ,?, un }

最优轨线,即执行最优策略时的状态序列

{ s , s ,?, s }
最优目标函数值
* V1,n

* 1

* 2

* n

f 1 ( s1 )

* * * 从 k 到终点最优策略 * * ? V1,n ( s1 , u1 ,?, sn , un )

子策略的最优目标函数值

f ?s ? ? opt v ?s , u
k k

?u ,?,u ?
k n

k ,n

k

k

, ? , sn ?1

?

(二)、动态规划的基本思想
1、动态规划方法的关键在于正确地写出基本的递推 关系式和恰当的边界条件(简称基本方程)。要做到 这一点,就必须将问题的过程分成几个相互联系的阶 段,恰当的选取状态变量和决策变量及定义最优值函 数,从而把一个大问题转化成一组同类型的子问题, 然后逐个求解。即从边界条件开始,逐段递推寻优, 在每一个子问题的求解中,均利用了它前面的子问题 的最优化结果,依次进行,最后一个子问题所得的最 优解,就是整个问题的最优解。

2、在多阶段决策过程中,动态规划方法是既把当前 一段和未来一段分开,又把当前效益和未来效益结合 起来考虑的一种最优化方法。因此,每段决策的选取 是从全局来考虑的,与该段的最优选择答案一般是不 同的. 3、在求整个问题的最优策略时,由于初始状态是 已知的,而每段的决策都是该段状态的函数,故最优 策略所经过的各段状态便可逐段变换得到,从而确定 了最优路线。 最优化原理:作为整个过程的最优策略具有这样的 性质:无论过去的状态和决策如何,相对于前面的决 策所形成的状态而言,余下的决策序列必然构成最优 子策略。”也就是说,一个最优策略的子策略也是最 优的。

(三)、建立动态规划模型的步骤 1、划分阶段k 划分阶段是运用动态规划求解多阶段决策问题的第一 步,在确定多阶段特性后,按时间或空间先后顺序, 将过程划分为若干相互联系的阶段。对于静态问题要 人为地赋予“时间”概念,以便划分阶段。

2、正确选择状态变量sk

选择变量既要能确切描述过程演变又要满足无后效性, 而且各阶段状态变量的取值能够确定。一般地,状态 变量的选择是从过程演变的特点中寻找。 3、确定决策变量uk(sk)及允许决策集合Dk(sk) 通常选择所求解问题的关键变量作为决策变量,同时 要给出决策变量的取值范围,即确定允许决策集合。

4、确定状态转移方程 根据k 阶段状态变量和决策变量,写出k+1阶段状态变量, 状态转移方程应当具有递推关系。 sk+1 =Tk (sk ,uk ) Tk —函数关系 5、确定阶段指标函数和最优指标函数,建立动态规 划基本方程 阶段指标函数是指第k 阶段的收益,最优指标函数是 指从第k 阶段状态出发到第n 阶段末所获得收益的最优 值,最后写出动态规划基本方程。

f k (sk ) = Opt [ Vk (sk ,uk ) + f k+1 (s k+1) ] fn+1 (s n+1 ) = 0 Opt 最优化(max,min)

f1(s1) 是整个问题的最优策略,最优值。 f k(sk) 表示从第k阶段(状态sk)到终点 的最优指标值。(距离、利润、成本等)

以上五步是建立动态规划数学模型的一般步骤。 由于动态规划模型与线性规划模型不同,动态规 划模型没有统一的模式,建模时必须根据具体问 题具体分析,只有通过不断实践总结,才能较好 掌握建模方法与技巧。

二、最短路径问题
例一、从A 地到D 地要铺设一条煤气管道,其中需经过 两级中间站,两点之间的连线上的数字表示距离,如 图所示。问应该选择什么路线,使总距离最短?
3
2 A 4 B2 B1 2 1 3 C2 4 C3 3

C1

1 D

3 1

3
2 A 4 B2 B1 2 1 3

C1
C2 4 C3 3

1 D

3 1

解:整个计算过程分三个阶段,从最后一个阶段开始。

第三阶段(C →D): C 有三条路线到终点D 。
显然有 f3 (C1 ) = 1 ; f3(C2 ) = 3 ; f3 (C3 ) = 4

3
2 A 4 B2 B1 2 1 3

C1
C2 4 C3 3

1 D

3 1

第二阶段(B →C): B 到C 有六条路线。
d( B1,C1 ) + f3 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f3 (C2 ) = min 3+3 d( B1,C3 ) + f3 (C3 ) 1+4 4 = min 6 = 4 (最短路线为B1→C1 →D) 5

3
2 A 4 B2 B1 2 1 3

C1
C2 4 C3 3

1 D

3 1

d( B2,C1 ) + f3 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f3 (C2 ) = min 3+3 d( B2,C3 ) + f3 (C3 ) 1+4 3 = min 6 = 3 (最短路线为B2→C1 →D) 5

3
2 A 4 B2 B1 2 1 3

C1
C2 4 C3 3

1 D

3 1

第一阶段( A → B ): A 到B 有二条路线。
f1(A)1 = d(A, B1 )+ f2 ( B1 ) =2+4=6 f1 (A)2 = d(A, B2 )+ f2 ( B2 ) =4+3=7 ∴ f1 (A) = min d(A, B1 )+ f2 ( B1 ) = min{6,7}=6 d(A, B2 )+ f2 ( B2 ) (最短路线为A→B1→C1 →D)

3 2 A 4 B2 B1 2 3 1 3 1

C1 C2 4 3

1 D

C3

最短路线为

A→B1→C1 →D

路长为 6

三、非线性规划问题
【例7-4】 用动态规划方法解下列非线性 规划问题

max z ? x1 ?

2 x2

? x3

? x1 ? x 2 ? x3 ? c ? i ? 1,2,3 ? xi ? 0

max z ? x1 ?

2 x2

? x3

? x1 ? x 2 ? x3 ? c ? i ? 1,2,3 ? xi ? 0
解: 解决这一类静态规划问题,需要人为地赋 予时间概念,从而将该问题转化为多阶段决 策过程。 按问题的变量个数划分阶段,把它看作一 个三阶段决策问题,k=1,2,3 设状态变量为s1,s2,s3,s4并记s1≤c 取问题中的变量x1,x2,x3为决策变量

状态转移方程为: s3=x3 s3+x2=s2 s2+x1=s1≤c 允许决策集合为: x 3= s 3 0≤x2≤s2 0 ≤ x 1≤ s 1 各阶段指标函数为:v1(x1)=x1 v2(x2)=x22 v3(x3)=x3, 各指标函数以乘积方式结合,最优指标函数 fk(sk) 表示从第k阶段初始状态sk出发到第3阶段所得到的 最大值,则动态规划基本方程为:

f ( s ) ? max [ v ( x ) ? f ( s )] ? k k k k k ? 1 k ? 1 ? xk ?Dk ( sk ) ? ? ? f 4 (s4 ) ? 1

k ? 3,2, ,1

用逆序解法由后向前依次求解:
k=3时,

f 3 ( s3 ) ? max [v3 ( x3 ) ? f 4 (s 4 )] ? max( x3 ) ? s3
x3?D3 ( s3 ) x3 ? s3

x3*=s3

k=2时,
f 2 (s2 ) ? max [v2 ( x2 ) ? f 3 (s3 )] ? max ( x ? s3 ) ? max [ x ? (s2 ? x2 )]
x2 ?D2 ( s2 ) 0 ? x2 ? s 2 2 2 0 ? x2 ? s 2 2 2

令h2(s2,x2)=x22(s2-x2) 用经典解析法求极值点:dh2
dx2

2 ? 2 x 2 s 2 ? 3x 2 ?0

解得:

x2

2 ? s2 3

x2=0(舍)

d 2 h2 ? 2s 2 ? 6 x 2 2 dx2

所以

2 x2 ? s2 3

d 2 h2 2 ? ?2s 2 ? 0 2 dx2 x2 ? s 2 3

是极大值点。
2 x ? s2 3
* 2

2 2 4 3 2 f 2 (s2 ) ? ( s2 ) (s2 ? s2 ) ? s2 3 3 27

k=1时,
4 3 4 f1 ( s1 ) ? max [v1 ( x1 ) ? f 2 ( s 2 )] ? max ( x1 ? s 2 ) ? max [ x1 ? ( s1 ? x1 ) 3 ] x1?D1 ( s1 ) 0? x1 ? s1 0? x1 ? s1 27 27 4 令 h1 ( s1 , x1 ) ? x1 ? ( s1 ? x1 ) 3 27

dh1 4 12 3 ? ( s1 ? x1 ) ? x1 ( s1 ? x1 ) 2 (?1) ? 0 dx1 27 27
1 解得: x1 ? s1 x1=s1(舍) 4 d 2 h1 12 12 24 24 2 2 ? (s1 ? x1 ) (?1) ? (s1 ? x1 ) ? x1 (s1 ? x1 ) ? (s1 ? x1 )(2 x1 ? s1 ) 2 27 27 27 dx1 27
d 2 h1 9 2 1 ? ? s1 ? 0 2 27 dx1 x1 ? s1 4

1 所以 x1 ? 4 s1

是极大值点。

1 4 1 3 1 4 f1 (s1 ) ? s1 ? (s1 ? s1 ) ? s1 4 27 4 64
1 4 max f1 ( s1 ) ? max ( s1 ) 0? s1 ? c 0? s1 ? c 64

1 x ? s1 4
* 1

由于s1未知,所以对s1再求极值, 显然s1=c时,f1(s1)取得最大值 1 4 f1 ( s1 ) ? c 反向追踪得各阶段最优决策及最优值: 64 1 1 * 1 x1 ? s1 ? c s1=c f1 ( s1 ) ? c 4
3 s2 ? s1 ? x ? c 4
* 1

4

4

1 s3 ? s 2 ? x ? c 4
* 2

2 1 x ? s2 ? c 3 2
* 2

64

4 3 1 3 f 2 (s2 ) ? s2 ? c 27 16

1 x ? s3 ? c 4
* 3
* 1

1 f 3 ( s3 ) ? s3 ? c 4

所以最优解为:

1 * 1 * 1 * 1 4 x ? c, x 2 ? c, x 3 ? c, z ? c 4 2 4 64

一般地,如果阶段指标函数 vk ( sk , uk ) 是 线性函数或凸函数时,最优指标函数 fk ( sk ) 的表达式比较容易得到,但是当 vk ( sk , uk ) 不具备上述特性时,最优指标函数 fk ( sk ) 的 表达式不易得到,就需要采用数值法,即对连 续变量进行离散化处理,再分散求解。 例如静态规划模型
max z ? g1 ( x1 ) ? g 2 ( x2 ) ? ? ? g n ( xn ) ? x1 ? x2 ? ? ? xn ? a ? ? x j ? 0 j ? 1,2,?, n

其动态规划基本方程为:
[ g k ( xk ) ? f k ?1 (sk ?1 )] ? ? f k (sk ) ? xkmax ?Dk ( sk ) ? ? ? f n?1 (sn?1 ) ? 0 k ? n, n ? 1,?,1

状态转移方程为sk+1=sk-xk

s1=a

状态变量 sk 及决策变量 xk 都是连续变量,对其进行离散 化处理,具体做法是: a 1. 对区间[0,a]进行分割,分割数m= ? ,其中Δ是分 割后的小区间的长度,其大小可以根据所求解问题要 求的精度及计算机运算能力而定,分割点为 0,Δ, 2Δ,…,mΔ= a。 2. 规定状态变量sk及决策变量xk仅在离散点0,Δ, 2Δ,…,mΔ处取值,最优指标函数fk(sk)也定义在 这些离散点上。动态规划基本方程可以写为:
[ g k ( p?) ? f k ?1 (sk ? p?)] ? ? f k (sk ) ? p?max 0,1, 2?,q ? ? ? f n?1 (sn?1 ) ? 0 k ? n, n ? 1,?,1

其中sk=qΔ ,xk=pΔ 。 3. 由后向前逐段递推,直至求出整个过程最优解。

【例7-5】

max z ? x12 ? x2 ? x33 ? x1 ? x2 ? x3 ? 6 ? ? x j ? 0 j ? 1,2,3

解 按变量个数将原问题分为三个阶段,阶段变量 k=1,2, 3; 选择xk为决策变量; 状态变量sk表示第k阶段至第3阶段决策变量之和; 取小区间长度Δ=1,小区间数目m=6/1=6,状态变量 sk的取值点为: k?2 ?s k ? 0,1,2,3,4,5,6
? ?s1 ? 6

状态转移方程:sk+1=sk-xk; 允许决策集合:Dk(sk)={xk|0≤xk≤sk} k=1,2,3 xk,sk均在分割点上取值;

阶段指标函数分别为:g1(x1)=x12 g2(x2)=x2 g3(x3)=x33, 最优指标函数fk(sk)表示从第k阶段状态sk 出发到第3阶段所得到的最大值,动态规划的基 [ g k ( xk ) ? f k ?1 (sk ?1 )] k ? 3,2,1 本方程为:? ? f k (sk ) ? 0max ? x ?s
? ? ? f 4 (s4 ) ? 1
k k

k=3时,

3 3 f 3 ( s3 ) ? max( x3 ) ? s3 x3 ? s3

s3及x3取值点较多,计算结果以表格形式给出, 见表7-1所示。

表7-1 取值

[ x2 ? f 3 ( s3 )] ? max [ x2 ? f 3 (s 2 ? x2 )] k=2时, f 2 (s2 ) ? 0max ? x ?s 0? x ? s 计算结果见表7-2
2 2 2 2

2 2 f ( s ) ? max [ x ? f ( s )] ? max [ x k=1时, 1 1 0? x1 ?s1 1 2 2 1 ? f 2 ( s1 ? x1 )] 0? x1 ? s1 其中s1=6,计算结果见表7-3所示。

由表7-3知,x1*=2,s1=6,则s2= s1-x1*=6-2=4,查 表 7-2 得: x2*=1 , 则 s3= s2 - x2*=4 - 1=3 , 查表 7-1 得: x3*=3,所以最优解为:x1*=2,x2*=1,x3*=3,f1(s1)=108。 本例也可用经典解析法求得各段的极值,读者可自 行求解,二者结论完全相同。需要指出的是当连续变量 离散化处理以后,由于状态变量和决策变量只在给定的 离散点上取值,故有可能漏掉最优解,因此需要慎重选 择参数m与Δ。

四、资源分配问题
资源分配问题就是将一定数量的一种或若干种资 源(原材料、资金、设备等)合理分配给若干使用者, 使得资源分配后总结果最优。一种资源的分配问题称 为一维资源分配问题,两种资源的分配问题称为二维 资源分配问题。

假设有一种资源,数量为a,将其分配给n个使用者, 分配给第i个使用者数量xi时,相应的收益为gi(xi), 问如何分配使得总收入最大?这就是一维资源分配问题, 该问题的数学模型为:

max z ? g1 ( x1 ) ? g 2 ( x2 ) ? ? ? g n ( xn ) ? x1 ? x2 ? ? ? xn ? a ? ? xi ? 0 i ? 1,2,?, n
这是一个静态规划问题,应用动态规划方法求解时 人为赋予时间概念,将其看作是一个多阶段决策问题。

按变量个数划分阶段,k=1,2,…,n; 设决策变量 uk=xk ,表示分配给第 k 个使用者的资源数量; 设状态变量为 sk ,表示分配给第 k 个至第 n 个使用者的总 资源数量; 状态转移方程:sk+1=sk-xk,其中s1=a; 允许决策集合:Dk(sk)={xk|0≤xk≤sk} 阶段指标函数: vk(sk, uk)=gk(xk)表示分配给第 k个 使用者数量xk时的收益; 最优指标函数fk(sk)表示以数量sk的资源分配给第k个至 第n个使用者所得到的最大收益,则动态规划基本方程 为:

f ( s ) ? max [ g ( x ) ? f ( s )] ? k k k k k ? 1 k ? 1 ? 0 ? xk ? s k ? ? ? f n?1 (s n?1 ) ? 0

k ? n,?,1

由后向前逐段递推,f1(a)即为所求问题的最大收益。

【例7-6】 某公司打算在3个不同的地区设置4个 销售点,根据市场部门估计,在不同地区设置 不同数量的销售点每月可得到的利润如表 7-4 所示。试问在各地区如何设置销售点可使每月 总利润最大。 表7-4

解 如前所述,建立动态规划数学模型: 将问题分为3个阶段,k=1,2,3; 决策变量xk表示分配给第k个地区的销售点数; 状态变量为 sk 表示分配给第 k 个至第 3 个地区的销售点总 数; 状态转移方程:sk+1=sk-xk,其中s1=4; 允许决策集合:Dk(sk)={xk|0≤xk≤sk} 阶段指标函数: gk(xk)表示xk个销售点分配给第 k 个地区所获得的利润; 最优指标函数fk(sk)表示将数量为sk的销售点分 配给第k个至第3个地区所得到的最大利润,动态规划 基本方程为: f (s ) ? max [ g ( x ) ? f (s ? x )] k ? 3,2,1 ? k ?1 k k ? k k 0 ? xk ? s k k k ? ? ? f 4 (s4 ) ? 0

f 3 ( s3 ) ? max [ g 3 ( x3 )] k=3时, x ?s 数值计算如下表7-5
3 3

表7-5

[ g 2 ( x2 ) ? f 3 (s 2 ? x2 )] k=2时,f 2 (s2 ) ? 0max ? x ?s 计算结果见下表7-6
2 2

表7-6

[ g1 ( x1 ) ? f 2 ( s1 ? x1 )] k=1时, f1 (s1 ) ? 0max ? x ?s k=1时,只有s1=4的情况。
1 1

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

计算结果如表7-7所示。
所以最优解为:x1*=2,x2*=1, x3*=1,f1(4)=47,即在第1个 地区设置2个销售点,第2个 地区设置1个销售点,第3个 地区设置1个销售点,每月可获利润47。表7-7

【例7-7】机器负荷问题 某工厂有100台机器,拟分四期使用,每一期都可在高、低 两种不同负荷下进行生产。若把x台机器投入高负荷下进行生产, 则在本期结束时将有1/3x台机器损坏报废;余下的机器全部投 入低负荷下进行生产,则在期末有1/10的机器报废。如果高负 荷下生产时每台机器可获利润为10,低负荷下生产时每台机器 可获利润为7,问怎样分配机器使四期的总利润最大? 解 将问题按周期分为4个阶段,k=1,2,3,4; 状态变量sk表示第k阶段初完好的机器数,s1=100,0≤sk≤100; 决策变量xk表示第k阶段投入高负荷下生产的机器数, 则sk-xk表示第k阶段投入低负荷下生产的机器数; 允许决策集合:Dk(sk)={xk|0≤xk≤sk} 状态转移方程:sk+1=Tk(sk,xk),即第k+1阶段初拥有的完好机 器数sk+1为:

2 9 s k ?1 ? xk ? ( s k ? xk ) 3 10

阶段指标函数:vk(sk,xk)=10xk+7(sk-xk)表示第k阶段所获得的利润; 最优指标函数fk(sk)表示从第k阶段初完好机器数为sk至第四阶段的最大 利润,动态规划基本方程为:f ( s ) ? max [v ( s , x ) ? f ( s )] k ? 4,3,2,1

? ? k k 0 ? xk ? s k ? ? ? f 5 ( s5 ) ? 0

k

k

k

k ?1

k ?1

k=4时,

f 4 ( s 4 ) ? max [10 x4 ? 7( s 4 ? x4 )] ? max (3x4 ? 7 s 4 ) ? 10 s 4
0 ? x4 ? s 4 0 ? x4 ? s 4

x 4*= s 4
k=3时,

f 3 ( s3 ) ? max [10x3 ? 7( s3 ? x3 ) ? f 4 ( s 4 )]
0? x3 ? s3

? max [10x3 ? 7( s3 ? x3 ) ? 10s 4 ]
0? x3 ? s3

2 9 ? ? ? max ?10x3 ? 7( s3 ? x3 ) ? 10[ x3 ? ( s3 ? x3 )]? 0? x3 ? s3 3 10 ? ? 2 ? max ( x3 ? 16s3 ) 0? x3 ? s3 3 50 ? s3 3 ∴ x 3*= s 3

k=2时, f 2 ( s 2 ) ? 0max [10x 2 ? 7( s 2 ? x 2 ) ? ? x ?s
2 2

f 3 ( s3 )]

k=1时, f1 ( s1 ) ? max[10x1 ? 7( s1 ? x1 ) ? f 2 (s 2 )] 0? x ? s
1 1

50 s3 ] 0 ? x2 ? s 2 3 50 2 9 ? ? ? max ?10x 2 ? 7( s 2 ? x 2 ) ? [ x 2 ? ( s 2 ? x 2 )]? 0 ? x2 ? s 2 3 3 10 ? ? 8 ? max (22s 2 ? x 2 ) 0 ? x2 ? s 2 9 *=0 ∴ x 2 ? 22s 2 ? max [10x 2 ? 7( s 2 ? x 2 ) ?

? max[10x1 ? 7( s1 ? x1 ) ? 22s 2 ]
0? x1 ? s1

2 9 ? ? ? max ?10x1 ? 7( s1 ? x1 ) ? 22[ x1 ? ( s1 ? x1 )]? 0? x1 ? s1 3 10 ? ? 134 32 ? max ( s1 ? x1 ) 0? x1 ? s1 5 15 134 ? s1 ∴ x1*=0 5

因为s1=100,所以f1(100)=2680,逆向追踪得: s1=100, x1*=0

2 * 9 * s 2 ? x1 ? ( s1 ? x1 ) ? 90 3 10 2 * 9 * s3 ? x 2 ? ( s 2 ? x 2 ) ? 81 3 10 2 * 9 * s 4 ? x3 ? ( s 3 ? x3 ) ? 54 3 10

x2*=0 x3*=s3=81 x4*=s4=54

即,第1,2期把全部完好机器投入低负荷下生产,第 3,4期把全部完好机器投入高负荷下生产所得利润最大。

五、生产计划问题
在企业生产经营活动中,经常会遇到 如何合理安排生产、库存及销售计划, 使总效益最高的问题,这一类问题统称 为生产计划问题。

【例7-8】 (生产—库存问题)

某工厂要对一种产品制定今后四个时期的生产计划, 据估计在今后四个时期内,市场对该产品的需求量分别 为2,3,2,4单位,假设每批产品固定成本为3千元, 若不生产为0,每单位产品成本为1千元,每个时期最大 生产能力不超过6个单位,每期期末未出售产品,每单 位需付存贮费0.5千元,假定第1期初和第4期末库存量 均为0,问该厂如何安排生产与库存,可在满足市场需 求的前提下总成本最小。 解 以每个时期作为一个阶段,该问题分为 4个阶段, k=1, 2, 3, 4; 决策变量xk表示第k阶段生产的产品数; 状态变量sk表示第k阶段初的库存量;

以dk表示第k阶段的需求,则状态转移方程: sk+1=sk+xk-dk k=4,3,2,1 由于期初及期末库存为0,所以s1=0,s5=0; 允许决策集合Dk(sk)的确定: 当sk≥dk时,xk可以为0,当sk<dk时,至少应生产dk -sk,故xk的下限为max(0,dk-sk);每期最大生产 能力为6,xk最大不超过6,由于期末库存为0, x 还应 4 k 小于本期至4期需求之和减去本期的库存量 ? d j ? sk, j ?k 所以xk的上限为min( 4 ,6),故有: ? d j ? sk
j ?k

Dk(sk)={xk| max(0,dk-sk)≤xk≤min(

,6)} d ? s ?j k
j ?k

4

阶段指标函数rk(sk,xk)表示第k期的生产费用与 存贮费用之和:

?0.5sk rk (sk , xk ) ? ? ?3 ? xk ? 0.5sk

xk ? 0 xk ? 1,2,3,4,5,6

最优指标函数 fk ( sk )表示第 k 期库存为 sk 到第 4 期 末的生产与存贮最低费用,动态规划基本方程为:

f ( s ) ? min [ r ( s , x ) ? f ( s )] ? k k k k k k ? 1 k ? 1 ? xk ?Dk ( sk ) ? ? ? f5 (s5 ) ? 0

k ? 4,3,2,1

先求出各状态允许状态集合及允许决策集合,如 表7-8所示。 表7-8

k=4时,

f 4 (s4 ) ? min [r4 (s4 , x4 ) ? f5 (s5 )]
x4 ?D4 ( s4 )

? min [r4 ( s4 , x4 )]
x4 ?D4 ( s4 )

计算结果见表7-9所示。 表7-9

k=3时,

f3 (s3 ) ? min [r3 ( s3 , x3 ) ? f 4 ( s4 )]
x3?D3 ( s3 )

计算结果如下表:

? min [r3 (s3 , x3 ) ? f 4 (s3 ? x3 ? 2)]
x3?D3 ( s3 )

k=2时,

f 2 ( s2 ) ? min [r2 ( s2 , x2 ) ? f3 ( s3 )]
x2 ?D2 ( s2 )

计算结果如下表

? min [r2 ( s2 , x2 ) ? f3 ( s2 ? x2 ? 3)]
x2 ?D2 ( s2 )

k=1时,

f1 ( s1 ) ? min [r1 ( s1 , x1 ) ? f 2 ( s2 )]
x1?D1 ( s1 )

? min [r1 ( s1 , x1 ) ? f 2 ( s1 ? x1 ? 2)] x1?D1 ( s1 ) 计算结果见表7-12所示

逆向追踪可得:x1*=5,s2=3,x2*=0,s3=0,x3*=6, s4=4,x4*=0,即第1时期生产5个单位,第3时期生产6个 单位,第2,4时期不生产,可使总费用最小,最小费用 为20.5千元。

【例7-9】 (库存—销售问题) 设某公司计划在1至4月份从事某种商品经营。已知仓 库最多可存储 600件这种商品,已知 1月初存货 200件,根 据预测知1至4月份各月的单位购货成本及销售价格如表 713所示,每月只能销售本月初的库存,当月进货供以后各 月销售,问如何安排进货量和销售量,使该公司四个月获 得利润最大(假设四月底库存为零)。 表7-13

解 按月份划分阶段,k=1,2,3,4; 状态变量sk表示第k月初的库存量,s1=200,s5=0; 决策变量 xk表示第k月售出的货物数量, yk表示第k月购进的货物数量; 状态转移方程:sk+1=sk+yk-xk; 允许决策集合:0≤xk≤sk,0≤yk≤600-(sk-xk); 阶段指标函数为:pkxk-ckyk表示k月份的利润,其中pk为 第k月份的单位销售价格,ck为第k月份的单位购货成本; 最优指标函数 fk(sk)表示第 k月初库存为sk时从第k月至 第4月末的最大利润,则动态规划基本方程为:
max [ p k x k ? c k y k ? f k ?1 ( s k ?1 )] ? f k (sk ) ? 0 ? xk ? s k ? 0? y k ? 600 ? ( sk ? xk ) ? ? ? f 5 ( s5 ) ? 0 k ? 4,3,2,1

k=4时, f 4 (s4 ) ?

0 ? x4 ? s 4 0? y4 ? 600 ? ( s4 ? x4 )

max

(44 x4 ? 42 y 4 ) ? 44 s 4 x *=s 4 4
max [39x3 ? 40 y 3 ? f 4 ( s 4 )]

y4*=0

k=3时, f ( s ) ? 3 3
? ?

0? x3 ? s3 0? y3 ? 600 ? ( s3 ? x3 ) 0? x3 ? s3 0? y3 ? 600 ? ( s3 ? x3 ) 0? x3 ? s3 0? y3 ? 600 ? ( s3 ? x3 )

max max

[39x3 ? 40 y 3 ? 44( s3 ? y 3 ? x3 )] (44s3 ? 5 x3 ? 4 y 3 )

为求出使 44s3 - 5x3+4y3 最大的 x3 , y3,须求解线性规划问 题: max z ? 44s ? 5 x ? 4 y
3 3 3

? x3 ? s 3 ? ?? x3 ? y 3 ? 600 ? s 3 ?x , y ? 0 ? 3 3

max z ? 44s 3 ? 5 x3 ? 4 y 3 ? x3 ? s 3 ? ?? x3 ? y 3 ? 600 ? s 3 ?x , y ? 0 y3 ? 3 3

只有两个变量 x3 , y3 ,可 用图解法也可用单纯形法 求解,图解法求解示意图 如图7-5所示: 在A点处取得最优解,

600-s3

A

x3*=0,y3*=600-s3, f3(s3)=40s3+2400

0

s3
图7-5

600

x3

k=2时, f 2 (s 2 ) ?
? ?

0 ? x2 ? s 2 0? y2 ?600 ?( s2 ? x2 ) 0 ? x2 ? s 2 0? y2 ?600 ?( s2 ? x2 ) 0 ? x2 ? s 2 0? y2 ?600 ?( s2 ? x2 )

max

[42x2 ? 38y 2 ? f 3 ( s3 )]

max max

[42x2 ? 38y 2 ? 40( s 2 ? y 2 ? x2 ) ? 2400] (40s 2 ? 2 x2 ? 2 y 2 ? 2400)

类似地求得:x2*=s2,y2*=600,f2(s2)=42s2+3600 k=1时, f1 ( s1 ) ? max [45x1 ? 40 y1 ? f 2 ( s 2 )]
0? x1 ? s1 0? y1 ? 600 ? ( s1 ? x1 )

? ?

0? x1 ? s1 0? y1 ? 600 ? ( s1 ? x1 ) 0? x1 ? s1 0? y1 ? 600 ? ( s1 ? x1 )

max max

[45x1 ? 40 y1 ? 42( s1 ? y1 ? x1 ) ? 3600 ] (42s1 ? 3x1 ? 2 y1 ? 3600 )

类似地求得:x1*=s1,y1*=600, f1(s1)=45s1+4800=13800

逆向追踪得各月最优购货量及销售量: x1*=s1=200 y1*=600; x2*=s2=s1+ y1*-x1*=600 y2*=600; x3*=0 y3*=600-s3=600-(s2+ y2*-x2*)=0 x4*=s4=(s3+ y3*-x3*)=600 y4*=0 即1月份销售200件,进货600件,2月份销售600件, 进货600件,3月份销售量及进货量均为0,4月份销售600 件,不进货,可获得最大总利润13800。

六、背包问题
有人携带背包上山,其可携带物品的重量限度为 a 公斤,现有n种物品可供选择,设第i种物品的单件重量为 ai 公斤,其在上山过程中的价值是携带数量 xi 的函数 ci (xi),问应如何安排携带各种物品的数量,使总价值最 大。这就是背包问题,类似的货物装载问题,下料问题都 等同于背包问题。 背包问题的数学模型为:

max z ? c1 ( x1 ) ? c 2 ( x 2 ) ? ? ? c n ( x n ) ?a1 x1 ? a 2 x 2 ? ? ? a n x n ? a ? ? xi ? 0且为整数(i ? 1,2, ? , n)

下面用动态规划方法求解: 按照装入物品的种类划分阶段,k=1,2,…,n; 状态变量sk表示装入第k种至第n种物品的总重量; 决策变量xk表示装入第k种物品的件数; 状态转移方程为:sk+1=sk-akxk 允许决策集合为: ? ? sk Dk ( s k ) ? ? xk 0 ? xk ? [ ], xk 为整数? ak ? ? sk sk ] 表示不超过 其中 [ 的最大整数; 阶段指标函数 ck ( xk )表示第 k 阶段装入第 k 种商品 xk 件 时的价值; 最优指标函数 fk ( sk )表示第 k 阶段装入物品总重量为 sk 时的最大价值,动态规划基本方程为:
? f k (s k ) ? maxs [ck ( xk ) ? f k ?1 (s k ?1 )] ? xk ?0,1,?,[ k ] ak ? ? f (s ) ? 0 ? n?1 n?1 k ? n, n ? 1,?,1

ak

ak

【例7-10】 某工厂生产三种产品,各产品重量与利润关 系如表7-14所示,现将此三种产品运往市场销售,运输能 力总重量不超过6吨,问如何安排运输使总利润最大? 表7-14
种类 单位重量(吨) 1 2 2 3 3 4

单位利润(元)

80

130

180

解 设xi为装载第i种货物的件数,i=1,2,3,该问题数学 模型为: max z ? 80x ? 130x ? 180x
1 2 3

?2 x1 ? 3x 2 ? 4 x3 ? 6 ? ? xi ? 0且为整数(i ? 1,2,3)

按前述方法建立动态规划模型; k=3时, 3 3 s3 x3 ? 0 ,1,?,[ ] 4

f (s ) ?

max

(180 x3 )

计算结果如表7-15所示。

k=2时,f 2 ( s 2 ) ?

s2 x2 ?0,1,?,[ ] 3 s2 x2 ?0,1,?,[ ] 3

max [130x2 ? f 3 ( s3 )]

?

max [130x2 ? f 3 ( s 2 ? 3x2 )]

计算结果如表7-16所示。 表7-16

[80x1 ? f 2 ( s 2 )] k=1时, f1 ( s1 ) ? x max ? 0 ,1, 2 , 3
1

? max [80x1 ? f 2 ( s1 ? 2 x1 )]
x1 ? 0 ,1, 2 , 3

计算结果如表7-17所示。 表7-17

反向追踪得最优方案Ⅰ:x1*=0,x2*=2,x3*=0; 最优方案Ⅱ:x1*=1,x2*=0,x3*=1; 最大总利润为260元。

七、复合系统工作可靠性问题
某个机器工作系统由n个部件串联而成, 其中只要有一个部件失效,则整个系统不能正 常工作,因此为了提高系统工作的可靠性,在 设计时,每个主要部件上都装有备用元件,一 旦某个主要部件失效,备用元件会自动投入系 统工作,显然备用元件越多,系统工作可靠性 越大,但是备用元件越多,系统的成本、重量、 体积相应增大,工作精度降低,因此在上述限 制条件下,应选择合理的备用元件数,使整个 系统的工作可靠性最大。

设第 i (i=1, 2 , … , n )个部件上装有 ui个备用元件,正 常工作的概率为pi(ui),则整个系统正常工作的可靠性 n 为 P? i个部件的费用为ci,重量为wi,要 p (,装第 u)

?
i ?1

i

i

求总费用不超过 c ,总重量不超过 w ,则静态规划数学模 n 型为: max P ? pi (u i )

?
i ?1

?n ?? ci u i ? c ? i ?1 ?n ?? wi u i ? w ? i ?1 ?u i ? 0且为整数i ? 1,2, ?, n ? ?

按部件个数划分阶段,k=1,2,…,n; 决策变量uk表示部件k上的备用元件数; 状态变量xk表示从第k个到第n个部件的总费用, yk表示从第k个到第n个部件的总重量; 状态转移方程为: xk+1=xk-ckuk yk+1=yk-wkuk 允许决策集合为: ? ? xk y k Dk ( x k , y k ) ? ?u k 0 ? u k ? min([ ],[ ]),且u k 为整数? c k wk ? ? 阶段指标函数为pk(uk),表示第k个部件的正常工作概率; 最优指标函数fk(xk,yk)表示由状态xk,yk出发,从部件k到部件 n的系统工作最大可靠性,则动态规划基本方程为:

[ pk (u k ) ? f k ?1 ( xk ?1 , yk ?1 )] ? ? f k ( xk , y k ) ? uk ?max Dk ( xk , yk ) ? ? ? f n?1 ( xn?1 , y n?1 ) ? 1

k ? n, n ? 1,?,1

f1(c,w)即为整个系统工作的最大可靠性。

【例7-11】 某厂设计的一种电子设备由三种元件 A 、 B 、 C 串联而成,已知三种元件的价格及可靠 性如表7-18所示,要求设计中使用元件的总费用不 超过 10 万元,问如何设计使设备的可靠性达到最 大(不考虑重量限制)。 表7-18

解 如前所述建立动态规划数学模型; 按元件种类划分为3个阶段,k=1,2,3; 决策变量xk表示第k个部件配备的元件数; 状态变量 sk 表示从第 k 阶段到第 3 阶段配备元件的总费用 ; 状态转移方程为: sk+1=sk-ckxk 其中ck表示第k种部件的元件单价; 允许决策集合为: ? ? sk
Dk ( s k ) ? ? x k 0 ? x k ? [ ],且x k 为整数? ck ? ?

以pk表示第k个部件中的1个元件的正常工作概率,假定 xk为xk个元件均 部件k的xk个元件是并联的,则

(1 ? pk )

不正常工作的概率,fk(sk)表示由状态sk开始从第k个到 第3个部件的设备最大可靠性。

k=3时, f 3 ( s3 )

? max [1 ? (1 ? p3 ) ]
x3 x3?D3 ( s3 )

? max (1 ? 0.4 x3 )
x3?D3 ( s3 )

由于 A 、 B 至少要购置 1 件,用于购置 C 的最高金额为 s3=10-2-3=5万元,计算结果如表7-19所示。 表7-19

k=2时, f ( s ) ? max [1 ? (1 ? p ) x2 ] ? f ( s ) 2 2 2 3 3
x2 ?D2 ( s2 )

?

x2 ?D2 ( s2 )

? max ?(1 ? 0.2

? ?

x2

) ? f 3 ( s 2 ? 3x2 )

计算结果如表7-20所示。 表7-20

x1 k=1时, f ( s ) ? max ? [ 1 ? ( 1 ? p ) ] ? f 2 ( s 2 )? 1 1 1 x1?D1 ( s1 )

? max (1 ? 0.3 ) ? f 2 ( s1 ? 2 x1 )
x1 x1?D1 ( s1 )

?

?

计算结果如表7-21所示。 表7-21

逆向追踪得:x1*=2,s2=6,x2*=1,s3=3,x3*=3,即A元件 用2个,B元件用1个,C元件用3个,最高可靠性为0.682。


相关文章:
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划(Dynamic Programming) 动态规划
运筹学7动态规划.ppt
运筹学7动态规划_数学_自然科学_专业资料。运筹学7动态规划 第七 章动态规划 主要内容: §7.1 多阶段决策过程的最优化 §7.2 动态规划的基本概念和基本原理 ...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 (Dynamic programming) 动态规
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
运筹学动态规划习题_图文.ppt
运筹学动态规划习题 - 习题三 一、某工厂购进100台机器,准备生产A、B 两种
运筹学动态规划分析_图文.ppt
运筹学动态规划分析 - Page:1 运动 态筹 规 划学 华东理工大学 工商经
运筹学动态规划.ppt
运筹学动态规划_数学_自然科学_专业资料。第7章重点: 动态规划 (Dynami
第七章运筹学动态规划_图文.ppt
第七章运筹学动态规划 - 动态规划 引言 □动态规划是解决多阶段决策过程最优化的
清华大学运筹学课件动态规划_图文.pdf
清华大学运筹学课件动态规划 - 动态规划 主要内容 基本概念 多阶段问题 建模与
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
15《运筹学》(第四版)连续动态规划_图文.pdf
15《运筹学》(第四版)连续动态规划_工学_高等教育_教育专区。对应教材为《运筹学》(第四版)清华大学出版社,融合多个版本运筹学课件优点。...
运筹学_动态规划分析_图文.ppt
运筹学_动态规划分析 - ? ? 非线性规划问题 决策变量连续的动态规划问题 乘积形式的目标函数 随机型动态规划 ? ? 非线性规划问题 ? 应用动态规划求解问题 2 2...
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
运筹学课件(动态规划)_图文.ppt
运筹学课件(动态规划) - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化...
运筹学---动态规划_图文.ppt
运筹学---动态规划 - 这是关于运筹学里的动态规划的课件ppt... 运筹学---动态规划_理学_高等教育_教育专区。这是关于运筹学里的动态规划的课件ppt 动态...
运筹学第八章 动态规划_图文.ppt
运筹学第八章 动态规划 - 第八章 动态规划 8.1 8.2 8.3 8.4 动态规划的研究对象和特点 动态规划的基本概念与最优化原理 动态规划的求解与应用 随机动态规划 ...
运筹学动态规划PPT_图文.ppt
运筹学动态规划PPT - 动态规划 (Dynamic programming)
运筹学第10章 动态规划_图文.ppt
运筹学第10章 动态规划 - Page:1 管理运筹学 动态规划 Page:2
运筹学 07 动态规划_图文.ppt
运筹学 07 动态规划 - 1 多阶段决策过程的最优化 ? 概述 ? 多阶段决策过程及其最优化 ? 多阶段决策过程举例 ? 动态规划求解的多阶段决策问题的特点 ? 动态...
运筹学 动态规划应用.ppt
运筹学 动态规划应用_数学_自然科学_专业资料。第七章 动态规划动态规划问题的基
更多相关文章: