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

第六章(上课) 运筹学动态规划04修改


(Dynamic programming)

1

主要内容
一、多阶段决策问题

二、动态规划的基本概念
三、动态规划的基本思想 四、动态规划递推求解方法 五、动态规划的最优性原理 六、动态规划问题应用举例

2

概述
? 1951年Bellman提出,1957《动态规划》

动态规划是解决多阶段决策问题的一种数学方法。 动态规划思想:把多阶段决策问题变换为一系列互相联系的 单阶段问题,然后逐个加以解决。即:把一个n 维决策问题 变换为几个一维最优化问题,从而一个一个地去解决。 需指出:动态规划是求解某类问题的一种方法,是考察问题 的一种途径,而不是一种算法。必须对具体问题进行具体分 析,运用动态规划的原理和方法,建立相应的模型,然后再 用动态规划求解方法去求解。 应用:最短路线、资源分配、生产调度问题
3

一、多阶段决策问题
? 多阶段决策过程

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

1

2

?

状态n

决策n

n
4

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

5

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

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

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

7

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

18
G

3
4 D3

3
3 4 E3

6

6

F2

5

6

8

二、动态规划的基本概念
? (1)阶段 ? (2)状态

? (3)决策
? (4)策略

? (5)状态转移方程
? (6)指标函数和最优值函数

9

例一、从A 地到E地要铺设一条煤气管道,其中需经过三 级中间站,两点之间的连线上的数字表示距离,如图 所示。问应该选择什么路线,使总距离最短?
B1 2 A 1 5 10 6 B2 4 13 B3 12 11 10 C2 5 8 C3 10 D2 2 12 14 C1 9 6 E 3 D1 5

(1)阶段
把一个问题的过程,恰当地分为若干个相互联 系的阶段,以便于按一定的次序去求解。
描述阶段的变量称为阶段变量(k)。k=1,2 ,3, …,n

阶段的划分,一般是根据时间和空间的自然特征来 进行的,但要便于问题转化为多阶段决策。

11

例1分为四阶段,k=1,2,3,4.
B1 2 A 1 5 12 14
1 C

3 9
1 D

10 6 2 10 B 4 13 12 3 B 11

2 C

6 5 8
2 D

5 E 2

3 10 C

I

II

III

IV

(2)状态
表示每个阶段开始所处的自然状况或客观条件。 通常一个阶段有若干个状态,描述过程状态的变量 称为状态变量sk (表示第k阶段的状态变量 )。
状态变量的取值有一定的允许集合或范围,此集合 称为可达状态集合S K ={s1,s2, …, s k ,…}。

13

?令

sk

为k阶段初所处的位置。
B1 2 A 1 5 10 6 B2 10 4 13 B3 12 11 C2 5 8 C3 10 D2 2 12 14 C1 9 6 E 3 D1 5

S1 ? ? A?

S2 ? ?B1, B2 , B3?
S3 ? ?C1, C2 , C3?
S4 ? ?D1, D2?

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

? (3)令决策变量sk为处于某阶段某状态

(位置)时,选择下一个状态(位置)。
12 14 6 B2 10 4 1 13 B3 12 11 C2 5 8 C3 10 D2 2

D2 ( B1 ) ? ?C1 , C2 , C3 ?

D1 ( A) ? ?B1, B2 , B3?
B1 2 A 5 10

C1 9 6

3 D1 5 E

D2 ( B2 ) ? ?C1 , C2 , C3 ?

D3 (C1 ) ? ?D1 , D2 ?

D2 ( B3 ) ? ?C1 , C2 , C3 ?

D3 (C2 ) ? ?D1 , D2 ? D3 (C3 ) ? ?D1 , D2 ?

D4 (D1 ) ? ?E?

D4 (D2 ) ? ?E?

(4)策略
相互连接的决策序列称为一个策略。 从第k阶段开始到第n阶段结束称为一个子策略 Pk,n(k>1)

从第1阶段开始到第n阶段结束称为全策略

P 1, n

所有策略当中有最优值的策略称为最优策略。
17

(5)状态转移方程
? 状态转移方程:确定过程由一个状态到另一个状 态的演变过程,描述了状态转移规律。

Tk为状态转移函数

