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

运筹学----动态规划


动 态 规 划
(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 8 3 D1 1 2 2 2 5 E2 2 D2 E1 3

5
A 3

B1

6
8 B2 7 6

C2

5
3

5

F1
3

4
G

C3 8 C4

3
4 D3

3
3 4 E3

6
6

F2

1

2

3

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

其状态转移方程如下(一般形式)
s 2 ? T1 ( s 1 , u 1 ) s 3 ? T 2 ( s1 , u1 , s 2 , u 2 ) ?? s k ? 1 ? Tk ( s1 , u1 , s 2 , u 2 , ? , s k , u k )
状态转移方程是确定 过程由一个状态到另 一个状态的演变过程。 如果第k阶段状态变量 sk的值、该阶段的决策 变量一经确定,第k+1 阶段状态变量sk+1的值 也就确定。

图示如下:

s1

u1 1

s2

u2 2

s3

?

sk

uk k

sk+1

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

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

动态规划中能 处理的状态转移 方程的形式。

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

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

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

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

小结: 无后效性 动态规划本质上是多阶段决策过程;
概念 : 阶段变量k﹑状态变量sk﹑决策变量uk;

方程 :状态转移方程
指标:
(sk) ?

s k ?1 ? T k ( s k , u k )

V k , n ? V k , n ( s k , u k , s k ?1 , u k ?1 , ? , s n ?1 )

效益

f

k

?u k ,? ,u n ?

opt V

k ,n

( s k , u k , ? , s n ? 1)
可递推

V k , n ( s k , u k , s k ?1 , u k ?1 , ? , s n ?1 )

? ? k [ s k , u k , V k ? 1 , n ( s k ? 1 , u k ? 1 , ? , s n ? 1 )]

指标函数形式: 和、



解多阶段决策过程问题,求出
最优策略,即最优决策序列
{u , u ,? , u }
* 1 * 2 * n

最优轨线,即执行最优策略时的状态序列
{ s1 , s 2 , ? , s n }
* * *

f1(s1)

最优目标函数值
* V1, n

?

* V1, n

* ( s1

,

* u1

* * 从 k,到终点最优策略 ,? s n , u n ) 子策略的最优目标函数值

f

k

? s ? ? opt v
k

?u

k

,? ,

un?

k ,n

?s , u
k

k

,? ,

s

n?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 1 2 3

C1
C2 4 C3 3

1 D

3 1

3
2 A 4 B2 B1 1 2 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 1 2 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 1 2 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 1 2 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 ? x

2 2

? x3

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

max

z ? x1 ? x

2 2

? x3

? x1 ? x 2 ? x 3 ? 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 允许决策集合为: x3=s3 0≤x2≤s2 0≤x1≤s1 各阶段指标函数为:v1(x1)=x1 v2(x2)=x22 v3(x3)=x3, 各指标函数以乘积方式结合,最优指标函数fk(sk) 表示从第k阶段初始状态sk出发到第3阶段所得到的 最大值,则动态规划基本方程为:
? f k ( s k ) ? max [ v k ( x k ) ? f k ? 1 ( s k ? 1 )] ? xk ?D k ( sk ) ? ? f 4 (s4 ) ? 1 ? k ? 3 , 2 , ,1

用逆序解法由后向前依次求解:
k=3时,
f 3 ( s 3 ) ? max [ v 3 ( x 3 ) ? f 4 ( s 4 )] ? max ( x 3 ) ? s 3
x3 ? D3 ( s3 ) x3 ? s3

x3*=s3

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

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

dx

2 x2s2 ? 3x2 ? 0
2

2

解得:
d h2 dx
2 2 2

x2 ?

2 3

s2
d h2 dx
2 2 2

x2=0(舍)
x2 ? 2 3 ? ?2s2 ? 0

? 2s2 ? 6 x2
2 3

s2

所以

x2 ?

s2

是极大值点。
2 3 s2 )
2

