第六章 课后习题——运筹学课件PPT

, ,
if if
xk 1; xk 0.
效益函数fk(sk)：第k阶段以后采用最优策略所能获得
的利润总额
阶段效益函数
d
k
(
sk
,
xk
)
8sk 5sk
, ,
if if
xk 1; xk 0.
当k=6时 f6 (s6 ) 0
当k=5时
f5 (s5 )
max
d d
k k
( (
s5 s5
,1) ,1)
max85ss33
12.6T3 12.6T3
(s3 (s3
,1) ,0)
max85ss33
12.6 12.6
* *
0.7s3 0.9s3
16.82s3
最优决策是: x3*=1。
当k=2时
f2 (s2 )
max
d2 (s2 ,1) d2 (s2 ,0)
f3 (s3 ) f3 (s3 )
max85ss22
f3 f3
(T2 (T2
(s2 (s2
,1)) ,0))
max85ss22
16.82T2 16.82T2
(s2 (s2
,1) ,0)
max85ss22
16.82 16.82
* *
0.7s2 0.9s2
20.138s3
最优决策是: x2*=0。
当k=1时
f1(s1)
f1 (1000)
最优决策是: x1*=0。 最优策略是：前两年低负荷生产，后三年高负荷生产。
x2*
s2 1 3
当k=1时：
f1(s1)
f1 (3)
min {x2
0 x1 3 1
2x1
f2 (s2 )}
min {x2
0 x1 3 1
2x1
f2 (s1
x1)}
min {x2
0 x1 3 1
2 x1
2(3
x1 ) 2
8(3 3
x1 )
1}
4
x2*
s2 1 3
1
x1* 1
x3* 1
min F 4
6.3 有四台设备分给甲，乙，丙，丁四厂，各厂盈 利如下表。如何分配使总盈利最大？
盈利 工厂 甲
乙
丙
丁
设备
0 1 2 3 4
0
0
0
0
3
4
5
6
10
7
8
9
13
14
11
12
16
17
18
15
解：阶段n=4，每个阶段决定一个工厂的设备数；
决策变量xk：分配给工厂k的专家数； 状态变量sk：第k 阶段初剩余的专家数； 可行决策集合：Xk={xk|0 ≤ xk ≤ sk} 状态转移方程：sk+1=sk-xk 阶段效益函数vk(xk)：给第k个厂xk台设备获得的盈利； 最优过程效益函数fk(sk):第k阶段初剩余sk台设备能获得
f f
6 6
(s6 (s6
) )
max85ss55
f6 f6
(s6 (s6
) )
max
85ss55
8s5
最优决策是: x5*=1。
当k=4时
f4 (s4 )
max
dd44((ss44,,10))
ff55((ss55))
max85ss44
f5 f5
(T4 (T4
(s4 (s4
,1)) ,0))
当k=3时：
f3 (s3 ) mx3 asx3 {x3} s3
x3* s3
当k=2时：
f2
(s2
)
max {x2
0x2 s2 2
f3
(s3 )}
max {x2
0x2 s2 2
f3 (s2
x2
)}
max {x2
0x2 s2 2
(s2
x2
)}
4 27
s23
x2*
2 3
s2
当k=1时：
f1(s1) f1(4) 0mxa1x4{x1 f2 (s2 )} 0mxa1x4{x1 f2 (4 x1)}
max
dd11((11000000,,10))
ff22((ss22))
8000 max5000
f2 (T1(1000, f2 (T1(1000,
1)) 0))
8000 max5000
20.138T1 (1000, 20.138T1 (1000,
1) 0)
8000 20.138* 700 max5000 20.138*900 23124.2
第六章 动态规划
6.1 试用动态规划方法求解从Q到T的最短路。
5
7
B3
A1
5
9 Q
2
7
A2
B1
4 B2
A3
8
6
B
3 C1
11
C2
C3 5
T0
6.2（1）
解：阶段数n=3,第k阶段决定变量xk的值； 决策变量xk
状态变量sk：第k阶段初剩余未决策变量的取值之和； 状态转移方程：sk+1=sk-xk
min{x 2
x3 s3 3
2 x3 }
s2 3
2s3
当k=2时：
x3* s3
f2 (s2 )
min {2x2
0x2 s2
2
4x2
f3 (s2
2
4x2
s2 3
2s3 )}
min {2x2
0x2 s2
2
4x2
(s2
x2 )2
2(s2
x2
))}
2s22 8s2 1 3
0 00
00
所以最优策略是： 工厂甲分配两个专家，工厂丙、丁各一个专家，
工厂乙没有专家，总利润为21。
6.5 机器负荷问题
解：阶段n=5，以年度划分阶段；
决策变量xk：
xk
1， 高负荷生产 0， 低负荷生产
状态变量sk：第k 阶段初剩余的完好机器数；
状态转移方程
sk
1
Tk
(sk
,
xk
)
00..97sskk
的总利润。
20 4
0
4 18 0
4 15
17 14
15 3
0
4
14 03
21
3
11
7
11
然1后4 标出阶段4 指标函数11 8
4 10 2 0
20
4
7
5
13
最后求出最优策略
7
8
6
16
1
0
6 10
4
5
5
首先画出状态点
0
3然1后及2 画状出态15可转选移决方策程，
8
12
5
9
29
0
11
0
6
16 0
18
00 0
max{
0 x14
x1
4(4 x1)3 27
}
4
x1* 1
x2*
2 3
s2
2
x3* 1
max F 4
6.2（2）
解：阶段数n=3,第k阶段决定变量xk的值； 决策变量xk
状态变量sk：第k阶段初剩余未决策变量的取值之和； 状态转移方程：sk+1=sk-xk
当k=3时：
f3 (s3 )
max85ss44
8T4 8T4
(s4 (s4
,1) ,0)
max
85ss44
8 8
* *
0.7s4 0.9s4
12.6s4
最优决策是: x4*=1。
当k=3时
f3 (s3 )
max
dd33((ss33,,10))
ff44((ss44))
max
8s3 5s3
f4 (T3 (s3,1)) f4 (T3 (s3,0))