第三章
运输问题

1 下列说法中正确的有：

（1）运输问题时一类特殊的线性规划模型。

（3.1）

因而对模型（3.1）的求解结果可能有：唯一最优解，无穷多最优解，无界解，无可行解；

（2）表上作业法实质上就是求解运输问题的单纯形法；

（3）如果教材表2-3-2（见表2-3-1）单位运价的某一行均加上常数k，最优调运方案不会改变；

（4）如果教材表2-3-2（见表2-3-1）单位运价的某一行均乘上常数k，最优调运方案不会改变。

解： （1）错误，运输问题目标函数有下界，不会趋于无穷大，因此必存在有限最优解；

（2）正确，求解运输问题的矩阵非常稀疏，其过程同样也是从一个可行解开始逐步迭代；

（3）正确，从闭合回路检验来看，每行每列如果在闭合回路中，一定会有偶数个数值，并且分别为加减，所以闭合回路检验数不会发生变化，不管初始解是否变化，经过调整后的最优解也不会发生变化；

（4）正确，从伏格尔法求初始解来看，分别乘上一个常数只是使得罚数（差值）增大K倍，不会影响罚数相对大小，所以初始解不变。从闭合回路求最优解来看，分别乘上一个常数只是使得检验数增大K倍，不会影响其正负，所以最优解不变。

因此说法正确的有（2）、（3）、（4）。

2 运输问题的基可行解应满足什么条件？试判断表2-3-2和表2-3-3中给出的调运方案可否作为表上作业法迭代时的基可行解？为什么？

答： 运输问题基可行解的要求时基变量的个数等于m＋n－1。表2-3-2和表2-3-3中给出的调运方案都不能作为表上作业法迭代时的基可行解。因为数字格的数量不等于m＋n－1。

3 试对给出运输问题初始基可行解的最小元素法和Vogel法进行比较，分析给出的解之质量不同的原因。

答： 最小元素法从最小的运输价格入手，一开始效果很好，但是到了最后因选择余地较少效果不好；Vogel法从产地和销地运价的级差来考虑问题，总体效果很好，但是方法较复杂。

4 简要说明用位势法（对偶变量法）求检验数的原理。

答： 原问题的检验数也可以利用对偶变量来计算

σ _ij ＝c _ij －（u _i ＋v _j ），i＝1，2，…，m；j＝1，2，…，n

其中，u _i 和v _j 就是原问题约束对应的对偶变量。由于原问题的基变量的个数等于m＋n－1。所以相应的检验数就应该等于0。即有：

c _ij －（u _i ＋v _j ）＝0，i＝1，2，…，m；j＝1，2，…，n

由于方程有m＋n－1个，而变量有m＋n个。所以上面的方程有无穷多个解。任意确定一个变量的值都可以通过方程求出一个解。然后再利用这个解就可以求出非基变量的检验数了。

5 用表上作业法求解运输问题时，在什么情况下会出现退化解？当出现退化解时应如何处理？

答： 当数字格的数量小于m＋n－1时，相应的解就是退化解。如果出现了退化解，首先找到同时划去的行和列，然后在同时划去的行和列中的某个空格中填入数字0。只要数字格的数量保持在m＋n－1个的水平即可。

6 一般线性规划问题具备什么特征才能将其转化为运输问题求解，请举例说明。

答： 如果线性规划问题有“供”和“需”的关系，并且有相应的“费用”，就可以考虑将线性规划问题转成运输问题求解。例如，生产满足需求的问题。

7 表2-3-4和表2-3-5分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。

解： （1）由最小元素法求得初始基可行解为，如表2-3-6所示。

闭回路法求检验数，如表2-3-7所示。

由于（A ₂ ，B ₄ ）的检验数小于0，故初始基可行解不是最优解。

故改进解，直到各非基变量的检验数大于0，得最优解表如表2-3-8所示。

（2）由于总产量13大于总销量10，需增加一假想销地B ₅ ，使其销量为3，如表2-3-9所示，此时产销平衡。

由最小元素法求得初始基可行解为，再进行多次迭代运算求得最优解如表2-3-10所示。

8 某企业和用户签订了设备交货合同，已知该企业各季度的生产能力、每台设备的生产成本和每季度末的交货量（见表2-3-11），若生产出的设备当季度不交货，每台设备每季度需支付保管维护费0.1万元，试问在遵守合同的条件下，企业应如何安排生产计划，才能使年消耗费用最低？

