6.4单纯形法理论基础 定理设X=(x1…xnm)∈S.X是S的顶点 的充要条件是X的非0元对应的A的列向量 线性无关 证用反证法 先证必要性.设X是S的顶点,不妨设X= XIX 0…0),x 是Ⅹ的非0 元,A1,A2,…,A是与这些非0元对应的A 的列向量.并设A1,A2,…,A线性相关 于是存在一组不全为0的常数α1,2,…, 4,使得
６．4 单纯形法理论基础 定理 设X＝( x1···xn+m )∈S．X是S的顶点 的充要条件是X的非0元对应的A的列向量 线性无关． 证 用反证法． 先证必要性．设X是S的顶点，不妨设X＝ ( x1 x2 ··· xk 0 ··· 0 )，x1 , x2 , ··· ,xk是X的非0 元，A1 , A2 , ··· , Ak是与这些非0元对应的A 的列向量．并设A1 , A2 , ··· , Ak线性相关． 于是存在一组不全为0的常数α1 , α2 , ··· , αk，使得 T T
6.4单纯形法理论基础 aA+OA +A=0 令Z=(a1α2…α130…0).存在常数e>0, m+n-k个 只要ε足够小,就有X±ε≥>0,并且 A(X±EZ)=b.但是 X-2(X+EZ)+X-&Z), 与X是S的顶点相矛盾.因而,A1,A2,…, A线性无关
６．4 单纯形法理论基础 1A1+ 2A2+ … + kAk ＝0． 令Z＝( 1 2 ··· k 0 ··· 0 )．存在常数ε>0， 只要ε足够小，就有X± ε≥0，并且 A(X± εZ )＝b．但是 X＝－( X + εZ ) + －( X－ εZ )， 与X是S的顶点相矛盾．因而，A1 , A2 , … , Ak线性无关． m+ n －k个 1 2 1 2
6.4单纯形法理论基础 再证充分性 设X=(x1x2…x0…0)∈S,x1,x2,…, m+n-k个 xk>0,A1,A2,…,A是这些非0元对应的 A的列向量,A1,A2,…,A线性无关,但 X不是S的顶点,于是存在X1,X2∈S, 1≠X2,t∈(0,1),X=tx1+(1-t)x2 因为Ⅹ的后n+m一k个元都为0,所以X1,X2 的后n+m一k个元也都为0.因而可设:
６．4 单纯形法理论基础 再证充分性． 设X＝ ( x1 x2 ··· xk 0 ··· 0 )∈S，x1 , x2 , ··· , xk > 0，A1，A2，… ，Ak是这些非0元对应的 m+ n －k个 A的列向量，A1，A2，… ，Ak线性无关，但 X不是S的顶点，于是存在X1，X2∈S， X1≠X2，t∈( 0 , 1 )，X＝tX1+ ( 1－t )X2． 因为X的后n+ m －k个元都为0，所以X1，X2 的后n+ m－k个元也都为0．因而可设： T
6.4单纯形法理论基础 1)0…0 X2=(X2)x2)…x2)0…0) 令Y=X+(X1-X2)=(y1y2…y0…0) 因为X1≠X2,所以Y≠X.因A(Y-X)=0, 所以有 (y1-x1)A1+(y2-x2)A2+…+(yk-x)Ak=0 这与A1,A2,…,A线性无关相矛盾.因 而Ⅹ是S的顶点
６．4 单纯形法理论基础 X1 ＝( x1 x2 ··· xk 0 ··· 0 ) X2 ＝( x1 x2 ··· xk 0 ··· 0 ) ( 1 ) ( 1 ) ( 1 ) ( 2 ) ( 2 ) ( 2 ) T T 令Y＝X+ ( X1－X2 ) = ( y1 y2 ··· yk 0 ··· 0 )． 因为X1≠X2，所以Y≠X．因A(Y－X)＝0， 所以有 ( y1－x1 )A1 + ( y2－x2 )A2 +···+ ( yk－xk )Ak ＝0 这与A1，A2， ··· ，Ak线性无关相矛盾．因 而X是S的顶点． T
6.4单纯形法理论基础 定义如果b可以表示为A的少于m个列向量 的线性组合,称为退化情况.否则称为非退 化情况 推论设A=(an1)m×mm的秩为m,在非退 化情况下,则Ⅹ是S的顶点的充要条件是Ⅹ的 非0元为m 证必要性:设X是S的顶点 由非退化假设,Ⅹ的非0元不少于m个.根据 定理,Ⅹ的非0元对应的A的列向量线性无关
６．4 单纯形法理论基础 定义 如果b可以表示为A的少于m个列向量 的线性组合，称为退化情况．否则称为非退 化情况． 推论 设A＝( aij )m×( n+ m )的秩为m，在非退 化情况下，则X是S的顶点的充要条件是X的 非0元为m个． 证 必要性：设X是S的顶点． 由非退化假设，X的非0元不少于m个．根据 定理，X的非0元对应的A的列向量线性无关