伏格尔法-详细解读

伏格尔法-详细解读

伏格尔法伏格尔法（VogelMethod）目录1什么是伏格尔法[1]2伏格尔法的步骤[1]3伏格尔法案例分析3.1案例一：伏格尔法的实例分析[1]3.2案例二：伏格尔法在退化性运输问题中的应用[2]4Reference什么是伏格尔法[1]伏格尔法又称差值法，该方法考虑到，某产地的产品如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。伏格尔法的步骤[1]伏格尔法一般能得到一个比用西北角法和最小元素法两种方法所得的初始基本可行解更好的初始基本可行解。伏格尔法要求首先计算出各行各列中最小的cij，与次小的cij之间的差的绝对值，在具有最大差值的那行或列中，选择具有最小的cij的方格来决定基变量值。这样就可以避免将运量分配到该行（或该列）具有次小的cij的方格中，以保证有较小的目标函数值。所以，伏格尔法的基本步骤如下。1、算出各行各列中最小元素和次小元素的差额，并标出差额最大的（若几个差额同为最大，则可任取其一）。2、在差额最大的行或列中的最小元素处填上尽可能大的数。3、对未划去的行列重复以上步骤，直到得到一个初始解。由此可见，伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。伏格尔法案例分析案例一：伏格尔法的实例分析[1]例：某公司有三个加工厂A1,A2,A3生产某产品，每日的产量分别为7T，4T，9T，该公司把这些产品分别运往四个销售点B1,B2,B3,B4，各销售点的每日销量分别为3T，6T，5T，6T。从各工厂到各销售点的单位运价如表1所示。问该公司如何调运产品，才能在满足各销售点需要量的前提下，使总费用最少？表1：B1B2B3B4A1

A2

A33

1

711

9

43

2

1010

8

