第3章 运输问题
注意：本章习题解法不唯一，有的题目，最优解也可能不唯一。 3.8 表3-32和表3-33分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。
表3-32
销地 产地 A1 A2 A3 销量 B1 4 1 3 6 B2 1 2 7 5 B3 4 5 5 6 B4 6 0 1 3 产量 8 8 4 20 解：由最小元素法求得上述运输问题的初始基可行解，其过程如下：
表3.8-1
销地 产地 B1 6 4 1 3 B2 1 2 7 5 B3 4 5 5 6 B4 6 0 1 3 产量 8 A1 A2 A3 销量 8 4 20 由于0为最小，所以，取3与8的最小值放在x24位置上，划去B4列，得表3.8-2
表3.8-2
销地 产量 B1 B2 B3 B4 产地 A1 A2 A3 销量 6 4 1 3 5 1 2 7 6 4 5 5 3 0 6 0 1 8 5 4 在没画线的表格中，由于1最小，所以取6与5的最小值放在x21位置上，划去A2行，
得表3.8-3
在表3.8-3中的没画线的表格中，由于1最小，所以取8与5的最小值放在x12位置上，划去B2列，得表3.8-4
运筹学习题答案及注释 第1页
在表3.8-4中没画线的表格中，由于3最小，所以取4与1的最小值放在x31位置上，划去B1列，得表3.8-5
表3.8-3 销地 产量 B1 B2 B3 B4 产地 A1 A2 A3 销量 5 1 4 1 3 5 1 2 7 6 4 5 5 3 0 6 0 1 8 0 4 表3.8-4
销地 产地 B1 5 4 1 3 1 B2 1 2 7 0 5 B3 4 5 5 6 B4 6 0 1 0 产量 3 A1 A2 A3 销量 3 0 4 表3.8-5 销地 产地 B1 5 4 1 3 0 B2 1 2 7 0 5 B3 4 5 5 6 B4 6 0 1 0 产量 3 A1 A2 A3 销量 3 0 1 3 在表3.8-5中没画线的表格中，由于4最小，所以取3与6的最小值放在x13位置上，划去A1行，得表3.8-6
在表3.8-6中没画线的表格中，由于5最小，所以取3与3的最小值放在x33位置上，划去A3行和B3列，得表3.8-7，这样就得到了一个初始基可行解，如表3.8-8所示。
在表3.8-8中，使用闭回路法计算非基变量的检验数（括弧内的数），得表3.8-9：
运筹学习题答案及注释 第2页
σ11 = c11- c13 + c33 - c31 = 4-4+5-3 = 2
σ14 = c14- c13 + c33 - c31 + c21 - c24 = 6-4+5-3+1-0 = 5
得表3.8-6 销地 产量 B1 B2 B3 B4 产地 A1 A2 A3 销量 5 1 0 4 1 3 5 0 1 2 7 3 3 4 5 5 3 0 6 0 1 3 0 3 表3.8-7
销地 产地 B1 4 1 3 0 B2 1 2 7 0 5 B3 4 5 5 0 3 3 B4 6 0 1 0 产量 0 A1 A2 A3 销量 5 1 3 0 0 表3.8-8 销地 产地 B1 5 1 6 4 1 3 B2 1 2 7 5 5 B3 4 5 5 6 3 3 B4 6 0 1 3 产量 8 A1 A2 A3 销量 3 8 4 20 σ22 = c22 - c12 + c13 - c33 + c31 - c21 = 2-1+4-5+3-1 = 2 σ23 = c23 - c33 + c31 - c21 = 5-5+3-1 = 2 σ32 = c32 - c33 + c13 – c12 = 7-5+4-1 = 5 σ34 = c34 - c24 + c21 – c13 = 1-0+1-3 = -1
在表3.8-9中，由于检验数σ34 = -1≤0 ，所以表3.8-9中的解不是最优解。选x34
运筹学习题答案及注释 第3页
为换入变量，找到闭回路为：x34 x24 x21 x31 ，由于3与1的最小数为1，故调整量为1，选x31为换出变量，调整后的解如表3.8-10所示
表3.8-9 销地 产量 B1 B2 B3 B4 产地 A1 A2 A3 销量 5 1 6 4 1 2 (2) 7 3 4 5 6 (5) 0 1 (-1) 3 (2) 5 1 3 8 (2) 3 5 8 (5) 3 5 6 表3.8-10
4 20 销地 产地 B1 6 6 4 1 3 B2 1 2 7 5 5 B3 4 5 5 6 3 3 B4 6 0 1 3 产量 8 A1 A2 A3 销量 2 1 8 4 20 在表3.8-10中，使用闭回路法计算各非基变量的检验数，得表3.8-11：
表3.8-11
销地 产量 B1 B2 B3 B4 产地 A1 A2 A3 销量 6 4 1 2 (1) 7 3 4 5 6 (6) 0 1 3 (3) 5 1 3 (1) 6 8 (1) 2 5 1 8 (5) 3 5 6 4 20 在表3.8-11中，由于所有检验数均大于等于 0 ，所以表3.8-11中的解就是最优解，其最
小运价为39 。
解：由最小元素法求得上述运输问题的初始基可行解，如下表3.8-21：
在表3.8-21中，使用闭回路法计算非基变量的检验数（括号内的数），得表3.8-22：
运筹学习题答案及注释 第4页
在表3.8-22中，由于所有检验数均大于等于 0 ，所以表3.8-22中的解就是最优解，其最小运价为 31 。
表3-33 销地 B1 B2 B3 B4 产量 产地 A1 A2 A3 销量 9 4 5 1 3 9 7 3 8 4 6 2 7 5 2 5 3 3 5 11 表3.8-21 销地 产地 B1 1 0 1 9 4 5 B2 3 9 7 3 3 0 B3 8 4 6 2 B4 7 5 2 5 产量 3 A1 A2 A3 销量 2 3 5 5 11 表3.8-22
销地 产地 B1 1 0 1 9 (8) 3 4 5 0 B2 3 9 B3 8 (7) 4 6 B4 7 (2) 5 (4) 2 5 产量 3 A1 A2 A3 销量 (3) 2 7 3 3 (1) 5 2 5 11 3.9 试求表3-34给出的产销不平衡运输问题的最优解。 表3-34 销地 B1 B2 B3 B4 产地 A1 A2 A3 销量 3 2 4 3 7 4 3 3 6 3 8 2 4 2 5 2 产量 5 2 6 运筹学习题答案及注释 第5页