细说单纯形法

　　摘 要：本文从分析检验数的本质含义入手，用通俗易懂的语言介绍了线性规划的最优化原理，并在此基础上重构单纯形法，避免了传统的利用矩阵语言来介绍单纯形法带来的阅读和理解上的困难。

　　关键词：线性规划 检验数 单纯形法

　　

　　线性规划是运筹学里至关重要的内容，单纯形法又是解决线性规划问题最重要的方法，如果不能深刻地理解单纯形法，对线性规划的学习，甚至是运筹学的学习都将带来严重的负面影响。但大部分运筹学教材在介绍单纯形法的时候都利用矩阵语言，显得艰涩难懂，这对初学运筹学的人来讲是一个不小的打击，会大大削弱他们学习运筹学的兴趣。为此，我们需要寻找一种更有效的方法来介绍单纯形法。（我们默认读者对线性规划模型以及关于线性规划解的基本概念有一定的了解，如果读者不了解，可以参考任意一本运筹学教材学习这些概念）

　　单纯形法大体分三步：

　　（1） 找出第一个（初始的）基可行解。

　　（2） 判断这个基可行解是否最优。

　　（3） 如果不是最优，我们将它调整为一个“更好的”基可行解，直至最终求出最优解。

　　以上三个步骤，我们通过“单纯形表”来完成。

　　下面我们通过具体的例子来了解单纯形表的构造。

　　

　　上表包括了线性规划问题中所有关键数据，而且我们可以很方便地找到初始基为：β=（X ，X ，X ），因为系数列向量P 、P 、P 都是不同的单位向量，前面我们介绍过P 、P 、P 线性无关。β确定的初始基可行解是:X =X =0，X =15，X =5，X =11，相应此解的目标函数值：Z =0。我们将上表称为初始基β的单纯形表。

　　通过初始基β的单纯形表，我们找出了初始基可行解，下面的问题是如何判断初始基可行解是否最优解。我们观察一下Z 行中X 、X 的系数为-5、-4，而X 、X 又是非基变量，取值都为0，这样对于求最小的Z 是很不利的，试想如果将X、X 都变成基变量，即允许X 、X 取值为正，那么Z 势必会减少（增加一个X ，Z 减少5；增加一个X ，Z 减少4），由此我们判断初始基并非最优基，初始基可行解也并非最优解。我们看到判断当前解是否最优解主要依据非基变量在目标函数中的系数。但要注意的是基变量的取值是有约束方程决定的，而非基变量取值是我们约定的为0，这种约定是否合理只有在目标函数中不含基变量或者说目标函数中基变量系数为0时才能很明显地表现出来，因此，我们在判断当前基可行解是否最优时一定要保证基变量在目标函数中系数为0。此时如果非基变量在目标函数中系数存在负数，则说明当前基可行解并非最优解，反之，如果非基变量在目标函数中系数全为正，则让它们等于0就是最好的选择，因此，当前基可行解就是最优解。

　　我们把基变量在目标函数中系数为0时，非基变量在目标函数中的系数称为检验数。记为σ (j=1，2，...n)。这样判定当前基可行解是否是最优解的标准可以描述为：如果所有检验数σ ≥0，则相应的基可行解是最优解。

　　如果经检验当前基可行解不是最优解，如何得到一个“更好的”基可行解呢？拿上面的例子来说，很自然的想法就是将X 、X 变成基变量，同时把X 、X 、X 中的某些变量变成非基变量，这步操作称为换基，前半步操作称为入基，后半步操作称为出基。为了便于操作，我们只选择一个变量入基，选择谁呢？我们注意到当X 增加1时，Z 会减少5，而X 增加1时，Z 只减少4，首先将X 入基优化的效果会更好些，所以我们选择X 入基。由此，我们得到选择入基变量的标准，即负检验数中最小的检验数对应的非基变量入基。入基变量选定后，如何选择出基变量呢？假如我们随便选取出基变量，比如选择X ，看看会出现什么样的结果。

