运筹学单纯形法

3单纯形法的基本原理,3.1两个概念（1）凸集：对于集合C中任意两点连线上的点，若也在C内，则称C为凸集。,或者，任给X1C，X2C，X=X1+(1-)X2C(01)，则C为凸集。,凸集,非凸集,（2）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。,或：设C为凸集，对于XC，不存在任何X1C，X2C，且X1X2，使得X=X1+(1-)X2C，(01)，则X为凸集顶点。,X,X,X,X,X,定理1：若线性LP模型存在可行解，则可行域为凸集。,证明：设maxz=CXst.AX=bX0,并设其可行域为C，若X1、X2为其可行解，且X1X2，则X1C，X2C，即AX1=b，AX2=b，X10，X20，,又X为X1、X2连线上一点，即X=X1+(1-)X2C，(01)，AX=AX1+(1-)AX2=b+(1-)b=b,(01)，且X0，XC，C为凸集。,3.2三个基本定理,引理：线性规划问题的可行解X=(x1,x2,xn)T为基本可行解的充要条件是X的正分量所对应的系数列向量线性独立。,证：（1）必要性：X基本可行解X的正分量所对应的系数列向量线性独立可设X=(x1,x2,xk,0,0,0)T，若X为基本可行解，显然，由基本可行解定义可知x1,x2,xk所对应的系数列向量P1,P2,Pk应该线性独立。,（2）充分性：X的正分量所对应的系数列向量线性独立X为基本可行解若A的秩为m，则X的正分量的个数km；当k=m时，则x1,x2,xk的系数列向量P1,P2,Pk恰好构成基，X为基本可行解。当km时，则必定可再找出m-k个列向量与P1,P2,Pk一起构成基，X为基本可行解。,证：用反证法X非基本可行解X非凸集顶点（1）必要性：X非基本可行解X非凸集顶点不失一般性，设X=(x1,x2,xm,0,0,0)T，为非基本可行解，X为可行解，,pjxj=b，,j=1,n,即pjxj=b(1),j=1,m,又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+(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取充分小,使得xjj0，则X1、X2均为可行解，但X=0.5X1+(1-0.5)X2，X是X1、X2连线上的点，X非凸集顶点。,（2）充分性：X非凸集顶点X非基本可行解,设X=(x1,x2,xr,0,0,0)T为非凸集顶点，则必存在Y、Z两点，使得,X=Y+(1-)Z，(01)，且Y、Z为可行解或者xj=yj+(1-)zj(00，当xj=0，必有yj=zj=0,pjyj=,j=1,n,pjyj=b(1),j=1,r,pjzj=,j=1,n,pjzj=b(2),j=1,r,(yj-zj)pj=0,j=1,r,(1)-(2),得,即,(y1-z1)P1+(y2-z2)P2+(yr-zr)Pr=0,Y、Z为不同两点，yj-zj不全为0，P1,P2,Pr线性相关，X非基本可行解。,3,4,O,(3,3),C(4,2),6,6,2X1+2X2+X3=12,4X2+X5=12,4X1+X4=16,XA=(0,3,6,16,0)T,XO=(0,0,12,16,12)T,XB=(3,3,0,4,0)T,XC=(4,2,0,0,4)T,XD=(4,0,4,0,12)T,A,D,B,X1,X2,定理3：若线性规划问题有最优解必在某个基本可行解处达到。,单纯形法的计算步骤：,初始基本可行解,新的基本可行解,最优否？,STOP,Y,N,问题：,（1）如何获得一个初始基本可行解,（2）如何判断当前的基本可行解是否为最优或问题无界,（3）若当前解不是最优，如何去寻找改善的基本可行解,3.3确定初始基可行解,考虑标准型线性规划问题：,设给定线性规划问题：,(1),因此约束方程组的系数矩阵为：,由于该矩阵含有一个单位子矩阵，因此，这个单位阵做基，就可以求出一个基可行解：,其标准形为：,(2)化标准形之前有大于等于的不等式左边-剩余变量+人工变量=,(3)化标准形之前已经是等式左边+人工变量=,3.4最优解的判别,将,代入目标函数,定理1(最优解判别定理):对于标准线性规划问题,若某个基本可行解对应的检验向量,则该基本可行解为最优解.,定理2(无穷多最优解判别定理):对于标准线性规划问题,若某个基本可行解对应的检验向量,并且其中存在一个非基变量的检验,数等于0，则该问题有无穷多最优解。,确定一个基本可行解，并判断是否为最优解。,解：,（1）确定初始基本可行解,（2）检验,3.5基本可行解的改进,具体做法：,（1）在检验数为正的非基变量中确定一个作为换入变量，即让它成为基变量；,（2）从基变量中确定一个作为换出变量，即让它成为非基变量；,（3）利用初等行变换，用换出变量的列向量去替换换入变量的列向量；,换入变量的确定最大增加原则,换出变量的确定最小比原则,不妨设x中的前m个分量为基变量,定理（无界判别定理）,解：,（1）确定初始基本可行解,（2）检验,（3）改进,a.选取换入变量,b.选取换出变量,c.改进基本可行解,（2）检验,（3）改进,a.选取换入变量,b.选取换出变量,c.改进基本可行解,（2）检验,3.5最优解的判别,依题义,z0=cjxj0=cixi0,i=1,m,j=1,n,z1=cjxj1=ci(xi0-aij)+cj,i=1,m,j=1,n,=cixi0+(cj-ciaij)=z0+j,i=1,m,i=1,m,因0，所以有如下结论：,(1)对所有j，当j0，有z1z0，即z0为最优值，X0为最优解(2)对所有j，当j0，但存在某个非基变量k=0，则对此Pk作为新基向量得出的解X1，应有z1=z0，故z1也为最优值，从而X1为最优解，且为基本可行解，X0、X1连线上所有的点均为最优解，因此该线性规划模型具有无穷多解；(3)若存在某个j0，对应aij0，则因当时，有z1，该线性规划模型具有无界解。,4表格单纯形法,第一步：列初始单纯形表,1.表中第一行为价值系数行（由已知可得）,2.表中最后一行为检验数行（由价值系数行求得）,第二步：进行最优性检验,(a)如果表中，所有检验数，则表中的基可行解就是问题的最优解，计算到此为止。,第三步：转换到新的基可行解，构造新单纯形表,1.确定换入变量,2.确定换出变量,3.求新的基可行解,用初等行变换将主元素划为1，K列其他元素划为0（包括检验数行），得到新的基本可行解，转到第二步。,例用单纯形法求解线性规划问题,解：将原线性规划问题化为标准型,列出初始单纯形表,1.确定换入变量,2.确定换出变量,3.作新单纯形表,由于上表中所有检验数都小于等于零，因此已经得到最优解，最优解为：,代入目标函数得最优值：,当计算检验数有相同值的时候，可从中任选一个变量作为换入变量。,当计算值出现相同时，也可以从中任选一个作为换出变量,注意：,单纯形法小结,对给定的线性规划问题应首先化为标准形式；选取或构造一个单位矩阵作为基；求出初始可行解并列出初始单纯形表；计算检验数，判断是否最优解；寻找换入及换出变量，构造新的单纯形表；求出最优解。,5单纯形法的进一步讨论,考察如下线性规划问题：,化标准形为：,它的系数矩阵是：,由于系数矩阵中存在单位阵，很容易找到初始可行基。但存在着不同的情况，考察下面的线性规划问题：,化为标准型：,例6,该问题的系数矩阵为：,这个矩阵中不含有单位矩阵，因此很难找到初始基。,对于这种线性规划问题的系数矩阵不含有单位矩阵的情况，我们往往采用添加人工变量的方法，来构造一个单位矩阵。这样的方法就是人工变量法。,为了构造出单位矩阵，在系数矩阵中添加两列单位列向量，系数矩阵变为：,线性规划问题的约束条件就变为：,因为、是人为添加的，因此其对应的变量、称为人工变量。,加入人工变量之后的问题已经有了初始基本可行解，可以利用单纯形法求解，但新问题与原问题并不等价。如果经过迭代后，人工变量全部变为非基变量，则原问题的约束条件被恢复，同时得到原问题的一个基本可行解。,因此，人工变量法的关键是将人工变量变为非基变量。,目标函数中赋予人工变量一个绝对值很大的负系数，用“M”来表示，这样，只要人工变量取值不为零，则目标函数就不能达到极大化。,目标函数变为：,添加M来处理人工变量的方法，称为大M法,一大M法,求解过程：,因此最优解为：,例求解线性规划问题,解：将其化为标准形：,该问题单纯形法求解如下：,当所有时，人工变量仍然留在基变量中，而且不为零，故问题无可行解。,二、两阶段法,第一阶段：建立辅助线性规划问题,原问题：,辅助问题：,第二阶段：在第一阶段求得可行解的基础上，继续迭代寻找原问题的最优解,（1）将价值系数行替换为原来的价值系数，并重新计算检验数,（2）舍去人工变量,例：minz=2x1+3x2maxz=-2x1-3x2+0 x3s.tx1+x23标准化s.tx1+x2-x3=3x1+2x2=4x1+2x2=4x10,x20 xj0,(j=1,2,3,4),minw=x4+x5s.tx1+x2-x3+x4=3x1+2x2+x5=4xj0,(j=1,2,3,4,5),第一阶段：先求解一个目标函数中只含有人工变量的线性规划问题。,用单纯形法求解，若最优值为0，表明该模型有可行解，则可进入第二阶段，求原模型最优解。,Cj,x1,x2,x3,x4,XB,b,CB,11-11012001,000-1-1,34,x4x5,-1-1,cj-zj,2,3,-1,0,3/1=3