250分悬赏线性规划问题（单纯形法）

一、线性规划单纯形法的概念

（一）线性规划单纯形解法的基本思路

若一个凸集仅包含有限个极点，则称此凸集为单纯形。
线性规划的可行域是单纯形（证明略，但可以从上节图解法的例子得到认同），进而线性规划的基可行解又与线性规划问题可行域的极点1-1对应（定理2.2.2）， 线性规划单纯形法就是基于线性规划可行域的这样的几何特征设计产生的。这个方法最初是在20世纪40年代由George Dantzig研究出来的。这个线性规划单纯形解法的基本思路是：先求得一个初始基可行解，以这个初始基可行解在可行域中对应的极点为出发点，根据最优准则判断这个基可行解是否是最优解，如果不是转换到相邻的一个极点，即得到一个新的基可行解，并使目标函数值下降，这样重复进行有限次后，可找到最解或判断问题无最优解。

（二）单纯形法的最优准则

设：线性规划（LP）为：

min cx
s.t. Ax=b
x≥0

A为（LP）的约束方程组的m*n阶系数矩阵（设n≥m），A的秩为m；B是线性规划的一个基，不失普遍性，记

定义

则：称λ，或者λj,(j=1,2,…,n)为检验数。

若：λ≤0，即全部λi非正，
则：由B确定的基可行解是（LP）的最优解。
（参看附录2.3.1）

二、线性规划单纯形法的表格解法

较简单的线性规划可以采用单纯形法的表格形式，这样利用计算器就可求解。单纯形法的表格解法的基本思路是，对基可行解建立单纯形表，依据此表作最优解判断，以及从原基可行解向目标值更小的新可行解转换的计算。

对于由基阵B确定的基可行解，其单纯形表为表2.3.1形式。对于初始基可行解，其单纯形表的构建方法为：先建立表2.3.2形式的表格，然后应用“行变换”将表2.3.2中的前m列，即基变量对应的列

转换为

其中0是m元0向量：0=(0,0,…,0), 是m阶单位方阵。在这样的行变换下，表2.3.2将转换为表2.3.1

表2.3.1

检验数

基变量
cBB-1A-c cBB-1b
xB B-1A B-1b

表2.3.2

检验数

基变量
-cB -cN o
xB B N B-1b

（参看附录2.3.2）

（一）直接求解
对如下形式的较简单的线性规划可直接采用单纯形法的表格形式求解：

min cx
s.t. Ax≤b
x≥0

这种形式的线性规划标准化后，为

min cx+ox"
s.t. Ax+lx"=b
x≥0,x"≥0

其中x"=(x1",x2",…,xm")为松驰变量，而o=(0,0,…,0)T 。现在新的约束矩阵为

因为I是m*n的单位矩阵。所以我们就可用这个矩阵作基阵，松驰变量是基变量，立即得到一个初始基可行解，其目标函数值为0，而相应的初始单纯形表如表2.3.3所示。表中

θ=o=(0,0,…,0)T,

从而可开始单纯形表上求解的过程。

表2.3.3

检验数

基变量
-c θ o
A I b

下面我们通过一个实例看单纯形表解线性规划问题的一般步骤

例2.3.1 用直接法求解（LP）

max z=40x1+45x2+24x3
s.t. 2x1+3x2+x3≤100
3x1+3x2+2x3≤120
x1,x2,x3≥0

解：
第一步 先将原问题化为标准形式

min -z=-40x1-45x2-24x3
s.t. 2x1+3x2+x3+x4=100
3x1+3x2+2x3+x5=120
x1,x2,x3,x4,x5≥0

第二步 列出初始单纯形表

x1 x2 x3 x4 x5
40 45 24 0 0 0
x4 2 3 1 1 0 100
x5 3 3 2 0 1 120

此时，基可行解(0,0,0,100,120)T为，目标函数值为0.

第三步 检查检验数

故

λ=(40,45,24,0,0)≥0

因此基可行解不是最优解，要进行基的转换。

线性规划检验数的定义和最优解的单纯形法检验准则：
检验数定义为

若 基可行解对应的λ为检验数为非正向量，即

则 此可行解为最优解。
当大于零的检验数不止一个，理论上可任选一个正检验数对应非基变量为进基变量，一般情况选取最大正值的检验数对应的非基变量为进基变量，这样迭代常常会快一些。为此，我们选x2进基，因为

因此，x4为离基变量，则新的基变量为x2，x5。

第四步 建立新的基相应的单纯形表

建立单纯形表的方法：
在计算过程中，只要将A中基变量对应的列组成的子矩阵
通过行变换化成单位阵，基变量对应的检验数化成零即可。

