[管理学]第二章单纯形法.ppt

文档介绍：第二章单纯形法
一单纯形法的一般原理
1确定初始基可行解
对标准型的线性规划问题
st.
假定在上述约束条件的系数矩阵中总存在一个单位矩阵:
1 0 ··· 0
0 1 ··· 0
···
0 0 ··· 1
式中称为基向量,对应基向量的变
量称为基变量。模型中其它的变量
称为非基变量。在标准型中令所有非基变量等于零,得到一个解,
因为b>0,这个解为基可行解。
2从一个基可行解转换为另一个基可行解
设初始可行基中前m个为基变量,即
代入约束条件,有
式(1)
写出(1)式系数矩阵的增广矩阵
是一组基,其他非基向量可以用
这个基的线性组合表示,有
或者(2)
将(2)式乘上一个正的数得

(3)
(1)+(3)并经过整理有
(4)
由(4)找到满足约束方程
的另外一个点X(1),有
3最优性检验和解的判别
将基可行解和X(1),分别代入目标函数得到
(5)
我们来看(5)式,因为是大于0的,所以只要
就有
通常简写为或