f 2 (s2 ) ? (

(s2 ?

2 3

s2 ) ?

4 27

s

3 2

x ?
* 2

2 3

s2

k=1时,
f 1 ( s 1 ) ? max [ v 1 ( x 1 ) ? f 2 ( s 2 )] ? max ( x 1 ?
x1 ? D 1 ( s1 ) 0 ? x1 ? s 1

4 27

s ) ? max [ x 1 ?
3 2 0 ? x1 ? s 1

4 27

( s1 ? x1 ) ]
3


dh 1 dx 1 ?

h1 ( s 1 , x 1 ) ? x 1 ?

4 27
3

( s1 ? x1 )

3

4 27

( s1 ? x1 )
1 4

? x1

12 27

( s 1 ? x 1 ) ( ? 1) ? 0
2

解得:
d h1 dx
2

x1 ?
2

s1
12 27

x1=s1(舍)
( s1 ? x1 ) ?
2

2

2 1

?

12 27

( s 1 ? x 1 ) ( ? 1) ?

24 27

x1 ( s1 ? x1 ) ?

24 27

( s 1 ? x 1 )( 2 x 1 ? s 1 )

d h1 dx
2 1

x1 ?

1 4

?? s1

9 27

s1 ? 0

2

所以

x1 ?

1 4

s1

是极大值点。

f 1 ( s1 ) ?

1 4

s1 ?

( s1 ? s1 ) ? s 27 4 64
3

4

1

1

4 1

x

* 1

?

1 4

s1

由于s1未知,所以对s1再求极值,
0 ? s1 ? c

max f 1 ( s 1 ) ? max (
0 ? s1 ? c

1

显然s1=c时,f1(s1)取得最大值 1 4 f1 反向追踪得各阶段最优决策及最优值:( s 1 ) ? c 64 1 1 1 x ? s ? c s1=c f (s ) ? c
* 1 4

64

s1 )

4

4

1

4

1

1

64
3 2

s 2 ? s1 ? x ? c 4
* 1

3

x ?
* 2

2 3

s2 ?

1 2

c

f 2 (s2 ) ?

4 27

s ?

1 16

c

3

s3 ? s2 ? x ? c 4
* 2

1

x ? s3 ?
* 3

1 4

c
* 1

f 3 (s3 ) ? s3 ?
1 4 c, x ?
* 2

1 4

c
*

所以最优解为:

x ?

1 2

c, x ?
* 3

1 4

c, z ?

1 64

c

4

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

其动态规划基本方程为:
? f k ( s k ) ? max [ g k ( x k ) ? f k ? 1 ( s k ? 1 )] ? xk ?Dk ( sk ) ? ? f n ?1 ( s n ?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)也定义在 这些离散点上。动态规划基本方程可以写为:
? f k ( s k ) ? max [ g k ( p ? ) ? f k ? 1 ( s k ? p ? )] ? p ? 0 ,1 , 2 ? , q ? ? f n ?1 ( s n ?1 ) ? 0 ? k ? n , n ? 1, ? ,1

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

【例7-5】

max z ? x 1 ? x 2 ? x 3
2

3

? x1 ? x 2 ? x 3 ? 6 ? j ? 1, 2 , 3 ?x j ? 0

解 按变量个数将原问题分为三个阶段,阶段变量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阶段所得到的最大值,动态规划的基 本方程为:? f ( s ) ? max [ g ( x ) ? f ( s )] k ? 3, 2 ,1 ?
k k

? ? f 4 (s4 ) ? 1 ?

0? xk ? sk

k

k

k ?1

k ?1

k=3时,

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

3

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

表7-1 取值

k=2时, f ( s ) ? max 计算结果见表7-2
2 2

0? x2 ? s2

[ x 2 ? f 3 ( s 3 )] ? max [ x 2 ? f 3 ( s 2 ? x 2 )]
0? x2 ? s2

k=1时, 0? x ? s 其中s1=6,计算结果见表7-3所示。
1 1

f 1 ( s 1 ) ? max [ x 1 ? f 2 ( s 2 )] ? max [ x 1 ? f 2 ( s 1 ? x 1 )]
2 2 0 ? x1 ? s1

由表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 ? g 1 ( x 1 ) ? g 2 ( x 2 ) ? ? ? g n ( x n ) ? x1 ? x 2 ? ? ? x n ? a ? ? x i ? 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个使用者所得到的最大收益,则动态规划基本方程 为: k ? n , ? ,1 ? f k ( s k ) ? max [ g k ( x k ) ? f k ? 1 ( s k ? 1 )] ? 0? xk ? sk ? ? f n ?1 ( s n ?1 ) ? 0 ? 由后向前逐段递推,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 k ? 0? xk ? sk ? ? f 4 (s4 ) ? 0 ?
k k k ?1 k k

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

3

( x 3 )]

表7-5

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

3

( s 2 ? x 2 )]

表7-6

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

1

? x 1 )]

f 1 ( s 1 ) ? max [ g 1 ( x 1 ) ? f 2 ( 4 ? x 1 )]
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为:

s k ?1 ?

2 3

xk ?

9

10

(sk ? xk )

阶段指标函数: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 ? sk ? ? f5 (s5 ) ? 0 ?
k k k k ?1 k ?1

k=4时,

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

x 4*= s 4
k=3时,
f 3 ( s 3 ) ? max [10 x 3 ? 7 ( s 3 ? x 3 ) ? f 4 ( s 4 )]
0 ? x3 ? s3

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

2 9 ? ? ? max ?10 x 3 ? 7 ( s 3 ? x 3 ) ? 10 [ x 3 ? ( s 3 ? x 3 )] ? 0 ? x3 ? s3 3 10 ? ? ? max (
0 ? x3 ? s3

2 3

x 3 ? 16 s 3 )

?

50 3

s3

∴ x 3*= s 3

k=2时, f

2

( s 2 ) ? max [10 x 2 ? 7 ( s 2 ? x 2 ) ? f 3 ( s 3 )]
0? x2 ? s2

? max [10 x 2 ? 7 ( s 2 ? x 2 ) ?
0? x2 ? s2

50 3

s3 ]

50 2 9 ? ? ? max ?10 x 2 ? 7 ( s 2 ? x 2 ) ? [ x2 ? ( s 2 ? x 2 )] ? 0? x2 ? s2 3 3 10 ? ? ? max ( 22 s 2 ?
0? x2 ? s2

8 9

x2 )

? 22 s 2

∴ x2*=0

k=1时,

f 1 ( s 1 ) ? max [10 x 1 ? 7 ( s 1 ? x 1 ) ? f 2 ( s 2 )]
0 ? x1 ? s1

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

2 9 ? ? ? max ?10 x 1 ? 7 ( s 1 ? x 1 ) ? 22 [ x 1 ? ( s 1 ? x 1 )] ? 0 ? x1 ? s1 3 10 ? ? ? max (
0 ? x1 ? s1

134 5

s1 ?

32 15

x1 )

?

134 5

s1

∴ x1*=0

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

2 3 2 3
2 3

x ?
* 1

9 10 9 10
9

( s 1 ? x 1 ) ? 90
*

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

x ?
* 2

( s 2 ? x ) ? 81
* 2

x ?
* 3

10

( s 3 ? x ) ? 54
* 3

即,第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,xk还应 4 小于本期至4期需求之和减去本期的库存量 ? d j ? s k, j? 所以xk的上限为min( 4 ,6),故有:k

?d
j?k

j

? sk

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

?

4

d j ? s k ,6)}

j?k

阶段指标函数rk(sk,xk)表示第k期的生产费用与 存贮费用之和:
? 0.5 s k rk ( s k , x k ) ? ? ? 3 ? x k ? 0.5 s k xk ? 0 x k ? 1, 2, 3, 4, 5, 6

最优指标函数fk (sk )表示第k期库存为sk 到第4期 末的生产与存贮最低费用,动态规划基本方程为:
? f k ( s k ) ? m in [ rk ( s k , x k ) ? f k ? 1 ( s k ? 1 )] ? xk ? D k ( sk ) ? ? f 5 ( s5 ) ? 0 ? k ? 4, 3, 2,1

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

k=4时,

f 4 ( s4 ) ?

x4 ? D 4 ( s4 )

m in [ r4 ( s 4 , x 4 ) ? f 5 ( s 5 )] m in [ r4 ( s 4 , x 4 )]

?

x4 ? D 4 ( s4 )

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

k=3时,

f 3 ( s3 ) ?

x3 ? D 3 ( s3 )

m in [ r3 ( s 3 , x 3 ) ? f 4 ( s 4 )]
x3 ? D 3 ( s3 )

计算结果如下表:

?

m in [ r3 ( s 3 , x 3 ) ? f 4 ( s 3 ? x 3 ? 2 )]

k=2时,

f 2 ( s2 ) ?

x2 ? D 2 ( s2 )

m in [ r2 ( s 2 , x 2 ) ? f 3 ( s 3 )] m in [ r2 ( s 2 , x 2 ) ? f 3 ( s 2 ? x 2 ? 3)]

计算结果如下表

?

x2 ? D 2 ( s2 )

k=1时,

f 1 ( s1 ) ?

x1 ? D1 ( s1 )

m in [ r1 ( s1 , x1 ) ? f 2 ( s 2 )]
x1 ? D1 ( s1 )

?

m in [ r1 ( s1 , x1 ) ? f 2 ( s1 ? x1 ? 2 )]

计算结果见表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 ? sk ? 0 ? y k ? 600 ? ( s k ? x k ) ? ? f (s ) ? 0 ? 5 5 k ? 4 , 3 , 2 ,1

k=4时,
f 4 (s4 ) ?
0? x4 ? s4 0 ? y 4 ? 600 ? ( s 4 ? x 4 )

max

( 44 x 4 ? 42 y 4 ) ? 44 s 4

