判断并解决线性规划“多反而少”悖论的逆最优值解法

开篇：润墨网以专业的文秘视角，为您筛选了一篇判断并解决线性规划“多反而少”悖论的逆最优值解法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：现有研究通过调整线性规划模型的右端项来消除“多反而少”悖论，而该文提出并验证了悖论是由技术系数矩阵、目标函数系数以及右端项三者的不合理搭配造成的。首先，通过建立原一对偶模型来判断悖论现象存在与否；然后，将悖论问题转换成逆最优值问题进行解决，构建了通过调整目标函数系数以及技术系数矩阵来消除悖论的模型；最后，提出了判断并解决悖论的逆最优值解法，阐述了其优势与经济意义，并通过数值算例验证其有效性。

关键词：运筹学；原一对偶模型；逆最优值解法；“多反而少”悖论

中图分类号：0221

文章标识码：A

文章编号：1007-3221（2015）01-0075-06

引言

发展生产力，提高经济效益一直是人类发展不可或缺的要求。对于现代企业管理者来说，更是如此。随着线性规划理论以及计算机技术的日趋成熟，越来越多的企业运用线性规划来进行管理工作，以期达到提高经济效益的目的。企业利用线性规划研究的主要内容是，在某一客观环境下，对管理系统中的有限资源进行统筹规划，为决策者提供最优方案，以实现科学管理。将线性规划的知识运用到企业管理中，能够使企业适应激烈的市场竞争，并及时、准确、科学的制定出生产计划、投资计划，以达到对资源的最优配置，并获得最大的经济效益。

然而，人们发现，在企业决策过程中会出现一些有悖于常理的现象。1971年，A.Charnes与D.Klingman在求解运输问题时发现了一个奇怪的现象：在某运输问题最优解的基础上，增加某些货物的供应量，总费用反而减少。他们将其称为“多反而少”悖论。这说明该运输问题的最优决策并没有使资源达到最优配置状态，反而产生了浪费的情况。在过去的40多年，人们对运输问题“多反而少”障论的研究有了很大的进展：文献给出了运输问题“多反而少”现象的定义及其存在的充要条件；文献在引理“判断m×n单位运价矩阵即可识别运输悖论是否存在”的基础上，提出了单位运价矩阵对运输悖论“免疫”的充要条件；文献通过改进运输问题的表上作业法来解决“多反而少”现象，使得其最优解具有更广泛的意义；文献51探讨了运输问题“悖论”存在的条件和表上作业法的调整方法，然后指出了运输问题数学模型挖潜的途径；文献在文献给出的运输问题悖论充要条件定理基础上，结合最小调整法，实现了增加运量而使得总运费不增的经济调整方案。综合现有的研究，人们对运输问题悖论现象的研究，都是通过改进供应量与需求量进行的。

由于运输问题属于特殊的线性规划问题，针对传统的线性规划“多反而少”障论的研究有利于从本质上分析悖论产生的原因，而由此提出的一般性解决办法，也可以运用到运输悖论的解决当中去。因此，本文就传统的线性规划悖论问题进行研究。现有研究主要通过改进右端项来消除悖论，比较典型的有：文献提出的最优技术结构模型，判断右端项是否符合最优技术比例，并通过改变右端项的比例来解决“多反而少”；文献给出了线性规划模型存在悖论现象的充要条件，并通过建立新模型来避免产生悖论；文献提出了判断并解决悖论问题的最优配置方法，并明确解释了悖论的经济意义。

从线性规划模型可以看出，提高经济效益有三种途径：一是技术改进，如开发新工艺，新能源等；二是生产组织与生产计划的改进，即合理利用现有的人力、物力资源；三是选择不同的市场等。围绕提高效益的途径与线性规划模型之间的内在联系，本文以系统工程的观点，对存在悖论现象的线性规划模型进行系统分析，试图找出技术系数矩阵、目标函数系数以及右端项三个参数的合理搭配。因此，线性规划悖论的研究能给经济效益低下的企业提供经营管理上的科学依据，企业依此转变生产结构、改进技术，可以提高经济效益。本文首先概要介绍线性规划“多反而少”悖论以及逆最优值问题；接着给出判断悖论现象存在与否的模型；之后给出通过调整目标函数系数以及技术系数矩阵来消除悖论的模型；然后总结提出逆最优值解法，并阐述其优势、经济意义及有效性；最后是结论与展望。

1 线性规划“多反而少”悖论以及逆最优化问题的介绍

1.1 “多反而少”悖论

