单纯形方法

线性规划基本定理.

给定线性规划的标准形式如下：

max cTx (1) s.t. Ax = b, x  0, (2)

其中A是秩为m的mn阶矩阵, b  0. i) 如果存在可行解, 则存在基可行解; ii) 如果存在最优解, 则存在最优的基可行解.

这个定理将求解线性规划的任务变成为搜索基可行解。因为对有n个变量和m个约束问题，基可行解最多不超过下面的数：

𝑛!𝑛

= 𝑚𝑚! 𝑛−𝑚 !

定理(顶点和基解等价). 设K是包括所有满足(2)的n维向量x的凸多面体。则向量x是凸多面体K的一个顶点当且仅当x是一个基可行解。

线性规划中的问题

根据线性规划基本定理，解线性规划只需要在约束凸多面体的所有顶点上寻找最优解。因此，我们需要考虑的问题有： 1. 怎样找到一个基可行解？ 2. 判别基可行解是否最优解。

3. 从非最优的基可行解找到另一个基可行解，使目标函数值增大。 4. 如果问题无最优解，能发现一族可行解，使目标函数无上限。

对于我们前面提出的四个问题，单纯形方法能解决其中的问题2-4。换句话说，单纯形

方法要求一个已知的基可行解。

当从非最优的基可行解找到另一个基可行解时，为了保证目标函数值增大，单纯形方法还要求如下的假定，这引入了下面的概念：

退化解和非退化解：设x 0 = [B 1b, 0]是一个基可行解，如果有基变量的取值是0，即B 1b中有分量等于零，则称基可行解x 0是退化的。否则，称x 0是非退化的。

非退化假定：假设线性规划的每个基可行解都是非退化的。

1

给定线性规划的标准形式如下：

max cTx (1)

(LP) s.t. Ax = b, (2)

x  0, (3)

其中A是行满秩的mn阶矩阵, b  0.

单纯形方法是在已知一个基可行解的情况下，寻找线性规划的最优基可行解的算法。 强调一下：单纯形方法就是在已知一个基可行解的情况下，寻找线性规划的最优基可行解。

单纯性方法直接能解决问题2-4。而问题1可以使用辅助线性规划来解决。 我们首先来解决问题2。

对线性规划(LP)，假设知道一个基可行解x0。因此，就有一个可行基B，假设B由约束系数矩阵A的前面m列构成，对应的基变量用xB表示， xD表示非基变量。这样，我们就可以将决策变量x，价值系数c和约束矩阵A分块成

x = [xB, xD]， c = [cB, cD]

和

A = [B, D]。

于是，线性规划可以被写成下面的形式：

𝑇𝑇 max 𝑐𝐵𝑥𝐵+𝑐𝐷𝑥𝐷

s.t. BxB + DxD = b, (4)

xB, xD  0.

基可行解x0就是在约束方程(4)中令非基变量xD = 0得到的结果。因为基B是可逆矩

0阵，所以有𝑥𝐵=𝐵−1𝑏。

单纯形方法怎么判断基可行解x0 = [B1b, 0]是否是最优的基可行解呢？ 我们从约束方程(4)解出所有的基变量xB ，用非基变量xD表示，得到

xB = B1b  B1DxD, (5)

把由(5)表示的基变量代入到目标函数中，就有

𝑇𝑇𝑇𝑇

𝑧=𝑐𝐵𝑥𝐵+𝑐𝐷𝑥𝐷=𝑐𝐵(𝐵−1𝑏−𝐵−1𝐷𝑥𝐷)+𝑐𝐷𝑥𝐷

整理后得到

𝑇−1𝑇𝑇−1

𝑧=𝑐𝐵𝐵𝑏+(𝑐𝐷−𝑐𝐵𝐵𝐷)𝑥𝐷

𝑇−1

