表上作业法解决运输问题.doc

_表上作业法解决运输问题谢荣华、林建、岳钱华、叶俊君【摘要】在物资调运问题中,希望运输费用最少总是人们最为关心的一个目标。在各种设定条件的约束下,如何寻找使得总运输费用最少的最优的运输方案是运输问题的核心。为给社会生产(生活)提供既便捷又经济实惠的物资调运方案,运输问题模型的求解方法可以产生最优的决策方案。因此对运输问题的深入研究具有极其重要的理论意义和实际应用价值。表上作业法是解决运输问题的重要方法本文讨论了产销平衡运输问题的表上作业法，利用伏格尔法求初始方案，位势法求检验数，闭合回路发对可行解进行调整和改进，直至求出最优解。【关键词】运筹学、运输问题、改善优化、表上作业法一、理论依据运输问题的表上作业法步骤1、制作初始平衡表用“西北最大运量，然后，每增加角方法”：即在左上角先给予最大运量，然后，每增加一个运量都使一个发量或手里饱。如果所有运量的数字少于（m+n-1），则补0使之正好（m+n-1）个。（注:补零时不能使这些书构成圈。）2、判断初始方案是否最优（1）求位势表：对运价表加一行一列，圈出运价表中相应于有运量的项，在增加的行列上分别添上数，使这些元素之和等于圈内的元素。这些元素称为位势数。（2）求检验数，从而得到检验数表。 结论：若对任意检验数小于等于0，则该方案最优，否则进入3进行调整.3、调整（1）找回路：在检验数大于0对应的应量表上对应元素为起点，沿横向或纵向前进，如遇到有运量的点即转向，直至起点，可得到一个回路。（2）找调整量：沿上述找到的回路，从起点开始，在该回路上奇数步数字的最小者作为调整量。（3）调整方式：在该回路上奇数步-，偶数步+，得到新回路。重复上述步骤，使所有检验数小于0，即得到最优方案。二、背景鉴于市场竞争日益激烈，消费者需求渐趋多样，工厂作为市场消费品的产出源头，唯有对这种趋势深刻理解、深入分析，同事具体的应用于实际中，才能使自身手艺，断发展壮大，不被新新行业所淘汰。对于今天的重点研究对象食品工厂而言，由于在不同产品在原料使用、物料损耗、市场价格等方面均存在各种差异，如何确定各产品的生产配比，以及在最优的生产配比方案之下工厂能够达到最大的产值，都是值得进行探讨研究的现实问题。三、实例-+=l甲、乙、丙三个城市每年需要煤炭分别为：320、250、350万吨，由A、B两处煤矿负责供应。已知煤炭年供应量分别为：A400万吨，B450万吨。由煤矿至各城市的单位运价(万元/万吨)见表1。由于需大于供，经研究平衡决定，甲城市供应量可减少030万吨，乙城市需要量应全部满足，丙城市供应量不少于270万吨。试求将供应量分配完又使总运费为最低的调运方案。表1：甲乙丙A151822B212516分析：甲、乙、丙三个城市每年的煤炭总需求量为：320+250+350=920万吨，A、B两处煤矿年煤炭总供应量为：400+450=850万吨。虚拟一个C煤矿，其供应量为70万吨，其单位运价如表2所示。表2:甲甲乙丙丙供应A1515182222400B2121251616450CM0MM070需求2903025027080920利用伏格尔法求出初始解如表3所示。表3：甲甲乙丙丙供应A150250400304070需求2903025027080920用位势法求各非基变量的检验数，如表4所示。甲甲乙丙丙uiA015515018122212220B021521125016006CM-5M00M-80MM00-10vj1510181010表4：由于表4中的所有非基变量检验数均为非负，所以表3中的解即为最优解。按表3中的方案可得运费最少为14650万元。四、结论对于运筹学在运输问题的研究，首先运筹学在寻求物流运输成本最低的运输组合中起着重要的作用，在企业拥有资源有限的情况下，比如运输工具有限。运输人员有限，运输时间的限制等，利用管理运筹学把现实中的抽象问题转化成具体的数学问题，再建立相应的数学模型并求解，使问题得到解决，因而使运输成本最小化。其次，我们在算法中引进这样的运算机制：将场地、销地、运输工具、运输数量等进行综合评估后得找到最优运输方案和运输路线及运量，运用管理运筹学表上作业法算法找出最优运输方案。第三，随着企业在运输过程中提出的目标不断增加，并且决定运输成本的因素也不断增加，问题会越来越复杂，如果不借助科学的方法，