当前位置:首页 >> 经济学 >>

运筹学-动态规划


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

描述阶段的变量称为阶段变量。阶段的划分,一般 是根据时间和空间的自然特征来进行的,但要便于问题 一个数、 年、月、 转化为多阶段决策。 一组数、
路段 一个向 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 ( s k ) ? opt V k ,n ( s k , u k ,?, s n ?1)
?u k ,?,u n?
Vk ,n ( sk , uk , sk ?1 , uk ?1 ,?, sn ?1 )
可递推

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

解多阶段决策过程问题,求出
最优策略,即最优决策序列

{u , u ,? , u }
最优轨线,即执行最优策略时的状态序列
* * * { s1 , s2 , ? , sn }

* 1

* 2

* n

f1(s1)

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

子策略的最优目标函数值

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

?u

k

,?,

un ?

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 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 。
显然有 f1 (C1 ) = 1 ; f1(C2 ) = 3 ; f1 (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 ) + 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 1 2 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 1 2 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 C2 2 2 D2 3 8 4 D3 3 3 E3 1 5

B1
6 8 7

3

3
5 3

D1

E1

3 5 F1 4 G

2

E2 6

2 6 F2

3

6

C3

C4

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

路长=18

C1 6 1 D1 2 E1 3 8 k=6, F1 G f6(F1)=4 B1 3 5 F1 4 5 2 C2 3 6 A 5 D2 1 E25 G F2 G ,f6(F2)=3 3 2 2 B2 87 C3 3 3 E36 F2 3 3 D3 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{5 ? 3} ? 7 1 2 6 2 ? ?

u5(E1)=F1
E1 F1 G

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

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

u5(E2)=F2
E2 F2 G

u5(E3)=F2
E3 F2 G

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

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)

5+13

= min

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 5 6

9
8 D1
1 2 3 D3 2 2 5 E2 6 D2

u6(F2)=G
最优策略
E1
3 5 F1 3 F2 4 G

8
7 6 C3

3
3

2
6

8 4
C4

3

E3

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

12
14 10

C1
9

3

D1
6

5 2

A

5
1

B2 B3

6

C2
8

4 13

5 12 11

E

D2
10

C3

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

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

?g k ( 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 ) ?

?g 2 ( 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 ) ?

?g 2 ( 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 ) ?

?g 2 ( y ) ? y ? 0 ,10,?, 40
max

f1 ( 40 ? y )?

? 90

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

?g 2 ( y ) ? y ? 0 ,10, 20, 30
max

f1 (30 ? y )?

? 70

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

f 2 ( 20 ) ? max ? 50

?g 2 ( y ) ? y ? 0 ,10, 20

f1 ( 20 ? y )?

最优策略为(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 ) ?

?g 4 ( 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 模型如下:

max Z ? ? 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 ) ? max ?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 ? a1 ? 1?

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

max Z ? 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) ? max
0? x 3 ?

? 12 x 3 ? 5

f 2 ( 5 ? 5 x 3 )?

a3 x 3整 数

f 3 ( 5) ? max
0? x 3 ?

? 12 x 3 ? 5

f 2 ( 5 ? 5 x 3 )?

=max ? 12 x 3 ? f 2 ( 5 ? 5 x 3 )? =max ? 12 x 3 ? f 2 ( 5 ? 5 x 3 )?
x 3 0, = 1 5 0? x 3 ? 5 x 3整 数

a3 x 3整 数

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

f 2 (5) ? max ? 5 x 2 ? f1 (5 ? 2 x 2 )?
0? x 2 ?

=max ? 5 x 2 ? f 1 (5 ? 2 x 2 )?
0? x 2 ?

5 a2 x 2整 数

= max ? 5 x 2 ? f 1 (5 ? 2 x 2 )?
x 2 0,, 2 = 1

5 2 x 2整 数

? ? =max ?0 ? f1 (5), 5 ? f 1 ( 3), 10 ? f 1 (1) ? ( x 2 ?1 ) ( x2 ? 2) ? ( x2 ? 0 ) ?

f 2 (0) ? max ? 5 x 2 ? f1 (0 ? 2 x 2 )?
0? x 2 ?

=max ? 5 x 2 ? f1 (0 ? 2 x 2 )?
0? x 2 ?

0 a2 x 2整 数

=max ? 5 x 2 ? f1 (0 ? 2 x 2 )?
x2 0 =

0 2 x 2整 数

? ? =max ?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, x 2 ? 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, x 2 ? 0) = ? ( x2 ? 0 ) ?

? ? ? f 3 ( 5) max ?0 ? f 2 ( 5), 12 ? f 2 ( 0)? = ( x 3 ?1 ) ? ( x3 ? 0 ) ? ? max ? 0 ? 13, 12 ? 0 ? ? 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:求下列问题的最优解

max Z ? 4 x1 ? 5 x 2 ? 6 x 3 ? 3 x1 ? 4 x 2 ? 5 x 3 ? 10 ? ? x1 , x 2 , x 3 ? 0且为整数
最优值为 Z = 13

X=(2. 1. 0)

五、排序问题
排序问题指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
9

j4
3

j3
7 +2

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

计算依据:

min t Ai ? max t Bi 即可按下式计算



min tC i ? max t 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


赞助商链接
相关文章:
9-《运筹学》-第九章
9-《运筹学》-第九章 - 第九章 第九章 动态规划应用举例 §1 资源分配问题与背包问题 1. 一维分配问题 问题:一种数量为 a 的资源,分配给 n 个用户。若...
更多相关文章: