B3 34
B4 产
ui
量 1 2 34
6 8 302
④
A2 A3 销量
31
2
25
30 8 1 1 5
⑤
3
7 15
1 4 224 ⑥
6
5
6
3
列12 罚22 数3
vj 4
111 11 11 1
②
①⑦
③
2020/5/29
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，在上述三种计算方法中，这种方法计算所需 运输费用是最省的。但还不知是否最优。现用闭回路法
产量
8 8 4
σ22=2-1+4-5=0
2020/5/29
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/5/29
14
第五个闭回路σ32，走7→1→4→5线路
2020/5/29
2
表3-27
销地 B1
B2 B3 B4
B5
产量
产地
A1
150
250
400
A2
200 300
500
A3
250
50
300
A4
90 210
300
A5
80 20
100
销量 240 410 550 330 70
解：表3-27产地个数m=5，销地个数n=5，m+n-1=5+5-1=9 个，而表3-27中非零个数的分量为10个≠9个，也不可作为表 上作业法时的基可行解。
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/5/29
8
② 用沃格尔法求解如下：
产地
销地
A1
B1 B2 4 51
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/5/29
17
①最小元素法求解：
销地 B1
2020/5/29
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/5/29
08
4 σ14=0 +12 σ24=2 2-1 5
2
2
7
4
30 5 0
0 σ25=5
0 σ15=0
3 -1
2 -4 61
由σ13=-1，故知z=35还不是最优解。经上表调整后得：x11=1
，x13=1，x15=3，x23=1，x24=1，x31=2，x32=3，x33=0，
x34=1，z*=1×3＋1×6＋3×0＋1×3＋1×2＋2×4＋3×3
2020/5/29
3
3.3 试对给出运输问题初始基可行解的最小元素法和 Vogel法进行比较，分析给出的解之质量不同的原因。
解： 对于任意给出运输问题初始基可行解的最小元素 法和Vogel法进行比较，分析给出的两种不同的方法求出 的解确有不同的原因。初看起来，最小元素法十分合理 。但是，有时按某一最小单位运价优先安排物品调运时 ，却可能导致不得不采用运费很高的其他供销点时，从 而使整个运输费用增加。我们称各销售地或供应地的单 位运价中找出的最小单位运价和次小单位运价之差为罚 数，若罚数的值不大，当不能按最小单位运价安排运输 时造成的运费损失不大；但如果罚数很大，不按最小运 价组织运输就会造成很大损失，故应尽量按最小运价安
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/5/29
7
②西北解法计算如下：
销地 B1
B2
B3
B4
产量
产地
A1
6 4 21
4
68
②
B2
产地
A1
13
7
A2
22
4
A3 销量
4
33
3
3
B3
6 3 28 2
B4 B5 产量
1 4 30
5
⑤
2
0
2②
15 0
6⑧
2
3
③
④
⑦
⑥
①
x11=1，x14=1，x15=3，x21=2，x32=3，x33=2，x34=1，总 费用=1×3＋1×4＋3×0＋2×2＋3×3＋2×8＋1×5＝41
2020/5/29
2020/5/29
19
③沃格尔法求解：
销地 B1 产地
A1
23
A2
2
A3
14
销量 3
列11
罚21 数31 vj 4 1
B2 B3 B4 B5
7
6
4
30
4
23
2
0
33 0 8 25 0
3
2
2
3
1 3 20
132 421
21
产
行罚数ui
量
1 2 34
5 3 1 11④
2 20
②
6 3 1 11⑧
⑥
③
⑤
表3-30位势法检验
产地 B1 B2 B3 B4 B5 Ui
销地
A1 2
3
0
A2
2
A3 1
3
0
2
vj
2020/5/29
21
表3-30 位势法检验
产地
B1
B2
B3
B4
B5 产 Ui
销地
量
A1 A2 A3 销量 vj
2-1 3
2 σ21=3 1+14
3 3
7 σ12=2
4 σ22=2
33
3 2
+1 6 σ13=-1 2-1 3
3.1 与一般线性规划的数学模型相比，运输问题的数 学模型具有什么特征？
答： 与一般线性规划的数学模型相比，运输问题的数 学模型具有如下特征：1.运输问题不象一般线性规划问 题那样，线性规划问题有可能有无穷多最优解，运输问 题只有有限个最优。2.运输问题约束条件系数矩阵的元 素等于0或1；且每一列有两个非零元素。3.运输问题的 解的个数不可能大于(m+n-1)个。
⑦
①
2020/5/29
20
x11=2，x15=3，x23=2，x31=1，x32=3，X33=0， x34=2，总费用=2×3＋0×6＋3×0＋2×3＋1×4＋ 3×3＋2×5＝35。在最小元素法中，总费用=41，在用 西北角法计算中，总费用=56，因此用沃格尔法计算所 需费用=35是最小的，但不知是否最优，还要用对偶变 量法（位势法）加以检验。如表3-30所示：
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/5/29
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
5
表3-29
销地 B1
B2
B3
B4
产量
产地
A1
3
7
6
4
5
A2
2
4
3
2
2
A3
4
3
8
5