运筹学全书习题答案.doc

运筹学全书习题答案

配套教材参考答案
↓
↓
↓
↓
↓
↓

请勿盗版 尊重作者

第1章参考答案

1.1 用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。
（1）有唯一最优解，最优值。 (2)问题有无界解。

1.1（1） 1.1（2）
(3)有唯一最优解，最优值。
(4)有无穷多最优解，，最优值。

1.1（3） 1.1（4）
1.2 将下列线性规划问题化成标准型。
(1) (2)
1.3 用单纯形法求解下述问题。
（1)先将问题化为标准型： ，然后用单纯形法求解如下：
Cj→
10
6
4
0
0
0
CB
xB
b
x1
x2
x3
x4
x5
x6
0
0
0
x4
x5
x6
100
600
150
1
10
1
1
4
1
1
5
3
1
0
0
0
1
0
0
0
1
σj
10
6
4
0
0
0
0
10
0
x4
x1
x6
40
60
90
0
1
0
3/5
2/5
3/5
1/2
1/2
5/2
1
0
0
-1/10
1/10
-1/10
0
0
1
σj
0
2
-1
0
-1
0
6
10
0
x4
x1
x6
200/3
100/3
50
0
1
0
1
0
0
5/6
1/6
2
5/3
-2/3
-1
-1/6
1/6
0
0
0
1
σj
0
0
-8/3
-10/3
-2/3
0
问题有唯一最优解，最优值。
(2)先将问题化为标准型，，再用单纯形法求解。过程如下：
Cj→
10
6
0
0
CB
xB
b
x1
x2
x3
x4
0
0
x3
x4
15
24
3
6
5
2
1
0
0
1
σj
2
1
0
0
0
2
x3
x1
3
4
0
1
4
1/3
1
0
-1/2
1/6
σj
0
1/3
0
-1/3
1
2
x2
x1
3/4
15/4
0
1
1
0
1/4
-1/12
-1/8
5/24
σj
0
0
-1/12
-7/24
问题有唯一最优解，最优值。

1.4 分别用单纯形法中的大M法和两阶段法求解下列线性规划问题。
(1)用大M法求解，过程如下：
先构造辅助问题：
Cj→
1
-1
1
-M
-M
CB
xB
b
x1
x2
x3
x4
x5
-M
-M
x4
x5
6
6
1
4
2
5
2
-6
1
0
0
1
σj
1+5M
-1+7M
1-4M
0
0
-M
-1
x4
x2
18/5
6/5
-3/5
4/5
0
1
22/5
-6/5
1
0
/
/
σj
9/5-3M/5
0
-1/5+22M/5
0
/
1
-1
x3
x2
9/11
24/11
-3/22
7/11
0
1
1
0
/
/
/
/
σj
39/22
0
0
/
/
1
1
x3
x1
9/7
24/7
0
1
3/14
11/7
1
0
/
/
/
/
σj
0
-39/14
0
/
/
由上表可知，辅助问题有最优解，且人工变量，故原问题有唯一最优解，最优值。
用两阶段法求解上述问题，过程如下：
先构造辅助问题：
Cj→
0
0
0
-1
-1
CB
xB
b
x1
x2
x3
x4
x5
-1
-1
x4
x5
6
6
1
4
2
5
2
-6
1
0
0
1
σj
5
7
-4
0
0
-1
0
x4
x2
18/5
6/5
-3/5
4/5
0
1
22/5
-6/5
1
0
/
/
σj
-3/5
0
22/5
0
/
0
0
x3
x2
9/11
24/11
-3/22
7/11
0
1
1
0
/
/
/
/
σj
0
0
0
/
/

由上表可知，辅助问题有最优解，且人工变量，因此得到原问题的一个可行解，重新计算原问题的检验数，并用单纯形法继续求解。
Cj→
1
-1
1
0
0
x3
x2
9/11
24/11
-3/22
7/11
0
1
1
0
σj
39/22
0
0
1
1
x3
x1
9/7
24/7
0
1
3/14
11/7
1
0
σj
0
-39/14
0
故原问题有唯一最优解，最优值。
(2) 用大M法求解，过程如下：
先构造辅助问题：
Cj→
-2
-3
-1
0
0
-M
-M
CB
xB
b
x1
x2
x3
x4
x5
x6
x7
-M
-M
x6
x7
8
6
1
3
4
2
2
0
-1
0
0
-1
1
0
0
1
σj
-2+4M
-3+6M
-1+2M
-M
-M
0
0
-3
-M
x2
x7
2
2
1/4
5/2
1
0
1/2
-1
-1/4
1/2
0
-1
/
/
0
1
σj

-5/4+5M/2
1/2-M
-3/4+M/2
-M
/
0
-3
-2
x2
x1
9/5
4/5
0
1
1
0
3/5
-2/5
-3/10
1/5
1/10
-2/5
/
/
/
/
σj
0
0
0
-1/2
-1/2
/
/
由上表可知，辅助问题有最优解，且人工变量，故原问题有最优解，最优值。又，可再进行一次迭代，以取代作为基变量，检验数不变，因此问题有无穷多最优解。
Cj→
-2
-3
-1
0
0
-M
-M
CB
xB
b
x1
x2
x3
x4
x5
x6
x7
-1
-2
x3
x1
3
2
0
1
5/3
2/3
1
-0
-1/2
0
1/6
-1/3
/
/
/
/
σj
0
0
0
-1/2
-1/2
/
/

用两阶段法求解上述问题，过程如下：
先构造辅助问题：
Cj→
0
0
0
0
0
-1
-1
CB
xB
b
x1
x2
x3
x4
x5
x6
x7
-1
-1
x6
x7
8
6
1
3
4
2
2
0
-1
0
0
-1
1
0
0
1
σj
4
6
2
-1
-1
0
0
0
-1
x2
x7
2
2
1/4
5/2
1
0
1/2
-1
-1/4
1/2
0
-1
/
/
0
1
σj
5/2
0
-1
1/2
-1
/
0
-3
-2
x2
x1
9/5
4/5
0
1
1
0
3/5
-2/5
-3/10
1/5
1/10
1/5
/
/
/
/
σj
0
0
0
0
0
/
/
辅助问题有最优解，且人工变量，故原问题有基可行解。重新计算检验数：
Cj→
0
0
0
0
0
CB
xB
b
x1
x2
x3
x4
x5
-3
-2
x2
x1
9/5
4/5
0
1
1
0
3/5
-2/5
-3/10
1/5
1/10
1/5
σj
0
0
0
-1/2
-1/2
因检验数，故即为问题的最优解，最优值。又，可再进行一次迭代，以取代作为基变量，检验数不变，因此问题有无穷多最优解。
(3) 用大M法求解，过程如下：
先构造辅助问题：
Cj→
-4
-1
0
0
-M
-M
CB
xB
b
x1
x2
x3
x4
x5
x6
-M
-M
0
x5
x6
x4
3
6
4
3
4
1
1
3
2
0
-1
0
0
0
1
1
0
0
0
1
0
σj
-4+7M
-1+4M
-M
0
0
0
-4
-M
0
x1
x6
x4
1
2
3
1
0
0
1/3
5/3
5/3
0
-1
0
0
0
1
/
/
/
0
1
0
σj
0
1/3+5M/3
-M
0
/
0
-4
-1
0
x1
x2
x4
3/5
6/5
1
1
0
0
0
1
0
1/5
-3/5
1
0
0
1
/
/
/
/
/
/
σj
0
0
1/5
0
/
/
-4
-1
0
x1
x2
x3
2/5
9/5
1
1
0
0
0
1
0
0
0
1
-1/5
3/5
1
/
/
/
/
/
/
σj
0
0
1/5
-1/5
/
/
由上表可知，辅助问题有最优解，且人工变量，故原问题有最优解，最优值。
用两阶段法求解上述问题，过程如下：
先构造辅助问题：
Cj→
0
0
0
0
-1
-1
CB
xB
b
x1
x2
x3
x4
x5
x6
-1
-1
0
x5
x6
x4
3
6
4
3
4
1
1
3
2
0
-1
0
0
0
1
1
0
0
0
1
0
σj
7
4
-1
0
0
0
0
-1
0
x1
x6
x4
1
2
3
1
0
0
1/3
5/3
5/3
0
-1
0
0
0
1
/
/
/
0
1
0
σj
0
5/3
-1
0
/
0
0
0
0
x1
x2
x4
3/5
6/5
1
1
0
0
0
1
0
1/5
-3/5
1
0
0
1
/
/
/
/
/
/
σj
0
0
0
0
/
/
辅助问题有最优解，且人工变量，故是原问题的一个基可行解。重新计算检验数：
Cj→
-4
-1
0
0
CB
xB
b
x1
x2
x3
x4
-4
-1
0
x1
x2
x4
3/5
6/5
1
1
0
0
0
1
0
1/5
-3/5
1
0
0
1
σj
0
0
1/5
0
-4
-1
0
x1
x2
x3
2/5
9/5
1
1
0
0
0
1
0
0
0
1
-1/5
3/5
1
σj
0
0
0
-1/5
检验数，所以原问题有最优解，最优值。

(4) 用大M法求解，过程如下：
先构造辅助问题：
Cj→
10
15
12
0
0
0
-M
CB
xB
b
x1
x2
x3
x4
x5
x6
x7
0
0
-M
x4
x5
x7
9
15
5
5
-5
2
3
6
1
1
15
1
1
0
0
0
1
0
0
0
-1
0
0
1
σj
10+2M
15+M
12+M
0
0
-M
0
10
0
-M
x1
x5
x7
9/5
24
7/5
1
0
0
3/5
9
-1/5
1/5
16
3/5
1/5
1
-2/5
0
1
0
0
0
-1
0
0
1
σj
0
6-M/5
10+3M/5
-2-2M/5
0
-M
0
10
12
-M
x1
x3
x7
3/2
3/2
1/2
1
0
0
39/80
9/16
-43/80
0
1
0
3/16
1/16
-7/16
-1/80
1/16
-3/80
0
0
-1
0
0
1
σj
0
27/8-43M/80
0
-21/8-7M/16
-5/8-3M/80
-M
0
由上表可知，辅助问题有最优解，但人工变量，故原问题不可行。
用两阶段法求解上述问题，过程如下：
先构造辅助问题：
Cj→
0
0
0
0
0
0
-1
CB
xB
b
x1
x2
x3
x4
x5
x6
x7
0
0
-1
x4
x5
x7
9
15
5
5
-5
2
3
6
1
1
15
1
1
0
0
0
1
0
0
0
-1
0
0
1
σj
2
1
1
0
0
-1
0
0
0
-1
x1
x5
x7
9/5
24
7/5
1
0
0
3/5
9
-1/5
1/5
16
3/5
1/5
1
-2/5
0
1
0
0
0
-1
0
0
1
σj
0
-1/5
3/5
-2/5
0
-1
0
0
0
-1
x1
x3
x7
3/2
3/2
1/2
1
0
0
39/80
9/16
-43/80
0
1
0
3/16
1/16
-7/16
-1/80
1/16
-3/80
0
0
-1
0
0
1
σj
0
-43/80
0
-7/16
-3/80
-1
0
检验数，所以辅助问题有最优解。但人工变量，故原问题不可行。

1.5 设为每吨合金中矿物的含量（吨）。建立线性规划模型如下：

1.6 当,,,,,,,时，目标函数最优值取得最小值。求解线性规划

得最优解，最优值。
当,,,,,,,时，目标函数最优值取得最大值。求解线性规划

得最优解（不唯一），最优值。
因此原问题目标函数最优值的下界为32/5，上界为21。
1.7设工厂每天生产A、B、C三种型号的产品分别为、、件。建立数学模型如下：

1.8 设该公司投资于债券的金额为，建立该问题的数学模型如下：

章末习题

2.1 写出下列线性规划问题的对偶问题
⑴ ⑵
⑶ ⑷
2.2 判断下面说法是否正确，为什么？
⑴错误。如果线性规划的原问题存在可行解但有无界解，则其对偶问题不可行。
⑵错误。如果线性规划的对偶问题无可行解，原问题可能有无界解，也可能无可行解。
⑶错误。在互为对偶的一对原问题与对偶问题中，如原问题求最小值，则其可行解的目标函数值一定不小于其对偶问题（求最小值）可行解的目标函数值。
⑷正确。对偶问题可能有不同形式，但实质上都是同一问题。
2.3 给出线性规划问题
⑴其对偶问题为
⑵证明：易知是对偶问题的一个可行解，其对应的目标函数值。
又观察可知，是原问题的一个可行解，所以原问题可行，根据弱对偶性知，。
2.4 证明：先写出对偶问题：
显然，时，，这与矛盾。因此对偶问题无可行解。
由观察可知是原问题的一个可行解，故原问题有可行解而对偶问题无可行解，由弱对偶性的推论（3）知，原问题目标函数值无界。
2.5 先写出对偶问题
将最优解代入各约束条件中，分别有
根据互补松弛性，得
解得原问题的最优解为。
2.6先写出对偶问题
将最优解代入各约束条件中，分别有
根据互补松弛性，得
解得原问题的最优解为。
2.7 （1）因为只有两个主约束，故基变量有两个，其他均为非基变量，
即约束（2）的松弛变量为非基变量。
因此约束条件（2）应为
将上式，得。故
（2）
（3）根据互补松弛性，，故
又，两式联立解方程组得。
2.8 用对偶单纯形法求解下列线性规划问题
⑴
Cj→
-3
-4
-5
0
0
CB
xB
b
x1
x2
x3
x4
x5
0
0
x4
x5
-8
-10
-1
-2
-2
-2
-3
-1
1
0
0
1
σj
-3
-4
-5
0
0
0
-3
x4
x1
-3
5
0
1
-1
1
-5/2
1/2
1
0
-1/2
-1/2
σj
0
-1
-7/2
0
-3/2
-4
-3
x2
x1
3
2
0
1
1
0
5/2
-2
-1
1
1/2
-1
σj
0
0
-1
-1
-1
因此问题的最优解为，。
⑵
Cj→
-5
-2
-4
0
0
CB
xB
b
x1
x2
x3
x4
x5
0
0
x4
x5
-4
-10
-3
-6
-1
-3
-2
-5
1
0
0
1
σj
-5
-2
-4
0
0
-5
0
x1
x5
4/3
-2
1
0
1/3
-1
2/3
-1
-1/3
-2
0
1
σj
0
-1/3
-2/3
-5/3
0
-5
-2
x1
x2
2/3
2
1
0
0
1
1/3
1
-1
2
1/3
-1
σj
0
0
-1/3
-1
-1/3
因此问题的最优解为，。
2.9 先用单纯形法求解该线性规划问题，得最优单纯形表如下：
Cj→
-5
5
13
0
0
CB
xB
b
x1
x2
x3
x4
x5
5
0
x2
x5
20
10
-1
16
1
0
3
-2
1
-4
0
1
σj
0
0
-2
-5
0
因此问题的最优解为，。
⑴由20变为45，，因此最优解发生变化。
用对偶单纯形法求解，得
Cj→
-5
5
13
0
0
CB
xB
b
x1
x2
x3
x4
x5
0
13
x4
x3
18
9
-23/5
6/5
-1/5
2/5
0
1
1
0
-3/10
1/10
σj
-103/5
-1/5
0
0
-13/10
新的最优解为，。
⑵由90变为70，，因此最优解发生变化。
用对偶单纯形法求解，得
Cj→
-5
5
13
0
0
CB
xB
b
x1
x2
x3
x4
x5
5
13
x2
x3
5
5
23
-8
1
0
0
1
-5
2
3/2
-1/2
σj
-16
0
0
-1
-1
新的最优解为，。
⑶由13变为8，仅的检验数发生变化：，最优解不变。
⑷由5变为6，因是基变量，所有检验数都发生变化，重新求检验数：
Cj→
-5
6
13
0
0
CB
xB
b
x1
x2
x3
x4
x5
6
0
x2
x5
20
10
-1
16
1
0
3
-2
1
-4
0
1
σj
1
0
-5
-6
0
6
-5
x2
x1
165/8
5/8
0
1
1
0
23/8
-1/8
3/4
-1/4
1/16
1/16
σj
0
0
-2
-5
0
新的最优解为，。
⑸增加变量（），，
，故最优解不变，仍为。
⑹增加一个约束条件，将原最优解代入该约束条件中：
，所以原最优解不再是可行解。
Cj→
-5
5
13
0
0
0
CB
xB
b
x1
x2
x3
x4
x5
x6
5
0
0
x2
x5
x6
20
10
50
-1
16
2
1
0
3
3
-2
5
1
-4
0
0
1
0
0
0
1
σj
0
0
-2
-5
0
0
5
0
0
x2
x5
x6
20
10
-10
-1
16
5
1
0
0
3
-2
-4
1
-4
-3
0
1
0
0
0
1
σj
0
0
-2
-5
0
0
5
0
13
x2
x5
x3
25/2
15
5/2
11/4
27/2
-5/4
1
0
0
0
0
1
-5/4
-5/2
3/4
0
1
0
3/4
-1/2
-1/4
σj
-5/2
0
0
-7/2
0
-1/2
新的最优解为，。
⑺的系数列向量由变为，，
，故原最优解不变, 。

章末习题
3.1总运费最省的调运方案为：
销售地
生产地
B1
B2
B3
生产量（吨）
A1

3
1
4
A2

7
7
A3
2

0
2
需求量（吨）
2
3
8
13
最低总运费为57。
3.2该问题的最优调运方案为：
销售地
生产地
B1
B2
B3
B4
生产量（吨）
A1

4
0
3
7
A2
6
2

8
A3

3

3
需求量（吨）
6
6
3
3
18
总运费为89。
3.3最优调运方案为：
销售地
生产地
B1
B2
B3
B4
生产量（吨）
A1
3

3
A2
3

2

5
A3

3
0
4
7
需求量（吨）
6
3
2
4
15
总运费为40。
3.4最优调运方案如下表，总运费为204。
销售地
生产地
B1
B2
B3
B4
生产量（吨）
A1
5
2
3

10
A2

5

3
8
A3

5

5
需求量（吨）
5
7
8
3
23

3.5 总的运输费用最低的调运方案如下表，其中B1城市少供应30万吨，B3城市少供应40万吨。
城市
企业
B1
B2
B3
生产量（万吨）
A1
150
250

400
A2
140

310
450
需求量（万吨）
320
250
350

总运费为14650。
3.6总运输费用最低的产品调运方案如下表所示，最低运输费用为5900。

A3
A4
A5
A6
A7
A8
产量
A1
700
100

800
A2

100

400
500
A3
600

400

300

1300
A4

1100

200

1300
需求量（吨）
1300
1300
400
200
300
400
3900

章末习题

4.1 设、、分别表示A、B、C三种规格的电视机的产量。

4.2设、分别表示A、B两种电视机的产量。

4.3设、分别表示甲、乙两种仪器的产量。

4.4 用图解法求解下列目标规划问题：
⑴满意解为，。

⑵连接点与点的线段AB上所有的点都是问题的满意解，。
其中A点对应的偏差变量值为；
B点对应的偏差变量值为。

4.5 用单纯形法求解下列目标规划：
⑴问题的满意解为，。

0
0

0
0

0

0

2
1
1

1/2
-1/2

0

1

-1
1
1/2
-1/2

38

-10

-3
3
1
-1

1

1

10

3
-3

1

(2)问题的满意解为，。

0
0
0

0

0

55

1
-1
1

30

-1

2
-2
-1
1
0

45
1
1

1
-1

1

1

-2
2
2

4.6满意解为，，。

章末习题
5.1 60单位长的标准玻璃纸裁为45、20、15三种规格，有五种裁剪方式：
方式
45
20
15
废料
1
2
3
4
5
1
0
0
0
0
0
3
2
1
0
1
0
1
2
4
0
0
5
10
0
设（）表示采用第种方式裁剪的标准玻璃纸的数量。建立模型如下：

5.2 设（）表示三种产品的产量。

5.3 设（）表示三种金属容器A、B、C的产量。

5.4 设

5.5⑴先用单纯形法求得松弛问题的最优解，结果如下表所示。

1
1
0
0

b

1

5/3
1
0
1/3
-1/3
1

5/2
0
1
0
1/2

0
0
-1/3
-1/6
以所在行为源行的割平面为，引入松弛变量加入上表中，求解得

1
1
0
0
0

b

1
1
0

2
2
1
1
0
0
0
1
0
1/2
-1/4
1/2
0
0
1
-1/2
3/4
-3/2

0
0
-1/4
0
-1/4
因此，原整数规划问题的最优解为，其最优值为。
（2）先用单纯形法求得松弛问题的最优解，结果如下表所示。

1
1
0
0

b

4

9/5
1
0
2/5
-1/5
5

23/10
0
1
-1/10
3/10

0
0
-11/10
-7/10
以所在行为源行的割平面为，引入松弛变量加入上表中，求解得

1
1
0
0
0

b

4
5
0

2
2
1
1
0
0
0
1
0
1/2
-1/4
1/2
0
0
1
-1/4
3/8
-5/4

0
0
-3/4
0
-7/8
因此，原整数规划问题的最优解为，其最优值为。

5.6 ⑴先用单纯形法原整数规划问题的松弛问题，最优解为不是整数。将和分别加入松弛问题中形成两个子问题，分别求解得和，前者是整数解，故其最优值构成原整数规划问题最优值的下界。而后者最优值。但因目标函数中价格系数均为整数，故当、均取整数时，目标函数值也应为整数。而不超过26/5的整数中最大的就是5，因此原整数规划问题的最优解为，最优值。（对（LP2）继续分支可得到另一个最优解）
⑵先用单纯形法原整数规划问题的松弛问题，最优解为不是整数。将和分别加入松弛问题中形成两个子问题，分别求解得和，均不是整数解，前者最优值，后者最优值，故取（LP2）进一步分支：和。这一分支的最优解为，，仍不是整数解；而这一分支不可行，因此进行剪支。继续对（LP21）进行分支：和，分别得到最优解和，最优值分别为和。由于为整数解，其函数值，因此（LP1）的进一步分支不可能得到比它更优的整数解，对（LP1）进行剪支。而虽大于14，但其中的整数解的目标函数值也不可能超过14，因此不必再进一步分支。至此，松弛问题的全部子问题均已考察完毕，保留下来的整数解即为原整数规划问题的最优解，最优值。
5.7 ⑴，。 ⑵，。
5.8 虚设一人，成本矩阵为，用匈牙利算法求得，即安排甲做B，乙做C和D，丙做E，丁做A，总花费131。
5.9 设，则原问题变为如下标准形：

由目标函数知，目标函数值由小到大依次为-10、-8、-6、-5、-4、-3、-2……
先令所有变量均为0，，代入两个约束条件中，均不成立。
令，其余变量仍为0，，约束条件（1）成立，但（2）不成立。
令，其余变量仍为0，，约束条件（1）、（2）都不成立。
令，其余变量仍为0，，约束条件（1）、（2）都不成立。
令，其余变量为0，，约束条件（1）、（2）均成立。
故原问题最优解为，最优值。

章末习题

6.1 s至t的最长路线为s→a→c→d→t或s→a→c→e→t或s→b→c→d→t或s→b→c→e→t。
6.2 A、B、C、D四个企业分配到的资金分别为0、20、40、40（万元），总盈利最大为85。
6.3 第一种资源3单位全都分配给第三个部门，第二种资源1单位分配给第一个部门，2单位分配给第二个部门。这样的分配方案获得的总利润最大，总利润为16。
6.4 既满足交货任务（不允许缺货）又使总费用最少的生产计划为：1月生产400件，3月生产400件，4月生产300件，5月生产300件，2月和6月不生产，最少总费用为161000元。
6.5 满足需求量又使热销季节总费用最小的订货方案为10月订货40双，11月订货50双，1月订货40双，2月订货50双，12月和3月不订货，总费用为610。
6.6 应分别装载三种货物2，2，0或3，2，1件，才能使所运货物总价值最大，总价值为480元。
6.7 装载货物的总价值最大为20，最优方案有三种：四种货物的装载量分别为1，3，1，0；或2，1，2，0；或0，5，0，0。
6.8 五年内所有机器都按低负荷投入生产，总收益最大。各年投入的机器数量分别为1000台、400台、160台、64台、25台。
6.9 ⑴初始役龄为7（T=7）的设备的10年最佳更新策略有三种：第1年、第5年和第8年更新；第1年、第5年和第7年更新或第1年、第3年和第7年更新，10年总收益最大为70万元。
⑵初始役龄T=6的设备的9年最优更新策略有四种：第1年和第6年更新；第1年和第5年更新；第1年、第3年和第6年更新；第1年、第3年和第7年更新，9年最大总收益为64万元。
6.10应安排1个E1， 1个E2，3个E3备用，总费用8000元，设备的可靠性最高可增加0.042。
章末习题

7.1 图（a）中，②、⑤之间有d、e两条箭线连接。图（b）中，有⑦、⑧两个终点节点。网络图中只能有一个起始节点和一个终点节点。图（c）中，①→②→③→①构成一条回路。
图（a）、图（b）改正如下：

7.2 根据表7-8，表7-9所示的工序明细表，绘制网络图。

7.3 各事项的最早与最迟时间见下图：

7.4 试画出表7-10、表7-11的网络图，并为事项编号。

7.5网络图及各节点时间参数如下图，关键路线为①→③→⑤→⑥→⑨→⑩。

（2）各工序的最早开工、最早完工、最迟开工、最迟完工时间及总时差、关键工序如下表：
工序
工时(周)
ES
LS
EF
LF
ST
关键工序
A(1-2)
3
0
1
3
4
1

B(1-3)
4
0
0
4
4
0
是
C(2-4)
4
3
4
7
8
1

D(7-10)
3
14
20
17
23
6

E(3-9)
4
4
13
8
17
9

F(6-9)
5
12
12
17
17
0
是
G(4-5)
2
7
8
9
10
1

H(5-6)
2
10
10
12
12
0
是
I(8-9)
2
14
15
16
17
1

K(9-10)
6
17
17
23
23
0
是
L(4-7)
7
8
8
14
15
1

M(3-5)
6
4
4
10
10
0
是
（3）若要求工程完工时间缩短2天，应缩短关键工序。但因A、C、L、I、K组成的路线所需工时为22周，仅比关键路线少1周，因此应缩短工序K的时间至少一周，再缩短关键工序（B、M、H、F、K）中任意一道工序一周。
7.6 各节点时间参数见下图：

关键路线为：①→②→⑤→⑧→⑨→⑩→⑾。
各工序的时间参数及关键工序如下表所示：
工序
工时(周)
ES
LS
EF
LF
ST
FT
关键工序
(1-2)
10
0
0
10
10
0
0
是
(1-3)
12
0
6
12
18
6
3

(1-4)
15
0
17
15
32
17
0

(2-3)
5
10
13
15
18
3
0

(2-5)
18
10
10
28
28
0
0
是
(3-5)
10
15
18
25
28
3
3

(3-6)
11
15
18
26
29
3
0

(3-7)
15
15
27
30
42
12
0

(4-7)
10
15
32
25
42
17
5

(5-8)
20
28
28
48
48
0
0
是
(6-8)
14
26
34
40
48
8
8

(6-9)
25
26
29
51
54
3
3

(7-9)
0
30
54
30
54
24
24

(7-10)
19
30
42
49
61
12
12

(8-9)
6
48
48
54
54
0
0
是
(8-11)
15
48
71
63
86
23
23

(9-10)
7
54
54
61
61
0
0
是
(9-11)
18
54
68
72
86
14
14

(10-11)
25
61
61
86
86
0
0
是

7.7各事项的最早时间和最迟时间如图所示：

各工序的最早开始、最早结束、最迟开工及最迟完工时间、总时差和自由时差如下表所示：
工序
工时(周)
ES
LS
EF
LF
ST
FT
关键工序
(1-2)
3
0