18

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

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

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

无后效性(马尔科夫性)
? 如果某阶段状态给定后,则在这个阶段以后过程的发展不受这个阶段以 前各段状态的影响;

? 过程的过去历史只能通过当前的状态去影响它未来的发展;
? 构造动态规划模型时,要充分注意是否满足无后效性的要求; ? 如果状态变量不能满足无后效性的要求,应适当地改变状态的定义或规 定方法。

状态具有无后效性的多阶段决策过程的状态转移方程如下:

s2 ? T1 ( s1 , u1 ) s3 ? T2 ( s2 , u2 ) ?? sk ?1 ? Tk ( sk , uk )

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

20

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

vk(sk,uk) 表示第k阶段位于sk状态、决策为uk的指
标值。
? 在不同的问题中,指标函数的含义是不同的,它

可能是距离、利润、成本、产量或资源消耗等。 ? 最短路问题中vk,n表示第k阶段由点sk到终点G的最 短距离
21

? 动态规划的指标函数应具有可分离性,并满足递 推关系式, 函数记为:

指标函数的形式:
?和

?积

最优值函数
? 指标函数的最优值,称为最优值函数。表示从第k 阶段的状态sk开始到第n阶段的终止状态的过程, 采取最优策略所得到的指标函数值。记为

( ) ? fk s k

opt V (s ,u ? ?
u k ,?,u n
k ,n k

, ? , ) s n ?1 k

? ?opt? ‘optimization’, min

, max

25

小结: 动态规划本质上是多阶段决策过程;
要求:无后效性

概念 : 阶段变量k﹑状态变量sk﹑决策变量uk

允许决策集合Dk(sk)、最优策略;
方程 :状态转移方程

sk ?1 ? Tk (sk , uk )

指标: Vk ,n ? Vk ,n (sk , uk , sk ?1, uk ?1,?, sn?1 )

效益

f (s
k

k

)?

?u

opt V
k

, ?,

un?

k ,n

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

Vk ,n (sk , uk , sk ?1, uk ?1,?, sn?1 )

? ? k [ sk , u k , Vk ?1, n ( sk ?1 , u k ?1 , ?, sn ?1 )]

27

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

f 1 ( s1 )

最优目标函数值
* V1,n * * * 从 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

?
28

三. 动态规划的基本思想
B1 2 A 5 1 10 6 B2 4 13 B3 12 11 10 C2 5 8 C3 10 D2 2 12 14 C1 9 6 E 3 D1 5

f5 ( E ) ? 0

k=4
f4 (D 1) ? 5 f 4 ( D2 ) ? 2

D 1 ? E D2 ? E

B1 2 A 1 5 10 6 B2 4 13 B3

12 14

C1 9 6 C2 5 8 C3

3 D1 5 E D2 10 2

10

k=3

12 11

? d3 (C1 , D1 ) ? f 4 ( D1 ) ? ?3 ? 5 ? f3 (C1 ) ? min ? ? ? min ? ? ? 8, ?9 ? 2? ?d3 (C1 , D2 ) ? f 4 ( D2 ) ?
? 6 ? f 4 ( D1 ) ? ?6 ? 5 ? f3 (C2 ) ? min ? ? ? min ? ? ? 7, ?5 ? 2? ?5 ? f 4 ( D2 ) ?

C1 ? D1

C2 ? D2

? 8 ? f 4 ( D1 ) ? ? 8?5 ? f3 (C3 ) ? min ? ? ? min ? ? ? 12, ?10 ? 2? ?10 ? f 4 ( D2 ) ?

C3 ? D2

f3 (C1 ) ? 8

f3 (C2 ) ? 7

f3 (C3 ) ? 12
B1 ? C1

k=2

? d 2 ( B1 , C1 ) ? f3 (C1 ) ? ? 12 ? 8 ? ? ? ? ? f 2 ( B1 ) ? min ?d 2 ( B1 , C2 ) ? f3 (C2 ) ? ? min ? 14 ? 7 ? ? 20, ? d ( B , C ) ? f (C ) ? ?10 ? 12 ? 3 3 ? ? 2 1 3 ? ?
B1 2 A 1 5 10 6 B2 4 13 B3 12 11 10 C2 5 8 C3 10 D2 2 12 14 C1 9 6 E 3 D1 5

