管理运筹学课件3单纯形法22P.ppt

文档介绍：§3 单纯形法 (Simplex Method)
本节重点:
检验数的概念和计算
最优性判别
基变换(换入变量和换出变量的确定)
旋转变换
基本思想
对于一个标准型LP问题,从一个初始基可行解出发,判断其是否为最优解,若是则结束;否则求一个与其“相邻”的、改进的基可行解。再判断这个解是否最优,若是则结束,否则再求一个“相邻”的、改进的基可行解……直至得到一个基最优解。
x1
x2
0
4
Q2(4,2)
Q1
Q3
Q4
4x1=16
4x2=12
x1+2x2=8
2x1+3x2=0
3
Q2
如例1,O Q1 Q2
或 O Q4 Q3 Q2
基变量解答值
非基变量解答值
注意:xj 的检验数是当z表示为非基变量的函数时目标函数中xj的系数。基变量的检验数为零。
例1中 z = 2x1+3x2 ,x1 ,x2为非基变量,1=2>0,2=3>0,X(0)不是最优解。
最优性判别定理:
若基可行解对应的检验数 0 ( j=1,2,…,n),则此解是最优解,否则不是最优解。
也可以任取大于0的

在中,令xk>0 ,
而xj =0(m+1  j  n,j  k),要保持xi  0 ( i=1,2,…,m),即
必须
于是,当为换出变量。
若所有则xk 可取无穷大,问题无最优解。
其它变量=0
无界