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