现实生活中的很多问题，如物资调运、资源利用、生产任务分配等，都可以利用线性规划模型来解决。线性规划模型的标准型为：文献给出的线性规划“多反而少”悖论存在的充要条件：模型（1）存在“多反而少”现象，当且仅当模型（1）的最优值大于如下线性规划模型（2）的最优值：

文献分析指出，悖论产生的原因是因为约束条件存在等式约束。文献则指出类似模型（1）这样的建模是不妥的，应将等式约束换为不等式约束。然而，无论是理论上还是现实生活问题的建模（运输、指派、分配等问题）都会存在这种强制等式约束的情形。一般来讲，线性规划模型的参数是事先估计出来的，而等式约束需要更准确、合理的参数估计结果才可能避免悖论的产生，若是利用模型（2）求得的最优解能否使资源达到最优配置状态则无法得知。因此，针对模型（1）的悖论研究很有必要，并会对估计的模型参数的改进提供帮助。

1.2 逆最优值问题

定义对于模型（1），给定期望的数值zo，希望通过调整模型参数c、6、A，或者它们的组合，使得调整后问题的目标函数最优值z*尽可能与zo接近，同时确保调整参数的改变量限制在某一范围G内。记：则模型（1）对应的逆最优值问题为：这里，G为满足一定条件限制的

其中g*≥0，为模型参数改变总量的容许上限值，II・II为Lp范数算子，表示了向量空间上的一种度量。

参照文献给出的解决逆最优值问题的方法，调整模型技术系数矩阵、目标函数系数以及右端项三个参数的任意之一都能够使模型的最优值尽可能的等于给定的期望值，故将线性规划悖论问题转换成逆最优值问题来处理不失为一个好的解决思路。

2 判断悖论存在性的原一对偶模型

模型（2）的对偶模型如下：

若模型（3）的最优值与模型（1）的不相等，则由对偶定理可知模型（2）的最优值与模型（1）的也不相等，也就是说明模型（1）存在悖论现象。显然，如果模型（3）与（1）的最优值相等，那么模型（1）就不会存在悖论现象。基于此，本文试图通过判断模型（3）与（1）最优值的差值是否为0来判断模型（1）是否存在悖论现象，构建的数学模型如下：称模型（4）为原一对偶模型。则判断悖论现象存在与否的定理如下：

定理假设原一对偶模型（4）的最优值存在。如果最优值为0，那么模型（1）将不存在悖论现象；反之，存在。并且，假设模型（4）在具有唯一最优解的情况下，其最优解由模型（l）与（3）的最优解构成；假设模型（4）具有无穷多最优解的情况下，任意一个最优解也是由模型（1）与（3）的最优解构成。

证明 模型（4）的约束条件是由模型（1）与（3）中的约束条件联合所得，而目标函数则是模型（1）与（3）目标函数相减。显然，模型（4）所得的最优解中的x与y分别满足模型（1）与（3）中的约束条件，故是模型（1）与（3）的可行解。设x与y是模型（1）与（3）的最优解，则可行解与最优解的目标函数值有如下关系：

（1）如果模型（4）的最优值为o，那么cx =bry。假设此时模型（1）存在悖论现象，即有cx>bry。又由于，故可以推出。这显然与已知矛盾，故假设不成立。即若模型（4）的最优值为0，则模型（1）将不存在悖论现象。

此时，满足

（i）假设具有唯一最优解的情况下，有也就是说，模型（4）的最优解由模型（1）与（3）的最优解构成。

（ii）假设具有无穷多最优解的情况下，任取模型（4）的一个最优解。下面证明模型（1）与（3）至少有一个有无穷多最优解。假设模型（1）、（3）只有唯一最优解，为x与多。由于选取的任意性，不失一般性，令。由于而且x与y分别是模型（1）与（3）的可行解，这说明x与γ，也是（1）与（3）的最优解。这与假设矛盾，故假设不成立。

因此，模型（4）有无穷多最优解可以推出模型（I）与（3）至少有一个有无穷多最优解。而且由上述证明可知，模型（4）的任一最优解（x，y）的x与y都分别是模型（1）与（3）的最优解。即模型（4）的最优解（x，γ）由模型（1）与（3）的最优解构成。

（2）如果模型（4）的最优值不为o，那么。假设此时模型（1）不存在悖论现象，即。由于，故。但是因为，所以可以推出或，或者二者同时成立。假设成立时，则x仅是模型（1）的可行解而非最优解。此时，目标函数值的值大于故显然只是模型（4）的可行解，而非最优解。这与“模型（4）的最优解为”相矛盾，故假设不成立。同理可证，也不成立。因此，在模型（4）的最优值不为o的情况下，假设模型（1）不存在悖论现象不成立。