x4*=s4

y4*=0

k=3时,

f 3 (s3 ) ? ? ?

0 ? x3 ? s3 0 ? y 3 ? 600 ? ( s 3 ? x 3 )

max

[ 39 x 3 ? 40 y 3 ? f 4 ( s 4 )]

0 ? x3 ? s3 0 ? y 3 ? 600 ? ( s 3 ? x 3 )

max max

[ 39 x 3 ? 40 y 3 ? 44 ( s 3 ? y 3 ? x 3 )] ( 44 s 3 ? 5 x 3 ? 4 y 3 )

0 ? x3 ? s3 0 ? y 3 ? 600 ? ( s 3 ? x 3 )

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

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

max

z ? 44 s 3 ? 5 x 3 ? 4 y 3

? x3 ? s3 ? ? ? x 3 ? 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 (s2 ) ? ? ?

0? x2 ? s2 0 ? y 2 ? 600 ? ( s 2 ? x 2 )

max

[ 42 x 2 ? 38 y 2 ? f 3 ( s 3 )]

0? x2 ? s2 0 ? y 2 ? 600 ? ( s 2 ? x 2 )

max max

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

0? x2 ? s2 0 ? y 2 ? 600 ? ( s 2 ? x 2 )

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

? ?

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

max max

[ 45 x 1 ? 40 y 1 ? 42 ( s 1 ? y 1 ? x 1 ) ? 3600 ] ( 42 s 1 ? 3 x 1 ? 2 y 1 ? 3600 )

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

类似地求得: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 ? c 1 ( x 1 ) ? c 2 ( x 2 ) ? ? ? c n ( x n )
? a1 x1 ? a 2 x 2 ? ? ? a n x n ? a ? ? x i ? 0 且为整数 ( i ? 1, 2 , ? , n )

下面用动态规划方法求解: 按照装入物品的种类划分阶段,k=1,2,…,n; 状态变量sk表示装入第k种至第n种物品的总重量; 决策变量xk表示装入第k种物品的件数; 状态转移方程为:sk+1=sk-akxk 允许决策集合为: ? ? sk 其中 [

sk

D k ( s k ) ? ? x k 0 ? x k ? [ ], x k 为整数 ? ak ? ?

ak ak 阶段指标函数ck (xk )表示第k阶段装入第k种商品xk 件 时的价值; 最优指标函数fk (sk )表示第k阶段装入物品总重量为sk 时的最大价值,动态规划基本方程为:
? f k ( s k ) ? max [ c k ( x k ) ? f k ? 1 ( s k ? 1 )] sk ? x k ? 0 ,1 ,? ,[ ] ak ? ? f (s ) ? 0 ? n ?1 n ?1 k ? n , n ? 1, ? ,1

] 表示不超过

sk

的最大整数;

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

单位利润(元)

80

130

180

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

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

按前述方法建立动态规划模型; k=3时,

f 3 (s3 ) ?

max
s3 4 ]

(180 x 3 )

