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

运筹学第10章 动态规划


Page:1

管理运筹学
动态规划

Page:2





动态规划是解决多阶段决策过程最优

化问题的一种方法。动态规划所研究
的对象是多阶段决策问题。它把困难

的多阶段决策问题变换成一系列互相
联系较容易的单阶段问题。

Page:3





多阶段决策问题是指一类活动过程,它可以分 为若干个相互联系的阶段,在每个阶段都需要作 出决策。这个决策不仅决定这一阶段的效益,而 且决定下一阶段的初始状态。

每个阶段的决策确定以后,就得到一个决策
序列,称为策略。多阶段决策问题就是求一个策

略,使各阶段的效益的总和达到最优。

Page:4





动态规划可以解决管理中的最短路径、装载 问题、库存问题、资源分配、生产过程最优化问 题。

Page:5

§1.多阶段决策过程最优化问题举例

最短路径问题:

Page:6

最短路径问题的应用
12 14 9 6 10 4 1 13 B3 12 11 C3 10 C2 5 8 D2 2 E D1 5 6 A 5 B2

B1 2 10

C1

3

找出A到E的最短路径

Page:7

阶段划分
B1 2 A 1 5 10 6 B2 4 13 B3 12 11 C3 10 10 C2 5 8 D2 2 12 14 9 6 E D1 5 C1 3

I

II

III

IV

Page:8

求解策略 记SE(x)为节点x到E的最短路

将A到E的最短路径问题,转化为三个性质 完全相同,但规模较小的子问题

S ( A) ? min d A, Bi ? S ( Bi )
i
j

?

?

S ( Bi ) ? min d Bi ,C j ? S (C j )

?

?
?
S ( Dk )

S (C j ) ? min d C j , Dk ? S ( Dk )
k

?

Page:9

求解 S(D1)=5,
? 3 ? S( D 1 ) ? ? 3 ? 5? ? ? ? ? S(C 1 ) ? min ? ? min ? ? ? ? 8, ?9 ? S( D 2 ) ? ?9 ? 2 ? ? ? ? ?
?6 ? S( D 1 ) ? ?6 ? 5? ? ? ? ? S(C 2 ) ? min? ? min ? ? ? ? 7, ?5 ? S( D 2 ) ? ?5 ? 2? ? ? ? ?

D1?E D2?E
C1 ? D1

S(D2)=2

C2 ? D2

? 8 ? S( D 1 ) ? ? 8?5 ? ? ? ? ? S(C 3 ) ? min ? ? min ? ? ? ? 12 , ?10 ? S( D 2 ) ? ?10 ? 2? ? ? ? ?

C3 ? D2

S(C1)=8;S(C2)=7; S(C3)=12

Page:10

S(C1)=8;S(C2)=7; S(C3)=12
?12 ? S(C1 ) ? ? 12 ? 8 ? ? ? ? ? ? ? ? ? S( B1 ) ? min?14 ? S(C 2 ) ? ? min? 14 ? 7 ? ? 20 , ? ? ? ? ?10 ? S(C 3 ) ? ?10 ? 12? ? ? ? ? ? 6 ? S(C1 ) ? ? 6?8 ? ? ? ? ? ? ? ? ? S( B 2 ) ? min?10 ? S(C 2 ) ? ? min?10 ? 7 ? ? 14 , ? ? ? ? ? 4 ? S(C 3 ) ? ?4 ? 12? ? ? ? ? ?13 ? S(C1 ) ? ? 13 ? 8 ? ? ? ? ? ? ? ? ? S( B 3 ) ? min?12 ? S(C 2 ) ? ? min? 12 ? 7 ? ? 19 , ? ? ? ? ?11 ? S(C 3 ) ? ?11 ? 12? ? ? ? ?

B1 ? C1

B 2 ? C1

B3 ? C 2

Page:11

S(B1)=20;S(B2)=14;S(B3)=19

?2 ? S( B1 ) ? ?2 ? 20? ? ? ? ? ? ? ? ? S(A) ? min?5 ? S( B2 ) ? ? min?5 ? 14 ? ? 19 , ? ? ? ? ?1 ? S( B3 ) ? ?1 ? 19 ? ? ? ? ?

A ? B2

Page:12

最优解

