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

运筹学-动态规划


动 态 规 划
(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、阶段: 把一个问题的过程,恰当地分为若干个相互联系的 阶段,以便于按一定的次序去求解。

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

变量称为状态变量。 状态变量的取值有一定的允许集合或范围,此集合 称为状态允许集合。

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

描述决策的变量,称为决策变量。决策变量是状态 变量的函数。可用一个数、一组数或一向量(多维情 形)来描述。 在实际问题中决策变量的取值往往在某一范围之内, 此范围称为允许决策集合。 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、策略:是一个按顺序排列的决策组成的集合。在 实际问题中,可供选择的策略有一定的范围,称为允 许策略集合。从允许策略集合中找出达到最优效果的 策略称为最优策略。
6、状态转移方程:是确定过程由一个状态到另一 个状态的演变过程,描述了状态转移规律。 7、指标函数和最优值函数:用来衡量所实现过程优 劣的一种数量指标,为指标函数。指标函数的最优值, 称为最优值函数。在不同的问题中,指标函数的含义 是不同的,它可能是距离、利润、成本、产量或资源 消耗等。 动态规划模型的指标函数,应具有可分离性,并满 足递推关系。

小结: 无后效性 动态规划本质上是多阶段决策过程;
概念 : 阶段变量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、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一 步,在确定多阶段特性后,按时间或空间先后顺序, 将过程划分为若干相互联系的阶段。对于静态问题要 人为地赋予“时间”概念,以便划分阶段。

2、正确选择状态变量

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

4、确定状态转移方程
根据k 阶段状态变量和决策变量,写出k+1阶段状态变 量,状态转移方程应当具有递推关系。

5、确定阶段指标函数和最优指标函数,建立动态规 划基本方程
阶段指标函数是指第k 阶段的收益,最优指标函数 是指从第k 阶段状态出发到第n 阶段末所获得收益的最 优值,最后写出动态规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。由于 动态规划模型与线性规划模型不同,动态规划模型没有统 一的模式,建模时必须根据具体问题具体分析,只有通过 不断实践总结,才能较好掌握建模方法与技巧。

二、最短路径问题
例一、从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 。
显然有 f1 (C1 ) = 1 ; f1(C2 ) = 3 ; f1 (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 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (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 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (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 有二条路线。
f3(A)1 = d(A, B1 )+ f2 ( B1 ) =2+4=6 f3 (A)2 = d(A, B2 )+ f2 ( B2 ) =4+3=7 ∴ f3 (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

练习1: 求从A到G的最短路径
1 5 A 3 B2 C1 6 8 5 D2 3 8 4 D3 3 3 E3 1 D1 2 2 E1 5 6

B1
6 8 7

3

C2

3
3

3 5 2 6 F2 F1 4 G

2

E2

6

C3

3

C4

最优路线为:A → B1 → C2 → D1 → E2 → F2 → G

路长=18

C1 6 2 E1 3 1 D1 8 k=6 , F1 G f6(F1)=4 B1 3 5 F1 4 5 2 C2 3 6 A 5 5 1 G F2 G ,f6(F2)=3 E2 D2 3 2 2 B2 87 C3 3 6 F2 3 3 D3 3 E3 6 6 C4 8 3 k=5,出发点E1、E2、E3 4

3? 4 ?d5 ?E1 , F1 ? ? f 6 ?F1 ? ? f 5( E1) ? min ?d 5 ?E , F ? ? f ?F ? ? ? min{ } ? 7 5?3 1 2 6 2 ? ?

u5(E1)=F1
E1 F1 G

? d5 ?E2 , F1 ? ? f 6 ?F1 ? f5 ?E 2? ? min ? ?d5 ?E2 , F2 ? ? f 6 ?F2 ?
? d5 ?E3 , F1 ? ? f 6 ?F1 ? f 5 ?E3? ? min ? ?d5 ?E3 , F2 ? ? f 6 ?F2 ?

5? 4 ? ? ? min{ } ? 5 2?3 ?
6?4 ? }?9 ? ? min{ 6?3 ?

u5(E2)=F2
E2 F2 G

u5(E3)=F2
E3 F2 G

k=4, f4(D1)=7 u4(D1)=E2

k=3,

f3(C1)=13 u3(C1)=D1

f4(D2)=6 u4(D2)=E2 f4(D3)=8 u4(D3)=E2
k=2, f2(B1)=13 u2(B1)=C2

f3(C2)=10 u3(C2)=D1
f3(C3)=9 u3(C3)=D1

f3(C4)=12 u3(C4)=D3

f2(B2)=16 u2(B2)=C3
k=1,

f1(A)= min

d1(A,B1)+ f2(B1)
d1(A,B2)+ f2(B2)

= min

5+13

3+16

=18

u1(A)=B1

u2(B1)=C2

u3(C2)=D1

u4(D1)=E2

u1(A)=B1
E1 F1 G

u2(B1)=C2
E2 F2 G

u3(C2)=D1

u4(D1)=E2 u5(E2)=F2

u5(E1)=F1 u5(E2)=F2

u5(E3)=F2
E3 F2 G

7
1 5 A 3 B2 B1 6 3

5
C1 C2 3 6

9
8
5 D2 3 D3 1 2

u6(F2)=G
E1

D1

2 2

最优策略
5 6 3 5 F1 3 F2 4 G

8
7 6 C3

3
3

E2

2
6

8 4
C4

3

E3

练习2: 求从A到E的最短路径
B1
2

12
14 10

10

C1
9

3

D1
6

5 2

A

5
1

B2 B3

6

4 13

C2
8

5

E

12 11

D2
10

C3

路线为A→B2→C1 →D1 →E ,最短路径为19

三、投资分配问题
现有数量为a(万元)的资金,计划分配给n 个工厂, 用于扩大再生产。 假设:xi 为分配给第i 个工厂的资金数量(万元) ; gi(xi)为第i 个工厂得到资金后提供的利润值(万元)。 问题是如何确定各工厂的资金数,使得总的利润为 最大。 n 据此,有下式: m ax Z ? g (x )

?
i ?1

i

i

? n ?? xi ? a ? i ?1 ? x ? 0 i ? 1 .2 . ? . n ? i

令:fk(x) = 以数量为x 的资金分配给前k 个工厂,所 得到的最大利润值。 用动态规划求解,就是求 fn(a) 的问题。 当 k=1 时, f1(x) = g1(x) (因为只给一个工厂)

当1<k≤n 时,其递推关系如下: 设:y 为分给第k 个工厂的资金(其中 0≤y ≤ x ),此时 还剩 x - y(万元)的资金需要分配给前 k-1 个工厂,如 果采取最优策略,则得到的最大利润为fk-1(x-y) ,因此 总的利润为:

gk(y) + fk-1(x-y)

所以,根据动态规划的最优化原理,有下式:

f k ( x ) ? max?g k ( y ) ? f k ?1 ( x ? y )?
0? y ? x

其 中k ? 2.3.?.n
如果a 是以万元为资金分配单位,则式中的y 只取 非负整数0,1,2,…,x。上式可变为:

f k ( x) ?

? gk ( y) ? y ? 0 ,1, 2 ,?, x
max

f k ?1 ( x ? y )?

例题:
设国家拨给60万元投资,供四个工厂扩建使用,每 个工厂扩建后的利润与投资额的大小有关,投资后的 利润函数如下表所示。
投资 利润

0

10

20

30

40

50

60

g1(x) g2(x) g3(x) g4(x)

0 0 0 0

20 20 25 25

50 40 60 40

65 50 85 50

80 55 100 60

85 60 110 65

85 65 115 70

解:依据题意,是要求 f4(60) 。

按顺序解法计算。 第一阶段:求 f1(x)。显然有 f1(x) = g1(x),得到下表
投资

0 0 0

10 20 10

20 50 20

30 65 30

40 80 40

50 85 50

60 85 60

利润

f1(x) = g1(x)

最优策略

第二阶段:求 f2(x)。此时需考虑第一、第二个工厂如 何进行投资分配,以取得最大的总利润。
f 2 (60) ?

? g2 ( y ) ? y ? 0 ,10 ,?, 60
max

f1 (60 ? y )?

? g 2 (0) ? f1 (60) ? ?0 ? 85 ? ? g (10) ? f (50) ? ?20 ? 85? 1 ? 2 ? ? ? ? g 2 (20) ? f1 (40)? ?40 ? 80? ? ? ? ? ? max? g 2 (30) ? f1 (30) ? ? max?50 ? 65? ? 120 ? g (40) ? f (20)? ?55 ? 50? 1 ? 2 ? ? ? ? g 2 (50) ? f1 (10) ? ?60 ? 20? ? ? ?65 ? 0 ? ? ? ? g 2 (60) ? f1 (0) ?
最优策略为(40,20),此时最大利润为120万元。 同理可求得其它 f2(x) 的值。

f 2 (50) ?

? g2 ( y) ? y ? 0 ,10 ,?, 50
max

f1 (50 ? y )?

? g 2 (0) ? f1 (50) ? ? g (10) ? f ( 40) ? 1 ? 2 ? ? ? g 2 ( 20) ? f1 (30) ? ? ?? ? ? 105 ? g 2 (30) ? f1 ( 20) ? ? g 2 ( 40) ? f1 (10) ? ? ? ? ? g 2 (50) ? f1 (0) ? ?
最优策略为(30,20),此时最大利润为105万元。

f 2 ( 40) ?

? g2 ( y) ? y ? 0 ,10 ,?, 40
max

f1 ( 40 ? y )?

? 90
最优策略为(20,20),此时最大利润为90万元。

f 2 (30) ?

? g2 ( y) ? y ? 0 ,10 , 20 , 30
max

f1 (30 ? y )?

? 70
最优策略为(20,10),此时最大利润为70万元。

f 2 ( 20) ? max ?g 2 ( y ) ? f1 ( 20 ? y )?
y ? 0 ,10 , 20

? 50
最优策略为(20,0),此时最大利润为50万元。

f 2 (10) ? max?g 2 ( y ) ? f1 (10 ? y )?
y ? 0 ,10 ,

? 20 最优策略为(10,0)或( 0 , 10 ) ,此时最大利润 为20万元。
f2(0) =0。最优策略为(0,0),最大利润为0万元。 得到下表

投资 利润

0 0

10 20

20 50

30 70

40 90

50 105

60 120

f2(x) 最优策略

(0,0) (10,0) (20,0) (20,10) (20,20) (30,20) (40,20) (0,10)

第三阶段:求 f3(x)。此时需考虑第一、第二及第三个 工厂如何进行投资分配,以取得最大的总利润。
f 3 (60) ?

? g3 ( y ) ? y ? 0 ,10 ,?, 60
max

f 2 (60 ? y )?

? g3 (0) ? f 2 (60) ? ?0 ? 120 ? ? g (10) ? f (50) ? ?25 ? 105? 2 ? 3 ? ? ? ? g3 (20) ? f 2 (40)? ?60 ? 90 ? ? ? ? ? ? max? g3 (30) ? f 2 (30) ? ? max?85 ? 70 ? ? 155 ? g (40) ? f (20)? ?100? 50? 2 ? 3 ? ? ? ? g3 (50) ? f 2 (10) ? ?110? 20? ? ? ?115? 0 ? ? ? ? g3 (60) ? f 2 (0) ?
最优策略为(20,10,30),最大利润为155万元。

同理可求得其它 f3(x) 的值。得到下表

投资 利润

0 0

10 25

20 60

30 85

40 110

50 135

60 155

f3(x)

最优 (0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30) 策略

第四阶段:求 f4(60)。即问题的最优策略。
f 4 (60) ?

? g4 ( y ) ? y ? 0 ,10 ,?, 60
max

f 3 (60 ? y )?

? g 4 (0) ? f 3 (60) ? ?0 ? 155 ? ? g (10) ? f (50) ? ?25 ? 135? 3 ? 4 ? ? ? ? g 4 (20) ? f 3 (40)? ?40 ? 110? ? ? ? ? ? max? g 4 (30) ? f 3 (30) ? ? max?50 ? 85 ? ? 160 ? g (40) ? f (20)? ?60 ? 60 ? 3 ? 4 ? ? ? ? g 4 (50) ? f 3 (10) ? ?65 ? 25 ? ? ? ?70 ? 0 ? ? ? ? g 4 (60) ? f 3 (0) ?
最优策略为(20,0,30,10),最大利润为160万元。

练习:
求投资分配问题得最优策略,其中a=50 万元,其余 资料如表所示。
投资 利润

0 0 0

10 21 15

20 40 36

30 52 50

40 80 73

50 85 100

g1(x) g2(x)

g3(x)

0

25

60

65

68

70

例:某公司打算在3个不同的地区设置4个销售点, 根据市场部门估计,在不同地区设置不同数量的销 售点每月可得到的利润如表所示。试问在各地区如 何设置销售点可使每月总利润最大。
地 区 1 2 3 销售点 0 0 0 0 1 16 12 10 2 25 17 14 3 30 21 16 4 32 22 17

x1=2,x2=1,x3=1,f3(4)=47

四、背包问题
有一个徒步旅行者,其可携带物品重量的限度为a 公 斤,设有n 种物品可供他选择装入包中。已知每种物品 的重量及使用价值(作用),问此人应如何选择携带 的物品(各几件),使所起作用(使用价值)最大?
物品 重量(公斤/件) 每件使用价值

1
a1

2
a2




j
aj




n
an

c1

c2



cj



cn

这就是背包问题。类似的还有工厂里的下料问题、 运输中的货物装载问题、人造卫星内的物品装载问题 等。

设xj 为第j 种物品的装件数(非负整数)则问题的数学 n 模型如下:

maxZ ? ? c j x j
j ?1

?n ?? a j x j ? a ? j?i ? x ? 0且为整数 ( j ? 1.2.? .n) ? j
用动态规划方法求解,令

fk(y) = 总重量不超过 y 公斤,包中只装有前k 种物品 时的最大使用价值。
其中y ≥0, k =1,2, …, n 。所以问题就是求 fn(a)

其递推关系式为:
y 0? x k ? ak

f k ( y ) ? m ax ?ck x k ? f k ?1 ( y ? a k x k )?

其中 2 ? k ? n
当 k=1 时,有:

? y? f1 ( y ) ? c1 ? ?a ? ? , ? 1?

? ? y ?? ? x1 ? ? ?a ? ?? ? 1 ?? ?

? y? y ? 其中? ? a ?表示不超过 a 的最大整数 1 ? 1?

例题:求下面背包问题的最优解

m axZ ? 8 x1 ? 5 x 2 ? 12 x 3 ? 3 x1 ? 2 x 2 ? 5 x 3 ? 5 ? ? x1 , x 2 , x 3 ? 0且为整数
解:a=5 ,问题是求 f3(5)

1 重量(公斤) 3 使用价值 8
物品

2 2 5

3 5 12

f 3 (5) ? m ax ? 12x 3 ? f 2 (5 ? 5 x 3 )?
5 0? x 3 ? a3 x 3整 数

f 3 ( 5) ? m ax ? 12 x 3 ? f 2 ( 5 ? 5 x 3 )?
0? x 3 ?

=m ax? 12 x 3 ? f 2 ( 5 ? 5 x 3 )?
0? x 3 ?

5 a3 x 3整 数

? 12x 3 ? f 2 (5 ? 5 x 3 )? =m ax
x3 = 0, 1

5 5 x 3整 数

? ? =m ax?0 ? f 2 ( 5), 12 ? f 2 ( 0)? ( x 3 ?1 ) ? ( x3 ? 0 ) ?

f 2 (5) ? m ax ? 5 x 2 ? f 1 (5 ? 2 x 2 )? =m ax? 5 x 2 ? f 1 (5 ? 2 x 2 )? = m ax? 5 x 2 ? f 1 (5 ? 2 x 2 )?
x2 =0, 1, 2 5 0? x 2 ? 2 x 2整 数 5 0? x 2 ? a2 x 2整 数

? ? =m ax?0 ? f 1 (5), 5 ? f 1 ( 3), 10 ? f 1 (1) ? ( x 2 ?1 ) ( x2 ? 2) ? ( x2 ? 0 ) ?

f 2 (0) ? m ax ? 5 x 2 ? f 1 (0 ? 2 x 2 )? =m ax? 5 x 2 ? f1 (0 ? 2 x 2 )? =m ax? 5 x 2 ? f1 (0 ? 2 x 2 )?
x2 =0 0 0? x 2 ? 2 x 2整 数 0 0? x 2 ? a2 x 2整 数

? ? =m ax?0 ? f1 (0) ? ? f1 (0) ? ( x2 ? 0 ) ?

? ? ? f 2 (5) ? max?0 ? f1 (5), 5 ? f1 ( 3), 10 ? f1 (1) ? ( x 2 ?1 ) ( x2 ? 2 ) ? ( x2 ? 0 ) ? ? max?8, 5 ? 8, 10? ? 13 ( x1 ? 1, x2 ? 1)

5 f1 (5) ? c1 x1 ? 8 ? ? 8 3 3 f1 ( 3) ? c1 x1 ? 8 ? ? 8 3 1 f1 (1) ? c1 x1 ? 8 ? ? 0 3 0 f1 (0) ? c1 x1 ? 8 ? ? 0 3

( x1 ? 1) ( x1 ? 1) ( x1 ? 0) ( x1 ? 0)

? ? f 2 ( 0) =max?0 ? f1 (0) ? ? f1 (0) ? 0 ( x1 ? 0, x2 ? 0) ? ( x2 ? 0 ) ?

? ? ? f 3 ( 5) =m ax?0 ? f 2 ( 5), 12 ? f 2 ( 0)? ( x 3 ?1 ) ? ( x3 ? 0 ) ? ? 0 ? 13, 12 ? 0 ? ? m ax ? 13 ( x1 ? 1, x 2 ? 1, x 3 ? 0)
所以,最优解为 X=(1 . 1 . 0),最优值为 Z = 13。

练习1:某厂生产三种产品,各种产品重量与利 润的关系如表所示。现将此三种产品运往市场出售, 运输能力总重量不超过 6 吨,问如何安排运输,使 总利润最大?
种类

1

2

3

重量(吨/公斤)
单件利润(元)

2

3

4

80 130 180

最优方案:X1 =(0.2.0)X2 =(1.0.1)Z=260

练习2:求下列问题的最优解

m axZ ? 4 x1 ? 5 x 2 ? 6 x 3 ? 3 x1 ? 4 x 2 ? 5 x 3 ? 10 ? ? x1 , x 2 , x 3 ? 0且为整数
X=(2. 1. 0) 最优值为 Z = 13

五、排序问题
排序问题指n 种零件经过不同设备加工是的顺序问题。 其目的是使加工周期为最短。 1、n × 1 排序问题

即n 种零件经过1 种设备进行加工,如何安排?

例一、
零件代号 加工时间(t) 交货日期(d)

j1

j2

j3

j4

j5

3 23

7 20

1 8

5 6

4 14

(1)平均通过设备的时间最小
按零件加工时间非负次序排列顺序,其时间最小。(即 将加工时间由小到大排列即可)
零件加工顺序 工序时间 实际通过时间 交货时间
j3
j1

j5

j4

j2

1 1 8

3 4 23

4 8 14

5 13 6

7 20 20

平均通过时间

1 x ? ( 20 ? 13 ? 8 ? 4 ? 1) ? 9.2 5

延迟时间 = 13 – 6 = 7
(2)按时交货排列顺序
零件加工顺序 工序时间 实际通过时间
j4

j3

j5

j2

j1

5 5

1 6

4 10

7 17

3 20

交货时间

6

8

14

20

23

延迟时间 = 0

1 平均通过时间 x ? ( 20 ? 17 ? 10 ? 6 ? 5) ? 11.6 5

(3)既满足交货时间,又使平均通过时间最小
零件加工顺序 工序时间 实际通过时间 交货时间
j3
j4
j1

j5

j2

1 1 8

5 6 6

3 9 23

4 13 14

7 20 20

延迟时间 = 0 平均通过时间

1 x ? ( 20 ? 13 ? 9 ? 6 ? 1) ? 9.8 5

2、n × 2 排序问题
即n 种零件经过2 种设备进行加工,如何安排?

例二、
设备 A 零件

j1
6

j2
8

j3
7

j4
3

j5
5

B
A B

3

2

5

9

4

T

经变换为
设备 A B 零件

j4
3 9

j3
7 5

j5
5 4

j1
6 3

j2
8 2

加工周期 T = 3+7+5+6+8+2 = 31 即? t Ai ? t B小 加工顺序图如下:
A B
j4
3

j3
7 +2 9

j5
5 +2 5

j1
6 4 3

j2
8 -5 2

T

3、n × 3 排序问题
即n 种零件经过 3 种设备进行加工,如何安排?

例三、

j1 j2 j3 j4 j5

A 10 7 8 6 6

B 3 5 6 4 5

C 9 3 4 3 8

A B C T

变换

j1 j2 j3 j4 j5

A+B 10+3 7+5 8+6 6+4 6+5

B+C 3+9 5+3 6+4 4+3 5+8

排序

j5

j1
j3

j2 j4

A+B 6+5 10+3 8+6 7+5 6+4
A 6 10 8 7 6 B 5 3 6 5 4

B+C 5+8 3+9 6+4 5+3 4+3
C 8 9 4 3 3

复原
j5

j1 j3 j2 j4

计算

T = 6+10+8+7+6+4+3 = 44

计算依据:

m int Ai ? m axt Bi 即可按下式计算



m int C i ? m axt Bi ? t B ? t C 或 ? t ci ? t B ? t A

?t

Ai

练习:
j1 j2 j3 j4
j2
j1
A 6 7 9 5 B 4 2 7 8 C 7 8 10 11

j4

j3

T=45


相关文章:
运筹学动态规划_图文.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) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化...
更多相关文章: