运筹学第三章课后习题答案知识讲解

71 5
14
销量
6
5
6
3
σ34=1-5+5-0=1，至此，六个闭回路全部计算完，σ11=4， σ14=2，σ22=0，σ31=2，σ32=2，σ34=1，即全部检验数σ 均大于或等于0。即用上述三种方法计算中，用沃格尔法
计算所得结果z*=35为最优解。
2020/3/31
16
表3-29
销地 B1
B2
2020/3/31
4
排运输。这就是最小元素法和沃格尔法质量不同的原因。
3.7 表3-28和表3-29分别给出了各产地和各销地的产量 和销量，以及各产地至各销地的单位运价，试用表上作业 法求最优解。
表3-28
销地 B1
B2
B3
B4
产量
产地
A1
4
1
4
6
8
A2
1
2
5
0
8
A3
3
7
5
1
4
销量
ห้องสมุดไป่ตู้
6
5
6
3
20
2020/3/31
3.2 运输问题的基可行解应满足什么条件?试判断形表 3-26和表3-27中给出的调运方案是否作为表上作业法迭 代时的基可行解?为什么?
2020/3/31
1
表3-26
销地 B1
B2
B3
B4
产量
产地
A1
0
A2
A3
5
销量
5
15
15
15
10
25
5
15
15
10
解：表3-26产地个数m=3，销地个数n=4，m+n-1=3+4-1=6 个，而表3-26中非零个数的分量为5个≠6个，所以表3-26不 可作为表上作业法时的基可行解。
A2 A3 销量
1 32 55
08
④
3
7 15 3 1 4
⑦
6
5
6
3
20
①
③
⑤
⑥
从上表计算知：x11=6，x12=2，x22=3，x23=5，x33=1， x34=3。总费用=6×4＋2×1＋3×2＋5×5＋1×5＋ 3×1=65
2020/3/31
8
② 用沃格尔法求解如下：
产地
销地
A1
B1 B2 4 51
A1
B1
B2
B3
45 13 4
B4
6
A2 3 1
22 5 3 0
A3
3
71 5
1
销量
6
5
6
3
产量
8 8 4
σ14=6-0+5-4=7
2020/3/31
12
第三个闭回路σ22，走2→1→4→5线路
产地 销地
A1
B1
B2
B3
45 13 4
B4
6
A2 3 1
22 5 3 0
A3 销量
3
71 5
1
6
5
6
3
B3
B4
产量
产地
A1
3
7
6
4
5
A2
2
4
3
2
2
A3
4
3
8
5
6
销量
3
3
2
2
解：（2）表3-29用三种方法计算，用位势法检验。因 为总产量=13，总销量=10，所以该题的总产量＞总销 量，所以该题是产销不平衡的问题，故假设一销地B5 ①用最小元素法计算如下表所示
2020/3/31
17
①最小元素法求解：
销地 B1
产地 销地
A1
B1
B2
B3
45 13 4
B4
6
A2 3 1
22 5 3 0
A3 销量
3
71 5
1
6
5
6
3
产量
8 8 4
σ32=7-1+4-5=2
2020/3/31
15
第六个闭回路σ34，走1→5→5→0线路
产地 销地
A1
B1
B2
B3
45 13 4
B4 产量
6
8
A2 3 1
22 5 3 0 8
A3
3
2
5 30 8
③
13
7 35
14
⑦
6
5
6
3
20
④
②
⑥
①
从上表计算知：x12=5，x13=3，x21=5，x24=3，x31=1， x33=3。总费用=5×1＋3×4＋5×1＋3×0＋1×3＋ 3×5=40
2020/3/31
7
②西北解法计算如下：
销地 B1
B2
B3
B4
产量
产地
A1
6 4 21
4
68
②
B3 34
B4 产
ui
量 1 2 34
6 8 302
④
A2
31
2
25
30 8 1 1 5
⑤
A3
3
7 15
1 4 224 ⑥
销量
6
5
6
3
列12 罚22 数3
111 11 11
vj 4
1
②
①⑦
③
2020/3/31
9
从上表计算知：x12=5，x13=3，x21=3，x23=2，x24=3， x33=1。总费用=5×1＋3×4＋3×1＋2×5＋3×0＋ 1×5=35，在上述三种计算方法中，这种方法计算所需 运输费用是最省的。但还不知是否最优。现用闭回路法
B2
产地
A1
13
7
A2
22
4
A3 销量
4
33
3
3
B3
6 3 28 2
B4 B5 产量
3.1 与一般线性规划的数学模型相比，运输问题的数 学模型具有什么特征？
答： 与一般线性规划的数学模型相比，运输问题的数 学模型具有如下特征：1.运输问题不象一般线性规划问 题那样，线性规划问题有可能有无穷多最优解，运输问 题只有有限个最优。2.运输问题约束条件系数矩阵的元 素等于0或1；且每一列有两个非零元素。3.运输问题的 解的个数不可能大于(m+n-1)个。
5
表3-29
销地 B1
B2
B3
B4
产量
产地
A1
3
7
6
4
5
A2
2
4
3
2
2
A3
4
3
8
5
6
销量
3
3
3
2
解：（1）表3-28用三种方法计算，用闭回路法检验。 ①用最小元素法计算如下表所示
2020/3/31
6
① 最小元素法求解如下：
销地 B1
B2
B3
B4
产量
产地
A1
4 5 1 34
68
⑤
A2 A3 销量
51
产量
8 8 4
σ22=2-1+4-5=0
2020/3/31
13
第四个闭回路σ31，走3→1→5→5线路
产地 销地
A1
B1
B2
B3
45 13 4
B4
6
A2 3 1
22 5 3 0
A3 销量
3
71 5
1
6
5
6
3
产量
8 8 4
σ31=3-1+5-5=2
2020/3/31
14
第五个闭回路σ32，走7→1→4→5线路
2020/3/31
2
3.3 试对给出运输问题初始基可行解的最小元素法和 Vogel法进行比较，分析给出的解之质量不同的原因。
解： 对于任意给出运输问题初始基可行解的最小元素 法和Vogel法进行比较，分析给出的两种不同的方法求出 的解确有不同的原因。初看起来，最小元素法十分合理 。但是，有时按某一最小单位运价优先安排物品调运时 ，却可能导致不得不采用运费很高的其他供销点时，从 而使整个运输费用增加。我们称各销售地或供应地的单 位运价中找出的最小单位运价和次小单位运价之差为罚 数，若罚数的值不大，当不能按最小单位运价安排运输 时造成的运费损失不大；但如果罚数很大，不按最小运 价组织运输就会造成很大损失，故应尽量按最小运价安
检验如下：
闭回路法检验如下：
2020/3/31
10
第一个闭回路σ11，走4→1→5→4线路
产地 销地
A1
B1
B2
B3
45 13 4
B4
6
A2 3 1
22 5 3 0
A3 销量
3
71 5
1
6
5
6
3
产量
8 8 4
σ11=4-1+5-4=4
2020/3/31
11
第二闭回路σ14，走6→0→5→4线路
产地 销地