




如果您无法下载资料,请参考说明:
1、部分资料下载需要金币,请确保您的账户上有足够的金币
2、已购买过的文档,再次下载不重复扣费
3、资料包下载后请先用软件解压,在使用对应软件打开
第三节单纯形法原理(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,x40 已知下列各点均满足以上的两个方程: (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成为这两个点连线上的一个点。或者这样叙述:对任何X1C,X2C,不存在X=X1+(1-)X2C(01),则称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有 x110由引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从一个基可行解转换为相邻的基可行解。 定义:两个基可行解称为相邻的,如果它们之间变换且仅变换一个基变量

ys****39
实名认证
内容提供者


最近下载