运筹学表上作业法改进

《运筹学表上作业法改进》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、运筹学表上作业法改进四川工程职业技术学院李成贵内容提要：运筹学表上作业法是运输问题这种特殊的线性规划的最主要解法，但计算繁难。文章介绍的高效的“六合一”表上作业法，从实用的角度出发，大幅度地减少了作业法的工作量，并且提高了可靠性，简单明了，易学易用。运筹学的主要内容之一运输问题这种线性规划，其最主要解法是表上作业法，一般表上作业法求最优解至少要经历下面儿个步骤：一、根据运输表（即产销平衡与单位运价合一表）求初始基可行解，也就是初始调运方案，一般用西北角法，最小元素法和Vogel法（下面我们只用最小元素法说明问题）。这样可以得初始调运表。二、

2、检验初始方案的最优性，即计算行位势和列位势，再计算检验数，得检验数表。三、根据检验数的情况对方案进行闭回路调整，然后产生新的（基解）调运方案表。下面用例子说明一般表上作业法的操作步骤。例1：设产销平衡运输问题的有关数据如下表（运输表），求使运费最低的调运方案：Bib2b3B4产量asA】291079a213425A384257销量bj384621用最小元素法求得初始调运方案如下:Bib2b3B4产量dAiX2⑤9X10④79a2③1X3X4②25A3X8③4④2X57销量bj384621利用位势方程色+Vj•求出行位势给和列位势专，再用检验

3、数公式入”=Cst-（Ms+vt）求出检验数几，得下表:6977产量a.utBib2b3B40Ai・42⑤9310④79・5a2③1-1324②255A378③4④2357销量bj384621最后用闭冋路调整法得新的调运方案:56977Bib2b3B4产量aj0A.+3A⑤3・3④9-4・5a2・3③-12+3②55A37③④37销量bj384621下面是新的调运方案:产量缶iBiB.BaB4Ai③⑤①9a2⑤5A3③④7销量bj384621上面的计算完成了一次迭代的全过程。在计算中，实际我们己省略了一些步骤，但从中看出，这样的计算仍然繁难

4、，并且表格较多，完成一次迭代至少耍三至四张表格，如果迭代次数在三次(这大概是表上作业法的最少步骤)以上，其繁难程度可想而知。如果我们仔细分析上面的整个计算过程，可以看出，要想简化计算，可以从简化操作步骤和改进计算方法这两方面入手。我们的想法是先从简化操作步骤入手来降低计算的繁难程度。下面先减少计算用表格,这是减少工作量的关键。我们只需对表格稍微进行简单的处理，就可以把1、求初始解，2、计算行列位势,3、计算检验数，4、方案调整合并在一张表中处理，如果加上产销平衡表和单位运价表，就得到下面的“六合一”表上作业法，下面是第一表：6977uiBl

5、B2B3B4产量爲0Al+3・4X(2⑤(93X(10-3(7④9-5A2-3③(1-1X(32X(4+3(2②55A37X(8③(4④(23X(57销量bj384621表中“O”内的数字为基变量的值，“(”后的数字为运价，闭回路调整的数字写在闭回路顶点上方，而格子内的其它数字为检验数，行列位势及产销量很清楚地分布在表的四周，(X在第一表中可以出现也可以不出现，但以后迭代中不用)，可见“六合一”表是十分简洁清晰的。用此表进行计算，可以大大减少了操作程序，是一种很实用的改进。如果对上面的计算再进一步分析，我们发现，表上作业法的两个基本计算（位

6、势和检验数计算）还可以进一步大幅度简化。比如检验数的计算，在逐次迭代求最优解的过程中，绝大部分为正数，但我们的最优性检验并不关心正数的大小，只要知道是正数即可，而这可以通过观察检验数十分简单的计算公式入，=5-（冷+儿）直接得到。所以在求检验数时先通过观察确定其正负，正数者在表格内记+,不再计算出具体数值；负数者求出其大小（有零者记0）,这就是计算方法方面的改进。上例的进一步改进如下表（例1“六合一”法第一表）：6977产量％BlB2B3B40Al+3・4X(2⑤（9+X(10-3(7④9・5A2・3③(1-1X(3+X(4+3(2②55A

7、3+X(8③（4④（2+X(57销量bj384621进一步改进后的“六合一”表上作业法为一种高效的表上作业法，它既大幅度地减少了计算量，同时又使操作步骤更简洁清晰，使出错的概率大大降低。笔者在教学屮使用此法，收到了相当好的效果。下面我们来看例1的“六合一”法第二表2977产量％%Bib2b3B40Ai③（2-5⑤(9+(10+5(7①9-5a2+(1+51(3+(4-5(25-1-5A3+(8③（4④（2+(57销量bj384621例1“六合一”法第三表:2977产量逐%BiB.BsB40Ai③(2©(9+(10⑥(79・6a2+(1⑤(3

8、+(4+(25・5A3+(8③(4④(2+(57销量bj384621所有检验数为正，得最优解：兀11二3,斗2二°，召4=6,兀22=5,兀32二3,兀33=4。下面用一个例子对