运输问题出现退化解时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 (i=l、2、…山) 有n个销地Bj其需求量分别bj (j=l> 2、•••!!) 从Ai到Bj运输单位物资的运输单价为Cij,将此信息 汇总于表1和表2o 若用Xij表示Ai到Bj运量(如上表),则在产量平衡 条件下,数学模型为 minz 二■■CijXij BXij=bj, j=l, 2, •••n・Xij=ai, i=l, 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元位置不当导致调整工作量增大 同样取上例,若在确定X24=l0时,把0元选择填入方 格(2, 3),如表7。继续在空格(3, 2)处填入20后,又 出现了退化现象,需添加0元,若仅满足步骤④要求,将0 元随意添至(3, 1)格,如下表7o通过计算表7空格检验