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

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

1、ValueEngineering·59·．运输问题出现退化解时0元添加的改进方法∑∑ImprovementMethodsof”0”AdditionforDegenerateSolutioninTransportationProblemsCX丁龙DINGLong；付小连FUXiao—lian；吴珊WUShan；苏瑞超SURui—chao(三峡大学水利与环境学院，宜昌443002】(CollegeofHydraulic＆EnvironmentalEngineeringofChinaThreeGorgesUniversity，Yichang4302，China)摘要：运输问题表上作业法确定初始基可

2、行解时，可能出现退化解，此时应当在适当的位置添加一个O元。本文探讨了这种情况下，如何恰当选取0元添加的位置，以减少表上作业法调整的工作量，最后提出了0元添加的改进方法。Abstract：Whenthetabledispatchingmethodoftransportationproblemsdeterminesinitialbasicfeasiblesolution，degeneratesolutionmayappear，atthistime，a’0’shouldbeaddedinappropriateposition．Thispaperdiscussedhowtoproperlyselec

3、ttheadditionpositionoftlle”0”inthissituationSOastoreducetheworkloadoftabledispatchingmethodadjustment．andfinallyproposesimprovementmethodsfor”0”addition．关键词：运输问题；退化解；闭回路；初始基可行解；最优解Keywords：transportationproblems；degeneratesolution；closedloop；initialbasicfeasiblesolution；optimalsolution中图分类号：0223文献标

4、识码：A文章编号：1006—431l(2014)02—059—02O引言确定初始基可行解方法很多，一般比较简单便于求得运输问题及其数学模型：最优解的方法包括最小元素法和伏格尔法。而其中，最小有m个产地A可供应某物资量分别为凰(i=l、2、⋯112)元素法往往会为了节省一处的费用而造成其他某处要多有n个销地Bi其需求量分别bj(j=1、2、⋯n)花几倍的费用。伏格尔法考虑到一产地产品若不能按最小从Ai到运输单位物资的运输单价为C，将此信息运费就近供应，就考虑次小运费，其从整体费用的角度出汇总于表1和表2。发，克服了最小元素法仅考虑就近的，局部的利益的缺点，往往得出的初始可行解与最优解更相近，甚

5、至直接得到最表1表2优方案。＼掰魈＼＼销地产＼12n产量产12n产曩用伏格尔法确定初始基可行解的一般步骤：①算出单位运价表中各行各列的最小运费和次小运1Cl1Cl2C1al1X儿X也Xhal2CmC∞Ca22x21X丑a2费之差，找出最大差额；●●●●●●●●●●●●●●●_●●●_●●●●②若同时有几个相等最大差额，则应选取单位运价最CⅡdCCmammXlXXmam销量blb2b销量blb2b小的那行或那列：③在选取的最大差额最小元素上填上尽可能大的运著用X表示Ai到Bj运量(如上表)，则在产量平衡条量，同时划去已满足的行或列：件下，数学模型为④若在表格(i，)填入某一数后，出现Ai处的余

6、量和Bi处的需量相等，这时在产销平衡表上(i，i)处填一个数，∑Xd=bjIJF12．．ni=1在单位运价表中相应的划去该行和该歹9，并且在对应的那行或那列的任一不构成闭合回路的空格处添加0元：∑Xij=a4i：12．．m⑤重复上述步骤直至给出初始基可行解。j=11．2确定初始基可行解的改进方法Xij0在上述用伏格尔法确定初始基可行解的一般方法中，由于产销不平衡问题易转化为产销平衡问题，故本仅有些文献认为0元的添加比较随意，甚至都没有给出“0探讨产销平衡类运输问题。求解此类问题用表上作业法比元的添加应当不能在表中构成闭合回路”这一要求(否则较简便，其实质是单纯形法的一种简化方法，但其在检验在

7、用位势位法检验时，某些空格可能找不到闭合回路)。如数计算和调整过程中，计算量会比较大，特别是在确定初《运筹学》教材编写组编一3版中关于O元的添加定义比始基可行解出现退化解时，如果0元的添加位置选取不较随意，好在由唐文广等学者给出了这一明确的要求。但当，会导致后面调整工作量增大，甚至得不到最优解。如何是这种0元位置的选取方法某些时候仍然得不到最优的有效选取O元的添加位置，使初始基可行解与最优解更接初始基可行解，