下载掌阅APP，畅读海量书库
立即打开
从上一节中我们看到，若线性规划有最优解，必在可行域的某个顶点达到。最可能想到的是把所有顶点都找出来，然后逐个比较，求出最优解，这种方法事实上是行不通的，因为顶点的个数非常多。例如，
m
＝20，
n
＝40，顶点的个数有
个，要计算这么多顶点对象的目标函数值，显然是不可能的。
换一种思考方法，从某一个基本可行解出发，每次总是寻找比上一个更好的基本可行解，如果不比上一个好就不去计算，这样做就可以大大减少计算量。其基本想法是判别当前解是否最优，提出问题的标准，从可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数逐步增大，最后就得到了最优解。美国数学家丹捷格提出的单纯形方法解决了此问题，单纯形方法到目前为止是求解线性规划的最普遍、最有效的方法。
为了确定初始基可行解，要首先找出初始可行基，其方法如下：
若线性规划问题：
从A中确定一个初始可行基，使得：
，构造初始可行基有两种方式。若约束条件是“≤”型的不等式，在每个约束条件的左端加上一个松弛变量。经整理，重新对x
i
及a
ij
进行编号，可得到下列方程组：
显然可以得到一个单位矩阵：
以 B 作为可行基，将每个等式移项：
令 x m ＋1 ＝ x m ＋2 ＝…＝ x n ＝0，由上式可得到一个初始基可行解：
对所有约束条件是“≥”形式的不等式及等式约束情况，化为标准型后若不存在单位矩阵式，就采用人造基方法。即对“≥”型不等式约束减去一个非负剩余变量，再加上一个非负人工变量；对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。
由两个变量的线性规划图解方法，我们得到启示，线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况，为此需要建立对解的判别准则。根据上文得到的基解计算公式可归纳如下：
将上式代入目标函数式，整理后得到：
令：
于是：
再令 σ j ＝ c j － z j （ j ＝ m ＋1，…， n ）
则：
（1）最优解判别定理：若
X
（0）
＝（
b
，
b
，…，
b
′
，0，…，0）
T
为对应于基
B
的一个基可行解，且对于一切
j
＝
m
＋1，…，
n
有
σ
j
≤0，则
X
（0）
为最优解，称
σ
j
为检验数。
（2）无穷多最优解判别定理：若
X
（0）
＝（
b
′
，
b
′
，…，
b
′
，0，…，0）
T
为一基可行解，对于一切
j
＝
m
＋1，…，
n
，有
σ
j
≤0，又存在某个非基变量的检验数
σ
m＋k
＝0，则线性规划问题可能有无穷多最优解。
（3）无界解判别定理：若
X
（0）
＝（
b
，
b
，…，
b
′
，0，…，0）
T
为一基可行解，有一个
σ
m＋k
＞0，并且对
k
＝1，2，…，
m
，有
a
，
m
＋
k
≤0，那么该线性规划问题具有无界解（或称为无穷解或无有限最优解）。
若初始基可行解 X （0） 不是最优解及不能判断无界时，需要找一个新的基可行解。具体做法是从原可行解基中换出一个列向量（当然要保持线性独立），从原非可行基中换入一个列向量，得到一个新的可行基，称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行交换，得到一个新的基可行解。
当某些 σ j ＞0时， x j 增加则目标函数值还可以增大，这时要将某个非基变量 x j 换入到基变量中去（称为换入变量）。若有两个以上的 σ j ，那么选 σ j ＞0中大的那个，即：max（ σ j ＞0）＝ σ k ，则对应的 x k 为换入变量。但也可以任选或按最小足码选。
在确定 x k 为换入变量后，由于其他的非基变量仍然为非基变量，即 x j ＝0（ j ＝1，2，… n 且 j ≠ k ），则约束方程组有：
由于所有的 x j ≥0，所以若令：
则 x k 的增加不能超过 θ ，此方程相应的变量 x l 即为换出变量。这时的 θ 值是按最小比值来确定的，称为最小比值原则；与此相应的 a lk 称为主元素。
首先介绍一下单纯形表，为了计算上的方便和规格化，对单纯形法计算设计了一种专门表格，称为单纯形表（见表2.3）。
表2.3
在单纯形表的第2～3列列出某个基可行解中的基变量及它们的取值，接下来列出问题中的所有变量。在基变量下面各列数字分别是对应的基向量数字。表中变量 x 1 ， x 2 ，…， x m 下面各列组成的单位矩阵就是初始基可行解对应的基。
其中：每个基变量 x j 下面的数字，是该变量在约束方程的系数向量 P j 表达为基向量线性组合时的系数。
c j 为表最上端的一行数，是各变量的目标函数中的系数值；
C B 为表中最左端一列数，是与各基变量对应的目标函数中的系数值；
b 列中填入约束方程右端的常数。
检验数 σ j ＝ c j － z j （ j ＝ m ＋1，…， n ）称为变量 x j 的检验数，将 x j 下面的这列数字 P j 与 C B 这列数中同行的数字分别相乘，再用 x j 上端 c j 值减去上述乘积之和，即：
θ
i
列的数字是在确定换入变量后，按
θ
规则计算后填入；其中，
（
x
j
为换入变量）。
根据以上讨论，将求解线性规划问题的单纯形法的计算步骤归纳如下：
第一步，求出线性规划的初始基可行解，列出初始单纯形表。
第二步，进行最优性检验。各非基变量检验数为 σ j ＝ c j － z j （ j ＝ m ＋1，…， n ），如果 σ j ≤0，则表中的基可行解是问题的最优解，计算到此结束，否则进入下一步。
第三步，在 σ j ＞0， j ＝ m ＋1，…， n 中，若有某个 σ k 对应 x k 的系数列向量 P k ≤0，则此问题无界，停止计算；否则，转入下一步。
第四步，从一个基可行解换到另一个目标函数值更大的基可行解，列出新的单纯形表。
（1）确定换入变量。有 σ j ＞0，对应的变量 x j 就可作为换入变量，当有两个以上检验数大于零，一般取最大的 σ k ，即 σ k ＝max｛ σ j ｜ σ j ＞0｝，取 x k 作为换入变量。
（2）确定换出变量。根据最小
θ
规则，对
p
k
列由公式计算得：
，确定是
X
1
换出变量。
（3）元素 a lk 决定了从一个基本可行解到另一个可行解的转移去向，取名为主元素。以 a lk 为主元素进行旋转变换，得到新的单纯形表，转到步骤二。
下面，我们用例2.1说明单纯形表进行迭代运算：
（1）根据问题的标准型，取松弛变量 x 3 ， x 4 ， x 5 为基变量，对应得单位矩阵的基，得到初始基可行解 X （0） ＝（0，0，6，8，18） T ，得到初始单纯形表，如表2.4所示。
表2.4
其中，非基变量的检验数：
（2）由检验数 σ 1 ， σ 2 大于零， P 1 ， P 2 有正分量，转入下一步。
（3）max（ σ 1 ， σ 2 ）＝max（4，3）＝4，对应 x 1 为进入变量。
θ ＝min｛ b i ／ a i 1 ｜ a i 1 ＞0｝＝min｛6／1，－，18／2｝＝6
它对应的基变量 x 3 是换出基变量， x 3 所对应的行与 x 1 所对应的列包括检验数变为（1，0，0，0） T ，在 X B 列将 x 3 换成 x 1 得到新单纯形表（见表2.5）。
表2.5
此时，新基变量 X B ＝（ x 1 ， x 4 ， x 5 ） T ，对应于基可行解 X （1） ＝（6，0，0，0，8） T ，相应的目标值 z ＝24。检验表2.5中的检验数行得知 x 2 的检验数为3＞0，说明 x 2 应为换入基变量，计算 θ 值：
所以对应的 x 5 为换出基变量，基变量 x 5 的行与进入基变量 x 2 的列交叉处元素3为主元素，再对主元素进行旋转变换，使 x 2 列变为单位向量（0，0，1，0） T ，得到表2.6。
表2.6
此时，基变量为 X B ＝（ x 1 ， x 4 ， x 2 ） T ，对应的基可行解为 X （3） ＝（6，2，0，4，0） T ，对应目标函数值 z ＝30。由于所有检验数均小于或等于0，所以此解是最优解，对应基为最优基。