20 B1 2 19 A 1 5 10 14 6 B2 12 14

8
C1 9 7 6 5 8 3 5 D1 5 0 E

10 4

C2

13 B3

D2
2

2

12 11
C3 10 12

19

Page:13

§2. 基本概念、基本方程与最优化原理
一、基本概念 1.阶段:用动态规划方法求解问题时,首先将 问题的全过程适当地分成若干个互相联系 的阶段,以便能按一定的次序去解.划分的标 准是时间或空间.

Page:14

§2. 基本概念、基本方程与最优化原理
2. 状态. 状态是指每个阶段开始时所处的自然状 态或客观条件.在例1中某个阶段的状态就是 某个阶段的始点.S2={B1,B2,B3,B4}
x1 s1 s2 x2 s3 x3 s4

北京
指标值(收益) V1(s1,x1)

上海
指标值(收益) V2(s2,x2)

广州
指标值(收益) V3(s3,x3)

Page:15

§2. 基本概念、基本方程与最优化原理
3. 决策. 决策是某一阶段内的抉择,第N阶段的决策 与第N个阶段的状态有关,通常用Xn(Sn)表示 第n阶段处于Sn状态时的决策量,而这个决策 量又决定第n+1阶段的状态.
x1 x2 x3 S1

北京
指标值(收益) V1(s1,x1)

s2

上海
指标值(收益) V2(s2,x2)

s3

广州
指标值(收益) V3(s3,x3)

s4

Page:16

§2. 基本概念、基本方程与最优化原理
4. 策略.

由所有各阶段的决策函数序列称为全过程 策略,简称策略,记为p1,n(s1),能够达到总体最 优的策略叫做最优策略.从第K个阶段开始 到最后阶段的决策组成的决策函数序列称 为K子过程策略,简称K子策略,记为Pk,N(Sk)

P,n (S1 ) ? ?X1 (S1 ), X2 (S 2 ), ??, Xn (S n )? 1

Page:17

§2. 基本概念、基本方程与最优化原理
5. 指标函数:指标函数是衡量全过程策略或 K子过程策略优劣的数量指标,指标函数的 最优值称之为最优指标函数,记作f1(S1)或 fk(Sk)

最短距离f1(s1),
最大收益fk(sk)

Page:18

§2. 基本概念、基本方程与最优化原理
6. 状态转移方程:已知第N+1阶段的状态是 由第N阶段的状态和第N阶段的决策所决定 的,用方程表示为: Sn+1=Tn(Sn,Xn)

状态转移方程.

Page:19

§2. 基本概念、基本方程与最优化原理
二、基本方程:

动态规划递归方程
f k (Sk ) ? min ?rk (Sk ,X k ) ? f k ?1 (Sk ?1 )? ? X k ?Dk (Sk ) ? ? k ? n,n ? 1,?,1 ? ?初始(终点)条件: f (S ) ? 0 n ?1 n ?1 ? ?

Page:20

§2. 基本概念、基本方程与最优化原理
二、基本方程:

动态规划递归方程
f k (Sk ) ? max?rk (Sk , X k ) ? f k ?1 (Sk ?1 )? ? ? k ? n, n ? 1,?,1 ? ?初始条件 : f (S ) ? 0 n ?1 n ?1 ?

Page:21

§2. 基本概念、基本方程与最优化原理
二、基本方程:

动态规划递归方程
?f k (S k ) ? Opt ?rk (S k , X k ) ? f k ?1 (S k ?1 )? X k ?D k (S k ) ? ? k ? n, n ? 1,?,1 ? ? f (S ) ? 0 (or) 1 ? n ?1 n ?1 ?

Page:22

三、最优化原理与动态规划的基本方法
? Bellman原理 ? 动态规划的基本方法
– 逆向顺序法 – 前向顺序法

Page:23

Bellman原理示意图
整个 问题

最后一步 部分优化

最后两步 部分优化 整个问 题优化

Page:24

Bellman最优性原理

“作为整个过程的最优策略具有这样的性 质:无论过去的状态和决策如何,相对于 前面决策所形成的状态,余下的决策必然

形成最优子策略” .

最优策略的子策略也是最优的.

Page:25

Bellman最优性原理

最短路径的子路径仍然是最短路径。
全长最优,那么部分仍然是最优。

