运筹学单纯形法

《运筹学单纯形法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§3单纯形法的基本原理3.1两个概念（1）凸集：对于集合C中任意两点连线上的点，若也在C内，则称C为凸集。或者，任给X1C，X2C，X=X1+(1-)X2C(0<<1)，则C为凸集。凸集非凸集（2）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。或：设C为凸集，对于XC，不存在任何X1C，X2C，且X1≠X2，使得X=X1+(1-)X2C，(0<<1)，则X为凸集顶点。XXXXX定理1：若线性LP模型存在可行解，则可行域为凸集。证明：设maxz=CXst.AX=bX0并设其可行域为C，若X1、X2为其可行解，且

2、X1≠X2，则X1C，X2C，即AX1=b，AX2=b，X10，X20，又X为X1、X2连线上一点，即X=X1+(1-)X2C，(0<<1)，∴AX=AX1+(1-)AX2=b+(1-)b=b,(0<<1)，且X0，∴XC，∴C为凸集。3.2三个基本定理引理：线性规划问题的可行解X=(x1,x2,······,xn)T为基本可行解的充要条件是X的正分量所对应的系数列向量线性独立。证：（1）必要性：X基本可行解X的正分量所对应的系数列向量线性独立可设X=(x1,x2,······,xk,0,0,······,0)

3、T，若X为基本可行解，显然，由基本可行解定义可知x1,x2,······,xk所对应的系数列向量P1,P2,······,Pk应该线性独立。（2）充分性：X的正分量所对应的系数列向量线性独立X为基本可行解若A的秩为m，则X的正分量的个数km；当k=m时，则x1,x2,······,xk的系数列向量P1,P2,······,Pk恰好构成基，∴X为基本可行解。当k

4、失一般性，设X=(x1,x2,······,xm,0,0,······,0)T，为非基本可行解，∵X为可行解，∴pjxj=b，j=1n即pjxj=b······(1)j=1m又X是非基本可行解，∴P1,P2,······,Pm线性相关，即有1P1+2P2+······+mPm=0，其中1，2，······，m不全为0，两端同乘≠0，得1P1+2P2+······+mPm=0，······（2）定理2：线性规划模型的基本可行解对应其可行域的顶点。由(1)+(2)得(x1+1)P1+(x2+2)P2+····

5、··+(xm+m)Pm=b由(1)-(2)得(x1-1)P1+(x2-2)P2+······+(xm-m)Pm=b令X1=(x1+1，x2+2，······，xm+m，0，·····，0)TX2=(x1-1，x2-2，······，xm-m，0，·····，0)T取充分小,使得xjj0，则X1、X2均为可行解，但X=0.5X1+(1-0.5)X2，∴X是X1、X2连线上的点，∴X非凸集顶点。（2）充分性：X非凸集顶点X非基本可行解设X=(x1,x2,······,xr,0,0,······,

6、0)T为非凸集顶点，则必存在Y、Z两点，使得X=Y+(1-)Z，(0<<1)，且Y、Z为可行解或者xj=yj+(1-)zj(0<<1)，（j=1,2,······,n)，yj0，zj0∵>0,1->0，当xj=0，必有yj=zj=0∴pjyj=j=1npjyj=b······(1)j=1rpjzj=j=1npjzj=b······(2)j=1r(yj-zj)pj=0j=1r,(1)-(2),得即(y1-z1)P1+(y2-z2)P2+······+(yr-zr)Pr=0∵Y、Z为不同两点，∴yj-zj不全为0，∴

7、P1,P2,······,Pr线性相关，∴X非基本可行解。34O(3,3)C(4,2)662X1+2X2+X3=124X2+X5=124X1+X4=16XA=(0,3,6,16,0)TXO=(0,0,12,16,12)TXB=(3,3,0,4,0)TXC=(4,2,0,0,4)TXD=(4,0,4,0,12)TADBX1X2定理3：若线性规划问题有最优解必在某个基本可行解处达到。单纯形法的计算步骤：初始基本可行解新的基本可行解最优否？STOPYN问题：（1）如何获得一个初始基本可行解（2）如何判断当前的基本可行解是否为最优或问题无界（3）若当

8、前解不是最优，如何去寻找改善的基本可行解3.3确定初始基可行解考虑标准型线性规划问题：设给定线性规划问题：(1)因此约束方程组的系数矩阵为：由于该矩阵含有一个单位子