第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
北航计算机研究生课程 算法设计与分析 Assignment_1.docx
一、 解：
设第 k 月的需求量为 Nk(k=1,2,3,4)
状态变量 Xk：第 k 月初的库存量，X1=X5=0，0≤Xk≤Nk+…+N4
决策变量 Uk：第 k 月的生产量，max{0，Nk-Xk}≤Uk≤min{6，Nk+…+N4 - Xk}
状态转移方程：Xk+1 = Uk + Xk – Nk
第 k 月的成本 Vk = 0.5*(Xk - Nk)
3 + Uk + 0.5*(Uk + Xk - Nk)
Uk=0
Uk≠0
设 Fk(Xk)是由第 k 月初的库存量 Xk 开始到第 4 月份结束这段时间的最优成本
则 Fk(Xk) = min{Vk + Fk+1(X k+1)}
1≤k≤4
= min{ 3 + Uk + 0.5*(Uk + Xk - Nk) + Fk+1(Uk + Xk - Nk) } Uk≠0
min{ 0.5*(Xk - Nk) + Fk+1(Xk - Nk) }
Uk=0
F5(X5)=0
四个月内的最优成本为 F1(X1)=F1(0)
详细计算步骤如下：
（1）k=4 时
0≤X4≤4，max{0，4 - X4}≤U4≤min{6，4-X4}
V4 + F5(X5)
X4
7=F4(0)
0
6=F4(1)
1
5=F4(2)
2
4=F4(3)
3
4
0=F4(4)
即对于状态 X4 的每个取值，都有唯一确定的决策变量 U4 使得 F4(X4)最优
F5(X5)
0
0
0
0
0
U4
4
3
2
1
0
V4
7
6
5
4
0
（2）k=3 时
0≤X3≤6，max{0，2 - X3}≤U3≤min{6，6-X3}
X3
0
X5
0
0
0
0
0
X4
0
1
2
3
4
0
1
2
3
4
0
U3
2
3
4
5
6
1
2
3
4
5
0
1
2
V3
5
6.5
8
9.5
11
4
5.5
7
8.5
10
0
F4(X4)
7
6
5
4
0
7
6
5
4
0
7
V3 + F4(X4)
12
12.5
13
13.5
11=F3(0)
11
11.5
12
12.5
10=F3(1)
7=F3(2)
1
2
3
4
0
1
2
3
0
1
2
0
1
0
1
2
3
4
1
2
3
4
2
3
4
3
4
4
4.5
6
7.5
9
0.5
5
6.5
8
1
5.5
7
1.5
6
3
3
4
5
6
（3）k=2 时
0≤X2≤9，max{0，3 - X2}≤U2≤min{6，9-X2}
X2
0
6
5
4
0
6
5
4
0
5
4
0
4
0
0
F3(X3)
11
10
7
6.5
11
10
7
6.5
6
11
10
7
6.5
6
5.5
11
10
7
6.5
6
5.5
2
10
7
6.5
10.5
11
11.5
9
6.5=F3(3)
10
10.5
8
6=F3(4)
9.5
7
5.5=F3(5)
6
2=F3(6)
V2 + F3(X3)
17
17.5
16=F2(0)
17
16
16.5
15=F2(1)
16
17
15
15.5
14=F2(2)
15
16
17
11=F2(3)
14.5
13
14
15
16
14
10.5=F2(4)
13
13
V2
6
7.5
9
10.5
5
6.5
8
9.5
11
4
5.5
7
8.5
10
11.5
0
4.5
6
7.5
9
10.5
12
0.5
5
6.5
U2
3
4
5
6
2
3
4
5
6
1
2
3
4
5
6
0
1
2
3
4
5
6
0
1
2
X3
0
1
2
3
0
1
2
3
4
0
1
2
3
4
5
0
1
2
3
4
5
6
1
2
3
1
2
3
4
3
4
5
0
1
2
3
4
0
1
2
3
0
1
2
0
1
0
4
5
6
2
3
4
5
6
3
4
5
6
4
5
6
5
6
6
5
6
7
8
9
（4）k=1 时
X1=0，max{0，2}≤U1≤min{6，11}
X1
0
U1
2
3
4
5
6
X2
0
1
2
3
4
8
9.5
11
1
5.5
7
8.5
10
1.5
6
7.5
9
2
6.5
8
2.5
7
3
V1
5
6.5
8
9.5
11
6
5.5
2
7
6.5
6
5.5
2
6.5
6
5.5
2
6
5.5
2
5.5
2
2
14
15
13
8=F2(5)
12
13
14
12
8=F2(6)
12
13
11
8=F2(7)
12
10
8=F2(8)
9
5=F2(9)
F2(X2)
16
15
14
11
10.5
V1 + F2(X2)
21
21.5
22
20.5=F1(0)
21.5
由以上计算可得，4 个月的总最优成本为 F1(0) = 20.5(千元)
从 k=1 回溯，可得最优结果中各阶段的状态变量 Xk 和决策变量 Uk 如下表：
每月成本 Vk
月份 k
1
9.5
0
2
11
3
4
0
月初库存量 Xk 需求量 Nk
0
3
0
4
产量 Uk
5
0
6
0
2
3
2
4
二、 解：
1、变量设定
阶段 k：已遍历过 k 个结点，k=1,2…6,7。
K=1 表示刚从 V1 出发，k=7 表示已回到起点 V1
状态变量 Xk=(i，Sk)：已遍历 k 个结点，当前位于 i 结点，还未遍历的结点集合
为 Sk。则 X1=(1，{2,3,4,5,6})，X6=(i，Φ)，X7=(1，Φ)
决策变量 Uk=(i，j)：已遍历 k 个结点，当前位于 i 结点，下一个结点选择 j。
状态转移方程：Xk+1 = T(Xk，Uk) = (j，Sk-{j})
第 k 阶段的指标函数 Vk = D[i,j]。
最优指标函数 Fk(Xk) = Fk(i，Sk)：已遍历 k 个结点，当前从 i 结点出发，访问 Sk
中的结点一次且仅一次，最后返回起点 V1 的最短距离。
F7(X7) = F7(1，Φ) = 0
则 Fk(i，Sk) = min{ D[i,j] + Fk+1(j，Sk-{j}) }
1≤k≤6
2、分析：
（1）k=6 时，F6(i，Φ) = min{D[i,1] + F7(X7)} = D[i,1]
i=2,3,4,5,6
X6=(i，Φ)
(2，Φ)
(3，Φ)
(4，Φ)
(5，Φ)
(6，Φ)
即 k=6 时，对于每一种状态 X6，都有唯一的决策 U6。
X7=(1，Φ)
(1，Φ)
(1，Φ)
(1，Φ)
(1，Φ)
(1，Φ)
U6=(i，j)
(2，1)
(3，1)
(4，1)
(5，1)
(6，1)
V6=D[i,j]
12
23
34
45
56
F7(1，Φ)
0
0
0
0
0
V6 + F7(X7)
12=F6(2,Φ)
23=F6(3,Φ)
34=F6(4,Φ)
45=F6(5,Φ)
56=F6(6,Φ)
（2）k=5 时，F5(i，S5) = min{D[i,j] + F6(j，Φ)}
X5=(i,S5)
(2,{6}}
(2,{5}}
(2,{4}}
(2,{3}}
(3,{6})
(3,{5})
(3,{4})
(3,{2})
(4,{6})
(4,{5})
(4,{3})
(4,{2})
(5,{6})
(5,{4})
(5,{3})
(5,{2})
(6,{5})
(6,{4})
X6=(j, Φ)
(6，Φ)
(5，Φ)
(4，Φ)
(3，Φ)
(6，Φ)
(5，Φ)
(4，Φ)
(2，Φ)
(6，Φ)
(5，Φ)
(3，Φ)
(2，Φ)
(6，Φ)
(4，Φ)
(3，Φ)
(2，Φ)
(5，Φ)
(4，Φ)
U5=(i,j)
(2,6)
(2,5)
(2,4)
(2,3)
(3,6)
(3,5)
(3,4)
(3,2)
(4,6)
(4,5)
(4,3)
(4,2)
(5,6)
(5,4)
(5,3)
(5,2)
(6,5)
(6,4)
V5=D[i,j]
21
25
30
18
15
10
5
19
16
8
4
32
18
10
11
27
12
20
i=2,3,4,5,6
F6(j,Φ)
56
45
34
23
56
45
34
12
56
45
23
12
56
34
23
12
45
34
V5 + F6(X6)
77=F5(2,{6})
70=F5(2,{5})
64=F5(2,{4})
41=F5(2,{3})
71=F5(3,{6})
55=F5(3,{5})
39=F5(3,{4})
31=F5(3,{2})
72=F5(4,{6})
53=F5(4,{5})
27=F5(4,{3})
44=F5(4,{2})
74=F5(5,{6})
44=F5(5,{4})
34=F5(5,{3})
39=F5(5,{2})
57=F5(6,{5})
54=F5(6,{4})
(6,{3})
(6,{2})
即 k=时，对于每一种状态 X5，都有唯一决策 U5。
(3，Φ)
(2，Φ)
(6,3)
(6,2)
16
22
23
12
39=F5(6,{3})
34=F5(6,{2})
（3）k=4 时，F4(i,S4) = min(D[i,j] + F5(j,S5) )
X4=(i,S4)
(2,{3,4})
(2,{4,5})
(2,{5,6})
(2,{3,5})
(2,{3,6})
(2,{4,6})
(3,{2,4})
(3,{2,5})
(3,{2,6})
(3,{4,5})
(3,{4,6})
(3,{5,6})
(4,{2,3})
(4,{2,5})
(4,{2,6})
(4,{3,5})
(4,{3,6})
(4,{5,6})
U4=(i,j)
(2,3)
(2,4)
(2,4)
(2,5)
(2,5)
(2,6)
(2,3)
(2,5)
(2,3)
(2,6)
(2,4)
(2,6)
(3,2)
(3,4)
(3,2)
(3,5)
(3,2)
(3,6)
(3,4)
(3,5)
(3,4)
(3,6)
(3,5)
(3,6)
(4,2)
(4,3)
(4,2)
(4,5)
(4,2)
(4,6)
(4,3)
(4,5)
(4,3)
(4,6)
(4,5)
X5=(j,S5)
(3,{4})
(4,{3})
(4,{5})
(5,{4})
(5,{6})
(6,{5})
(3,{5})
(5,{3})
(3,{6})
(6,{3})
(4,{6})
(6,{4})
(2,{4})
(4,{2})
(2,{5})
(5,{2})
(2,{6})
(6,{2})
(4,{5})
(5,{4})
(4,{6})
(6,{4})
(5,{6})
(6,{5})
(2,{3})
(3,{2})
(2,{5})
(5,{2})
(2,{6})
(6,{2})
(3,{5})
(5,{3})
(3,{6})
(6,{3})
(5,{6})
i=2,3,4,5,6
F5(j,S5)
39
27
53
44
74
57
55
34
71
39
72
54
64
44
70
39
77
34
53
44
72
54
74
57
41
31
70
39
77
34
55
34
71
39
74
V4 + F5(j,S5)
57=F4(2,{3,4})
57=F4(2,{3,4})
83
69=F4(2,{4,5})
99
78=F4(2,{5,6})
73
59=F4(2,{3,5})
89
60=F4(2,{3,6})
102
75=F4(2,{4,6})
83
49=F4(3,{2,4})
89
49=F4(3,{2,5})
96
49=F4(3,{2,6})
58
54=F4(3,{4,5})
77
69=F4(3,{4,6})
84
72=F4(3,{5,6})
73
34=F4(4,{2,3})
102
47=F4(4,{2,5})
109
50=F4(4,{2,6})
59
42=F4(4,{3,5})
75
55=F4(4,{3,6})
82
V4=D[i,j]
18
30
30
25
25
21
18
25
18
21
30
21
19
5
19
10
19
15
5
10
5
15
10
15
32
4
32
8
32
16
4
8
4
16
8
(5,{2,3})
(5,{2,4})
(5,{2,6})
(5,{3,4})
(5,{3,6})
(5,{4,6})
(6,{2,3})
(6,{2,4})
(6,{2,5})
(6,{3,4})
(6,{3,5})
(6,{4,5})
(4,6)
(5,2)
(5,3)
(5,2)
(5,4)
(5,2)
(5,6)
(5,3)
(5,4)
(5,3)
(5,6)
(5,4)
(5,6)
(6,2)
(6,3)
(6,2)
(6,4)
(6,2)
(6,5)
(6,3)
(6,4)
(6,3)
(6,5)
(6,4)
(6,5)
(6,{5})
(2,{3})
(3,{2})
(2,{4})
(4,{2})
(2,{6})
(6,{2})
(3,{4})
(4,{3})
(3,{6})
(6,{3})
(4,{6})
(6,{4})
(2,{3})
(3,{2})
(2,{4})
(4,{2})
(2,{5})
(5,{2})
(3,{4})
(4,{3})
(3,{5})
(5,{3})
(4,{5})
(5,{4})
16
27
11
27
10
27
18
11
10
11
18
10
18
22
16
22
20
22
12
16
20
16
12
20
12
57
41
31
64
44
77
34
39
27
71
39
72
54
41
31
64
44
70
39
39
27
55
34
53
44
（4）k=3 时，F3(i,S3) = min{D[i,j] + F4(j,S4)}
X3=(i,S3)
(2,{3,4,5})
i=2,3,4,5,6
V3=D[i,j]
18
30
25
18
30
21
18
25
21
30
25
21
19
5
F4(j,S4)
54
42
37
69
55
47
72
57
46
73
72
56
69
47
U3=(i,j)
(2,3)
(2,4)
(2,5)
(2,3)
(2,4)
(2,6)
(2,3)
(2,5)
(2,6)
(2,4)
(2,5)
(2,6)
(3,2)
(3,4)
X4=(j,S4)
(3,{4,5})
(4,{3,5})
(5,{3,4})
(3,{4,6})
(4,{3,6})
(6,{3,4})
(3,{5,6})
(5,{3,6})
(6,{3,5})
(4,{5,6})
(5,{4,6})
(6,{4,5})
(2,{4,5})
(4,{2,5})
(2,{3,4,6})
(2,{3,5,6})
(2,{4,5,6})
(3,{2,4,5})
73=F4(4,{5,6})
68
42=F4(5,{2,3})
91
54=F4(5,{2,4})
104
52=F4(5,{2,6})
50
37=F4(5,{3,4})
82
57=F4(5,{3,6})
82
72=F4(5,{4,6})
63
47=F4(6,{2,3})
86
64=F4(6,{2,4})
92
51=F4(6,{2,5})
55
47=F4(6,{3,4})
71
46=F4(6,{3,5})
73
56=F4(6,{4,5})
V3 + F4(j,S4)
72
72
62=F3(2,{3,4,5})
87
85
68=F3(2,{3,4,6})
90
82
67=F3(2,{3,5,6})
103
97
77=F3(2,{4,5,6})
88
52=F3(3,{2,4,5})
(3,{2,4,6})
(3,{2,5,6})
(3,{4,5,6})
(4,{2,3,5})
(4,{2,3,6})
(4,{2,5,6})
(4,{3,5,6})
(5,{2,3,4})
(5,{2,3,6})
(5,{2,4,6})
(5,{3,4,6})
(6,{2,3,4})
(6,{2,3,5})
(6,{2,4,5})
(3,5)
(3,2)
(3,4)
(3,6)
(3,2)
(3,5)
(3,6)
(3,4)
(3,5)
(3,6)
(4,2)
(4,3)
(4,5)
(4,2)
(4,3)
(4,6)
(4,2)
(4,5)
(4,6)
(4,3)
(4,5)
(4,6)
(5,2)
(5,3)
(5,4)
(5,2)
(5,3)
(5,6)
(5,2)
(5,4)
(5,6)
(5,3)
(5,4)
(5,6)
(6,2)
(6,3)
(6,4)
(6,2)
(6,3)
(6,5)
(6,2)
(6,4)
(6,5)
(5,{2,4})
(2,{4,6})
(4,{2,6})
(6,{2,4})
(2,{5,6})
(5,{2,6})
(6,{2,5})
(4,{5,6})
(5,{4,6})
(6,{4,5})
(2,{3,5})
(3,{2,5})
(5,{2,3})
(2,{3,6})
(3,{2,6})
(6,{2,3})
(2,{5,6})
(5,{2,6})
(6,{2,5})
(3,{5,6})
(5,{3,6})
(6,{3,5})
(2,{3,4})
(3,{2,4})
(4,{2,3})
(2,{3,6})
(3,{2,6})
(6,{2,3})
(2,{4,6})
(4,{2,6})
(6,{2,4})
(3,{4,6})
(4,{3,6})
(6,{3,4})
(2,{3,4})
(3,{2,4})
(4,{2,3})
(2,{3,5})
(3,{2,5})
(5,{2,3})
(2,{4,5})
(4,{2,5})
(5,{2,4})
10
19
5
15
19
10
15
5
10
15
32
4
8
32
4
16
32
8
16
4
8
16
27
11
10
27
11
18
27
10
18
11
10
18
22
16
20
22
16
12
22
20
12
54
75
50
64
78
52
51
73
72
56
59
49
42
60
49
47
78
52
51
72
57
46
57
49
34
60
49
47
75
50
64
69
55
47
57
49
34
59
49
42
69
47
54
64
94
55=F3(3,{2,4,6})
79
97
62=F3(3,{2,5,6})
66
78
82
71=F3(3,{4,5,6})
91
53
50=F3(4,{2,3,5})
92
53=F3(4,{2,3,6})
63
110
60=F3(4,{2,5,6})
67
76
65
62=F3(4,{3,5,6})
84
60
44=F3(5,{2,3,4})
87
60=F3(5,{2,3,6})
65
102
60=F3(5,{2,4,6})
82
80
65=F3(5,{3,4,6})
65=F3(5,{3,4,6})
79
65
54=F3(6,{2,3,4})
81
65
54=F3(6,{2,3,5})
91
67
66=F3(6,{2,4,5})
(6,{3,4,5})
(6,3)
(6,4)
(6,5)
(3,{4,5})
(4,{3,5})
(5,{3,4})
16
20
12
54
42
37
70
62
49=F3(6,{3,4,5})
（5）k=2 时，F2(i,S2) = min{D[i,j] + F3(j,S3)}
X2=(i,S2)
(2,{3,4,5,6})
X3=(j,S3)
(3,{4,5,6})
(4,{3,5,6})
(5,{3,4,6})
(6,{3,4,5})
(2,{4,5,6})
(4,{2,5,6})
(5,{2,4,6})
(6,{2,4,5})
(2,{3,5,6})
(3,{2,5,6})
(5,{2,3,6})
(6,{2,3,5})
(2,{3,4,6})
(3,{2,4,6})
(4,{2,3,6})
(6,{2,3,4})
(2,{3,4,5})
(3,{2,4,5})
(4,{2,3,5})
(5,{2,3,4})
U2=(i,j)
(2,3)
(2,4)
(2,5)
(2,6)
(3,2)
(3,4)
(3,5)
(3,6)
(4,2)
(4,3)
(4,5)
(4,6)
(5,2)
(5,3)
(5,4)
(5,6)
(6,2)
(6,3)
(6,4)
(6,5)
U1=(1,j)
(1,2)
(1,3)
(1,4)
(1,5)
(1,6)
V2=D[i,j]
18
30
25
21
19
5
10
15
32
4
8
16
27
11
10
18
22
16
20
12
i=2,3,4,5,6
F3(j,S3)
71
62
65
49
77
60
60
66
67
62
60
54
68
55
53
54
62
52
50
44
V2 + F3(j,S3)
89
92
90
70=F2(2,{3,4,5,6})
96
65=F2(3,{2,4,5,6})
70
81
99
66=F2(4,{2,3,5,6})
68
70
95
66
63=F2(5,{2,3,4,6})
72
84
68
70
56=F2(6,{2,3,4,5})
F2(j,S2)
70
65
66
63
56
V1 + F2(j,S2)
80=F1(1,{2,3,4,5,6})
85
96
103
106
(3,{2,4,5,6})
(4,{2,3,5,6})
(5,{2,3,4,6})
(6,{2,3,4,5})
（6）k=1 时，F1(1,S1) = min{D[1,j] + F2(j,S2)}
X1=(1,S1)
(1,{2,3,4,5,6})
X2=(j,S2)
(2,{3,4,5,6})
(3,{2,4,5,6})
(4,{2,3,5,6})
(5,{2,3,4,6})
(6,{2,3,4,5})
V1=D[1,j]
10
20
30
40
50
3、伪代码和时间复杂度
为方便计算，结点编号改为 0 到 5.
(1)用一张二维表格 F[][]表示 F(i,Sk)，行数是 n，列数是 2n-1。
(2)行号表示当前所在的结点 i。
列号对应的五位二进制表示表示{V5,V4,V3,V2,V1}的一个子集，1 表示在集合中，0
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