Page:26

20 B1 2 19 10 14 6 12 14

8 C1 3 5 D1 6 5 0 E

9 7
10 C2

A
1

5

B2 4 13 B3 19

5
8 12 11 C3 10 12 D2 2 2

A到E的最 优是: A?B2?C1?D1?E

A?B2?C1?D1 是A到D1的最优

Page:27

四、 动态规划建模与求解步骤
? 建立动态规划模型的基本要求 ? 动态规划的求解步骤

Page:28

一、建立动态规划模型的基本要求
? 将问题划分成若干阶段。有的问题的阶 段性很明显,有的则不明显,需要分析 后人为假设。 ? 确定各阶段的状态变量,并给出状态转 移方程,状态转移方程的形式应当与递 推顺序一致。 ? 状态变量应当满足无后效性要求。 ? 明确指标函数,给出最优函数递推方程, 递推方程的形式应当与递推顺序一致。

Page:29

二、动态规划的求解步骤
? 正确划分阶段。 ? 确定状态变量和决策变量,并给出状态变 量和决策变量的可行集合。 ? 确定求解的递推顺序,给出状态转移方程。 ? 确定阶段、子过程(子策略)的指标函数,确 定最优值函数的递推方程和边界条件。 ? 递推求解。 ? 与递推过程反向求出最优策略(最优决策变 量值系列)和最优状态变化路线。

Page:30

建立动态规划模型及求解步骤
划分阶段
确定状态变量及允许状态集合

确定决策变量及决策空间
确定状态转移方程 确定转移指标函数并建立递归方程

Page:31

§3 动态规划应用
一、资源分配问题
二、背包问题 三、生产与存贮问题

Page:32

资源分配问题
例2:某公司有4个推销员在北京、上海和广州三个市场推销 货物,这三个市场里推销人员数与收益的关系如表所示:试 做出使决收益最大的分配方案。

推销员 市场 北京 上海 广州

0 20 40 50

1 32 50 61

2 47 60 72

3 57 71 84

4 66 82 84

Page:33

解:1。阶段划分。分成三个阶段,K=3;并按逆向 编号。广州 K=1,上海K=2 北京K=3,分配推销员 的优先顺序为北京?上海?广州. 或按顺向编号。广州 K=3,上海K=2 北京K=1,分 配推销员的优先顺序为北京?上海?广州. x1 s1 s2 x2 s3 x3 s4

北京
指标值(收益) V1(s1,x1)

上海
指标值(收益) V2(s2,x2)

广州
指标值(收益) V3(s3,x3)

Page:34

解:2.确定状态量Sk。状态量Sk表示第K阶段初未 分配的推销员数.显然S1=4;S2,S3的取值为0--4 3.确定决策变量Xk. 决策变量Xk表示分配给第K 阶段市场的推销数.显然Xk<=Sk.

x1
s1 s2

x2
s3

x3
s4

北京
指标值(收益) V1(s1,x1)

上海
指标值(收益) V2(s2,x2)

广州
指标值(收益) V3(s3,x3)

Page:35

解:4.确定状态转移方程Sk。根据前面的定义:

Sk+1=Sk-Xk 期末=期初-本期发生额
5.确定直接效果函数dk(Sk,Xk). 它表示第K阶段 初有推销员数SK,分配给第K市场XK个推销员时所产 生的直接效益,这些效益指标由于表1给出. x1 s1 s2 x2 s3 x3 s4

北京
指标值(收益) V1(s1,x1)

上海
指标值(收益) V2(s2,x2)

广州
指标值(收益) V3(s3,x3)

Page:36

解:6.确定最优指标函数。由于三个市场的总收益 等于三个市场的收益之和.所以最优指标函数为:

f k (sk ) ? max ?dk (sk , xk ) ? f k ?1 ( xk ?1 )? k ? 1,2,3
xk

x1 s1 s2

x2 s3

x3 s4

北京
指标值(收益) V1(s1,x1)

上海
指标值(收益) V2(s2,x2)

广州
指标值(收益) V3(s3,x3)

Page:37

解:7.确定边界:fn+1(xn+1)=0

f4(x4)=f4(s4)=0

x1 s1 s2

x2 s3

x3 s4

