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

《运输问题出现退化解时0元添加改进方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、运输问题出现退化解时0元添加改进方法摘要：运输问题表上作业法确定初始基可行解时，可能出现退化解，此时应当在适当的位置添加一个o元。本文探讨了这种情况下，如何恰当选取o元添加的位置，以减少表上作业法调整的工作量，最后提出了o元添加的改进方法。Abstract:Whenthetabledispatchingmethodoftransportationproblemsdeterminesinitialbasicfeasiblesolution,degeneratesolutionmayappear,atthistime,a"0”shouldb

2、eaddedinappropriateposition.Thispaperdiscussedhowtoproperlyselecttheadditionpositionofthe“0”inthissituationsoastoreducetheworkloadoftabledispatchingmethodadjustment,andfinallyproposesimprovementmethodsfor“0”addition.关键词：运输问题；退化解；闭回路；初始基可行解;最优解Keywords:transportationprobl

3、ems；degeneratesolution；closedloop；initialbasicfeasiblesolution；optimalsolution中图分类号:0223文献标识码：A文章编号:1006-4311（2014）02-0059-020引言运输问题及其数学模型：有m个产地Ai可供应某物资量分别为ai（i=l、2、…m）有n个销地Bj其需求量分别bj（j=l、2、…n）从Ai到Bj运输单位物资的运输单价为Cij,将此信息汇总于表1和表2O若用Xij表示Ai到Bj运量（如上表），则在产量平衡条件下，数学模型为minz二■■C

4、ijXijBXij=bj,j=l,2,…n・Xij=ai,i=l,2,-mXij?叟0由于产销不平衡问题易转化为产销平衡问题，故本仅探讨产销平衡类运输问题。求解此类问题用表上作业法比较简便，其实质是单纯形法的一种简化方法，但其在检验数计算和调整过程中，计算量会比较大，特别是在确定初始基可行解出现退化解时，如果0元的添加位置选取不当，会导致后面调整工作量增大，甚至得不到最优解。如何有效选取0元的添加位置，使初始基可行解与最优解更接近，以减少调整工作量。本文提出了一种全新的有效方案。1确定初始基可行解的方法及其改进1.1确定初始基可行解确定

5、初始基可行解方法很多，一般比较简单便于求得最优解的方法包括最小元素法和伏格尔法。而其中，最小元素法往往会为了节省一处的费用而造成其他某处要多花几倍的费用。伏格尔法考虑到一产地产品若不能按最小运费就近供应，就考虑次小运费，其从整体费用的角度出发，克服了最小元素法仅考虑就近的，局部的利益的缺点，往往得出的初始可行解与最优解更相近，甚至直接得到最优方案。用伏格尔法确定初始基可行解的一般步骤：①算出单位运价表中各行各列的最小运费和次小运费之差，找出最大差额；②若同时有几个相等最大差额，则应选取单位运价最小的那行或那列；③在选取的最大差额最小元素

6、上填上尽可能大的运量，同时划去已满足的行或列；④若在表格（i,j）填入某一数后，出现Ai处的余量和BJ处的需量相等，这时在产销平衡表上（i,j）处填一个数，在单位运价表中相应的划去该行和该列，并且在对应的那行或那列的任一不构成闭合回路的空格处添加0元；①重复上述步骤直至给出初始基可行解。1.2确定初始基可行解的改进方法在上述用伏格尔法确定初始基可行解的一般方法中，有些文献认为0元的添加比较随意，甚至都没有给出“0元的添加应当不能在表中构成闭合回路”这一要求（否则在用位势位法检验时，某些空格可能找不到闭合回路）。如《运筹学》教材编写组编一

7、3版中关于0元的添加定义比较随意，好在由唐文广等学者给出了这一明确的要求。但是这种0元位置的选取方法某些时候仍然得不到最优的初始基可行解，依然会导致后面的调整工作量比较大，甚至得不到最优解。下面举一实例分别说明无法得到最优解和导致调整量比较大的情况。1.2.1选取的0元位置不当导致无法得到最优解如表3所示产销平衡问题，表中“一”表示无此运输线路，用伏格尔法计算差额如表4。若在空格（2,4）处填入10后，出现了退化现象，需添加一个0元，若此时仅仅满足上文中“用伏格尔法确定初始基可行解的一般步骤”中的步骤④的要求，把0元添加到如表5所示位置

8、（4,4）处，则在用位势法计算检验数时，会导致很多空格处的检验数位负，如上表6用位势法算取的某些空格处检验数都为负，且后面无论怎么调整都得不到最优解。1.2.2选取的0元位置不当导致调整工作量增大同样取上例