当非基变量xD = 0时，得到𝑧(𝑥0)=𝑐𝐵𝐵𝑏。 𝑇𝑇−1我们令 = (m+1, …, n) = 𝑐𝐷−𝑐𝐵𝐵𝐷。

这里 是行向量，并且正好是用非基变量表示的目标函数中所有变量的系数。而目标函数可以写成

2

zcBBT1bm1xm1...nxn

我们看到，如果有某个j > 0，取非基变量xj > 0，则

目标函数值= z(x0) + j xj > z(x0)。

这样得到的一个x还是可行解吗？在非退化假定下，我们可以从方程(5)中得到这样的一个可行解。我们回头看看方程(5)

xB = B1b  B1DxD, (5)

因为基可行解都是非退化的，所以B1b > 0。当xj > 0充分小时，可以保证xB > 0。因此，可以得到一个可行解x具有非基变量xj > 0。从而有z(x) = z(x0) + j xj > z(x0)。

由于当j > 0时，存在可行解 x使得目标函数值比在基可行解x0处的目标函数值更大，所以x0不是最优解。

这样，我们得到单纯形方法的最优性判据。

最优性判据：如果存在j > 0 (m +1  j  n)，则基可行解x0不是最优解；如果  0，

𝑇𝑇−1则x0是最优解；其中 = (m+1, …, n) = 𝑐𝐷−𝑐𝐵𝐵𝐷。

因为根据j (j =m +1, …, n)的符号可以判别基可行解x0是否是最优解，所以，人们称

j 为检验数。

现在“判别基可行解x0是否是最优解”的问题2已经被解决。通过检查检验数j (j =m +1, …, n)的符号，可以确定x0是否是最优解。

我们还看到，当x0不是最优解时，在非退化假定下，可以从基可行解x0找到一个可行解x使目标函数值增加。那么，可以从基可行解x0找到另一个基可行解x1使目标函数值增加吗？回答是肯定的。

现在，我们回头看看方程(5)的两种表示形式：

xB = B1b  B1DxD, (5-1)

和

xB + B1DxD = B1b. (5-2)

令G = B1D = (gij) = (gm+1, …, gn)是m(nm)矩阵。则方程(5-2)可以写成

xB + GxD = B1b 或 xB + gm+1 xm+1 +…+ gn xn = B1b

当q > 0 (m +1  q  n)时，我们令其他非基变量等于零，得到

xB + gq xq = B1b.

写成元素的形式是

x1 + g1q xq = 1,

…… xp + gpq xq = p,

……

3

xm + gmq xq = m,

其中 = (1, 2, …, m)T = B1b > 0，我们让非基变量xq > 0尽可能大，保证x1 , …, xm都非负，则xq可以取到多大的值呢？ 显然当

xq = min{i /giq | giq > 0, 1 i  m} = p /gpq (6)

时，有xp = 0 (1  p  m)。而xq > p /gpq时，xp < 0。上面的方程可以写成：

x1 = 1  g1q xq = g1q(1 /g1q  xq), x2 = 2  g2q xq = g2q(2 /g2q  xq),

……

xp + gpq xq = p = gpq(p /gpq  xq),

……

xm = m  gmq xq = gmq(m /gmq  xq),

当giq < 0时， xi随着xq增大而增大。所以(6)中的最小值是对giq > 0求的。

我们同时看到，如果所有的giq  0, i = 1, …, m, 则随着xq的增大，所有xi都增大。而在其他非基变量等于零时，目标函数是

zcBBbxqT1

于是z将随着xq增大而无限增大。 这样，前面提出的问题

3. 从非最优的基可行解找到另一个基可行解，使目标函数值增大。 4. 如果问题无最优解，能发现一族可行解，使目标函数无上限。

都被解决了。我们有了无界解的判别和找到一个使目标函数值增大的新基可行解方法如下：

无界解判别：如果q > 0并且所有giq  0, i = 1, …, m, 则线性规划无最优解，目标函数可以无限增大。

否则，令

xq = min{i /giq | giq > 0, 1 i  m} = p /gpq (6)