北京
指标值(收益) V1(s1,x1)

上海
指标值(收益) V2(s2,x2)

广州
指标值(收益) V3(s3,x3)

Page:38

各阶段计算过程如下:

第3阶段:S3=0,1,2,3,4
f3(s3)=max{d3(s3,x3)+f4(s4)}=max{d3(s3,x3)}

f3(0)=50, f3(1)=61,f3(2)=72,f3(3)=84,f3(4)=84

x1 s1 s2

x2 s3

x3 s4

北京
指标值(收益) V1(s1,x1)

上海
指标值(收益) V2(s2,x2)

广州
指标值(收益) V3(s3,x3)

Page:39

各阶段计算过程如下:

第2阶段:S2=0,1,2,3,4
f2(s2)=max{d2(s2,x2)+f3(s3)}

f2(0)=max{d2(0,x2)+f3(0)}=40+50=90
f2(1)=max{d2(1,x2)+f3(s3)} d2(1,0)+f3(1) =max d2(1,1)+f3(0) 40+61 =max 50+50 =101

Page:40

各阶段计算过程如下:

第2阶段:S2=0,1,2,3,4
f2(s2)=max{d2(s2,x2)+f3(s3)}

f2(2)=max{d2(2,x2)+f3(s3)}
d2(2,0)+f3(2)

=max
=max

d2(2,1)+f3(1)

d2(2,2)+f3(0) 40+72 =112 50+61 60+50

Page:41

各阶段计算过程如下:

第2阶段:S2=0,1,2,3,4
f2(s2)=max{d2(s2,x2)+f3(s3)}

f2(3)=max{d2(3,x2)+f3(s3)}
d2(3,0)+f3(3) 40+84 50+72 60+61 71+50 =124

=max

d2(3,1)+f3(2) d2(3,1)+f3(1) d2(3,2)+f3(0)

=max

Page:42

各阶段计算过程如下:

第2阶段:S2=0,1,2,3,4
f2(s2)=max{d2(s2,x2)+f3(s3)}

f2(4)=max{d2(4,x2)+f3(s3)}
d2(4,0)+f3(4) d2(4,1)+f3(3) d2(4,2)+f3(2) d2(4,3)+f3(1) d2(4,4)+f3(0) =134 40+84 50+84 =max 60+72 71+61 82+50

=max

Page:43

各阶段计算过程如下:

第1阶段:S3=4
f1(s1)=max{d1(s1,x1)+f2(s2)}

f1(4)=max{d1(4,x1)+f2(s2)}
d1(4,0)+f2(4) d1(4,1)+f2(3) d1(4,2)+f2(2) d1(4,3)+f2(1) d1(4,4)+f2(0) =159 20+134 32+124 =max 47+112 57+101 66+90

=max

Page:44

分配方案:北京市场 2个推销员,上海0个, 广州市场2个推销员, 总收益为159单位元.

Page:45

Page:46

资源分配问题
有资金4万元,投资A、B、C三个项目,每个项目的投资效益 与投入该项目的资金有关。三个项目A、B、C的投资效益 (万吨)和投入资金(万元)的关系见下表:
项目 投入资金 1万元 2万元 3万元 4万元 A 15万吨 28万吨 40万吨 51万吨 B 13万吨 29万吨 43万吨 55万吨 C 11万吨 30万吨 45万吨 58万吨

求对三个项目的最优投资分配,使总投资效益最大。

Page:47

x1
s1 s2

x2
s3

x3
s4

项目A
指标值(收益) V1(s1,x1)

项目B
指标值(收益) V2(s2,x2)

项目C
指标值(收益) V3(s3,x3)

阶段k:每投资一个项目作为一个阶段; 状态变量sk:投资第k个项目前的资金余额; 决策变量xk:第k个项目的投资额; 决策允许集合:Dk(sk)={0≤xk≤sk} 状态转移方程:sk+1=sk-xk 阶段指标:vk(sk,xk)见表中所示; 递推方程:fk(sk)=max{vk(sk,xk)+fk+1(sk+1)} 终端条件:f4(s4)=0

Page:48

