1.3 线性规划问题的单纯形法

1.3.1 线性规划问题的标准形式

线性规划问题的标准形式如下：

或简写成

令

A=(aij)m×n，

aj=(a1j,a2j,…,amj)T，

C=(c1,c2,…,cn)，

b=(b1,b2,…,bm)T，

X=(x1,x2,…,xn)T

则上述标准线性规划问题可以用矩阵形式表示：

max z=CX

非标准形式的线性规划问题，可以通过一些简单代换化为标准线性规划问题。

1. 最小值问题

目标函数为最小值问题，如，可以等价地化为最大值问题，因为。

2. 不等式约束问题

形如aj1x1+aj2x2+…+ajnxn≤bj的不等式约束，可以通过引入所谓“松弛变量xn+1”化为等式约束aj1x1+aj2x2+…+ajnxn+xn+1=bj（其中xn+1≥0）；而形如aj1x1+aj2x2+…+ajnxn≥bj的不等式约束，可以通过引入所谓“剩余变量xn+2”化为等式约束aj1x1+aj2x2+…+ajnxn−xn+2=bj（其中xn+2≥0）。

3. 变量无符号限制问题

变量xj无非负约束条件问题，可以定义，其中，从而化为非负约束。

例1-5 将以下线性规划问题转化为标准形式。

解：令z'=-z，引进松弛变量x4≥0，引进剩余变量x5≥0，并令x2=x2'-x2''，其中，x2'≥0，x2''≥0

得到以下等价的标准形式：

1.3.2 线性规划解的概念

对于线性规划的标准型：

max z=CX

设r（Am×n）=m＜n，将A按列分块，记为A=(P1,P2,…,Pn)。有以下几个线性规划问题的基与解的概念。

（1）基、基变量、非基变量 A的任一非奇异m阶子矩阵B均称为线性规划的一个基；设B=（P1,P2,…,Pm），则称Pj（j=1,2,…,m）为基向量；称与其相对应的变量xj（j=1,2,…,m）为基变量；其余的变量称为非基变量。

（2）基（本）解、基（本）可行解、最优解 设B是线性规划的一个基，在AX=b中，令非基变量取零时由AX=b求出的解称为线性规划对应于基B的基（本）解，记为XB；若XB≥0，则称XB为基（本）可行解，且基B为可行基；使目标函数取到最大值的基（本）可行解称为最优解。

（3）退化的基本解 若基本解中有基变量值为0，则称之为退化的基（本）解。类似地，有退化的基本可行解和退化的基本最优解。

1.3.3 单纯形法的基本思想

线性规划的有效算法是单纯形法（Simplex Method），它是由美国运筹学家丹捷格于1947年首创的。若线性规划问题存在最优解，则必存在某一个基本可行解为最优解，所以对于给定的线性规划问题，其求解思路为：从可行域中的一个基可行解出发，判别它是否是最优解，如果不是，寻找下一个基可行解，并且努力使目标函数得到改进；如此迭代下去，直到找到最优解或判定问题无解为止。

1.3.4 最优性检验与解的判别

对标准型的一般线性规划问题，经过变换、迭代，可将线性规划约束条件中非基变量移至方程右边，得出如下形式

即

将式（1-7）代入目标函数式中，整理得

令，于是i=1 i=1

再令σj=cj−zj，j=m+1,…,n，其中σj称为检验数，则有

由于是常数，式（1-9）表明，可以用检验数σj表示目标函数中的价值系数cj。

定理1-1最优解的判别定理 若为对应于基B的一个基可行解，对于一切j=m+1,…,n,，有检验数σj≤0，则X（0）为最优解。

事实上，在式（1-9）中，因为σj≤0，xj≥0，所以对一切xj都有z≤z0。因此，X（0）为最优解。

定理1-2无穷多最优解的判别定理 若为对应于基B的一个基可行解，对于一切j=m+1,…,n,，有检验数σj≤0，且存在某个非基变量对应的检验数σm+k=0，且存在另一个最优解，则该线性规划问题有无穷多个最优解。

证明：令决策变量为X=[x1,x2,…,xm+1,…,xm+k,…,xn]T，为线性规划问题的一个最优解。则有

若让原来的非基变量仍取值为0（xm+k除外），则有

存在时，取，这时，从而，我们可以得到一个可行解

故X(1)也是最优解。由于X(1)≠X(0)，它们的凸组合X=αX(0)+(1−α)X(1)也是最优解。

定理1-3无界解的判别定理 若为对应于基B的一个基可行解，存在某个非基变量对应的检验数σm+k>0，并且对应的变量系数，i=1,2,…,m，则该线性规划问题有无界解（或称为无最优解）。

证明：构造一个线性规划问题的新解X(1)，它的分量为

=0(j=m+1,…,n,但j≠m+k)

