章线性规划及单纯形法.pptVIP

第三节 单纯形法原理 一、线性规划规划问题的解的概念 （一）线性规划问题标准型 （1）可行解：满足上述约束条件(1.7),(1.8)的解X=(x1,…,xn)T，称为线性规划问题的可行解。全部可行解的集合称为可行域。 （2）最优解：使目标函数(1.6)达到最大值的可行解称为最优解。 （3）基：设A为约束方程组(1.7)的m×n阶系数矩阵，（设nm），其秩为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）可行基：对应基可行解的基称为可行基。 线性规划的基矩阵、基变量、非基变量 例：设有一标准的线性规划问题的约束条件如下： 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 若线性规划问题存在可行解，则问题的可行域是凸集。 将（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)为相应的基可行解。 当Km时，则一定可以从其余列向量中找出(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)为目标函数的最大值,故有 四、单纯形法迭代原理 1 确定初始基可行解 2 从一个基可行解转换为相邻的基可行解。 定