k=4,f4(s4)=0; k=3,0≤x3≤s3,s4=s3-x3
s3 D3(s3) s4 v3(s3,x3) v3(s3,x3)+f4(s4) f3(s3) x3*
0 1 0 0 1 0 1 2 0 1 2 3 0 1 2 3 4 0 1 0 2 1 0 3 2 1 0 4 3 2 1 0 0 0 11 0 11 30 0 11 30 45 0 11 30 45 58 0+0=0 0+0=0 11+0=11* 0+0=0 11+0=11 30+0=30* 0+0=0 11+0=11 30+0=30 45+0=45* 0+0=0 11+0=11 30+0=30 45+0=45 58+0=58* 0 11 0 1

2

30

2

3

45

3

4

58

4

Page:49

k=2,0≤x2≤s2,s3=s2-x2
s2 D2(s2)
0 1 0 0 1 0 1 2 0 1 2 3 0 1 2 3 4

s3
0 1 0 2 1 0 3 2 1 0 4 3 2 1 0

v2(s2,x2)
0 0 13 0 13 29 0 13 29 43 0 13 29 43 55

v2(s2,x2)+f3(s3)
0+0=0 0+11=11 13+0=13* 0+30=30* 13+11=24 29+0=29 0+45=45* 13+30=43 29+11=40 43+0=43 0+58=58 13+45=58 29+30=59* 43+11=54 55+0=55

f2(s2) x2*
0 13 0 1

2

30

0

3

45

0

4

59

2

Page:50

k=1,0≤x1≤s1,s2=s1-x1

s1 D1(s1)
4 0 1 2 3 4

s2
4 3 2 1 0

v1(s1,x1)
0 15 28 40 51

v1(s1,x1)+f2(s2)
0+59=59 15+45=60* 28+30=58 40+13=53 51+0=51

f1(s1) x1*
60 1

最优解为: s1=4, x1*=1, s2=s1-x1=3, x2*=0, s3=s2-x2*=3, x3*=3, s4=s3-x3=0

最大效益为60万吨

Page:51

机器负荷分配问题
某种机器可以在高、低两种负荷下生产。高负荷生 产条件下机器完好率为0.7,即如果年初有u台完好 机器投入生产,则年末完好的机器数量为0.7u台。 系数0.7称为完好率。年初投入高负荷运行的u台机 器的年产量为8u吨。系数8称为单台产量。低负荷 运行时,机器完好率为0.9,单台产量为5吨。设开 始时有1000台完好机器,要制订五年计划,每年年 初将完好的机器一部分分配到高负荷生产,剩下的 机器分配到低负荷生产,使五年的总产量为最高。

Page:52

x1

x2

x3

x4

x5

s1

第 s 2 1 年
指标值
(产量) V1(s1,x1)

第 s 3 2 年
指标值
(产量) V2(s2,x2)

第 s 4 3 年
指标值
(产量) V3(s3,x3)

第 s5 4 年
指标值
(产量) V4(s4,x4)

第 s 6 5 年
指标值
(产量) V5(s5,x5)

Page:53

动态规划模型构造
阶段k:
状态变量xk: 决策变量dk:

运行年份(k=1,2,3,4,5,6);
第k年初完好的机器数(k=1,2,3,4,5,6); 第k年投入高负荷运行的机器数;

状态转移方程:sk+1=0.7xk+0.9(sk-xk) 决策允许集合:Dk(sk)={xk|0?xk?sk} 阶段指标: vk(sk,xk)=8xk+5(sk-xk)

终端条件:
递推方程:

f6(s6)=0
fk(sk)=max{vk(sk,xk)+fk+1(sk+1)}
xk?Dk(sk)

=max{8xk+5(sk-xk)+fk+1[0.7xk+0.9(sk-xk)]}
0?xk?sk

Page:54

f 5 (s5 ) ? max ?8x5 ? 5(s5 ? x 5 ) ? f 6 (s6 )? ? max ?3x5 ? 5s5 ? ? 8s5
0? x 5 ?s 5 0? x 5 ?s 5

x5

x ? s5
* 5

s5

第 s 6 … 5 年
指标值 (产量) V5(s5,x5)

+f6(s6)

Page:55

