2.3单纯形法.ppt

回顾：LP问题的基本概念
设 r(A) = m, 且B是A的m 阶非奇异的子矩阵（det(B)  0), 则称矩阵B为线性规划问题的一个基(阵)。
(1) 基(阵)
( mn) r(A)=m，至少有一个m阶子式不为0。
a11 … a1m a1m+1 … a1n
a21 … a2m a2m+1 … a2n
………… ……………
am1 … amm amm+1 … amn
A1 … Am Am+1 … An
B
N
(2) 基变量、非基变量
设 A=( A1, A2, ……, An )，
若B=( Ai1, Ai2, ……, Aim )为 A的基阵，
则称x1, x2, ……, xn 中的xi1, xi2, ……, xim 为对应于B的基变量，其余的称为非基变量。
A= ( A1 … Am Am+1 … An ) = ( B, N )
基向量 非基向量
X= ( x1 … xm xm+1 … xn )T = ( XB XN)T
基变量 非基变量
(3) 基解
令非基变量取值为零,
则基变量的取值可从 AX=b 中唯一解得。
如此的一组解称为对应于B的一个基解。
(4) 基可行解
若X0是一个基解，而且又是一个可行解，
则称X0是一个基可行解。
基可行解对应于可行域的顶点。
(5) 退化的基可行解
问题: 在基可行解中,非基变量的取值必定为零, 基变量的取值是否必定大于零?
若X0是一个基可行解, 其基变量的取值全部大于零，则称X0是非退化的; 否则称为退化的。
解的关系
可行解
基解
基可行解
最优解
四、单纯形法
例 max Z = 2x1+3x2
. x1+2x2  4
4x1  8
4x2  6
x1, x2  0

划为标准型：
min Z = -2x1-3x2 -0x3 -0x4-0x5
. x1+2x2 +x3 = 4
4x1 +x4 = 8
4x2 +x5 = 6
x1, x2, x3, x4, x5  0