如何从原来的表转到新的基相应的单纯形表呢？只要把A中x2相应的列向量通过初等变换化成单位向量即可。因此在上表中只要把x2对应的列

化成

我们称基变量x4所在行和非基变量x2所在列相交元素为变换轴心，用加＊表示，现在这数为3，将这行乘以（-1）加到第三行，乘以（-15）加到第一行，然后将这行行除以3，得一个新的单纯行表

x1 x2 x3 x4 x5
10 0 9 -15 0 -1500
x2 2/3 1 1/3 1/3 0 100/3
x5 1* 0 1 -1 1 20

这样我们作了一次转换，新的基可行解为(0,100/3,0,0,20),目标函数值为-1500。

现在再回到第三步。现在λ1=10,λ3=9均大于零，仍不是最优解，取x1进基；

因为：

所以，x5离基。

x1 x2 x3 x4 x5
0 0 -1 -5 -10 -1700
x2 0 1 -1/3 1 -2/3 20
x1 1 0 1 -1 1 20

现在所有检验数均小于等于零，这个基可行解（20，20，0，0，0）是最优解，原问题最优值1700.以后。

实际在表上作业时，求λk与xr的过程可不写，这些表可连在一起。

（二）单纯形法求解的基本步骤

首先我们需要对单纯形表作进一步的认识，注意到检验数：

可见，对应于基变量的λj=0(j=1,2,∧,m)，而且

再记

进而记

这样单纯形表2.3.1可呈现为表2.3.4的形式：

表2.3.4

x1 x2 … xm xm+1 … xn
检验数

基变量
0 0 … 0 λm+1 … λn f0
x1 1 0 … 0 y1m+1 … y1n
x2 0 1 … 0 y2m+1 … y2n
… … … … … … … … …
xm 0 0 … 1 ymm+1 … ymn

有了表2.3.4，单纯形表上解法的一般步骤为：

步一：把线性规划模型变成它的标准形式；

步二：确定初始基可行解，建立初始单纯形表；

步三：检查对应于非基变量的检验数λj,(j∈N)；若所有这些λj均小于零，则已得到最优解，停止计算，否则转入下一步；

步四：在所有的λj>0中，若有一个λk在单纯形表上对应的列向量的全部元素yik≤0(i=1,2,…,m)，则此问题无解，停止计算；否则转入下一步；

步五：根据max{λj>0|j∈N}=λk, 即确定λk对应的非基变量λk为进基变量；再根据

确定基变量xr为离基变量；

步六：基可行解的转换运算，即实施行变换，将单纯形表上xk对应的列向量变换为单位向量，其中包括将λk变换为0，而原yrk变换为1，称元素yrk为变换轴心。

（三）两阶段法

对一般的线性规划，往往不会象用直接法求解形为Ax≤b的线性规划那样，能够很容易找到初始基可行解，甚至连有无可行基都难以判定，这时就需要应用两阶段法来求解线性规划。

二阶段法就是把解线性规划问题划分为两个阶段，第一阶段求出原问题的一个基可行解或判断原问题可行域为空；第二阶段在得到的基可行解基础上求解原问题。方法如下：

第一阶段
人为地在原约束矩阵中增加一些变量使得到单位矩阵，增加的变量称为人工变量，目标函数是人工变量之和。具体而言，对于原线性规划标准化后的Ax=b,(b≥0)的形式，若A中不包括单位矩阵，则我们在每个方程后面加一个“人工变量”得到一个新的线性规划（LP）如下：

（当A中有一些单位向量时，人工变量可少于m个）

为书写方便我们记（LP0）为：

其中Em=(1,1,K,1),分量全为1的m元横向量，

这儿Im是可行基，又因为xa≥目标函数Emx有下界0，所以（LP0）一定有最优解。设最优解为：

则可能有三种情形：

(1)若：在最优解x0的基变量中，不存在人工变量，即人工变量xn+1,xn+2,…,xn+m都是非基变量。
则：x0的前n个分量(x10,x20,K,xn0)便是原线性规划问题的一个基可行解。可进入第二阶段。

(2)若：在最优解x0的基变量中，包括某些人工变量，并且最优值z>0。
则：原线性规划可行域为空，原线性规划无解。

这是因为，否则可设原规划有可行解(x1*,x2*,…,xn*),
则(x1*,x2*,…,xn*,0,…,0)是（LP0的可行解，其目标函数值
为0，这与最优值大于零矛盾。