f 4 (s4 ) ? max ?8x4 ? 5(s4 ? x 4 ) ? f 5 (s5 )? ? max ?8x4 ? 5(s4 ? x 4 ) ? 8s5 ? ? max ?8x4 ? 5(s4 ? x 4 ) ? 8[0.7x ? 0.9(s4 ? x 4 )]? 4 ? max ? 1.4x4 ? 12.3s4 ? ? 13.7s4
0? x 4 ?s 4 0? x 4 ?s 4 0? x 4 ?s 4 0? x 4 ?s 4

x4 第 s 5 … 4 年
指标值

s4

x ? s4
* 4

(产量)
V4(s4,x4)

+f5(s5)

Page:56

f3(s3)=max{8x3+5(s3-x3)+f4(s4)}
0?x3?s3

=max{8x3+5(s3-x3)+13.7s4}
0?x3?s3 0?x3?s3 0?x3?s3

=max{8d3+5(s3-d3)+13.7[0.7d3+0.9(s3-d3)]} x3 =max{0.28x3+17.24s3}=17.52s3

s3

第 s 4 … 3 年
指标值 (产量) V3(s3,x3)

x3*=s3

+f4(s4)

Page:57

f2(s2)=max{8x2+5(s2-x2)+f3(s3)}
0?x2?s2

=max{8x2+5(s2-x2)+17.52s3}
0?x2?s2

=max{8x2+5(s2-x2)+17.52[0.7x2+0.9(s2-x2)]} x2
0?x2?s2

=max{-0.504x2+20.77s2}=20.77s2
0?x2?s2

s2

第 s 3 … 2 年
指标值 (产量) V2(s2,x2)

x2*=0

+f3(s3)

Page:58

f1(s1)=max{8x1+5(s1-x1)+f2(s2)}
0?x1?s1

=max{8x1+5(s1-x1)+20.77s2}
0?x1?s1

=max{8x1+5(s1-x1)+20.77[0.7x1+0.9(s1-x1)]}
0?x1?s1

x1

=max{-0.05x1+23.69s1}=23.69s1
0?x1?s1

s1

第 s 2 … 1 年
指标值 (产量) V1(s1,x1)

x1*=0

+f2(s2)

Page:59

由此可以得到:

f1(s1)=23.69s1,
f2(s2)=20.77s2, f3(s3)=17.52s3, f4(s4)=13.60s4, f5(s5)=8s5

x1*=0
x2*=0 x3*=s3 x4*=s4 x5*=s5

用s1=1000代入,得到五年最大产量为 f1(s1)=f1(1000)=23690

Page:60

每年投入高负荷运行的机器数以及每年初完好的机 器数为: s1=1000

x1*=0,
x2*=0,

s2=0.7x1+0.9(s1-x1)=900
s3=0.7x2+0.9(s2-x2)=810

x3*=s3=810,
x4*=s4=567, x5*=s5=397,

s4=0.7x3+0.9(s3-x3)=567
s5=0.7x4+0.9(s4-x4)=397 s6=0.7x5+0.9(s5-x5)=278

Page:61

生产-库存问题

生产量 x1 1 月初库存量: s1=0

生产量 x2 3 月初库存量: 7 月初库存量: s7

生产量 x7

生产 系统

2 月初库存量: s2

生产 系统
决策准则: 生产成本 c2x2 最小

s3

生产 系统

7 月底库存量: s8 = 0

决策准则: 生产成本 c1x1 最小

决策准则: 生产成本 c7x7 最小

Page:62

一个工厂生产某种产品,1~7月份生产成本和 产品需求量的变化情况如下表:
月份(k) 1 2 3 4 5 6 7 生产成本(ck) 11 18 13 17 20 10 15 0 8 5 3 2 7 4 需求量(rk)

为了调节生产生产和需求,工厂设有一个产品仓 库,库容量H=9。已知期初库存量为2,要求期末 (七月低)库存量为0。每个月生产的产品在月末 入库,月初根据当月需求发货。求七个月的生产 量,能满足各月的需求,并使生产成本最低.。

Page:63

阶段k:月份,k=1,2,…,7,8; 状态变量sk:第k个月初(发货以前)的库存量; 决策变量xk:第k个月的生产量; 状态转移方程:sk+1=sk-rk+xk; 决策允许集合:Dk(sk)={xk | xk?0, rk+1?sk+1?H} ={xk | xk?0, rk+1?sk-rk+xk?H}; 阶段指标:vk(sk,xk)=ckxk; 终端条件:f8(s8)=0,
xk?Dk(sk)

