摘 要：运输在现代经济活动中占有重要的地位，管理者通常会借助运筹学中的运输问题的数学模型求解来制定一个成本最低、切实可行的最优方案。本文举出实证对最小元素法和伏格尔法求初始可行基进行对比，以求更好的应用于实践之中。
关键词：运筹学 运输问题 最小元素法 伏格尔法
物资的调运工作是生产活动中必不可少的环节，如何实现运输费用最低、制定最优的调运方案是当前经济和管理研究的热点和前沿话题。在运筹学中，根据各地的生产量和需求量及各地之间的运输费用，制定运输方案，使得运输费用最小，这样的问题称为运输问题。为了解决该问题，运筹学长期展开对运输问题的研究并建立运输问题的数学模型课题及一系列计算方法，为此提供了相应的理论基础和可行办法。表上作业法是求解该问题中最常用也是最有效的方法，在利用表上作业法求解运输问题数学模型初始可行基解的确定中，有诸多方法例如：最小元素、伏格尔法、西北角法等。通过对比最小元素法和伏格尔法，认识这两种方法的共性与差异，以求更好的认识到这两种方法在运用中各自的特点，助力于其在实践中更好的发挥作用。
一、运输问题的数学模型
已经知有m个生产地点Ai，i=1，2，3…..m。可供应某种物资，其供应量（产量）分别为ai，i=1，2，3…..m，有n个销地Bj，j=1，2…，n，其需要量分别为bj，j=1，2…，n，从Ai到Bj运输单位的物资运价（单价）为Ci。将其汇总于产销平衡表和单位运价表中，若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得运费最小的调运方案，可求解以下数学模型：
上述模型即为运输问题的数学模型。运输问题的数学模型是一个线性规划模型，求解方法为单纯型法。由于运输问题的特殊性，可以采用简化了的单纯型发即表上作业法和图上作业求解。该模型包含m×n个变量，（m+n）个约束方程。在产销不平衡的运输问题的数学模型中，当产大于销（∑mi=1ai>∑mi=1bj）时，约束条件∑mi=1xij=ai（i=1，2，…，m）变为∑mj=1xij≤ai（i=1，2，…，m）即可；当销大于产（∑mi=1ai<∑mj=1bj）时，约束条件∑mi=1xij=bj（j=1，2，…n）变为∑mi=1xij≤bj（j=1，2，…，n）即可，对于产销不平衡的问题，均可转化产销平衡的问题，故只考虑产销平衡的情况。建立一个运输问题的实例：有A1、A2、A3三个纺织品生产厂，可供某纺织品8、5、10，现将产品销往B1、B2、B3、B4四个生产商，其需求分别为4、7、6、6.安排计划使运输费用最少。（运费见表1）
二、表上作业法求解运输问题的数学模型
表上作业法是单纯形法在求解运输问题时的一種简化方法，其实质是单纯型法，也称运输问题单纯型法，其具体计算步骤如下：
Step1：找出初始基可行解（初始调运方案）。即在有（m×n）的产销平衡表上按一定规则，给出m+n-1个数字，称为数字格。它们就是初始基变量的取值。常用的方法有最小元素法、伏格尔法（Vogel近似法）、西北角法等；
Step2：求各非基变量的检验数并判断是否得到最优解。如果得到最优解，则停止计算，否则进入下一环节；
Step3：确定换入变量和换出变量，即调整运量，找到新的基可行解；
Step4：重复step2、step3直到找到最优解为止。
从表上作业法的运算过程中，我们不难发现初始基解的确定是十分重要的。确定的方法有很多，在此，我们只讨论其中最常用的最小元素法和伏格尔法。
1.最小元素法。最小元素法的思想就是就近运送，即最小运价cij对应的变量xij优先赋xij=min{ai，bj}（从单位运价表中最小的运价开始确定运输关系，然后次小），直到得出初始基可以解为止。
最小元素法求解运输问题实例中的初始基本可行解：
Step1：从表1中找出运价最小为2，表示将A2纺织厂的产品优先供应给B1。因为a2b1，A2除满足B1的全部需求外还剩余1单位产品。在（A2，B1）的交叉格中填上4。并将表1的B1列划去。
Step2：划去的元素中再找出运价最小的3，按照第一部的方法进行。这样一步一步地进行下去，直到单位运价表上所有元素被划去为止。最后在产销平衡表上得到一个调运方案，见表2。
2.伏格尔法。伏格尔法考虑到产品如果不能按照最小运费就近供应，就考虑次小运费，说明不能按照最小运费调运时，运费增加越多。因而在差额最大处，就应当采用最小运费调运。
伏格尔发求解运输问题实例中的初始基本可行解：
Step1：在表1中分别计算出各行和和列的最小运费和次小运费的差额，并填入该表的最右列和最下行。
Step2：从行或列差额中选出最大者，现在它所在行或列中最小元素。新表中B2列是最大差额所在列。B2列中最小元素为5.可确定纺织厂A3的产品优先管院B2的需要。因为a3b2，所以B2列无剩余，将B2列从运价表中划去，并对未划去的元素再分别计算各行、各列的最小运费和次小运费的差额并填入该表最右列和最下行。
Step3：重复step、step2，直到给出初始解为止。得到表7，即为一个调运方案，即初始基解。
三、两种方法对比
伏格尔法和最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比最小元素法的初始解更接近最优解。
1.伏格尔法求得的初始基解较最小元素法求得的解更接近于最优解。从实例中可以看出，用最小元素法求得的一组方案最小运费为117单位，而用伏格尔法求得的可行方案的最小运费为116单位，显而易见，伏格尔法求解的结果较最小元素法更为优化。伏格尔法考虑到最小费用与次小费用的差额越大，说明不能按最小运费调运时，运费增加就越多，因而对差额最大处采用最小运费调运。伏格尔法的求解思想较最下元素法从单位运价表中最小运价确定供销关系的求解思路更注重到元素间的内在关系，所以在通常情况下两种方法求解的结果会相同，但当最小费用与次小费用差额较大时会有一定的区别，提现出伏格尔法在这方面的优越性。
2.最小元素法较伏格尔法简单易懂，且操作更为方便。最小元素法在求解的过程中只用简单的对比运销平衡表中的运价元素的大小，计算简单，能够快速的确定运销关系。伏格尔法需要先计算各行各列间最小元素与次小元素的差值，比较差值的大小并在最大差值存在的行或列中寻找最小元素，从而确定运销关系。可见最小元素法较伏格尔法简单。
参考文献：
[1]《运筹学》教材编写组.运筹学[M].4版.北京：清华大学出版社，2012.
[2]习在筠，刘桂真运筹学[M].3版.北京：高等教育出版社，2007.
[3]邓成梁主编.运筹学的原理和方法（第二版）[M].武汉：华中科技大学出版社，2002.
[4]胡新生.物流定量分析方法[M].北京：中央广播电视大学出版社，2005-02，24.
推荐访问： 格尔 最小 数学模型 元素 运输