解： 设x _ij 为第i季度生产而于第j季度交货的设备数量，可列出该运输问题的如下产销平衡表和单位运价表合一的表。表中D为虚设的需求地，M为任意大的正数，表明不允许后面季度的产量用于前面季度交货。表中小方格内的单位运价为i季度生产用于j季度交货的每台设备消耗的费用，为生产成本和保管费用之和。用最小元素法得出初始运输方案，如表2-3-12所示。

再经过迭代得最优解如表2-3-13所示。

即最优分配计划为：x ₁₁ ＝15，x ₂₂ ＝20，x ₂₃ ＝15，x ₃₃ ＝10，x ₃₄ ＝20，总的消耗费用z ^* ＝913.5。

9 某市有3个面粉厂，它们供给3个面食加工厂所需的面粉。各面粉厂的产量、各面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均示于表2-3-14中。假定在第1、2和3面食加工厂制作单位面粉食品的利润分别为12、16和11，试确定使总效益最大的面粉分配计划（假定面粉厂和面食加工厂都属于同一个主管单位）。

解： 由表数据，用最小元素法得出初始运输方案，再经过迭代得到最优解如表2-3-15所示。

即最优分配计划为：x _{Ⅰ 1} ＝0，x _{Ⅰ 3} ＝20，x _{Ⅱ 1} ＝15，x _{Ⅱ 2} ＝5，x _{Ⅲ 2} ＝20，总收益z ^* ＝425。

因面粉厂的总产量大于食品厂的总需量，故面粉厂 Ⅱ 的产量中有10个单位面粉滞留。

10 表2-3-16示出一个运输问题及它的一个解，试问：

（1）表中给出的解是否为最优解？请用位势法进行检验。

（2）若价值系数C ₂₄ 由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。

（3）若所有价值系数均增加1，最优解是否改变？为什么？

（4）若所有价值系数均乘以2，最优解是否改变？为什么？

（5）写出该运输问题的对偶问题，并说明二者最优解的关系。

解： （1）用位势法检验后算出各空格的检验数如表2-3-17所示。

因为所有的检验数σ _ij ≥0，故表中给出的解即为最优解。

（2）若价值系数C24由1变为3，用位势法求得检验数如表2-3-18所示。

由于σ ₂₂ ＝－2＜0，故知表中解不再是最优解，且以x ₂₂ 为换入变量，它对应的闭合回路如表2-3-19所示。

该闭合回路的偶数顶点位于格（A ₁ ，B ₂ ）、（A ₃ ，B ₃ ）和（A ₂ ，B ₄ ），由于

min{x ₁₂ ，x ₃₃ ，x ₂₄ }＝min{5，3，2}＝2

故应对解作如下调整：

x ₂₂ ：加2，x ₁₂ ：减2，x ₁₃ ：加2，x ₃₃ ：减2，x ₃₄ ：加2，x ₂₄ ：减2

得到新的基可行解是：x ₁₂ ＝3，x ₁₃ ＝5，x ₂₁ ＝8，x ₂₂ ＝2，x ₃₃ ＝1，x ₃₄ ＝3，其他为非基变量，这时的最优解z ^* ＝43。现再用位势法求这个新解各非基变量的检验数，结果如表2-3-20所示。

由于所有非基变量的检验数全为非负，故这个解为最优解。

（3）最优解不变，因为这样做不改变非基变量检验数的值。

（4）最优解不变，就如图将单位运价由元/500g变为元/kg，价格增加为原2倍一样，这样做不会改变非基变量检验数的符号。

（5）对偶问题如下：

其最优解是：u ₁ ＝－1，u ₂ ＝0，u ₃ ＝0，v ₁ ＝1，v ₂ ＝2，v ₃ ＝5，v ₄ ＝1

11 1、2、3三个城市每年需分别供应电力320个单位、250个单位和350个单位，由 Ⅰ 、 Ⅱ 两个电站提供，它们的最大可供电量分别为400个单位和450个单位，单位费用如表2-3-21所示。由于需要量大于可供量，决定城市1的供应量可减少0～30个单位，城市2的供应量不变，城市3的供应量不能少于270个单位，试求总费用最低的分配方案（将可供电量用完）。

解： 根据表与已知，解得总费用最低的分配方案如表2-3-22所示。

即最优分配方案为：电站 Ⅰ 供给城市1—150单位，城市2—250单位；电站 Ⅱ 供给城市1—140单位，城市3—310单位。 YKO32uocSHSTXIcYWjJSpMGPsdPSWsvERIjjQaQi3UafWKYAnU08TIHPzyyzE+OM