第1章 线性规划及单纯形法(2).ppt

第三节单纯形法原理（1）可行解：满足上述约束条件(1.7),(1.8)的解X=(x1,…,xn)T，称为线性规划问题的可行解。全部可行解的集合称为可行域。
（2）最优解：使目标函数(1.6)达到最大值的可行解称为最优解。
（3）基：设A为约束方程组(1.7)的m×n阶系数矩阵，（设n>m），其秩为m，B是矩阵A中的一个m×m阶的满秩子矩阵，称B是线性规划问题的一个基。不失一般性，设B中的每一个列向量Pj(j=1,…,m)称为基向量，与基向理Pj对应的变量xj称为基变量。线性规划中除基变量以外的变量称为非基变量。（4）基解：在约束方程组(1.7)中，令所有非基变量为xm+1=xm+2=…=xn=0零，以因为有|B|≠0，根据克莱姆法则，由m个约束方程可解出m个基变量的唯一解XB=(x1,…,xm)T。将这个解加上非基解中变量取0的值有X=（x1,x2,…,xm,0,0,…,0）T，称X为线性规划问题的基解。显然在基解中变量取非零值的个数不大于方程数m，故基解的总数不超过Cnm个。
（5）基可行解：满足变量非负约束条件(1.8)的基解称为基可行解。
（6）可行基：对应基可行解的基称为可行基。可行解线性规划的基矩阵、基变量、非基变量（四）求出下列线性规划问题的所有基解、基可行解基变量x1、x2、x3，非基变量x4、x5、x6基变量x1、x2、x4，非基变量x3、x5、x6基变量x1、x2、x5，非基变量x3、x4、x6基变量x1、x2、x6，非基变量x3、x4、x5基变量x2、x3、x4，非基变量x1、x5、x6基变量x1、x2、x3，非基变量x4、x5、x6基变量x1、x2、x3，非基变量x4、x5、x6例：设有一标准的线性规划问题的约束条件如下：
2x1+x2+x4=7
x2+x3=3
x1,x2,x3,x40
已知下列各点均满足以上的两个方程：
(1)(0,7,-4,0)T,(2)(2,3,0,0)T,(3)(1,0,3,5)T
(4)(2.5,2,1,0)T,(5)(0,3,0,4)T二、凸集及其顶点2顶点
凸集C中满足下述条件的点X称为顶点：如果C中不存在任何两个不同的点X1，X2，使X成为这两个点连线上的一个点。或者这样叙述：对任何X1C，X2C，不存在X=X1+(1-)X2C（01），则称X是凸集C的顶点。三、几个定理的证明将（1.9）代入（1.10）得：引理线性规划问题的可行解X=（x1,x2,…xn)为基可行解的充要条件是X的正分量所对应的系数列向量线性独立的。
证：（1）必要性（结论条件）
由基可行解的定义显然成立。
（2）充分性。（条件结论）若向量P1,P2,…,Pk线性独立，则必有k≤m.
当k=m时，它们恰好构成一个基，从而X=(x1,x2,…,xm,0,0,..,0)为相应的基可行解。
当K<m时，则一定可以从其余列向量中找出(m-k)个与P1,P2,…,Pk构成一个基，其对应的解恰为X，所以根据定义它是基可行解。定理2线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。
证：即要证明X是可行域顶点X是基可行解
反证法，即X不是可行域顶点X不是基可行解
（1）X不是基可行解X不是可行域顶点
不失一般性，设X的前m个分量为正，即：(1.12)式乘上一个不为零的数μ得：
1P1+2P2+…+mPm=0(1.13)
式(1.11)+(1.13)得：
(x1+1)P1+(x2+2)P2+…+(xm+m)Pm=b
式(1.11)-(1.13)得：
(x1-1)P1+(x2-2)P2+…+(xm-m)Pm=b
令：X(1)=[(x1+1),(x2+2),…,(xm+m),0,…,0]
X(2)=[(x1-1),(x2-2),…,(xm-m),0,…,0]
又可以这样来选取，使得对所有i=1,2,…,m有
x110由引X(1)C,X(2)C,又X=X(1)/2+X(2)/2
即X不是可行域的顶点。
（2）X不是可行域顶点X不是基可行解
不失一般性，设X=(x1,x2,…,xr,0,…,0)不是可行域的顶点，因而可以找到可行域内另外两个不同点Y和Z，
有X=Y+(1-)Z(0<<1)，或可写成
xj=yj+(1-)zj(0<<1;j=1,…,n)
因>0,1->0,故当xj=0时,必有yj=zj=0
因有故有定理3若线性规划问题有最优解，一定存在一个基可行解是最优解。
证设X(0)=(x10,x20,…,xn0)是线性规划的一个最优解,因CX(0)为目标函数的最大值,故有四、单纯形法迭代原理2从一个基可行解转换为相邻的基可行解。
定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量