文档介绍：改进单纯形法的步骤
(1) 根据给出的线性规划问题的标准型,确定初始基变量和初始可行基B。求初始可行基B的逆阵B-1,得初始基本可行解
。
(2)计算单纯形乘子,得目标函数当前值
(3) 计算非基变量检验数,
若σN≤0,则当前解已是最优解,停止计算;否则转下一步。
(4)  根据,确定非基变量为换入变量,计算,若≤0,则问题没有有限最优解,停止计算,
否则转下一步。
(5) 根据,确定基变量

为换出变量。
(6) 用替代得新基B1,由变换公式
计算新基的逆阵B1-1,求出新的基本可行解
其中为变换矩阵,构造方法是:
从一个单位矩阵出发,把换出变量在基B中的对应列的单位
向量,替换成换入变量对应的系数列向量,并做如下变形,
主元素(应在主对角线上)取倒数,其它元素除以主元素
并取相反数。
重复(2)~(6)直至求得最优解。
换入
无界解
换出
≤0
≤0
①
②
④
③
⑤
最优解
初始基
新基
⑥
例9、试用改进单纯形法求解
解:
(1)观察法确定

, 为基变量为非基变量
(2)计算单纯行乘子
目标函数当前值
(3)非基变量检验数
(4)  选择换入变量

故为换入变量。计算
(1)
(2)
(3)
(4) 选择换入变量
(5)

选择换出变量,主元素=
(6) 用代替得新可行基
为基变量,
为非基变量,

进入第三循环.
(1)
(2)
(3)
非基变量对应的检验数全部非正,
故当前解即为最优解,
相应的目标函数最优值。
六、单纯形法总结
1、Min型单纯形表与Max型的区别仅在于:
令σk=min{σj ≤0}的xk进基,当σ≥0时最优。
2、解的几种情况及其在单纯形表上的体现(讨论Max型)
唯一
最优解
σj ≤0,
非基σ<0
多重
最优解
σj ≤0
有非基σk=0
无界解
有σk >0
但B-1Pk ≤ 0
无可行解
用大M法求解,最优基中含有X人
退化解
最优解中某基变量为0