下载掌阅APP，畅读海量书库
立即打开
单纯形法是Dantzig于 1947 年提出的,70 多年来，它一直是求解线性规划最有效的方法之一。该算法的单纯形表可以把 2.1.4 的高斯迭代算法的所有信息表达出来，本节讨论单纯形法的基本算法。
考虑标准形式的线性规划:
假设已找到(SLP)的一个可行基 B ,不妨设 B 是由矩阵 A 的前 m 列组成，即 B =( P 1 , P 2 ,…, P m )。这时，可把( SLP)的约束方程组(2.5 )等价变换(两边左乘 B - 1 )为如下的形式:
其中
,
,…,
≥0 (这里我们用
,
表示约束方程组在迭代过程中变化的系数，以区别于初始数据
a
ij
和
b
i
)。
(2.7)式的系数矩阵含有一个
m
阶单位阵，且右端项非负，我们称它为约束方程组关于可行基
B
的典式。在典式(2.7)中令非基变量
x
m+ 1
=
x
m+ 2
= …=
x
n
= 0,便可得到基可行解
X
(0)
= (
,
,…,
,
)
T
,其相应的目标值
z
0
=
。
由(2.7)式可得
将(2.8)式代入目标函数(2.4)式，整理后得
记
则
再记
于是有
对于任意可行解 X ,其分量 x j ≥0,因此，若所有 σ j ≤0, j = m + 1,…, n ,由(2.12)式可见 X 的目标函数值 z ≤ z 0 。
最优解判别准则 若所有非基变量的 σ j ≤0,则 X (0) 为最优基可行解。这时，称 X (0) 相应的基为最优基。
我们称
σ
j
为检验数。注意(2.11)式中的
z
j
等于两个
m
维向量
C
B
与
的内积(两向量相应分量乘积之和），其中
C
B
的分量是基变量在目标函数中的系数，而
是典式(2.7)中系数矩阵的第
j
列。因此，也可以计算基变量的检验数，易见所有基变量的检验数都等于零。
注：上述判别准则只是最优性的充分条件而非必要条件。然而，若假设 X (0) 非退化，则该准则也是必要的。
若最优性条件不满足，即存在某非基 σ k > 0。由(2.12)式可见，若令 x k 增加(对于 X (0) 有 x k = 0),而其他非基 x j 保持取零值，可使目标函数 z 的值增加。设 x k 由 0 增加到 θ > 0,其他非基 x j = 0,这时由(2.8)式有
记所得到的解为 X ( θ ),显然，若 X ( θ )满足非负性条件，则 X ( θ )便是可行解。 X ( θ )的目标函数值为:
且 θ 越大, z 越大。
我们分两种情形讨论。
情形 1:
相应的列
≤0, 这时, 由 (2. 13) 式不难看出, 对于任意
θ
> 0,
X
(
θ
)都是可行解。当
θ
→ + ∞ ,有
z
=
z
0
+
θσ
k
→ + ∞ ,因此,(SLP)具有无界解。
情形2:
相应的列
有正分量。为了保证
X
(
θ
) 的非负性, 由 (2. 13) 式可见,
x
k
的最大增值应为:
上式的含义是：对所有
>0 计算比值
,然后取其中最小者为
θ
,并假定比值的最小者在某个基中的指标
l
中达到。我们称它为
θ
规则，或最小比值规则。
令
x
k
入基,
x
l
出基(在线性代数中已知道
≠0,这点一定能够做到）。变换方程组以得到新基可行解及其典式，由(2.14)式可见新目标函数值
z
≥
z
0
(当
θ
> 0 时严格不等式成立)。
需要说明的是:
(1) 变换方程组的具体做法是使用初等行变换把典式方程组中
x
k
对应的列
=
变为单位向量
←第
l
个分量, 该变换称为旋转变换或转轴, 元素
称为主元, 标之为 [
]。
(2)若基可行解 X (0) 非退化，则 θ 一定大于零，故新目标值 z > z 0 。
为了用更简洁、紧凑的方式描述单纯形法的计算步骤，人们专门设计了一种计算表格，称为单纯形表，它是由典式(2.7)和(2.12)式的系数组成的。表 2 -3 是例 4 的初始单纯形表。
表 2 -3
单纯形表的第一行是目标函数系数。第二行是表头，其中 C B 、 X B 分别代表基变量的目标函数系数和基变量。 b′ 表示典式的右端项，也是基变量的当前值。第三行起(除最后一行）的主要部分是典式的方程组系数和右端项。最后一行是目标函数值(等于 C B 列与 b′ 的内积，写在 b′ 列的格中）和各变量的检验数, x j 列的检验数可用它“头顶上的”目标函数系数减去 C B 列与该列的内积。在任何时候，基变量的检验数一定等于零，因此只需计算非基变量的检验数。最右一列用来确定出基变量，它是用入基列向量的各正元素去除 b′ 列的对应元素而得到的。
下面给出单纯形法的计算步骤:
(1)将问题化为标准型，确定初始bfs,建立初始单纯形表。
(2)若各检验数 σ j ≤0,则已得到最优解，可停止计算；否则进入步骤(3)。
(3)若存在某
σ
k
>0 且相应的列
≤0,则问题无界，停止计算；否则进入步骤(4)。
(4)选取某 σ k > 0,确定 x k 为入基变量，相应的列为主元列。
计算
θ
以确定出基变量
x
l
,相应的行为主元行。主元列与主元行的交
为主元。进入步骤(5)。
(5)进行旋转变换，把
x
k
所对应的列变换为单位列向量(主元
变为 1)。旋转变换的具体运算如下:
①把主元行除以主元得新表最先行(新表 x k 所在行)。
②对于 i ≠ l ,则
新表第
i
行=旧表第
i
行-
×新表最先行
其中
是旧表第
i
行与主元列的交。
将 X B 列中的 x l 换为 x k ,得到新的单纯形表。转回步骤(2)。
步骤(2)到步骤(5)叫作单纯形法的迭代。每迭代一步都得到一个新的单纯形表。
现从表 2 -3 来说明上述计算步骤。
由于
σ
2
= 120 > 0,标记为[120],令
x
2
为入基变量，用
x
2
列的正元素去除
b′
列的对应元素，并求其中的最小者，可得
θ
= min{
,
,
}=
= 30,它所在行对应的
x
5
为出基变量。
对[120]所在列和[30]所在行的位置以 10 为主元进行旋转运算，即作初等行变换，使
x
2
对应的列
变换成
,将
X
B
列中的
x
5
换为
x
2
,后续完整的算法过程如表2 -4所示。
表 2 -4 的最终表中所有检验数都已为负或零，于是得到最优解 X ∗ = (20,24,84,0,0) T ,最优值 z ∗ = 4 280。这与图解法的结果是一致的。而且读者不难看出，表 2 -4 的初始表对应于图 2 -1 的顶点 O ,第二个表对应于顶点 A ,而最终表对应于顶点 B 。所以，单纯形法迭代的几何意义就是从可行域的一个顶点转移到另一个相邻的“更好”的顶点。
两点注意:
注意 1 对于求min的线性规划，可以使用下面三种方法之一进行处理。
(1)把求min问题转化为求max问题。
(2)把最优解判别准则改为所有非基变量的检验数 σ j = c j - z j ≥0。入基变量是检验数小于零的那个变量，确定出基变量的方法与求max问题相同。
(3)单纯形表中的检验数不是 c j - z j ,而是 z j - c j 。最优解的检验及确定入基变量与出基变量的方法和求max问题所述相同。
注意 2 若仔细分析单纯形法的迭代原理，我们可以发现，对应于每个可行基的单纯形表中的全部数据都可以通过矩阵运算直接从原问题的初始数据得到。
表 2 -4
表 2 -4 的第三个表对应的可行基(也是最优基）是:
注意 B 的数据是初始数据。记 B 的逆阵为 B - 1 ,则
由单纯形表的变换原理不难看出表 2 -4 中第三个表的
b′
列和各
列满足
其中 b 和 P j 都是初始数据。而
(2.16)式的具体数值计算为:
建议读者自行验算其他式子。