产销平衡的运输问题

时间：2022-06-22 百科知识版权反馈

【摘要】：编制初始调运方案，是运输问题表上作业法的首要环节。同单纯形求解线性规划问题的过程类似，确定运输问题初始可行调运方案，实际上就是寻找运输问题的初始基本可行解。也就是去掉产地到销售地物资的运输费用，腾出单元格以备填写产地到销售地的物资运输量。表3.31在表3.31没有被划去的运费中选取一个最小的值，此时为c33＝4，意味着要考虑产地A3和销售地B3之间的运量分配问题。

2．产销平衡的运输问题

由于平衡运输问题的约束方程都取等号，如果直接采用单纯形方法求解，势必会引进m+n个人工变量，另外还由于模型的结构特征会不断出现退化的情况，从而使求解的过程变得非常复杂，有鉴于此，对运输问题人们习惯上采用表上作业进行求解。

2.1表上作业法的求解过程

表上作业法求解的基本过程是：

第一步，编制初始可行调运方案。编制初始调运方案，是运输问题表上作业法的首要环节。同单纯形求解线性规划问题的过程类似，确定运输问题初始可行调运方案，实际上就是寻找运输问题的初始基本可行解。获得初始可行调运方案的方法有很多种，但比较常用的是西北角法、最小元素法和伏格尔法等。

第二步，检验初始可行调运方案是否为最优解。判断一个调运方案是否已为最优调运方案，就是判别一个基本可行解是不是最优解的问题。如果能够判断当前调运方案是最优调运方案，则求解过程结束，不然的话就转入第三步。

第三步，方案调整。即从当前调运方案出发，确定人基变量和出基变量，通过不断迭代，寻找下一个更好的调运方案，以使目标函数值逐渐逼近最优状态。

下面，结合例3.16的资料，详细地介绍运输问题表上作业求解的开展过程。

2.2确定初始调运方案

（1）西北角法

运用西北角法确定初始调运方案，首先将表3.20改写成如表3.23所示的形式。也就是去掉产地到销售地物资的运输费用，腾出单元格以备填写产地到销售地的物资运输量。

表3.23

选取位于表3.23西北角的x₁₁作为第一个基变量，并给它赋以约束条件所允许的、

尽可能大的数，即令x₁₁=min{a1，b1}=min{5，3}=3。它表示产地A₁的产量为5吨，销售地B₁的需求量为3吨，因此，由产地A₁向销售地B₁的物资运送量为3吨，将数字3填入单元格（A₁，B₁），这时，销售地B₁的需求已达到满足，不再需要从其他产地运进物资了，将B₁所在的列划去，产地A₁的产量还剩2吨。表3.23可以改写成表3.24。

表3.24

选取另一个西北角元素x₁₂作为基变量，令x₁₂=min{5—3，3}=2。这是因为销售地B₂

需要3吨的物资，而产地A₁最多只能提供5—3=2吨的供应量，所以x₁₂=2。至此，产地A₁供应量耗尽，将所在的行划去，销售地B₂需求量还差1吨。整理后得到表3.25。

表3.25

现在选取x₂₂为基变量，则x₂₂=min{10，1}=1，表明销售地B₂还缺少1吨的物资由产

地A₂供应，这时候，销售地B₂的需求全部得到满足，划去所在列，相应地A₂供应量还剩9吨。得到表3.26。

表3.26

对表3.26，选取x₂₃为基变量，x₂₃=min{9，12}=9，将产地A₂剩下的9吨物资全部供应给销售地B₃，产地A₂的生产量全部供应完毕，划去所在行，B₃需求量还差3吨，得到表3.27。

表3.27

对表3.27，选取x₃₃为基变量，x₃₃=min{3，15}=3，B₃需求量满足，划去所在列，A₃供应量还剩12吨，如表3.28。

表3.28

最后，以A₃剩余12吨供应量满足B₄需求量，运输表中所有x_ij全部划完，最终得到初始调运方案，如表3.29。

表3.29

对应这一运输方莱的总运输费用20×3+11×2+9×1+10×9+4×3+1×12＝205百元

值得一提的是，如果在某一单元格处恰好行列条件同时满足（a_i＝b_j），那么填写数字后，只能划去a_i所在的行或b_j所在的列中的一个，而将另一个改写成0。这样，下一个单元格填入的必定是0。0不可以省略，原因是必须要保证m+n－1个基变量。

利用西北角法确定初始调运方案显得非常简单，只要由西北向东南逐次分配运量即可。但是，这种方法的最大缺陷是，完全按产量约束分配运输量，而根本不考虑产地到销售地运输费用的大小。如果单位运输费用由西北向东南逐渐减少，那么由西北角法确定的初始运输方案，必将是运输费用最高的，从而就会给随后的最优方案的调整增加不必要的工作量。

（2）最小元素法

最小元素法又叫最低费用法，这种方法在确定初始调运方案时，首先选取运输费用最小的C_ij所对应的决策变量x_ij作为基变量，让其先得到供应，然后再选择运输费用次低的C_ij′所对应的决策变量x_ij′作为基变量，直至获得初始可行调运方案。在这一过程中，如果碰到几个单元格的运输费用取同样的最小值，我们可以从中任选一个处理。

