运输问题出现退化解时0 元添加的改进方法.docVIP

精品论文 参考文献 运输问题出现退化解时0 元添加的改进方法 Improvement Methods of 0 Addition for Degenerate Solution in Transportation Problems 　　丁龙DING Long曰付小连FU Xiao-lian曰吴珊WU Shan曰苏瑞超SU Rui-chao（三峡大学水利与环境学院，宜昌443002）（College of Hydraulic amp; Environmental Engineering of China Three Gorges University，Yichang 443002，China） 　　摘要院运输问题表上作业法确定初始基可行解时，可能出现退化解，此时应当在适当的位置添加一个0 元。本文探讨了这种情况下，如何恰当选取0 元添加的位置，以减少表上作业法调整的工作量，最后提出了0 元添加的改进方法。 　　Abstract: When the table dispatching method of transportation problems determines initial basic feasible solution, degenerate solutionmay appear, at this time, a 0 should be added in appropriate position. This paper discussed how to properly select the addition position ofthe 0 in this situation so as to reduce the workload of table dispatching method adjustment, and finally proposes improvement methods for0 addition. 　　关键词院运输问题；退化解；闭回路；初始基可行解；最优解 　　Key words: transportation problems；degenerate solution；closed loop；initial basic feasible solution；optimal solution 　　中图分类号院O223 文献标识码院A 文章编号院1006-4311（2014）02-0059-020 　　引言运输问题及其数学模型：有m 个产地Ai 可供应某物资量分别为ai（i=1、2、…m）有n 个销地Bj 其需求量分别bj（j=1、2、…n）从Ai 到Bj 运输单位物资的运输单价为Cij，将此信息汇总于表1 和表2。 　　由于产销不平衡问题易转化为产销平衡问题，故本仅探讨产销平衡类运输问题。求解此类问题用表上作业法比较简便，其实质是单纯形法的一种简化方法，但其在检验数计算和调整过程中，计算量会比较大，特别是在确定初始基可行解出现退化解时，如果0 元的添加位置选取不当，会导致后面调整工作量增大，甚至得不到最优解。如何有效选取0 元的添加位置，使初始基可行解与最优解更接近，以减少调整工作量。本文提出了一种全新的有效方案。 　　1 确定初始基可行解的方法及其改进1.1 确定初始基可行解确定初始基可行解方法很多，一般比较简单便于求得最优解的方法包括最小元素法和伏格尔法。而其中，最小元素法往往会为了节省一处的费用而造成其他某处要多花几倍的费用。伏格尔法考虑到一产地产品若不能按最小运费就近供应，就考虑次小运费，其从整体费用的角度出发，克服了最小元素法仅考虑就近的，局部的利益的缺点，往往得出的初始可行解与最优解更相近，甚至直接得到最优方案。 　　用伏格尔法确定初始基可行解的一般步骤：淤算出单位运价表中各行各列的最小运费和次小运费之差，找出最大差额；于若同时有几个相等最大差额，则应选取单位运价最小的那行或那列；盂在选取的最大差额最小元素上填上尽可能大的运量，同时划去已满足的行或列；榆若在表格（i，j）填入某一数后，出现Ai 处的余量和Bj 处的需量相等，这时在产销平衡表上（i，j）处填一个数，在单位运价表中相应的划去该行和该列，并且在对应的那行或那列的任一不构成闭合回路的空格处添加0 元；虞重复上述步骤直至给出初始基可行解。 　　1.2 确定初始基可行解的改进方法在上述用伏格尔法确定初始基可行解的一般方法中，有些文献认为0 元的添加比较随意，甚至都没有给出“0元的添加应当不能在表中构成闭合回路”这一要求（否则在用位势位法检验时，某些空格可能找不到闭合回路）。如《运筹学》教材编写组编一3 版中关于0 元的添加定义比较随意，好在由唐文广等学者给出了这一明确的要求。但是这种0 元位置的选取方法某些时候仍然得不到最