s8=0;

递推方程:fk(sk)=min{vk(sk,xk)+fk+1(sk+1)} =min{ckxk+fk+1(sk-rk+xk)}
xk?Dk(sk)

Page:64

三、生产存储问题
? 某公司生产并销售某产品。根据市场预测, 今后四个月的市场需求量如表3-7所示。

时期(月) 1 2 3 4

需求量(dk) 2 3 2 4

Page:65

已知的其它条件
? 已知生产一件产品的成本是1千元,每批产品的 生产准备成本是3千元,每月仅能生产一批,每 批6件。每件存储成本为0.5千元,且第一个月初 无存货,第四个月末的存货要求为零。求最优生 产计划。 ? 设第k月的生产量uk,存储量为Sk,则总成本为

?uk ? 3? Ck ( S k , uk ) ? ? ? ? 0.5S k ? 0 ?

Page:66

建立数学模型
? 以月划分阶段,k=1,2,3,4 ? 各阶段决策变量为该阶段生产量uk,状态变量 为该阶段存储量Sk。需求dk ? 采用逆序算法,则状态转移方程为 ? 最低成本递推公式是
0?u k ? 6 S k ?uk ? d k

Sk ?1 ? Sk ? uk ? dk

f k ( S k ) ? min {Ck ( S k , u k ) ? f k ?1 ( S k ?1 )} f 5 ( S5 ) ? 0

Page:67

第四阶段的最优解
? 当k=4时,d4=4,因第四阶段末无存货,因 此S4=(0,1,2,3,4) S4
0 1 2 3 4

u4
4 3 2 1 0

本期成本 生产 存储

C4
7 6.5 6 5.5 2

S5 f5(S5) f4(S4)
0 0 0 0 0 0 0 0 0 0 7 6.5 6 5.5 2

7 6 5 4 0

0 0.5 1 1.5 2

第三阶段最优解
? 当k=3时,由于S4 ? 4,且第三阶段需求量 d3=2,S3=(0,1,2,3,4,5,6) S3
0

Page:68

u3
2 3 4 5 6

本期成本 生产 存储

C3
5 6 7 8 9

S4 f4(S4) f3(S3)
0 1 2 3 4 7 6.5 6 5.5 2 12 12.5 13 13.5 11

5 6 7 8 9

0 0 0 0 0

Page:69

第三阶段最优解:S3=1
S3
1

u3
1 2 3 4 5

本期成本

生产

存储

C3
4.5 5.5 6.5 7.5 8.5

S4 f4(S4) f3(S3)
0 1 2 3 4 7 6.5 6 5.5 2 11.5 12.0 12.5 13.0 10.5

4 5 6 7 8

0.5 0.5 0.5 0.5 0.5

Page:70

第三阶段最优解:S3=2
S3
2

u3
0 1 2 3 4

本期成本

生产

存储

C3
1 5 6 7 8

S4 f4(S4) f3(S3)
0 1 2 3 4 7 6.5 6 5.5 2 8 11.5 12.0 12.5 10.0

0 4 5 6 7

1 1 1 1 1

Page:71

第三阶段最优解:S3=3,4
S3
3

u3
0 1 2 3 0 1 2

本期成本

生产

存储

C3
1.5 5.5 6.5 7.5 2 6 7

S4 f4(S4) f3(S3)
1 2 3 4 2 3 4 6.5 6 5.5 2 6 5.5 2 8 11.5 12.0 9.5 8 11.5 9

0 4 5 6 0 4 5

1.5 1.5 1.5 1.5 2 2 2

4

Page:72

第三阶段最优解:S3=5,6
S3
5 6

u3
0 1 0

本期成本
生产 存储

C3
2.5 6.5 3

S4 f4(S4) f3(S3)
3 4 4 5.5 2 2 8 8.5 5

0 4 0

2.5 2.5 3

Page:73

第二阶段最优解
? 当k=2时,d2=3,由于最生产能力为6, 而d1=2,因此S2=(0,1,2,3,4)

S2
0

u2
3 4 5 6

本期成本 生产 存储

C2
6 7 8 9