由于≤0,i=1,2,m，所以对任意的λ>0都是可行解。把x(1)代入式（1-9）中，，当λ→+∞时，由于σm+k>0，从而z→+∞。可见，该线性规划问题目标函数无界。

1.3.5 单纯形法的计算步骤与单纯形表

单纯形表求解线性规划问题的具体步骤为：

（1）找出初始可行基，确定初始基可行解，建立初始单纯形表。

（2）根据各非基变量的检验数对线性规划问题解的情况进行判别。

① 若所有非基变量xj（j=m+1,…,n）的检验数σj≤0，则已得到最优解，问题求解完成。否则转入下一步。

② 若存在非基变量xj，其检验数σj>0，但对i=1,2,…,m，有ai,j≤0，则此问题为无界解，停止计算。否则转入下一步。

（3）根据max(σj≥0)=σk，确定xk为换入变量。如果有两个或多个相同的最大值，选取下标最小的非基变量xk为换入变量。

（4）按θ规则，计算，确定x1为换出变量。如果有两个或多个相同的最小值，选取下标最小的基变量为换出变量。

（5）以alk为主元素进行迭代（运用矩阵的初等行变换），把xk所对应的列向量Pk=(a1k,a2x,…,alk,…,amk)T转变为第l个元素为1的向量(0 … 0 1 0… 0)T。同时，将XB列的xl换为xk，CB列的cl换为ck，得到新的单纯形表。

重复步骤（2）～（5），直到问题求解结束。

单纯形法的求解过程，就是从一个基可行解转换到另一个相邻的基可行解，每一次基变换，从几何意义上说，就是从一个顶点转换到另一个顶点。

单纯形算法的实质是将非基变量视为一组参数，并将目标函数和基变量都表示成为由非基变量表示的形式。用一个矩阵来表示单纯形法迭代中所需要的全部信息，这就是单纯形表，单纯形法基本计算步骤可以在单纯形表中来完成，如表1-4所示。

例1-6 求线性规划问题：

解：引入松弛变量x3，x4，x5（x3，x4，x5≥0），约束条件化成等式，将原问题进行标准化，得

（1）确定初始可行基为单位矩阵I=[P3，P4，P5]，基变量为x3，x4，x5，非基变量为x1，x2，则有

对应的基可行解X(0)=(x1,x2,x3,x4,x5)=(0,0,8,16,12)T，目标值Z=2×0+3×0+0×8+0×16+0×12=0。将例题求解过程列成单纯形表表格形式，如表1-5～表1-8所示。

（2）根据

确定换入、换出变量后，以alk为主轴元素进行迭代（即高斯消元法或称为旋转运算），把xk换入基变量，对应系数列向量调成单位列向量。

在上述例题中，表1-5中非基变量对应的检验数分别为

σ1=c1−z1=2−(0×1+0×4+0×0)=2

σ2=c2−z2=3−(0×2+0×0+0×4)=3

因检验数大于0，max(σ1,σ2)=max(2,3)=3，对应的x2为换入变量，计算θ，

x2替换x5

对应的新的基可行解

X(1)=(0,3,2,16,0)T，目标函数取值Z=9。

进行旋转运算，得到表1-7。

x5换入，x4换出，再次进行旋转运算，得到表1-8。

非基变量检验数，，则该线性规划具有唯一最优解，最优解是x1*=4,x2*=2,x3*=0,x4*=0,x*5=4，目标函数最优值 z*=14。

例1-7 求线性规划问题：

解：引入松弛变量x3，x4，x5（x3，x4我，x5≥0），约束条件化成等式，将原问题进行标准化，得

建立单纯形表，并进行迭代运算，如表1-9所示。

非基变量检验数σ3=−2,σ4=0，迭代已经得到最优解X*=(2,3,0,2,0)T，Z*=16，由于σ5=0，如果以x5作为换入变量，x4作为换入变量，再次旋转运算，得表1-10。

非基变量检验数σ3=−2,σ5=0，得到该线性规划另一最优解，X*=(4,2,0,0,1) T，Z*=16，所以该线性规划具有无穷多最优解。

例1-8 求线性规划问题：

解：引入松弛变量x3，x4，x5（x3，x4，x5≥0），约束条件化成等式，将原问题进行标准化，得

建立单纯形，并进行迭代运算，如表1-11所示。

本例第2个单纯形表中，非基变量x2对应的检验数σ2>0，并且对应的变量系数ai,2′≤0（i=1,2,3），根据无界解判定定理，该线性规划问题有无界解（或无最优解）。

如果从方程角度来看，第2个表格还原为线性方程

即

令x3=0，则

此时，若x2进基，则x1,x4,x5会和基变量x2同时增加，同时目标函数值无限增长，所以本题无界。