运输问题的多重最优解

运输问题的多重最优解简介：运输问题存在于各行各业中，水利水电工程建设也不例外。作为线性规划问题的一个特例，运输问题的求解无论是在理论上还是在计算技术上，都已经相当成熟。本文对运输问题的最优解作了较为深入的探究，特别对多重最优解的存在定理作了进一步证明和推论，最后给出了计算实例。关键字：运输问题最优解线性规划方案1问题的提出运输问题是线性规划的一个特例，可以用求解线性规划的一般方法一一单纯形法求解。然而运输问题有它自身的特殊结构系数矩阵，其独特的求解方法较单纯形法更为简单实用，这就是表上作业法。目前以表上作业法编制的计算机程序已广泛地得到应用，但遗憾的是已见之于公开发表的文献书籍(见参考文献)上的程序却对运输问题的多重最优解显得无能为力，甚至不予提及。而在实践中往往会遇到这样的问题:所给题目在求出了最佳调运方案之后还存不存在其它最佳调运方案(即问题的多重最优解)?如果存在，又如何判断有多少种最佳调运方案?怎样很快求得这些最佳调运方案?另一方面，如果原题目存在多重最优解，我们仅在得到了一个最佳调运方案后就不再予以追究了，那么就有可能漏掉调运更为合理可行的真正名符其实的最佳调运方案。因此，当原题目多重最优解存在时，我们应尽可能地多求几组出来供决策者选择。同样地，如果实际情况发生了变化，原最佳调运方案在车辆安排，管理运营等方面有困难时，希望对原方案进行调整，那么有多个最佳调运方案进行比较，其效果就不言而喻了。以上问题本文作了一些探讨，认为得到了满意的回答。2运输问题多重最优解的存在定理我们知道用表上作业法求解运输问题时，在初始调运方案得到后需进行最优性检验，通常采用位势法求各非基变量的检验数。当所有非基变量的检验数均大于等于零时，所得到的调运方案就是该题目的最佳调运方案。如果这些检验数中出现零，则该方案就可能不是唯一的最佳调运方案。这是因为以检验数为零的空格作为闭回路的起点，以基变量为转角点画出闭回路重新迸行迭代调整，其结果将得到另一新方案，并且这样的迭代不会使目标函数值发生变化，那么这个与原最佳调运方案具有相同目标函数的新方案也是最佳调运方案。同理，如果原题目存在多个非基变量检验数为零的空格，分别以各空格为进入变量，重复以上迭代过程，即可得到多个最佳调运方案。此外，以检验数为零的空格作为进入变量，其调入的具体数量也可以是不同的，只要满足约束条件即可，换句话说，进人变量的数量不是唯一的，可在该量所涉及的范围之内变化，从而可得到更多的最佳调运方案。以上分析可归结为如下定理:定理1给定的运输问题，其最佳调运方案非唯一性的条件是:1)在已获得的最佳调运方案中存在有非基变量检验数为零的空格；2）以此检验数为零的空格为一顶点的闭回路上需要减少运输量的顶点的不能为零。定理l的存在是显而易见的，证明从略。定理2设存在有个检验数为零的空格满足定理1，那么该运输问题至少存在个最佳调运方案。式中为最佳调运方案的最少个数，(1，2，…,)为在个空格中任取个空格作为进入变量的组合数。证明当所给运输问题已经获得了最佳调运方案，其调运表中存在有个满足定理1的零检验空格，在此个空格中任取1个作为进入变量进行迭代，可得到一个新的最佳调运方案，其取法有种，即新的最佳调运方案有个。又分别在个空格中任取2个作为进人变量进行迭代，可得到个最佳调运方案。以此类推，可得到个新的最佳调运方案，加上最先得到的一个方案，则总调运方案的个数到此为止有：个。