B1 2 A 1 5 10 6 B2 4 13 B3

12 14

C1 9 6 C2 5 8 C3

3 D1 5 E D2 10 2

10

12 11

f3 (C1 ) ? 8

f3 (C2 ) ? 7

f3 (C3 ) ? 12

? 6 ? f3 (C1 ) ? ? 6?8 ? ? ? ? ? f 2 ( B2 ) ? min ?10 ? f3 (C2 ) ? ? min ?10 ? 7 ? ? 14, ? 4 ? f (C ) ? ?4 ? 12 ? 3 3 ? ? ? ?
?13 ? f3 (C1 ) ? ? 13 ? 8 ? ? ? ? ? f 2 ( B3 ) ? min ?12 ? f 3 (C2 ) ? ? min ? 12 ? 7 ? ? 19, ?11 ? f (C ) ? ?11 ? 12 ? 3 3 ? ? ? ?

B2 ? C1

B3 ? C2

f2 ( B1 ) ? 20

f 2 ( B2 ) ? 14

f 2 ( B3 ) ? 19

? 2 ? f 2 ( B1 ) ? ?2 ? 20 ? ? ? ? ? f1 ( A) ? min ?5 ? f 2 ( B2 ) ? ? min ? 5 ? 14 ? ? 19, ?1 ? f ( B ) ? ? 1 ? 19 ? 2 3 ? ? ? ?

k=1

A ? B2

最优路径为
A ? B2 ? C1 ? D1 ? E

最短距离为 19

最优解(标号法)
20 B1 19 A 1 2 5 10 14 6 B2 4 13 B3 18 12 11 10 12 14 8 C1 9 7 C2 5 8 C3 10 12 D2 2 2 6 3 5 D1 5 0 E

动态规划的基本方程
? K阶段与k+1阶段递推关系

? 边界条件

动态规划基本思想:

2、在多阶段决策过程中,动态规划方法是既把当 前一段和未来一段分开,又把当前效益和未来效 益结合起来考虑的一种最优化方法。因此,每段 决策的选取是从全局来考虑的,与该段的最优选 择答案一般是不同的。 ? 3、在求整个问题的最优策略时,由于初始状态是 已知的,而每段的决策都是该段状态的函数,故 最优策略所经过的各段状态便可逐段变换得到, 从而确定了最优路线。
?

37

四、动态规划递推求解方法
? 建立动态规划模型步骤
? 静态规划与动态规划的关系 ? 求解方法 ? 逆推解法 ? 顺推解法

38

建立动态规划模型的步骤
1、划分阶段k 划分阶段是运用动态规划求解多阶段决策问题的第 一步,在确定多阶段特性后,按时间或空间先后顺 序,将过程划分为若干相互联系的阶段。对于静态 问题要人为地赋予?时间?概念,以便划分阶段。 2、正确选择状态变量sk 选择变量既要能确切描述过程演变又要满足无后效 性,而且各阶段状态变量的取值能够确定。一般地, 状态变量的选择是从过程演变的特点中寻找。

39

3、确定决策变量uk(sk)及允许决策集合Dk(sk)

通常选择所求解问题的关键变量作为决策变量,同 时要给出决策变量的取值范围,即确定允许决策集 合。 4、确定状态转移方程
根据 k阶段状态变量和决策变量,写出 k+1阶段状态 变量,状态转移方程应当具有递推关系。

sk+1=Tk(sk,uk)

Tk —函数关系

40

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)
41

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

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

静态规划与动态规划的关系
时间
静态规划 (与时间无关)

动态规划

43

逆推解法与顺推解法
? 应用条件: ? 当初始状态给定时,用逆推比较方便 ? 当终止状态给定时,用顺推比较方便

44

逆序解法基本方程

思考:顺序解法基本方程
45

顺序解法基本方程
重新定义: 递推关系:

边界条件:

五、动态规划最优性(最优化) 原理和最优性定理
? 最优性原理:作为整个过程的最优策略具有这样的性

质:无论过去的状态和决策如何,相对于前面的决策 所形成的状态而言,余下的决策序列必然构成最优子 策略。”也就是说,一个最优策略的子策略也是最优 的。
3