(3)若：在最优解x0的基变量中，包括某些人工变量，但最优值z=0，即，此时为基变量的人工变量都取值为0。
则：设xn+1是一个人工变量的基变量，其在最优解的单纯形表中对应第S行，设J是非人工变量中非基变量的下标集。

① 如果单纯形表的第S行中，所有的ysk=0,(k∈J)此示原约束Ax=b中第S行为其余行的线性组合，即是个多余的约束，应当删去；

② 如果存在ysk≠0 (k∈J),
则无论ysk是正还是负，以它为变换轴心，xk进基，xn+1离基.如果新表中的基变量中还有人工变量，重复以上步骤，有限次可得到（1）的情形。

第二阶段

步1：以第一阶段最优解对应的单纯形表为基础，删去人工变量对应的列，并且将原规划（已标准化）的-c作为检验数，放在第一行，然后用用行变换将基变量对应的检验数消为零。

步2：以步1结束时建立单纯形表为原线性规划的初始单纯形表，求解原线性规划。

[例2.3.2] 用二阶段法求解（LP）：

min x1-2x2
s.t. x1+x2≥2
-x1+x2≥1
x2≤3
x1,x2≥0

解：
先标准化：

min x1-2x2
s.t. x1+x2-x3=2
-x1+x2-x4=1
x2+x5=3
x1,x2,x3,x4,x5≥0

第一阶段：
因为A中 对应单位向量

，故只要引进两个人工变量x6,x7即可

min x6+x7
s.t. x1+x2-x3+x6=2
-1+x2-x4+x7=1
x2+x5=3
x1,x2,K,x7≥0

在第一行放入检验数：

这等价于在第一行放-c，再用行变换使基变量的检验数为零。

x1 x2 x3 x4 x5 x6 x7
0 0 0 0 0 -1 -1 0
x6 1 1 -1 0 0 1 0 2
x7 -1 1 0 -1 0 0 1 1
x5 0 1 0 0 1 0 0 3
0 2 -1 -1 0 0 0 3
x6 1 1 -1 0 0 1 0 2
x7 -1 1 0 -1 0 0 1 1
x5 0 1 0 0 1 0 0 3
2 0 -1 1 0 0 -2 1
x6 2* 0 -1 1 0 1 -1 1
x2 -1 1 0 -1 0 0 1 1
x5 1 0 0 1 1 0 -1 2
0 0 0 0 0 0 -1 0
x1 1 0 -1/2 -1/2 0 1/2 -1/2 1/2
x2 0 1 -1/2 -1/2 0 1/2 1/2 3/2
x5 0 0 1/2 1/2 1 -1/2 -1/2 3/2

得到第一阶段最优解，人工变量不是基变量，最优值为0，则去掉x6,x7所在两列就是原问题基可行解。

第二阶段
仍将-c放在第一行，用行变换将基变量对应的检验数消为零。

x1 x2 x3 x4 x5
-1 2 0 0 0
x1 1 0 -1/2 1/2 0 1/2
x2 0 1 -1/2 -1/2 0 3/2
x5 0 0 1/2 1/2 1 3/2
0 0 1/2 3/2 0 -5/2
x1 1 0 -1/2 1/2* 0 1/2
x2 0 1 -1/2 -1/2 0 3/2
x5 0 0 1/2 1/2 1 3/2
-3 0 2 0 0 -4
x4 2 0 -2 2 0 1
x2 1 1 -1 0 0 2
x5 -1 0 1* 0 1 1
-1 0 0 0 -2 -6
x4 0 0 0 2 2 2
x2 0 1 0 0 1 3
x3 -1 0 1 0 1 1

现在检验数全小于等于零，得到原问题最优解x*=(0,3,1,2,0)T最优值-6。

[例2.3.1.3] 用二阶段法求解（LP）：

min -3x1+4x2
s.t. x1+x2≤4
2x1+3x2≥18
x1,x2≥0

标准化：

min -3x1+4x2
s.t. x1+x2+x3=4
2x1+3x2-x4=18
x1,x2,x3,x4≥0

第一阶段：

min x5
s.t. x1+x2+x3=4
2x1+3x2-x4+x5=18
x1,x2,x3,x4,x5≥0

为了少写一张表，也可在表最上方一行放 ，然后再用行变换使基变量的检验数为零。

0 0 0 0 -1
x1 x2 x3 x4 x5
2 +3 0 -1 0 18
x3 1 1* 1 1 0 4
x5 2 +3 0 -1 1 18
-1 0 -3 -1 0 6
x2 1 1 1 0 0 4
x5 -1 0 0 -1 1 16

已得到第一阶段最优解，但人工变量仍留在基里，并且最优值z=6>0故原问题可行域为空。原线性规划无解。