S3 f3(S3) f2(S2)
0 1 2 3 11.0 10.5 8.0 8.0 17 17.5 16 17

6 7 8 9

0 0 0 0

Page:74

第二阶段最优解:S2=1
S2
1

u2
2 3 4 5 6

本期成本 生产 存储

C2
5.5 6.5 7.5 8.5 9.5

S3 f3(S3) f2(S2)
0 1 2 3 4 11.0 10.5 8.0 8.0 8.0 16.5 17 15.5 16.5 17.5

5 6 7 8 9

0.5 0.5 0.5 0.5 0.5

Page:75

第二阶段最优解:S2=2
S2
2

u2
1 2 3 4 5 6

本期成本

生产

存储

C2
5 6 7 8 9 10

S3 f3(S3) f2(S2)
0 1 2 3 4 5 11.0 10.5 8.0 8.0 8.0 8.0 16.0 16.5 15.0 16.0 17.0 18.0

4 5 6 7 8 9

1 1 1 1 1 1

Page:76

第二阶段最优解:S2=3
S2
3

u2
0 1 2 3 4 5 6

本期成本

生产

存储

C2
1.5 5.5 6.5 7.5 8.5 9.5 10.5

S3 f3(S3) f2(S2)
0 1 2 3 4 5 6 11.0 10.5 8.0 8.0 8.0 8.0 5.0 12.5 16.0 14.5 15.5 16.5 17.5 15.5

0 4 5 6 7 8 9

1.5 1.5 1.5 1.5 1.5 1.5 1.5

Page:77

第二阶段最优解:S2=4
S2
4

u2
0 1 2 3 4 5

本期成本 生产 存储

C2
2 6 7 8 9 10

S3 f3(S3) f2(S2)
1 2 3 4 5 6 10.5 8.0 8.0 8.0 8.0 5.0 12.5 14 15 16 17 15

0 4 5 6 7 8

2 2 2 2 2 2

Page:78

第一阶段最优解
? 当k=1时,d1=2,S1=0
S1
0

u1
2 3 4 5 6

本期成本 生产 存储

C1
5 6 7 8 9

S2 f2(S2) f1(S1)
0 1 2 3 4 16.0 15.5 15.0 12.5 12.5 21 21.5 22 20.5 21.5

5 6 7 8 9

0 0 0 0 0

Page:79

最优解
? 从第一阶段向后反推最优路线,总结可得
时期 期初存货 期末存货 最优生 该期成本 总成本 产量 K Sk Sk+1 1 2 3 4 0 3 0 4 3 0 4 0 5 0 6 0 8 1.5 9 2 20.5 12.5 11 2

Page:80

设备更新问题
一台设备的价格为P,运行寿命为n年,每年的 维修费用是设备役龄的函数,记为C(t),新设 备的役龄为t=0。旧设备出售的价格是设备役龄 的函数,记为S(t)。在n年末,役龄为t的设备 残值为R(t)。现有一台役龄为T的设备,在使用 过程中,使用者每年都面临“继续使用”或 “更新”的策略。

Page:81

阶段k:运行年份;

状态变量sk:设备的役龄t;
决策变量xk:

?R (Re place)更新 xk ? ? ?K ( Keep)继续使用

状态转移方程:

xk ? R ?1 sk ?1 ? ? ? s k ? 1 xk ? K
? P ? C (0) ? S ( sk ) vk ? ? ?C ( sk ) ? P ? C (0) ? S (t ) ?? ?C (t ) xk ? R xk ? K xk ? R xk ? K

阶段指标:

Page:82

递推方程:

? P ? C (0) ? S ( sk ) ? f k ?1 ( sk ?1 ) f k ( sk ) ? min? ?C ( sk ) ? f k ?1 ( sk ?1 ) ? P ? C (0) ? S (t ) ? f k ?1 (1) ? min? ?C (t ) ? f k ?1 (t ? 1)
终端条件:

xk ? R xk ? K xk ? R xk ? K

fn(t)=-R(t)


赞助商链接
相关文章:
运筹学试卷A
运筹学试卷A - 学年第二 南阳理工学院 2011---2012 学年第二学期试卷 C.动态规划是基于最优化原理发展起来的 课程 运筹学 A卷 D.动态规划中多阶段决策问题...
更多相关文章: