习题五
5.2用元素差额法直接给出表5-53及表5-54下列两个运输问题的近似最优解.
表 5-53
【解】表。
Objective Vallue = 824 (Minimization)
表5-54 Z=495
Objective Value = 495 (Minimization)
^Eritering: Source 1 to Deslinator A Leading: Source 3 to Desti
5.3求表5-55及表5-56所示运输问题的最优方案.
(1)用闭回路法求检验数(表5-55)
（2）用位势法求检验数（表5-56）
【解】（1）
5.4求下列运输问题的最优解
(1) C i目标函数求最小值；(2) C2目标函数求最大值
3 5 9 2 50 7 10 15 20 60
C1 6 4 8 5 25 C 14 13 9 6 30
11 13 12 7 30 5 8 7 10 90
15 45 20 40 60 30 50 40
⑶目标函数最小值，B i的需求为30W b i w 50, B2的需求为40, B3的需求为20< b3W 60,A i不
可达A A , B4的需求为30.
4 9 7 70
6 5 3 2 20
8 4 9 10 50
(3)先化为平衡表
5.5 (1)建立数学模型
设X j (|=l,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往 B
i
, B
2
两城市的台班数，则
maxZ 40(80x 11 65x i 2 60夠 50冷2 50x 31 40x 32) 40x 11 40x 21 40x 31 400 40x 12 40x 22 40x 32
600
X 11
X
12 5 X 11 X
22
10
X 31
X
32
15
X
j
0(i 1,2,3; j
1,2)
(
2)
写
平衡
运价表
132333为了平衡表简单，故表中运价没有乘以 ，最优解不变
(3 )最优调度方案:
Z=40 (5 >80+5 >60+5 X50+10 >40) =54000 (元)
5.6 (1)设X j 为第i 月生产的产品第j 月交货的台数，则此生产计划问题的数学模型为
3
1.45X 14
M X 21 L
1 2
3
4
5 a i
1 50 15
65 2
25
10
30
65
1 2 3 4 5
a i 1 1 1.15 1.3 1.45 0 65 2 M 1.25 1.4 1.55 0 65 3 M M 0.87 1.02 0 65 4 M M M 0.98 0 65
b j
50 40 60 80
30
5列是虚设销地费 (2 )化为运输问题后运价表(即生产费用加上存储费用)如下，其中第
用为零，需求量为 30。
0.98X
44
min Z X ii 1.15X 12
1.3X
X ii X 21 X 31 X 41 50
X l2 X 22 X 32 X 42 40 X l3 X 23 X 33 X 43 60 X l4 X 24 X 34 X 44 80 X ii X i2 X i3 X i4 65
X 21 X 22 X 23 X 24 65 X 31 X 32 X 33 X 34 65
X 4i
X
42
X
43
X 44 65 X ij 0,(i, j
i,L ,4)
B 2城市，丙每天发10
辆车到B 2城市，多余5辆，最大收入为
上表表明：一月份生产 65台，当月交货50台；二月份交货15台,二月份生产35台，当月 交货25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月 份生产65台当月交货。
最小费用 Z=235万元。
5.7假设在例5.15中四种产品的需求量分别是
1000、2000、3000和4000件，求最优生产配
置方案.
【解】将表5-35所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子
用匈牙利法得到最优表
第一个工厂加工产品 ,第二工厂加工产品 ,第三个工厂加工产品 ，第四个工厂加
工产品 2;
总成本
Z = 1000X （58 + 920 + 510 + 110）= 1598000
注：结果与例5.15的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后 最优解不变”结论成立。
12 6 9 15
( 1) C =
20 12 18 26 35 18 10 25
6 10 15 20
【解】
最优解
1
1
X
,Z 43
1
1
26 38 41 52 27
c 25 33 44 59 21
(2) C =
20 30 47 56 25
5.8求解下列最小值的指派问题，其中第
（ 工作.
1000 .
2）题某人要作两项工作，其余 3人每人做一项
22 31 45 53 20
最优解：甲〜戊完成工作的顺序为3、5、1、2、4,最优值Z=165
最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。
5.9求解下列最大值的指派冋题：
10 9 6 17
c 15 110 20
(1) C =
18 113 19
16 8 12 26
【解】最优解
1
1
X ,Z 64
1
1
9 6 5 10
4 一8 5
(2) C= 7 10 9 12
6 15
7 16
9 8 6 8
【解】最优解
1
1
X 1 ,Z 44
1
1
第5人不安排工作。
表5-58成绩表（分钟）
5.10学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-58所示.如何从中选拔一个接力队，使预期的比赛成绩最好.
【解】设X ij为第i人参加第j项目的状态，则数学模型为min Z 20x1143X J2 33x1329x14L 28x54
x11 X12
X13 X14 1
x21 X22
X23 X24 1
x31 X32 X33 X34 1
X41 X42 X43 X44 1
x51 X52 X53 X54 1
X11 X
21
X31 X41 X51 1
x12 X22
X32 X42 ^52 1
x13 X23 X33 X43 X53 1
X14 X24 X34 X44 ^54 1
x ij
0 或
1,i 1,2,
L
,5；
j
1,2,3,
4
接力队最优组合
乙长跑
丙游泳丁登山
戊自行车
甲淘汰。
预期时间为107分
钟。