运用最小元素法确定初始调运方案的过程是，将表3.20改写成如表3.30的形式。

表3.30

表3.30中，将运价填入对应格子的右上角，运输量填入对应格子的中间。

通过观察可知，c₃₄＝1为最低运费，说明产地A₃的物资应优先供应销售地B₄，也就是说，可以考虑先给决策变量x₃₄赋值。由于产地A₃的产量为15吨，销售地B₄的需要量为12吨，所以x₃₄=min{15，12}=12，表明应从产地A₃生产的15吨物资中拿出12吨优先供应销售地B₄，这样，销售地B₄的全部需要得到满足，在进行下一次选择的时候，也无须再考虑到销售地B₄的问题，将B₄对应的列划去，A₃的产量还剩3吨。如表3.31。

表3.31

在表3.31没有被划去的运费中选取一个最小的值，此时为c₃₃＝4，意味着要考虑产地A₃和销售地B₃之间的运量分配问题。x₃₃=min{12，3}=3，表明应将产地A₃剩下的3吨物资供应给销售地B₃。现在产地A₃的产量全部供应完毕，于是可以划掉产地A₃所在行，B₃的需求量还差9吨。如表3.32。

表3.32

从表3.32剩下的运费中选择最低的一个c₂₁＝5，表明产地A2的产量应供应销售地B₁，此时，x₂₁=min{10，3}=3，即从产地A₂的10吨产量中拿出3吨供应销售地B₁，这样，销售地B₁全部得到满足，可以划掉销售地B₁所在列，A₂的产量还剩7吨。如表3.33。

表3.33

选取c₁₃=8所对应的决策变量x₁₃为基变量，x₁₃=min{5，9}=5，即将产地A₁的5吨物资全部供应给销售地B₃，同时划去产地A₁所在行，需求量还差4吨。如表3.34。

表3.34

选取c₂₂=9所对应的决策变量x₂₂为基变量，x₂₂=min{7，3}=3，从而得到表3.35。

表3.35

最后，考虑c₂₃，以A₂剩余供应量满足B₃需求量，运输表中所有成本单元格全部划完，最终得到初始调运方案，如表3.36。

表3.36

在这个初始运输方案下的总的运输费用为8×5+5×3+9×3+10×4+4×3+1×12＝146。

不难看出，由最小元素法确定的初始运输方案的费用比西北角法要小得多。

同样需要注意，在运用最小元素法确定初始运输方案的时候，如果在某一单元格处恰好行列条件同时满足（ai＝bj），那么填写数字后，只能划去ai所在的行或bj所在的列中的一个，而将另一个改写成0。这样，就会有一个单元格填入0，以确保基变量的个数为m+n－1。

（3）伏格尔法（Vogel method，又称运费差额法）

最小元素法的缺点是，为了节省一处的费用，有时造成在其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多。

这种确定初始可行调运方案的方法要求，首先要计算出运输费用表中各行各列中最小运输费用与次小运输费用之间的差的绝对值，然后在具有最大绝对差值的那个行或列中，选择具有最小运输费用的单元格所对应的变量作为基变量，并根据约束条件决定该变量的取值，划去已得到满足的行或列，然后再按同样的规则，重新计算各行各列运费的差值，并确定新的基变量及其取值，如此重复进行下去，直至找到m+n-1个基变量为止。

将表3.20改写成表3.37的形式，并计算运输费用行和列的最小运输费用与次小运输费用之间差的绝对值。

表3.37

需求地B₁所在列的两个最小单位运费的差值13最大，根据运费差额法的规则，应先考虑产地A₂和销售地B₁之间的调运关系，令x₂₁=min{10，3}=3，表明应从产地A₂生产的10吨的物资中，拿出3吨供应销售地B₁。这样，销售地B₁的需要全部得到满足，划去B₁所在列，产地A₂产量剩余7吨，再计算剩下的两个最小运输费用之间的差，得到表3.38。

表3.38

现在产地A₂所在行的两个最小运费的差值最大，而该行剩下的运费中c₂₄=2最小，意味着产地A₂剩下的7吨的物资应全部供应销售地B₄，也即x₂₄=min{7，12}=7。至此，产地A₂的产量已全部供应完毕，划去A₂所在行，销售地B₄需求量还差5吨。再计算运费差，得到表3.39。

表3.39

销售地B₄的运费差最大，x₃₄=min{15，5}=5，得到表3.40。

表3.40

B₂和B₃的运费差同为最大4，可以从中任选一个。在此，我们选择B₂的运费差，x₃₂=min{10，3}=3，得到表3.41。

表3.41

A₁所在行的运费差最大，x₁₃=min{5，12}=5，如表3.42。

表3.42

最终得到初始调运方案，如表3.43所示.

表3.43