则有xp = 0，得到一个新的基可行解， xq是这个基可行解的新的基变量， xp成为非基变量。

到目前为止，我们已经解决了问题2-4。

因此，如果知道一个基可行解，那么，我们能判别这个基可行解是否是最优解；如果不是最优解，则存在某个检验数q > 0；如果所有giq  0, i = 1, …, m，则该线性规划无最优解，目标函数可以无限增大；否则，计算比值

min{(i /giq | giq > 0, 1 i  m} = p /gpq,

4

令xq = p /gpq，计算所有变量xi, i = 1, …, m，的值，此时必定有xp = 0, 从而得到一个新的基可行解，在这个基可行解中，xq是新的基变量，xp成为非基变量。 这就是单纯形方法。

单纯形方法步骤

记G = B1D = (gij) = (gm+1, …, gn)，是方程(5)中非基变量的m(nm)系数矩阵，  = (m+1, …, n)是检验数行，  = (1, 2, …, m)T = B1b。

步骤1. 如果j  0, j = m +1, …, n, 则x0是最优解，算法终止。 步骤2. 假设q > 0 (m +1  q  n)，判别giq的符号。如果所有的giq  0

(i = 1, …, m)，则线性规划无最优解，目标函数值可以无限增大，算法终止。否则转步骤3。

步骤3. 计算比值

min{i /giq | giq > 0, 1 i  m} = p /gpq,

得到行标p对应的基变量xp，令列标q对应的非基变量xq取公式(6)中的值，其他非基变量仍然取零值，计算出所有变量的取值，则得到一个新的基可行解，在这个新的基可行解中，xq是新的基变量，xp是新的非基变量。设新的基为B，计算出新的和G转步骤1。

在单纯形算法中，由于原来基可行解中的非基变量xq成为新基可行解中的基变量，所以人们称xq为进基变量，同理，xp被称为离基变量。于是，单纯形算法又可以被描述为：

步骤1 (最优性判别). 如果j  0, j = m +1, …, n, 则x0是最优解，算法终止。 步骤2 (无界解判别). 对q > 0 (m +1  q  n)，判别giq的符号。如果所有的giq  0，i =1, …, m， 则线性规划无最优解，目标函数值可以无限增大，算法终止。

步骤3 (确定进基变量). 选择某个q > 0 对应的非基变量xq为进基变量(新基变量)。 步骤4 (确定离基变量). 计算比值

min{i /giq | giq > 0, 1 i  m} = p /gpq,

则行标p对应的基变量xs (xp)为离基变量(新非基变量)。

步骤5 (计算新基和新基可行解). 计算新的基B(还用原来的字母表示)，新基可行解，新检验数和新非基变量在约束方程(5)中的系数G，转步骤1。

5

单纯形表

我们看到，当基变量被解出来用非基变量表示时，原来的线性规划可以被写成： max z = z0 + m+1xm+1 + … + nxn

s.t. x1 + g1, m+1 xm+1 + … + g1n xn = 1, x2 + g2, m+1 xm+1 + … + g2n xn = 2, … …………………………. xm + gm, m+1 xm+1 + … + gmn xn= m, x1, x2, …, xm, xm+1, …, xn  0,

𝑇𝑇−1

其中 = (1, 2, …, m)T = B1b > 0, G = (gij)m(nm) = B1D,  = (m+1, …, n) = 𝑐𝐷−𝑐𝐵𝐵𝐷。

我们将前面的约束方程系数，右端项，目标函数中变量的系数和常数z0列成一个表如下：

x1 1 0 x2 1 0 … … … xm 1 0 xm+1 g1, m+1 g2, m+1 … gm, m+1 … … … … … … xn g1n g2n … gmn  1 2 … m z0 m+1 n 称这个表为(标准)单纯形表(注意，右下角是 z0)。

单纯形算法的所有运算都可以在单纯形表上进行。

6