线性规划增减约束条件的灵敏度分析

（东北财经大学 数量经济系，辽宁 大连 116025）

摘 要：本文在灵敏度分析的基础上，面对增减约束条件，特别对减少约束的情形，给出新最优方案的获得方法；并指出其特殊的经济意义。

关键词：运筹学；线性规划；灵敏度分析；增减约束

中图分类号：O221.1 文章标识码：A 文章编号：1007-3221(2007)02-0001-05

The Sensitivity Analysis of Increasing or Decreasing Restrain Conditions

for Linear Programming

XIA Shao-gang， LIU Xin

(Department of Quantitative Economics, Dong Bei University of Finance and Economics, Dalian 116025, China)

Abstract:Based on the sensitivity analysis, under the increasing or decreasing restrain conditions, especially. decreasing restrain condition, the new acquiring method of the best plan is advanced; and its special economic significance is pointed out.

Key words:operations research; linear programming; sensitivity analysis; increasing or decreasing restrain

0 引言

设线性规划问题

min f=CX

AX=b

X≥0(1)

的最优单纯形表为

它为实际操作提供最优方案。由于现实世界是不断发展变化的，体现在约束条件上，增加或减少约束条件则是随时可能发生的。这将导致最优方案的变化，如不与时俱进，及时做相应调整，必将造成经济损失。本文在灵敏度分析的基础上，面对增减约束条件的情形，给出新最优方案的获得方法。

1 增加约束条件

设增加的一个约束条件为

则应在原问题的最优表1中按（2）提供的数据，增加一行，然后用消去法，把这行中基变量的系数消为0，这显然对检验数没有影响，从而可化为仅缺少一个基变量且的问题，故可沿用对偶单纯形法^［1］或联合算法^［2］的规则，于新增之行确定主元，实行Gauss消元，便得一正则解，继之用对偶单纯形法迭代求优。如果增加的约束不止一个，可一并处理。由于比较简单这里不详述，参见文献［3］。

2 减少约束条件

对于减少约束条件的问题，大多的教材^{［4］［5］}和其它文献［6］都没有涉及。事实上它和增加约束一样重要。减少约束条件还有特殊的经济意义。对于资源利用问题，它意味着解除对某些资源的限制；而在工厂里又相当于去掉一道工序；这些都为创新增值提供途径或指示方向^［7］；故值得详细讨论之。

当需要减少一个约束时，并不是将最优表中，与该约束相应的行去掉就可以的，因为此约束的影响已通过Gauss消元施加在其它各行里了。那么，如不重新求解，应如何利用最优表而达到去掉某些约束的目的呢？

设初始单纯形表中含有一个单位矩阵，不妨假定它是由辅助变量（松弛变量，剩余变量或人工变量等）形成，而最优单纯形表为：

表2 初始单纯形表中含有单位矩阵的最优表

现在要去掉原约束条件AX=b中的一个约束，不妨设为第t个约束，则对上表应采取如下步骤：

考虑原第t个约束所加辅助变量这一列，即（n+t）列，若为基变量，则去掉最优表中第t个约束行和（n+t）列即可（此时最优解与最优值均不变）。否则，若列某系数

考察新检验数是否仍非正，是，则已得去掉原第t个约束后的最优解；否，用单纯形法迭代求优。

例1 某工厂去年根据市场需求和自身生产能力可以生产A，B两种产品，当时的条件如下表所示

这已经是最优表，按它进行调整，可增加利润180-168=12（百元）。

注意：由（3）知，主元所在之行未必一定是原约束中要去掉的那一行，如在例1中，若因进口设备而欲将第二个约束去掉，计算结果，主元是，因而消元之后，去掉的却是第三行。此外,之所以先考虑(3)式是因为去掉约束，一般将使目标函数值减少，但绝不会增大。

方法的原理是很简单的，通过比较，不难看出，初始表中将要去掉的约束行所加辅助变量那一列仅有一个1而其余都是0，而在最优表中该列一般将发生变化,说明将要去掉的约束行的影响已经通过迭代施加到别的行中。注意，若从一开始就去掉那个约束，则所加辅助变量那一列全为0，并且在迭代中保持不变；因此，只有经过上面的处理，使所加辅助变量那一列又全变回为0，要去掉之约束在单纯形迭代中对其它约束施加的影响（即指此行的若干倍加于其它诸行），才被消除。此外，按照（3）或（4）选主元是为了保证所得解的可行性。

如果初始表中没有单位矩阵,注意到前面的分析只涉及辅助变量 增减约束条件在不少方面有应用，例如求解变量有上限问题^［8］就用到增加约束，利用增减约束条件的手段还可以顺利地求得一个基可行解，限于篇幅有关内容将另文叙述。

参考文献：

［1］ 俞玉森.数学规划的原理和方法［M］.武汉：华中工学院出版社，1985.

［2］ 夏少刚.线性规划联合算法的理论和应用［J］.运筹与管理,2004,13(1):1-16.

［3］ 范贻昌.实用管理运筹学［M］.天津：天津大学出版社，1995.

［4］《运筹学》教材编写组.运筹学［M］（第三版）.北京：清华大学出版社,2005.

［5］ 胡运权.运筹学教程［M］.北京：清华大学出版社,1998.

［6］ 摩特J J，爱尔玛拉巴S E.运筹学手册（基础和基本原理）［M］.上海：上海科学技术出版社，1987.

［7］ 杨德权，等.线性经济系统管理创新的数量方法研究［J］.预测,2002,21（6）：32-35.

［8］ 夏少刚.有界变量线性规划的一种简易解法［J］.运筹与管理,2005，14（6）：12-18.

注：“本文中所涉及到的图表、注解、公式等内容请以PDF阅读原文”。

推荐访问:线性规划 增减 灵敏度 约束 条件