由运费差额法得到的调运方案总的运输费用为8×5+5×3+2×7+7×3+4×7+1×5＝123。显然，在三个初始运输方案的确定办法中，运费差额法的调运方案的总费用是最小的。

2.3最优调运方案的判别

回顾单纯形法的求解步骤，对于求最小值的线性规划问题，检查基本可行解是否最优，就是看其非基变量对应的检验数是否全部非负。利用运输问题及其基本可行解的特点，我们常用闭回路法或位势法求出检验数，完成最优调运方案的判别。

（1）闭回路法

在运输问题的初始调运方案表中，从任意一个非基变量所在的单元格（空格，未填入调运量的单元格）出发，沿着纵向或横向行进，遇到适当的填有数字的基变量所在的单元格就可以垂直转弯，并继续前进，最后总能回到原来的出发点。这条行进的路线，会形成一个封闭的折线图，人们称之为闭回路。因此，闭回路就是由水平或垂直的直线所构成的闭合图形。如在例3.16利用最小元素法确定的初始运输方案（表3.36）中，空格x₁₁的闭回路为x₁₁—x₁₃—x₂₃—x₂₁—x₁₁，如表3.44。

表3.44

闭回路一般具有如下的特征：

第一，闭回路必须从某个非基变量所在的单元格（空格，未填入调运量的单元格）出发，最终还要回到原来的出发点；

第二，闭回路必须由连续的水平线段和垂直线段连接而成；

第三，闭回路上的顶点除了出发点所在的单元格外，其余皆为填有数字的单元格，也即基变量所在的单元格。为此，闭回路上的一些线段可以穿越某些基变量所在的单元格（数字格、满格）或其他非基变量所在的单元格（空格）；

第四，对每一个非基变量所在的单元格（空格）都存在而且唯一存在一条闭回路；

第五，构成闭回路的一组单元格的个数一定是偶数。

闭回路法是判定当前基本可行调运方案是否为最优运输方案的一种方法。它相当于单纯形迭代过程中，最优解的判别数。我们把从没有填写过数字的单元格（空格）出发的闭回路中第偶数次拐点运价的总和减去第奇数次拐点运价的总和之差，称为该空格的检验数，记为回路法是根据运输方案检验数的大小，来判定是否获得了最优的运输方案。

由闭回路法得到的检验数的经济意义很明显，它表明：非基变量的取值从0增加一个单位的物资运量，对总的运输费用所带来的改变量。因此，闭回路法最优运输方案的判别规则是：如果检验数中没有负数，才表明当前运输方案为最优运输方案，如果检验数有负数出现，则需要对当前运输方案进行调整。

表3.44中，λ₁₁=（20+10）－（8+5）=17，其余空格的检验数计算结果见表3.45各空格左下角。

表3.45

λ₂₄=－5，根据闭回路法的检验规则，表3.45的调运方案不是最优调运方案。

（2）位势法

利用闭回路法求最优运输方案检验数，首先需要寻找闭回路，因而这种方法的计算工作量比较大。还有一种更为简便一点的运输方案的检验办法，这就是位势法。

位势法又叫做乘数法，通过它来检验最优调运方案的基本做法是：在得到的初始调运方案表中，将基变量所在单元格（数字格、满格）的运输费用，分解成产地和销售地的位势量，在确定出产地和销售地位势量的值之后，计算所有非变量（空格）的检验数，然后据此判定当前调运方案是否为最优方案。

引进m+n个未知变量，u₁，u₂，…，u_m，，v₁，v₂，…，v_n，它们是平衡运输模型的对偶问题的对偶变量，分别对应着平衡运输模型相应的约束方程。对于初始运输方案中基变量（数字格、满格）x_ij的i和j，都有：

u_i+v_j=c_ij

称ui和vj为相应的产地与销售地的位势。

由于i=1，2，…，m，j=1，2，…，n，在上式给出的方程组中共有m+n个未知变量，而方程的数目只有m+n一1个，因此，在求解ui和vj值的时候，需要事先给其中的一个变量赋以任意的值，比如u₁=0，或者一般可以取各行（列）中填入运输量数字最多的行（列）对应的ui=0，这样才能逐个地求出其余变量的值。

现在，根据闭回路求检验数的原理，可以得到利用位势法计算非基变量（空格）检验数的公式：

λ_ij=c_ij－（u_i+v_j）

当λij≥0时，表明当前运输方案为最优运输方案，否则，需要对当前运输方案进行调整。

下面，考虑例3.16利用最小元素法确定的初始运输方案（表3.36）中，利用位势法求检验数。

首先将u₁，u₂，u₃，v₁，v₂，v₃，v₄分别写在运输表对应的行、列上，记得使表中数字格的运价等于相应的行位势与列位势之和。前面提到，因为u₁，u₂，u₃，v₁，v₂，v₃，v₄中有一个自由变量，故可以先取定一个数，比如取各行（列）中填入运输量数字最多的行（列）对应的u_i为零，表3.36中第二行数字格最多，故令u₂=0，由此可得v₁=5，v₂=9，v₃=10，然后u₁=－2，u₃=－6，v₄=7。