证毕需要说明的是定理2所给出的个方案中，并不存在同解方案。这是因为在以上证明推导中采用的是组合数相加法，每一种组合都是独立存在的。换言之，凡严格满足定理1条件的运输问题，这个方案就不存在相同方案。推论当以零检验数空格作为进入变量进行迭代以寻求其它最佳调运方案时，设退出变量的数值为A，如果在区间(0，A)中任意选择退出变量的具体数量，则最佳调运方案的个数将急剧增加，远远超过定理2中给出的最少个数。推论是不难证明的。我们知道，在以检验数为零的空格作为进入变量进行迭代时，其进入变量的数量就是退出变量的全部数量，迭代后退出变量即在调运方案表中完全消失。如果我们仍然保留退出变量的一部分数量，即退出变量以部分退出的形式进行，进人变且的数量与退出变量退出那部分数量相同，以此进行迭代，这同样对目标函数值毫无影响。如此得到的新的最佳调运方案将不在定理2所给出的方案个数之内。还需要说明的是，作这种调整是在按定理2求得的任何一个最佳调运方案的基础上进行的，并不需要在此基础上继续进行“表上作业”，因而违背了非零变量的个数不大于独立约束方程组的个数和基变量所对应的约束方程组的系数列向量线性无关[5]这两个对表上作业法的原则要求。这是完全许可的。3求多重最优解程序(1)在现有的运输问题求解程序中根据定理1和定理2的原理增加设置多重最优解的判断程序段，以数组形式记存零检验数在最佳调运方案表中的位置，为下一步直接在已获得的最优解的基础上进行迭代以寻求其它最优解作淮备。(2)在得到最佳调运方案后，如果存在其它最优解的可能，则输出整个最佳调运方案表以及非基变量检验数表格，以便计算者直观分析判断多重最优解的分布情况及其可调性。(3)可直接在以上输出表格上进行特殊的表上作业，运算简单易行，可用手算，仅在以零检验数为顶点的闭回路的转角点上作相应的加减法即可得到新的调运方案，并不需要再计算各非基变量的检验数就知道该方案一定是最佳调运方案。(4)第3步也可编制成计算机程序，可采用人机对话形式，输入任意一个零检验数空格的行、列数，即可求得该空格作为进人变量迭代后的新方案。也可以把程序设计成按所有零检验数空格的不同组合方式进行迭代，并输出全部最佳调运方案，方案个数为定理2中的。(5)在获得了以上多重最优解之后，若计算分析者或决策者还希望进一步调整，可以某一最佳调运方案为基准，结合最佳调运方案检验数表，按推论中的原则进行。4计算实例今以文献[1]P.111中的数据表(本文表1)为例演算于下(此例为3个煤炭产地的产量和13个销地的需求量的运输问题)。(1)按程序设计要求的数据资料输入格式和顺序输入表1。(2)输入产地个数M(单价矩阵的行数)=3，需求地个数N(单价短阵的列数)=13。(3)运算。输出最佳调运方案(表2中的方案1)，同时显示存在多重最优解，输出该题目最佳调运表中零检验数空格所在的位置。此例有5个零检验数空格(表2方案1中的(0))。(4)从表2方案1看出，这5个检验数为零的空格均满足定理1的条件。以(2，7)空格为顶点的闭回路是(2，7)→(2，8)→(3，8)→(3，7)→(2，7)。其它各零检验数空格为起点的闭回路均有两个顶点是(1，2)、(2，2)，另两个顶点分别为各空格所在列的第一行和该零检验数空格本身。(5)求解其它最佳调运方案。分别以表2方案1第2行的3、4、5、6空格进行任意组合作为进人变量，即可得到表2中的方案2一16，其方案个数满足在4个事件中任取1～4个事件的组合数15，与方案l相加共为16个方案(即表2中方案1～16)。今再以(2，7)空格作为进入变量分别与前16个方案相组合(例如与方案1组给得到方案17)即可得到32个方案，满足定理2所给的最少方案个数=1+5+10+10+5+1=32。(6)按推论原则，以方案4为基础，仅仅使退出变量x(1，5)不全退出，例如退出一半，则得方案18。以此类推可得到若干个新方案。而在前述的32个基本方案中除了方案1之外，每一个方案都可作这样的谓整，词整后的方案又可进行不同形式的组合。所有这些调运方案都具有相同的目标函数，都属于最优解之列，其方案个数将多达成千上万，以致于笔者目前尚还不能对这些方案个数作出准确计算。有兴趣者可自行演算验证之。5结语实践证明，有相当一部分运输问题存在多重最佳调运方案。这些方案的存在判别与求解，依本文所述是很简单且易于掌握运用的。无论是分析者还浪决策者，细读本文，必有所悟。（本文原载：《系统工程理论与实践》1991年第3期，中国系统工程学会会刊）参考文献[1]朱廷昌、胡喜忠著:《企业管理常用方法的程序设计》，电子工业出版社，1987年9月。[2]孙钟秀主绵:《计算机与计划管理》，南京大学出版社，1987年8月。[3]万耀青等编:《最优化计算法常用程序汇编》，工人出版