确定初始无误的基可行解方法简单实用

这与一般线性规划问题不同，产销平衡的运输问题总是存在可行解，因此有

故运输问题存在最优解。

确定初始集可行解的方法很多，一般希望的方法是既简便，又尽可能地接近最优解。下面介绍两种方法：最小元素法和伏格尔（Vogel）法。

1.最小元素法

此方法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到给出初始基可行解为止。下面以例3-1 为例进行讨论。

第一步：从表3-3中找出最小运价1，它表示先将 A2的产品供应给 B1。因 a2＞b1，A2除满足 B1的全部需要外，还可多余1 t 产品。在表3-4的（A2，B1）的交叉格处填上3，得表3-5，并将表3-3的B1列运价划去，得表3-6。

表3-5

表3-6

第二步：在表3-6 未划去的元素中再找出最小运价2，确定 A2多余的1 t 供应 B3，并给出表3-7 和表3-8。

表3-7

表3-8

第三步：在表3-8 未划去的元素中再找出最小运价3；这样一步步地进行下去，直到单位运价表上的所有元素划去为止，最后在产销平衡表上得到一个调运方案，如表3-9 所示。此方案的总运费为86 元。

表3-9

用最小元素法给出的初始解是运输问题的基可行解，其理由为：

（1）用最小元素法给出的初始解，是从单位运价表中逐次地挑选最小元素，并比较产量和销量。当产大于销，划去该元素所在列；当产小于销，划去该元素所在行；然后在未划去的元素中再找最小元素，再确定供应关系。这样在产销平衡表上每填入一个数字，在运价表上就划去一行或一列。表中共有m 行n 列，总共可划（m+n）条直线。但当表中只剩一个元素时，当在产销平衡表上填上这个数字时，要在运价表上同时划去一行和一列，此时把单价表上的所有元素都划去了，相应地在产销平衡表上填了（m+n-1）个数字，即给出了（m+n-1）个基变量的值。(www.xing528.com)

（2）这（m+n-1）个基变量对应的系数列向量是线性独立的。

证明　若表中确定的第一个基变量为，它对应的系数列向量为

因当给定的值后，将划去第i1行或第 j1列，即其后的系数列向量中不再出现因而不可能用解中其他向量的线性组合表示。类似地，给出第二个，……，第（m+n-1）个。这（m+n-1）个向量都不可能用解中其他向量的线性组合表示，故这（m+n-1）个向量是线性独立的。

用最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列，这时就出现退化。关于退化时的处理将在3.2.4中讲述。

2.伏格尔法

最小元素法的缺点是：为了节省一处的费用，有时会造成在其他处要多花几倍的运费。而伏格尔法则考虑的是，一产地的产品假如不能按最小运费就近供应，就考虑次小运费。这就有一个差额问题，差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大点的处理，就应当采用最小运费调运。基于此，伏格尔法的步骤是：

第一步：在表3-3中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，如表3-10 所示。

表3-10

第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表3-10中，B2列是最大差额所在列。B2列中最小元素为4，可确定 A3的产品先供应 B2的需要，得表3-11。同时将运价表中的B2列数字划去，如表3-12 所示。

表3-11

第三步：对表3-12中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复第一、二步，直到给出初始解为止。用此法给出例3-1的初始解，列于表3-13中。

表3-12

表3-13

由以上可见：伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。

本例用伏格尔法给出的初始解就是最优解。