5第一步：求各行各列最小和次小元素的差值。在表2中，各行的差值分别为0，1，1，各列的差值分别为2，5，1，3。可见第二列差值最大，首先考虑第二列，在第二列中最小的cij为c32＝4，令x32＝min{6，9}＝6，填入表5-10中，第二列饱和，划去该列。第二步：求余下的各行各列最小和次小元素的差值。对剩下的方格重新计算各行各列的差值，各行差值分别为0，1，2，各列差值分别为2，1，4，第四列差值最大，在第四列中，最小的cij为c34=5，令x34＝min{6，9-6}=3，于是第三行饱和，划去第三行。第三步：重复上述过程。可得其他基变量的值为：x21=3,x13=4,x23=1,x14=3。见表3。此例的解所对应的Z=1×3+4×6+3×5+10×2+8×1+5×3=85。案例二：伏格尔法在退化性运输问题中的应用[2]求解线性优化运输问题的方法有两种：一种是将运输问题转化为线性规划问题，然后利用单纯形法求解；另一种是表上作业法，一般是先利用近似方法确定初始调运方案，然后检验该调运方案是否为最优，如果是最优调运方案则停止计算，如果还不是则进行调整，然后再检验，如此循环直到检验得到最优调运方案为止。前一种方法计算工作量较大，表上作业法计算量则相对较小。表上作业法的计算量主要取决于初始调运方案的近似程度，近似程度越高，后面经过检验、调整等循环步骤得到最优调运方案的速度就越快，从而计算量就越小。常见的确定初始调运方案的近似方法有西北角法、最小元素法和伏格尔法。其中伏格尔法是近似方法中近似程度最好的一种方法，这种方法得到的结果很接近最优调运方案。但在处理退化性的运输问题的时候，各种教材对伏格尔法的描述中却并不统一，多数教材描述不够精确，这都严重影响伏格尔法的近似程度，文中将以实例的计算来进行说明，给出伏格尔法在处理退化性运输问题中的规范应用方法以保证伏格尔法在应用中的计算效率。一、伏格尔法伏格尔法揭示，如果在任何行或列上，最便宜的选择没有被采用，那么至少次便宜的选择应该被采用．如果采用了次便宜的选择，就存在一个罚金成本，其数额至少等于该行列中最便宜的选择与次便宜的选择之间的差。伏格尔法中确定初始调运方案的具体步骤如下：第一步，计算运价表中每一行的罚金成本，即每行中次便宜选择的成本和最便宜选择的成本之差。第二步，计算运价表中每一列的罚金成本，即每列中次便宜选择的成本和最便宜选择的成本之差。第三步，找出这一罚金成本的最大值，并找出相应行或列成本的最低元素。第四步，尽可能为这一元素分配运输任务——以可能的供应量或剩余的需求量为限分配运输任务。分配了运输任务的格称为有货流格。第五步，从相应的供应量和需求量中减掉这一轮中已经分配的数量，然后不必再考虑那些已经没有剩余供应量的行和没有剩余需求量的列，重复这一步骤，直到所有的供应量用完，所有的需求量都已得到满足。二、伏格尔法在退化性运输问题中的应用问题线性运输问题也是一种线性规划问题，其基变量的个数应为m+n-1个,其中，m为运价表中的行数，n为运价表中的列数。在用近似方法求解线性运输问题时，运价表中最后应该有，m+n-1个有货流格，即相当于线性规划问题中的m+n-1个基变量。但可能遇到有货流格少于，m+n-1个的情况．这就叫做退化问题。当出现退化问题时应补充零货流格，即货流量为零的格，相当于线性规划问题中出现基变量等于零的情况。但在具体做法上，很多教材并不统一。在各种教材中，都在着重强调有货流格的个数应该为m+n-1，也就是说明这种线性运输问题是一种有，m+n-1个相互独立的约束条件的线性规划问题。退化的运输问题在计算过程中总会出现某行与某列同时平衡的时候，一般是认为划去相应行或列均可，然后再继续按照伏格尔法进行新一轮的计算。为了满足供需平衡以及有货流格为，m+n-1的要求，会在必要的时候在相应格中填上数字“0”，使该格成为零货流格。但这种说法是不够准确的，在实际操作中可能会带来比较大的误差，这样就体现不出伏格尔法的优点了。例：用伏格尔法求表l所示的运输问题的初始调运方案。表4运价表产地不同销售地运价产量ABCDI102201115Ⅱl2792025Ⅲ2l416185销量515l51O解：首先计算各行各列的罚金成本，结果见表。表5第一次计算所得各行各列罚金成本的运价表产地不同销售地运价产量行罚金成本ABCDI1O22011158Ⅱ12792O252Ⅲ21416l8512销量515151O列罚金成本8577罚金成本最大为12，相应行的最小运价单元格为(Ⅲ，A)，所以应最先满足其相应行或列的供需要求。此时发现此单元格对应的供应量与需求量相等，即当在(Ⅲ，A)单元格中填人“5”后供需同时满足，由此可以判断该运输问题为退化问题。此时如果将第一列划去然后再继续用伏格尔法计算，结果见表。表6在退化的运输问题中期去相应列的计算表产地不同销售地运价产量行罚金成本ABCDI2(5)11(10)158(9)9Ⅱ7(10)9(15)20(10)2522(11)Ⅲ2(5)18(0)5(12)22销量51515lO列罚金成本8577-577--77由此调运表格可得运费为2×5+2×15+9×15+l1×O十2O×1O+18×O＝375。如果在上表5中(Ⅲ，A)单元格填入“5”后相应行列供需要求同时满足，而选择将第三行划去，继续使用伏格尔法计算得到的结果如表7所示。表7在退化的运输问题中划去相应行的计算表产地不同销售地运价产量行罚金成本ABCDI2(5)11(10)15888(8)Ⅱ7(10)9(15)252255Ⅲ2(5)5(12)---销量1515lO列罚金成本857725(11)925-(9)25--由此调运表格可得运费为2×5+12×0+2×5+7×10+9×l5+11×10=335。表6和表7都是按照伏格尔法计算得到的，但显然表7的结果比表6的结果更好，由此可见伏格尔法在退化的运输问题的应用中，除了要注意补充零货流格以保证有货流格的个数为m+n-1外，还要注意当运价表中行列的供需要求同时得到满足时应进行特殊处理。三、伏格尔法在退化性运输问题中的规范应用方法用伏格尔法求运输问题时，若在计算过程中出现一个有货流格使得其所在的行与列的供需要求同时得到满足时，应将其所在的行与列同时划去。为了保证运输方案有，m+n-1个有货流格，还必须在相应行或列中任选一个空格填人“0”。按此方法计算的结果如表8所示。表8在退化的运输问题中规范方法的计算表产地不同销售地运价产量行罚金成本ABCDI2(5)11(10)15899Ⅱ7(10)9(15)2522(13)Ⅲ2(5)16(O)5(12)(12)-销量1515lO列罚金成本8577-5(11)9-5-9由此调运表格可得运费为2×5+2×5+7×1O+9×15+16×O+11×10=335。如此计算保证了结果最优．而且罚金成本比表7少算一次。可见要想保证伏格尔法在应用过程中的效率，当运输问题是一个退化性问题时．即在用伏格尔法的计算过程中出现一个有货流格使得其所在的行与列的供需要求同时得到满足时，应