x 3 ? 0 ,1 ,? ,[

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

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

max
x 2 ? 0 ,1 ,? ,[ s2 3

[130 x 2 ? f 3 ( s 3 )]
]

max
x 2 ? 0 ,1 ,? ,[ s2 3

[130 x 2 ? f 3 ( s 2 ? 3 x 2 )]
]

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

k=1时,

f 1 ( s 1 ) ? max [ 80 x 1 ? f 2 ( s 2 )]
x 1 ? 0 ,1 , 2 , 3

? max [ 80 x 1 ? f 2 ( s 1 ? 2 x 1 )]
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 ? ? p i ( u i )
i ?1

? n ?? ciu i ? c ? i ?1 ? n ?? wiu i ? w ? i ?1 ? u ? 0 且为整数 i ? 1, 2 , ? , n i ? ?

按部件个数划分阶段,k=1,2,…,n; 决策变量uk表示部件k上的备用元件数; 状态变量xk表示从第k个到第n个部件的总费用, yk表示从第k个到第n个部件的总重量; 状态转移方程为: xk+1=xk-ckuk yk+1=yk-wkuk 允许决策集合为: ? xk yk

? D k ( x k , y k ) ? ? u k 0 ? u k ? min([ ], [ ]), 且 u k 为整数 ? ck wk ? ?

阶段指标函数为pk(uk),表示第k个部件的正常工作概率; 最优指标函数fk(xk,yk)表示由状态xk,yk出发,从部件k到部件 n的系统工作最大可靠性,则动态规划基本方程为:
? f k ( x k , y k ) ? max [ p k ( u k ) ? f k ? 1 ( x k ? 1 , y k ? 1 )] ? u k ?Dk ( xk , yk ) ? ? f n ?1 ( x n ?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
D k ( s k ) ? ? x k 0 ? x k ? [ ], 且 x k 为整数 ? ck ? ?

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

(1 ? p k )

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

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

x3 ? D 3 ( s3 )

max

[1 ? (1 ? p 3 ) (1 ? 0 . 4
x3

x3

]

x3 ? D 3 ( s3 )

max

)

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

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

x2 ?D2 ( s2 )

?[1 ? (1 ?

p2 )
x2

x2

] ? f3 (s3 )

? ?

x2 ?D2 ( s2 )

?(1 ? 0 . 2

) ? f3 (s2 ? 3x2 )

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

k=1时, f

( s1 ) ? 1 ?

x1 ? D 1 ( s1 )

max

?[1 ? (1 ? ?(1 ? 0 . 3

p1 )
x1

x1

] ? f 2 (s2 )

? ?

x1 ? D 1 ( s1 )

max

) ? f 2 ( s1 ? 2 x1 )

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

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


相关文章:
运筹学7动态规划.ppt
运筹学7动态规划_数学_自然科学_专业资料。运筹学7动态规划 第七 章动态规划 主要内容: §7.1 多阶段...
运筹学(二)动态规划(1-2014)_图文.ppt
运筹学(二)动态规划(1-2014) - 运筹学(二) 动态规划 动态规划 ? 动态规划运筹学的一个分支...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 资源分配问题 生产计划...
运筹学动态规划习题_图文.ppt
运筹学动态规划习题 - 习题三 一、某工厂购进100台机器,准备生产A、B 两种
运筹学-第3版-课件-动态规划例题_图文.ppt
运筹学-第3版-课件-动态规划例题 - 8.1 用动态规划方法求整数规划模型,而
运筹学74动态规划应用举例.ppt
运筹学74动态规划应用举例_金融/投资_经管营销_专业资料。第七章 动态规划 ?
运筹学第八章 动态规划_图文.ppt
运筹学第八章 动态规划 - 第八章 动态规划 8.1 8.2 8.3 8.4 动态规划的研究对象和特点 动态规划的基...
运筹学-第3版-课件-第5章 动态规划_图文.ppt
第5章 动态规划 运筹帷幄之中 Dynamic Programming 决胜千里之外第 1页 综 述 动态规划运筹学的一个...
运筹学---动态规划_图文.ppt
运筹学---动态规划 - 这是关于运筹学里的动态规划的课件ppt... 运筹学---动态规划_理学_高等教育_教育专区。这是关于运筹学里的动态规划的课件ppt 动态...
运筹学课件(动态规划)_图文.ppt
运筹学课件(动态规划) - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化...
运筹学-动态规划_图文.ppt
运筹学-动态规划 - Page:1 运动 态筹 规 划学 华东理工大学 工商经济
运筹学-动态规划-13,14_图文.ppt
运筹学-动态规划-13,14 - 第五章 动态规划 ? §5.1 动态规划的基本
运筹学13-动态规划I-12-1_图文.ppt
运筹学13-动态规划I-12-1 - 第13讲 动态规划I 本讲提纲 1. 多阶段决策问题 2. 动态规划的基本概念与最优性原理 3. 动态规划模型的建立 School of Busine...
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
动态规划--运筹学课程设计_图文.doc
动态规划--运筹学课程设计 - 湖南农业大学 综合设计报告 综合设计五 动态规划算法 学生姓名:曾俊扬学号:200840204219 年级专业:2008 级信息...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 (Dynamic programming) 背包问
运筹学第五章_动态规划1_图文.ppt
运筹学第五章_动态规划1 - 第五章 动态规划 动态规划简介 动态规划所解决的问题:多阶段问题 动态规划的核心。 核心: 在于将问题公式化,也可以说,动态规划是将...
运筹学 07 动态规划_图文.ppt
运筹学 07 动态规划 - 1 多阶段决策过程的最优化 ? 概述 ? 多阶段决策过程及其最优化 ? 多阶段决策过程举例 ? 动态规划求解的多阶段决策问题的特点 ? 动态...
运筹学教程课件五 动态规划_图文.ppt
运筹学教程课件五 动态规划 - 第五章 动态规划 不要过河拆桥 1 动态规划 D
运筹学_动态规划分析_图文.ppt
运筹学_动态规划分析 - ? ? 非线性规划问题 决策变量连续的动态规划问题 乘积形式的目标函数 随机型动态规划 ? ? 非线性规划问题 ? 应用动态规划求解问题 2 2...
更多相关文章: