运筹学课后习题五.doc

习题五
5.2 用元素差额法直接给出表5-52及表5-53下列两个运输问题的近似最优解．
表5-52

B1
B2
B3
B4
B5
Ai
A1
19
16
10
21
9
18
A2
14
13
5
24
7
30
A3
25
30
20
11
23
10
A4
7
8
6
10
4
42
Bj
15
25
35
20
5

表5-53

B1
B2
B3
B4
Ai
A1
5
3
8
6
16
A2
10
7
12
15
24
A3
17
4
8
9
30
Bj
20
25
10
15

【解】

表5-52。Z=824

表5-53最优表如下，最优值Z=495

5.3 求表5-54及表5-55所示运输问题的最优方案．
（1）用闭回路法求检验数（表5-54）
表5-54

B1
B2
B3
B4
ai
A1
10
5
2
3
70
A2
4
3
1
2
80
A3
5
6
4
4
30
bj
60
60
40
20

（2）用位势法求检验数（表5-55）
表5-55

B1
B2
B3
B4
ai
A1
9
15
4
8
10
A2
3
1
7
6
30
A3
2
10
13
4
20
A4
4
5
8
3
40
bj
20
15
50
15

解（1）最优表如下，最优值Z＝610

(2)解 最优表如下，最优值Z＝445

5.4 求下列运输问题的最优解
（1）C1目标函数求最小值； （2）C2目标函数求最大值

(3)目标函数最小值,B1的需求为30≤b1≤50, B2的需求为40，B3的需求为20≤b3≤60,A1不可达B4 ，B4的需求为30．

【解】（1）

（2）

（3）先化为平衡表

B11
B12
B2
B31
B32
B4
ai
A1
4
4
9
7
7
M
70
A2
6
6
5
3
3
2
20
A3
8
8
5
9
9
10
50
A4
M
0
M
M
0
M
40
bj
30
20
40
20
40
30
180
最优解：

5.5（1）建立数学模型
设xij(I=1,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往B1，B2两城市的台班数，则

(2)写平衡运价表
将第一、二等式两边同除以40，加入松驰变量x13x23和x33将不等式化为等式，则平衡表为：

B1
B2
B3
ai
甲
乙
丙
80
60
50
65
50
40
0
0
0
5
10
15
bj
10
15
5

为了平衡表简单，故表中运价没有乘以40，最优解不变
（3）最优调度方案：

即甲第天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10辆车到B2城市，多余5辆，最大收入为
Z=40（5×80+5×60+5×50+10×40）=54000（元）
5.6（1）设xij为第i月生产的产品第j月交货的台数，则此生产计划问题的数学模型为

（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量为30。

1
2
3
4
5
ai
1
2
3
4
1
M
M
M
1.15
1.25
M
M
1.3
1.4
0.87
M
1.45
1.55
1.02
0.98
0
0
0
0
65
65
65
65
bj
50
40
60
80
30

(3)用表上作业法，最优生产方案如下表：

1
2
3
4
5
ai
1
2
3
4
50
15
25

60

10
5
65

30

65
65
65
65
Bi
50
40
60
80
30

上表表明：一月份生产65台，当月交货50台；二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小费用Z=235万元。
5.7 假设在例5－16中四种产品的需求量分别是1000、2000、3000和4000件，求最优生产配置方案．
【解】将表5-35所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子1000．

产品1
产品2
产品3
产品4
工厂1
58
138
540
1040
工厂2
75
100
450
920
工厂3
65
140
510
1000
工厂4
82
110
600
1120
用匈牙利法得到最优表

第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2；
总成本
Z＝1000×(58＋920＋510＋110)＝1598000
注：结果与例5.15的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。

5.8 求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作．
（1）
【解】最优解

（2）
【解】虚拟一个人，其效率取4人中最好的，构造效率表为

1
2
3
4
5
甲
26
38
41
52
27
乙
25
33
44
59
21
丙
20
30
47
56
25
丁
22
31
45
53
20
戊
20
30
41
52
20
最优解：，最优值Z=165

甲～戊完成工作的顺序为3、5、1、2、4，
最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。

5.9 求解下列最大值的指派问题：
（1）
【解】 最优解
（2）【解】

最优解
第5人不安排工作或第1人不安排工作。
表5-57 成绩表(分钟)

游泳
自行车
长跑
登山
甲
20
43
33
29
乙
15
33
28
26
丙
18
42
38
29
丁
19
44
32
27
戊
17
34
30
28
5.10 学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-57所示．如何从中选拔一个接力队，使预期的比赛成绩最好．
【解】设xij为第i人参加第j项目的状态，则数学模型为

接力队最优组合
乙
长跑
丙
游泳
丁
登山
戊
自行车
甲淘汰。预期时间为107分钟。