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

运输问题出现退化解时0元添加改进方法 摘要运输问题表上作业法确定初始基可行解时， 可能出现退化解，此时应当在适当的位置添加一个o元。本 文探讨了这种情况下，如何恰当选取o元添加的位置，以减 少表上作业法调整的工作量，最后提出了 0元添加的改进方 法。 Abstract When the table dispatching of transportation problems determines initial basic feasible solution, degenerate solution may appear, at this time, a 0 should be added in appropriate position. This paper discussed how to properly select the addition position of the 0 in this situation so as to reduce the workload of table dispatching adjustment, and finally proposes improvement s for 0 addition. 关键词运输问题；退化解；闭回路；初始基可行解; 最优解 Key words transportation problems； degenerate solution； closed loop； initial basic feasible solution； optimal solution 中图分类号0223文献标识码A文章编号1006-4311 2014 02-0059-02 0引言 运输问题及其数学模型 有m个产地Ai可供应某物资量分别为ai （il、2、山） 有n个销地Bj其需求量分别bj （jl 2、） 从Ai到Bj运输单位物资的运输单价为Cij,将此信息 汇总于表1和表2o 若用Xij表示Ai到Bj运量（如上表），则在产量平衡 条件下，数学模型为 minz 二■■CijXij BXijbj, jl, 2, n・Xijai, il, 2, -mXij叟 0 由于产销不平衡问题易转化为产销平衡问题，故本仅探 讨产销平衡类运输问题。求解此类问题用表上作业法比较简 便，其实质是单纯形法的一种简化方法，但其在检验数计算 和调整过程中，计算量会比较大，特别是在确定初始基可行 解出现退化解时，如果0元的添加位置选取不当，会导致后 面调整工作量增大，甚至得不到最优解。如何有效选取0元 的添加位置，使初始基可行解与最优解更接近，以减少调整 工作量。本文提出了一种全新的有效方案。 1确定初始基可行解的方法及其改进 1.1确定初始基可行解 确定初始基可行解方法很多，一般比较简单便于求得最 优解的方法包括最小元素法和伏格尔法。而其中，最小元素 法往往会为了节省一处的费用而造成其他某处要多花几倍 的费用。伏格尔法考虑到一产地产品若不能按最小运费就近 供应，就考虑次小运费，其从整体费用的角度出发，克服了 最小元素法仅考虑就近的，局部的利益的缺点，往往得出的 初始可行解与最优解更相近，甚至直接得到最优方案。 用伏格尔法确定初始基可行解的一般步骤 ① 算出单位运价表中各行各列的最小运费和次小运费 之差，找出最大差额； ② 若同时有几个相等最大差额，则应选取单位运价最小 的那行或那列； ③ 在选取的最大差额最小元素上填上尽可能大的运量， 同时划去已满足的行或列； ④ 若在表格（i, j）填入某一数后，出现Ai处的余量 和Bj处的需量相等，这时在产销平衡表上（i, j）处填一 个数，在单位运价表中相应的划去该行和该列，并且在对应 的那行或那列的任一不构成闭合回路的空格处添加0元； ⑤ 重复上述步骤直至给出初始基可行解。 1. 2确定初始基可行解的改进方法 在上述用伏格尔法确定初始基可行解的一般方法中，有 些文献认为0元的添加比较随意，甚至都没有给出“0元的 添加应当不能在表中构成闭合回路这一要求（否则在用位 势位法检验时，某些空格可能找不到闭合回路）。如运筹 学教材编写组编一 3版中关于0元的添加定义比较随意， 好在由唐文广等学者给出了这一明确的要求。但是这种0元 位置的选取方法某些时候仍然得不到最优的初始基可行解， 依然会导致后面的调整工作量比较大，甚至得不到最优解。 下面举一实例分别说明无法得到最优解和导致调整量比较 大的情况。 1.2.1选取的0元位置不当导致无法得到最优解 如表3所示产销平衡问题，表中“一”表示无此运输线 路，用伏格尔法计算差额如表4。 若在空格（2, 4）处填入10后，出现了退化现象，需 添加一个0元，若此时仅仅满足上文中“用伏格尔法确定初 始基可行解的一般步骤”中的步骤④的要求，把0元添加到 如表5所示位置（4, 4）处，则在用位势法计算检验数时， 会导致很多空格处的检验数位负，如上表6用位势法算取的 某些空格处检验数都为负，且后面无论怎么调整都得不到最 优解。 1.2.2选取的0元位置不当导致调整工作量增大 同样取上例，若在确定X24l0时，把0元选择填入方 格（2, 3）,如表7。继续在空格（3, 2）处填入20后，又 出现了退化现象，需添加0元，若仅满足步骤④要求，将0 元随意添至（3, 1）格，如下表7o通过计算表7空格检验