B

6

5 3

G

7
6 3
返回
47

A

8 7

C 2
1

E

F

2 H

J

4

D
过去 当前

I
未来

最优性定理

若一个问题有最优策略,则该问题的最优值 函数可用动态规划的基本方程来表示
48

六、动态规划优缺点
优点:
(1)能够得到全局最优解 (2)可以得到一族最优解 (3)能够利用经验提高求解效率

缺点:
(1)没有统一的标准模型,也没有构造模型的通 用方法,甚至没有判断一个问题能否构造动态规 划模型的具体准则 (2)求解时存在维数灾难
49

七、动态规划问题应用举例
? 最短路径问题
? 资源分配问题 ? 生产计划问题

50

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

C1

1 D

3 1

51

基本方程逆序解法
3 C1 C2 1 C3 4 3

2
A 4

B1
2 B2 1 3

3

1 D

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

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

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
53

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
54

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)
55

3 2 A 4 B2 B1 2 3 1 3 1

C1 C2 4 3

1 D

C3

最短路线为

A→B1→C1 →D

路长为 6
56

顺序解法
3 2 A 4 B2 B1 2 3 1 3 1 C1 C2 4 3 1 D

C3

57

Dijkstra(狄克斯拉)标号法
? 从起点vs开始,逐步给每个结点vj标号[dj,vi],其中

dj为起点vs到vj的最短距离,vi为该最短路线上的前一 节点。
3
2 A 4 B2 B1 2 1 3 C2 4 C3 3

C1

1 D

3 1

58

例题:
4

B

6

D

6

F

5

A

H

C

6

E

3

G

求A到H的最短路径?
59

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

60

假设有一种资源,数量为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
这是一个静态规划问题,应用动态规划方法求解时 人为赋予时间概念,将其看作是一个多阶段决策问题。
61

按变量个数划分阶段,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时的收益;

62

最优指标函数 f k( sk)表示以数量sk的资源分配给第 k个
至第n个使用者所得到的最大收益,则动态规划基本方

程为:

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

k ? n,?,1

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

按变量个数划分阶段,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时的收益; 最优指标函数 f k( sk)表示以数量 sk的资源分配给第 k个 至第n个使用者所得到的最大收益,则动态规划基本方 程为:

f ( s ) ? max [ g ( x ) ? f ( s )] k ? n , ? , 1 ? k k k k k ? 1 k ? 1 ? 0 ? xk ? s k ? ? f ( s ) ? 0 n ? 1 n ? 1 ? 由后向前逐段递推,f1(a)即为所求问题的最大收益。
64

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

65

解 如前所述,建立动态规划数学模型: 将问题分为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 个地区所获得的利润; 最优指标函数f k(sk)表示将数量为sk的销售点分 配给第k个至第3个地区所得到的最大利润,动态规划 基本方程为:

[ g k ( xk ) ? f k ?1 (sk ? xk )] ? ? f k (sk ) ? 0max ? xk ? s k ? ? ? f 4 (s4 ) ? 0

k ? 3,2,1

66

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

表6-5

67

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

表7-6
表6-6

68

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

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。表6-7

69

例三、机器负荷问题

某工厂有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

70

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

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 *= s
3 3

72

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

0 ? x2 ? s 2

