第三章 单纯形法
在线性规划的计算求解中，应用最多且最著名的就是单纯形法。这种方法是美国运筹学家G.B.Dantzig丹捷格在1947年提出的。后来经过人们多次改进，形成了许多变种。实践证明单纯形法是一种使用方便、行之有效的算法。
§3.1 单纯形法的原理
基本可行解的存在定理已经表明，若线性规划有最优解，则一定存在最优基本可行解，因此求线性规划问题就归结为寻找最优基本可行解。
单纯形法的基本思想就是从一个基本可行解出发，检查该基本可行解是否为最优解；若不是，则再设法求另一个未检查过的基本可行解，如此继续，直到查询到最优解为止。
按照以上的思路，需要解决三个难题： 1、 如何求出第一个基本可行解？
2、 如何判断这个基本可行解就是最优解？
3、 若不是最优解，如何从一个基本可行解过渡到另一个未检查过的基本可行解？ 第一个问题的彻底解决尚需留待今后，但是我们知道，求基本可行解就是解线性方程组
Ax?B，由于且r(A)?m，故可以解出m个变量，称之为基本变量，剩下的n-m个变量
称之为自由变量。于是，最简单的方法就是令所有的自由变量的值为零相应得到的解就是基本解。
例3.1 考虑线性规划
minz?x1?3x2?2x3?4x4s.t.2x1?4x3?x4?6?x1?x2?3x3?5xj?0,j?1,2,3,4 （3.1）
把约束方程写成表格的形式，如表3-1：
2
-1 0 1 -4 3 1 0 6 5
从上述表格的左端可以看出，由第二、四列构成一个单位子矩阵，或曰子块，即对角元为1，
3 - 1
其余为0，因此把x2和x4解出，即把x2和x4作为基本变量，余下x1和x3作为自由变量。
x4?6?2x1?4x3x2?5?x1?3x3 （3.2）
令所有的自由变量x1?x3?0，而x4?6,x2?5，从而得到一个基本解(0,5,0,6)T。若需要判断该基本解是否基本可行解？只需看左端有单位子矩阵时，右列的元素是否都是非负，若是，则为基本可行解。本例中的基本解是基本可行解。
如何判断所得到的基本可行解(0,5,0,6)T是最优解？
将约束方程的等价关系式（3.2）代入目标函数，消去基本变量，x2和x4，只剩下自由变量x1和x3：
z?x1?3x2?2x3?4x4?x1?3(5?x1?3x3)?2x3?4(6?2x1?4x3) （3.3） ?9?10x1?27x3 这个过程也可以在表格中进行，在表3-1的基础上加一个底行，把目标函数的系数相应写在底行中，如表3-2：
2 -1 1 0 1 -3 -4 3 2 1 0 4 6 5 0 右下角的0是目标函数中常数的变号值，表格中的竖线可以理解为一个等号，于是把目标函数中的常数项移到等号的另一边要变号。为了在目标函数中消去基本变量，x2和x4，即要把底行中x2和x4的系数变为0，可采用把底线以上的行倍加至底行的方法来实现。在本例中把第一行乘（-4）、第二行乘3均加至底行，即得表3-3：
2 -1 -10 0 1 0 -4 3 27 1 0 0 6 5 -9 表3-3中的底行系数与式（3.3）相一致，无非是把常数项移到等号的另一边而成为（-9），注意到9即为相应基本可行解(0,5,0,6)所对应的目标函数值。 这样，我们把线性规划（3.1）化成与之等价的线性规划：
T3 - 2
minz?9?10x1?27x3
s.t.x4?6?2x1?4x3x2?5?x1?3x3xj?0,j?1,2,3,4 （3.4）
判断基本可行解(0,5,0,6)T是否为线性规划（3.1）的最优解，只要判断它是否为线性规划（3.4）的最优解即可。因为x1和x3均不能为负，但表3-3的底行中有负的系数（-10），若
x1取正值，就可以使目标函数值减小。因此(0,5,0,6)不是线性规划（3.1）的最优解。
T 归纳以上所论，线性规划的表格以矩阵形式表为
A B C T o 上表分为四个部分，它们分别称为：
求解线性规划（2.3），即可以运用如下的运算：
1. 底线以上部分进行行交换； 2. 底线以上某一行乘一非零常数； 3. 底线以上的行进行倍加运算；
4. 把底线以上行乘常数后加至底行（包括右下端）上。 当表格具有如下特点：
1. 中心部位具有单位子块； 2. 右列元素非负；
3. 底行相应于单位子块位置的元素为0； 4. 底行其他元素非负。
则从表格中立即可以读出线性规划(2.3)的最优解和最优值。最优解的读法为：
单位子块中1所对应的变量取相应右列的值，不在单位子块位置中的变量取值0。而右下端元素变号即为（2.3）的最优值。
中心部位 底行 右列 右下端 3 - 3
例如，解线性规划（3.1），其表格形式如表3-2所示，对它进行一定的运算后得到表3-4：
1 0 0 0 1 0 -2 1 7 1/2 1/2 5 3 8 21 此表具备了四个特点，单位子块（子矩阵）由第一、二列构成，第一列中的1对应的变量为x1，取值为右列的3；第二列中的1对应的变量为x2，取值为右列的8；不在单位子块位置的变量x3,x4均取值0，于是最优解为-21，可以直接从表上读出。
当目前的基本可行解不是最优解，如何过渡到另一个基本可行解呢？正如对于线性规划（3.1），得表3-3后如何继续进行？从形式上看，当一个表已经具备了1.，2.，3.三个特点，而第四个特点尚不具备时如何进行？
§3.2 单纯形法的计算步骤
单纯形法的计算步骤是：
前提是假设当前的表格已经具备了1.，2.，3.三个特点，设一般为：
a11?am1a12?am2c2????a1n? amncn b1 ? bm c1 ?z 6 5 -9 具体的如表3-3：
② -1 -10* 0 1 0 -4 3 27 1 0 0 1、从底行的负元素中任选一个，设为cj，具体的例子就是-10，实质上是选该列所对应的变量xj，具体的例子是x1，要使得xj取正值，取正值即能使目标函数值下降。变量取正值则必须作为基本变量，即必须将该列调至单位子块中去。这一步称为选择进基变量。
2、从所选元素的对应列（xj列）底线以上的正元素中选择一个akj，其规则为：
bkakj???b??min?iaij?0? （3.5）
i???aij?3 - 4
在具体的例子中，由于所选的第一列中只有一个正元素2，当然就选它了，并标以记号，即画上一个圆圈。
我们既然要使xj作为基本变量，即必须将原有的基本变量中选定一个退出，作为自由变量。至于一定要在正元素中选，若不止一个正元素按式（3.5）选，是为了不破坏右列的非负性的特点。这一步称为选择离基变量。
3、利用初等行变换及倍加至底行的运算，把akj变为1，该列的其他元素，包括底行的相应元素变为0。在具体的例子中即得到表3-4。这一步运算称为旋转运算。
4、若底行的元素均非负，则算法结束，否则，回到1、。
这样每迭代一次，保证得到一个新的基本可行解，而且由下端的元素单调增大，当右列元素大于0时为严格单调增大。可知新的基本可行解不比原来的基本可行解差。因此当最优解存在且基变量的值都大于0时，经过有限步之后一定能得到最优解。
因为基本可行解只有有限个，且每个基本可行解不会被重复检查，上述结论可以归结为下面的收敛定理。
定理3.1 单纯形算法的收敛定理
在已知一个基本可行解（初始基本可行解）的前提下，使用单纯形算法求解线性规划时，若每次迭代得出的基本可行解的基变量均大于零（称为非退化），则算法必有限步终止。
定理所述的算法终止包括两种情况，一是使表具有四个特点而得到了最优解和最优值；另一个是在执行2、时，在所选列底线以上的元素中根本没有正元素，这时算法亦终止。
当有基变量的值等于零时，即右列有零元素，则称为退化。这时有可能会出现基本可行解被重复检查的情形，成为循环现象。现已经证明在执行1、时，每次都选底行中左边第一个负元素就可以避免循环现象。 例3.2 用单纯形法求解
minz??2x1?3x2s.t.?x1?x2?2x1?2x2?103x1?x2?15xj?0,j?1,2
解：先化为标准形
3 - 5
minz??2x1?3x2s.t.?x1?x2?x3?2x1?2x2?x4?103x1?x2?x5?15xj?0,j?1,2,3,4,5
列成表格：
-1 1 3 -2 ① 2 1 -3* 1 0 0 0 0 1 0 0 0 0 1 0 2 10 15 0 该表格已经具备了1.，2.，3.三个特点，x3,x4,x5组成一个单位子块，可采用单纯形法求解。首先从底行中任选一个负元素，例如选-3，再在第二列的三个正元素中，由2/1，10/2，15/1中最小者决定选第一行第二列的元素1，标以记号。迭代一次后得：
-1 ③ 4 -5* 1 0 0 0 1 -2 -1 3 0 1 0 0 0 0 1 0 2 6 13 6 从上表中可以看出，x2是进基变量，x3是离基变量。再从底行中选元素-5，和在第一列的二个正元素中，由6/3，13/4中最小者决定选第二行第一列的元素3，标以记号。再迭代一次后得：
0 1 0 0 再迭代一次：
1 0 0 0 1/3 -2/3 5/3 -1/3* 1/3 1/3 -4/3 5/3 0 0 1 0 4 2 5 16 0 1 0 0 1 0 0 0 0 0 1 0 3/5 -1/5 -4/5 7/5 -1/5 2/5 3/5 1/5 3 4 3 17 这时第4、个特点已具备，故终止。
从表中读出最优解：x2?3,x1?4,x3?3，且x4?x5?0。若把引进的松弛变量略去，则最优解为x?(4,3)，最优值为z??17。
线性规划单纯形算法的流程框图如下：
3 - 6
*T*