　　怎么才能使X 入基X 出基呢？很简单，以前我们选择X 为基变量是因为X 的系数列向量是（1，0，0）T，现在我们只需要把X 的系数列向量变成（1，0，0） ，那么X 就将会代替X 的位置变成基变量，同时X 就出基了。具体的操作，我们借助单纯形表2来完成。

　　

　　首先将第一个约束方程中X 的系数变成1，只需等式两边同除以3就可以了。然后将第二个、第三个约束方程中的X 的系数变成0，只需将第一个约束方程的左右两端乘以-2加在第二、三个约束方程的左右两端即可（我们前面所做的都是方程组的同解变形，不会改变方程组的解。换句话说，变形后的约束方程组和变形前的本质上是一样的）。把上面所做的变换称为单纯行变换。这时X 已经入基，X 已经出基，但我们注意到X =-5，基解不是可行解！所以选择X 出基是个错误。那么该选谁出基呢，这里我们看到，要选出的出基变量必须保证新基解可行，也就是说变换后右端项都要大于或等于0。若令X 出基，仿照上面的单纯形变换，右端项b 变为b - ・a = ≥0，b 变为 ，b 变为b - ・a =6≥0，这时右端项全都大于0，我们所得到的新基解可行。怎么才能迅速地找出合适的入基变量呢？我们观察一下上面的不等式，经变换可得 ≥ ， ≥ 。可以看到 是｛ (j=1，2，3)｝ 中最小的那一个，因此，我们可以通过这一特征来判定出基变量，若 =min{ }，j=1，2，3 则 b 所在方程中系数非零的基变量为出基。当然，如果是 是｛ (j=1，2，3)｝中最小的那一个，但它是负数，我们仍然不能选择X 出基。因为这时x = 是负数，新基解仍不可行。由此我们必须保证所有的 ≥0，又在标准化的线性规划问题中总有的，因此这里我们必须限定a ≥0。综合以上的分析我们可以得到判定出基变量的方法：若X 入基，设θ=min{ |a ＞0}，j=1，2，3，若θ= 则b 所在约束方程中系数非零的基变量出基，这种方法我们称之为最小比例原则。当确定了出基变量后，利用前面介绍过的单纯形变换，就可获得新基的单纯形表3如下：

　　

　　为了进一步判断新的基可行解是否最优，如前所述我们需要求出当前基可行解的检验数，为此我们需要把基变量X 在目标函数中的系数变为零，怎么做呢？由表3易知：

　　

　　由于Z 和Z ′仅相差一个常数，因此Z ′的取得最优值时Z 也应取得最优值，所以如果把目标函数改为Z ′=- X + X ，那么新线性规划问题的最优解和原线性规划问题的最优解是一致的，所以判断新LP问题的最优性的检验数也是判断原LP问题最优性的检验数，易知新的LP问题的检验数为：-3/2，5/2，我们就求得了当前基可行解的检验数为-3/2，5/2。

　　因为我们只关心检验数的取值，在实际运算过程中，只需用表3系数矩阵中第二行乘以5加在Z 行中即可得到检验数。这种做法其实和上面介绍的方程组同解变换是一样的。这点不难体会。由此我们就得到改进后的新基的单纯形表4：

　　

　　新基为（X ，X ，X ），新基的可行解为：x = ，x =0，x = ，x =0，x =6。新目标函数Z =-5・ +（-4）・0=- ，显然新目标函数值比原目标函数值更小了。但从表4可以看到，当前基可行解并非最优解。因为检验数不全大于等于零，因此我们要进一步优化。仿照前面的过程继续寻找“更好”的基可行解直到找到最优解或确定该LP问题无最优解为止。下面给出单纯形法基本步骤的流程图，以供大家参考：

　　

　　参考文献：

　　[1]朱求长.运筹学及其应用(修订本)[M].武汉:武汉大学出版社，1997.

　　[2]宋学锋，魏哓平.运筹学[M].南京:东南大学出版社，2003.

　　[3]韩伯堂.管理运筹学(2版)[M].北京:高等教育出版社，2005.

　　

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

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文