（1）不存在悖论现象不成立

此时，满足。

（i）假设具有唯一最优解的情况下，有也就是说，模型（4）的最优解由模型（1）与

（3）的最优解构成。

（ii）假设具有无穷多最优解的情况下，任取模型（4）的一个最优解。下面证明模型（1）与（3）至少有一个有无穷多最优解。假设模型（1）、（3）只有唯一最优解，为γ与x。由于（x，γ）选取的任意性，不失一般性，令。由于，而且x与γ分别是模型（1）与（3）的可行解，这说明x与），也是（1）与（3）的最优解。这与假设矛盾，故假设不成立。

因此，模型（4）有无穷多最优解可以推出模型（1）与（3）至少有一个有无穷多最优解。而且由上述证明可知，模型（4）的任一最优解（x，γ）的x与γ都分别是模型（1）与（3）的最优解。即模型（4）的最优解（x，γ，）由模型（1）与（3）的最优解构成。

所以，建模时若用原一对偶模型（4）替代模型（1），不仅能得出模型（1）与（3）的最优解，而且能判断悖论是否存在。另外，原一对偶模型的提出，也为本文接下来构建解决悖论的模型提供帮助。

3 调整目标函数系数以及技术系数矩阵来消除悖论的模型

3.1 消除悖论的思路

现阶段针对悖论的研究都是通过调整右端项进行的，而本文试图对存在悖论现象的线性规划模型进行系统分析，以找出模型的技术系数矩阵、目标函数系数以及右端项三个参数的合理搭配，并给出调整目标函数系数以及技术系数矩阵来消除悖论的方法。

模型（1）存在悖论现象的充要条件是模型（1）的最优值大于模型（3）的最优值，而若能保证模型（1）与（3）的最优值相等，则模型（1）将不存在悖论现象。因此，我们尝试将模型（1）与（3）的目标函数相等以及模型（1）的目标函数值尽可能等于已知模型（3）的最优值作为约束条件，并建立调整模型参数的数学模型来消除悖论。一方面，将模型（1）与（3）的目标函数相等作为约束条件，可以保证调整后的参数求解模型（1）时不会产生悖论；另一方面，模型（3）的最优值可由模型（4）求出，令其为初始期望值，是为了满足将悖论问题转换成逆最优值问题来解决所需的前提条件。

3.2 调整目标函数系数的模型

参照3.1中消除悖论的思路，利用模型（4）求出模型（3）的最优值，设其为给定初始期望值。构建调整目标函数系数来消除悖论的模型如下：

其中，待求解的向量是x、γ、c。引入约束条件是为了确保利用调整后的c求解模型（1）不产生悖论现象。

由于模型（5）是约束极值问题，初始点的给定十分关键。考虑到模型（5）的目的是调整目标函数来消除悖论，我们不妨将待调整的目标函数系数c作为初始的c。，将模型（4）的最优解中的z、y作为初始的x。、y。。最终得到的可能是局部最优解，但是由于消除了悖论现象，仍能说明调整后的目标函数系数是有效的。

3.3调整技术系数矩阵的模型

参照3.1中解决悖论的思路，利用模型（4）求出模型（3）的最优值，设其为给定初始期望值。构建调整技术系数矩阵来消除悖论的模型如下：

其中，待求解的向量是x与γ，矩阵是A。引入约束条件是为了确保利用调整后的c求解模型（l）不产生悖论现象。

由于模型（6）是约束极值问题，初始点的给定十分关键。考虑到模型（6）的目的是调整技术系数来消除悖论，我们不妨将待调整的技术系数矩阵A作为初始的A。，将模型（4）的最优解中的x、γ，作为初始的x。、γ。。最终得到的可能是局部最优解，但是由于消除了悖论现象，仍能说明调整后的技术系数矩阵是有效的。

3.4 对模型（5）与（6）的说明

模型（5）与（6）看起来一样，但实际上模型中参数的已知性却是不同的：模型（5）是固定技术系数矩阵A与右端项6来估计目标函数系数c，而模型（6）是固定目标函数系数c与右端项6来估计技术系数矩阵A。一方面，这说明不是只有通过调整右端项才能消除悖论，调整目标函数系数以及技术系数矩阵也能做到，扩充了解决悖论的方法；另一方面，通过调整线性规划模型的三个参数任意一个均能消除悖论也意味着这些参数在搭配上存在不合理，而调整后的某一参数与其他参数的搭配将更合理。

关于非线性模型（5）与（6）的求解问题，本文在此做一点说明：目前为止，尚无处理一般非线性约束非线性规划的通用且有效的方法，而乘子罚函数法、约束变尺度法、起作用约束集法和序列二次规划法等都是很重要的方法。但是初始解的选择会对最优解产生影响，最终得到的可能只是局部最优解。尤其是对于编程求解来说，每一次得到的最优解可能都是不一样的。如果存在不同的局部极小点，这说明可以找到不同的调整方式来达到消除悖论的目的。只要实现了这一目标，就说明所得极小点是有效的，并非不稳定。而且，在模型（4）具有无穷多最优解的情况下，选取不同的最优解作为初始解，解（5）、（6）都会得到相应的参数调整方式来消除悖论。由于本文旨在通过调整目标函数系数、技术系数矩阵来消除悖论，求解约束极值问题并不是本文的重点，故本文仅采用序列二次规划法，并通过Matlab2011b编程求解。

4 判断并解决悖论的逆最优值解法以及数值算例

为了更方便地判断并解决悖论问题，将本文前面提出的判断悖论是否存在的定理与解决悖论的模型归纳成一个算法，并称之为逆最优值解法。

4.1 逆最优值解法的流程

步骤1 构建原一对偶模型（4）来替代模型（1）。利用本文第二节提出的定理，若求得的最优值为O，则说明不存在悖论现象，终止算法；反之，存在悖论，转入步骤2。

步骤2确定初始期望值：利用模型（4）求出模型（3）的最优值，设其为给定初始期望值。

步骤3 如果希望通过调整目标函数来消除悖论，那么利用模型（5）求解；调整技术系数矩阵，利用模型（6）求解。

4.2 逆最优值解法的优势

逆最优值解法综合了判断悖论存在与否的模型以及解决悖论的模型。首先，模型（4）不仅可以判断悖论是否存在，而且能够得到模型（1）与（3）的结果，所以用模型（4）替代模型（1）是很有效的。其次，通过调整线性规划模型的目标函数系数以及技术系数矩阵来解决悖论的模型（5）与（6），是从系统的角度对线性规划模型的参数进行分析，扩充了解决悖论的方法，完善了悖论的研究。

4.3 逆最优值解法的经济意义

企业利用线性规划进行管理工作，由于在某一固定环境（如有限的资源、技术水平、市场）的要求下，构建的线性规划模型可能会存在悖论现象，此时解该模型得到的最优方案并不能使得资源达到最优配置状态。这也正是人们这么多年来致力于解决悖论问题的意义所在。

很明显，不同的技术水平、市场条件以及资源有不同的配置方案。正如本文所验证的，只要模型的技术系数矩阵、目标函数系数以及右端项三者合理搭配，就能避免悖论的产生。现有研究给出了在给定技术与市场的情况下合适的资源搭配方式，而逆最优值解法则找到了与给定技术和资源相适应的目标函数系数、与给定市场和资源相适应的技术水平。这就是为企业制定合理、全面的经济计划提供了帮助。

4.4数值算例

用文献中的例子来验证逆最优值解法的有效性：优解x。=[4；1；4；0]，y。=[0；O；0.2]，最优值为5.8。由第二节提出的定理可知，由于最优值不为0，故存在悖论现象。

步骤2 确定初始期望值。

步骤3 将例子中的A、c以及b代入模型（5），编程求解得到调整后的目标函数为：c=（1.297，2.8242，0.2972）；利用模型（6），编程求解得到调整后的技术系数矩阵为：

容易验证，用调整后的目标函数系数替代原模型中的系数不会产生悖论现象，调整后的技术系数矩阵也不会产生悖论，而且利用调整后的参数求解模型（1）得到的最优值均是9.2，这与步骤2确定的初始期望值相等。因此说明逆最优值解法是有效的。

5 结论与展望

本文的贡献在于三个方面：一是给出了判断线性规划悖论现象存在与否的原一对偶模型，并通过定理证明；二是构建了调整目标函数系数以及技术系数矩阵来消除悖论的模型，这验证了本文提出的观点：线性规划悖论的产生是模型参数的搭配不合理造成的，同时也就给出了验证构建的模型参数是否合理的方法；三是总结提出了判断与解决悖论的逆最优值解法流程，并阐述其优势、经济意义。

本文考虑的仅是通过改变线性规划模型的单一参数来消除悖论。接下来，我们希望找到调整参数的组合也能消除悖论的方法，并比较这些解决方法的优劣。