第4章 单纯形法的计算方法单纯形法求解线性规划的思路: 一般线性规划问题具有线性方程组的变量数大于方程个数, 这时有不定的解。

但可以从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步选择的单纯形。

这就是迭代,直到目标函数实现最大值或最小值为止。

4.1 初始基可行解的确定
为了确定初始基可行解, 要首先找出初始可行基, 其方法如下。

（1）第一种情况：若线性规划问题
max z =
从Pj ( j = 1 , 2 , ⋯ , n)中一般能直接观察到存在一个初始可行基
（2）第二种情况：对所有约束条件是“ ≤”形式的不等式, 可以利用化为标准型的方法, 在每个约束条件的左端加上一个松弛变量。

经过整理, 重新对 及 ( i = 1 , 2 , ⋯ , m; j = 1 , 2 , ⋯ , n)进行编号, 则可得下列方程组
显然得到一个m×m单位矩阵
以B 作为可行基。

将上面方程组的每个等式移项得
令由上式得
又因 ≥0, 所以得到一个初始基可行解
（3）第三种情况：对所有约束条件是“ ≥”形式的不等式及等式约
束情况, 若不存在单位矩阵时, 就采用人造基方法。

即对不等式约束减去一个非负的剩余变量后, 再加上一个非负的人工变量; 对于等式约束再加上一个非负的人工变量, 总能得到一个单位矩阵。

4.2 最优性检验和解的判别
对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况, 为此需要建立对解的判别准则。

一般情况下, 经过迭代后可以得到：
将上代入目标函数，整理后得
令
于是
再令
则
(1) 最优解的判别定理
若为对应于基B的一个基可行解，且对于一切 且有则 为最优解。

称为检验数。

(2) 无穷多最优解的判别定理
若为一个基可行解， 且对于一切 且有 又存在某个非基变量的检验数，则线性规划问题有无穷多最优解。

(3) 无界解判别定理
若为一个基可行解，有一个> 0 ,并且对i = 1 , 2 , ⋯, m,有≤0 , 那么该线性规划问题具有无界解(或称无最优解)。

4.3 基变换
若初始基可行解 不是最优解及不能判别无界时, 需要找一个新的基可行解。

具体做法是从原可行解基中换一个列向量(当然要保证线性独立),得到一个新的可行基, 这称为基变换。

为了换基, 先要确定换入变量, 再确定换出变量, 让它们相应的系数列向量进行对换, 就得到一个新的基可行解。

(1) 换入变量的确定
由看到, 当某些 > 0 时, 增加则目标函数值还可以增大, 这时要将某个非基变量换到基变量中去(称为换入变量)。

若有两个以上的 > 0 , 则为了使目标函数值增加得快, 从直观上一般选> 0 中的大者, 即
则对应的为换入变量。

(2) 换出变量的确定
设是一组独立的向量组，它们对应的基可行解是。

将它代入约束方程组得到
其他的向量 都可以用线性表示，若确定非基变量为换入变量，必然可以找到一组不全为零的数（i=1,2，...,m）使得
在上式两边同乘一个正数，然后将它加到式上，得到
或
当取适当值时, 就能得到满足约束条件的一个可行解( 即非零分量的数目不大于m个)。

就应使( i = 1 , 2 , ⋯ , m) 中的某一个为零,并保证其余的分量为非负。

这个要求可以用以下的办法达到: 比较各比值( i = 1 , 2 , ⋯ , m)。

又因为θ必须是正数, 所以只选择> 0 ( i = 1 , 2 , ⋯ , m) 中比值最小的等于θ。

按最小比值确定θ值, 称为最小比值规则。

将θ=代入X中便得到新的基可行解。

4.4 单纯形法的计算步骤
(1) 找出初始可行基, 确定初始基可行解, 建立初始单纯形表。

(2) 检验各非基变量的检验数是
则已得到最优解，可停止计算。

否则转入下一步。

(3) 在> 0 , j = m+ 1 , ⋯ , n 中,若有某个 对应的系数列向量0 , 则此问题是无界, 停止计算。

否则, 转入下一步。

(4) 根据确定为换入变量，按原则计算
可确定为换出变量，转入下一步。

(5) 以为主元素进行迭代，把所对应的列向量
将列中的换为，得到新的单纯形表。

重复（2）（5），直到终止。