max [10x 2 ? 7( s 2 ? x 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

73

因为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期把全部完好机器投入高负荷下生产所得利润最大。
74

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

75

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

76

解 按月份划分阶段,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月末的最大利润,则动态规划基本方程为:
?fk(s k ) ? max [p k x k ? ck y k ? fk ?1(s k ?1 )] 0 ? x k ?s k ? 0 ? y k ? 600 ?(s k ? x k ) ? ?f (s ) ? 0 ?5 5

k ? 4, 3, 2, 1

77

k=4时, f4(s 4 ) ?

0 ? x 4 ?s 4 0 ? y 4 ? 600 ?(s 4 ? x 4 )

max

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

x4*=s4

y4*=0

k=3时, f 3 ( s3 ) ? 0? x3 ?max s3
? ? max max

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

0? y3 ? 600 ? ( s3 ? x3 )

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

为求出使 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

78

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 ,可 用图解法也可用单纯形法 求解,图解法求解示意图 如图6-5所示: 在A点处取得最优解,

600-s3

A

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

0

s3
图6-5

600

x3

79

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时, f ( s ) ? max [45x ? 40 y ? f ( s )]
1 1 0? x1 ? s1 0? y1 ? 600 ? ( s1 ? x1 ) 1 1 2 2

? ?

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

80

逆向追踪得各月最优购货量及销售量: 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。
81


相关文章:
第六章(上课) 运筹学动态规划04修改_图文.ppt
第六章(上课) 运筹学动态规划04修改_理学_高等教育_教育专区。(Dynami
运筹学第六章动态规划_图文.pdf
运筹学第六章动态规划_数学_自然科学_专业资料。第六章 动态规划 第六章 动态规划 6.1 基本概念与方法 6.2 应用举例 天津大学管理与经济学部 http://come....
管理运筹学 第六章 动态规划_图文.ppt
管理运筹学 第六章 动态规划 - 第六章 动态规划 广东工业大学管理学院 第六章 动态规划 6.1 动态规划的基本概念 6.2 最优化原理 6.3 经济管理问题举例 多...
运筹学第六章 动态规划.doc
运筹学第六章 动态规划 - 第六章 动态规划 第 66 页 第六章 动态规划 主要内容:1、动态规划的基本概念 2、动态规划的最优性原理和基本方程 3、动态规划的...
运筹学第六章 运筹学 动态规划_图文.ppt
运筹学第六章 运筹学 动态规划 - 第六章 动态规划 ? ? ? ? ? ? 多
运筹学04_动态规划(1)_图文.ppt
运筹学04_动态规划(1) - 第四章 动态规划 Dynamic Programming 本章内容重点 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态...
第六章 动态规划(运筹学-重庆大学,熊中楷)_图文.ppt
动态规划(1) 运筹学 熊中楷教授 第六章 动态规划(1)重庆大学 上清寺 解放
运筹学04_动态规划(1)_图文.ppt
运筹学04_动态规划(1) - 第四章 动态规划 Dynamic Programming 本章内容重点 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态...
运筹学04_动态规划(2).ppt
运筹学第五章 动态规划2 48页 免费 2.运筹学 动态规划解法 29页 免费如
运筹学04动态规划1_图文.ppt
运筹学04动态规划1 - 本章内容重点 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例 动态规划是解决多阶段决策...
运筹学动态规划.ppt
运筹学动态规划_数学_自然科学_专业资料。第7章重点: 动态规划 (Dynami
运筹学 动态规划应用---背包问题_图文.ppt
运筹学 动态规划应用---背包问题_经济/市场_经管营销_专业资料。动态规应用-
运筹学之动态规划(东南大学).doc
运筹学动态规划(东南大学)_管理学_高等教育_教育专区。运筹学 ...根据动态规划的基本方程可以直接递归计算最优值,但是一般将其改为递推计 算,...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 (Dynamic programming) 动态规
运筹学-第3版-课件-动态规划例题_图文.ppt
运筹学-第3版-课件-动态规划例题_理学_高等教育_教育专区。8.1 用动态规划方法求整数规划模型,而 非线性规划模型的最优解。 例1 求解下列整数规划的最优解: ...
运筹学(二)动态规划(1-2014)_图文.ppt
运筹学(二)动态规划(1-2014) - 运筹学(二) 动态规划 动态规划 ? 动态规划运筹学的一个分支,它是 解决多阶段决策问题的一种数学方法。大 约产生...
运筹学第10章-动态规划_图文.ppt
运筹学第10章-动态规划 - Page:1 管理运筹学 动态规划 Page:2
运筹学第六章_图文.ppt
运筹学 第六章 动态规划应用举例 动态规划是一种将复杂问题转化为比较简单问题的最优 化方法,一些线性规划、非线性规划及整数规划都可以用 动态规划方法来求解。...
第七章运筹学动态规划_图文.ppt
第七章运筹学动态规划 - 动态规划 引言 □动态规划是解决多阶段决策过程最优化的
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划(Dynamic Programming) 动态规划
更多相关文章: