《运筹》教学课件- 线性规划求解

2006/08,-第1章线性规划-,-1-,线性规划的求解LinearProgramming,二维线性规划的图解法,2.线性规划的单纯形法,2006/08,-第1章线性规划-,-2-,1.1.4线性规划问题解的有关概念,设模型nmaxz=cjxjj=1ns.t.aijxj=bi（i=1,2,m)j=1xj0（j=1,2,n),（1）可行解：满足所有约束方程和变量符号限制条件的一组变量的取值。,（2）可行域：全部可行解的集合称为可行域。,（3）最优解：使目标函数达到最优值的可行解。,2006/08,-第1章线性规划-,-3-,（4）基：设A为线性规划模型约束条件系数矩阵（mn，mn），而B为其mm子矩阵，若|B|0，则称B为该线性规划模型的一个基。,（5）基变量：基中每个向量所对应的变量称为基变量。,（6）非基变量：模型中基变量之外的变量称为非基变量。,（7）基解（基解）：令模型中所有非基变量X非基=0后，由模型约束方程组naijxj=bi(i=1,2,m)得到的一组解。j=1,（8）基本可行解（基可行解）：在基解中，同时又是可行解的解称为基可行解。,（9）可行基：对应于基可行解的基称为可行基。,2006/08,-第1章线性规划-,-4-,Maxz=2x1+3x2st.x1+x23x1+2x24x1,x20,Maxz=2x1+3x2+0 x3+0 x4st.x1+x2+x3=3x1+2x2+x4=4x1,x2,x3,x40,A=,x1x2x3x4,11101201,可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T等。,设,B=,1001,，令,，则,|B|=10,令x1=x2=0，则x3=3,x4=4，X=(0,0,3,4)T,例：,x3x4,基变量,令,B=,1110,x1x3,，则,令x2=x4=0，则x3=-1,x1=4，X=(4,0,-1,0)T,|B|=-10,非基本可行解,基本可行解,标准化,2006/08,-第1章线性规划-,-5-,复习思考题：1.可行解和可行域有怎样的关系？2.一个标准化LP模型，最多可有多少个基？3.基解是如何定义的？怎样才能得到基解？4.可行解、基解、基可行解三者之间有什么关系？在LP模型中是否一定存在？5.什么是可行基？,2006/08,-第1章线性规划-,-6-,1.2线性规划问题的图解方法,*利用作图方法求解。例：maxz=2x1+3x2s.t2x1+2x212-x1+2x28-4x116-4x212-x10,x20,2006/08,-第1章线性规划-,-7-,x1,x2,2,2,4,6,8,4,6,0,Z=6,Z=0,(4,2),Zmax,2006/08,-第1章线性规划-,-8-,A,A,B,唯一解,无穷多解,无界解,无可行解,2006/08,-第1章线性规划-,-9-,步骤：（1）作平面直角坐标系，标上刻度；（2）做出约束方程所在直线，确定可行域；（3）做出一条目标函数等值线，判定优化方向；（4）沿优化方向移动，确定与可行域相切的点，确定最优解，并计算最优值。,讨论一：模型求解时，可得到如下几种解的状况：（1）唯一最优解：只有一点为最优解点，简称唯一解；（2）无穷多最优解：有许多点为最优解点，简称无穷多解；（3）无界最优解：最优解取值无界，简称无界解；（4）无可行解：无可行域，模型约束条件矛盾。,讨论二：LP模型求解思路：（1）若LP模型可行域存在，则为一凸形集合；（2）若LP模型最优解存在，则其应在其可行域顶点上找到；（3）顶点与基本解、基本可行解的关系：,2006/08,-第1章线性规划-,-10-,复习思考题：1.LP模型的可行域是否一定存在?2.图解中如何去判断模型有唯一解、无穷多解、无界解和无可行解？3.LP模型的可行域的顶点与什么解具有对应关系？4.你认为把所有的顶点都找出来，再通过比较目标函数值大小的方式找出最优解，是否是最好的算法？为什么？,2006/08,-第1章线性规划-,-11-,1.3单纯形法的基本原理（SimplexMethod）,1.3.1两个概念：（1）凸集：对于集合C中任意两点连线上的点，若也在C内，则称C为凸集。,或者，任给X1C，X2C，X=X1+(1-)X2C(01)，则C为凸集。,凸集,非凸集,2006/08,-第1章线性规划-,-12-,（2）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。,或者，设C为凸集，对于XC，不存在任何X1C，X2C，且X1X2，使得X=X1+(1-)X2C，(01)，则X为凸集顶点。,X,X,X,X,X,2006/08,-第1章线性规划-,-13-,定理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为凸集。,1.3.2三个基本定理：,2006/08,-第1章线性规划-,-14-,引理：线性规划问题的可行解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为基本可行解。,2006/08,-第1章线性规划-,-15-,证：用反证法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：线性规划模型的基本可行解对应其可行域的顶点。,2006/08,-第1章线性规划-,-16-,由(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非凸集顶点。,2006/08,-第1章线性规划-,-17-,（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,2006/08,-第1章线性规划-,-18-,Y、Z为不同两点，yj-zj不全为0，P1,P2,Pr线性相关，X非基本可行解。,2006/08,-第1章线性规划-,-19-,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,2006/08,-第1章线性规划-,-20-,z1=CX1=CX0-C=zmax-C，z2=CX2=CX0+C=zmax+Cz0=zmaxz1，z0=zmaxz2，z1=z2=z0，即X1、X2也为最优解，若X1、X2仍不是顶点，可如此递推，直至找出一个顶点为最优解。从而，必然会找到一个基本可行解为最优解。,定理3：若线性规划模型有最优解，则一定存在一个基本可行解为最优解。,证：设X0=(x10,x20,xn0)T是线性规划模型的一个最优解，z0=zmax=CX0若X0非基本可行解，即非顶点，只要取充分小，则必能找出X1=X0-0，X2=X0+0，即X1、X2为可行解，,2006/08,-第1章线性规划-,-21-,单纯形法的计算步骤：,初始基本可行解,新的基本可行解,最优否？,STOP,Y,N,2006/08,-第1章线性规划-,-22-,1初始基本可行解的确定：,设模型nmaxz=cjxjj=1ns.t.aijxjbi（i=1,2,m)j=1xj0（j=1,2,n),nmmaxz=cjxj+0xsij=1I=1ns.t.aijxj+xsi=bi（i=1,2,m)j=1xj0，xsi0（j=1,2,n;i=1,2,m),化标准形,初始基本可行解X=(0,0,0,b1,b2,bm)T，,n个0,2006/08,-第1章线性规划-,-23-,2从一个基本可行解向另一个基本可行解转换,不失一般性，设基本可行解X0=(x10,x20,xm0,0,0)T，前m个分量为正值，秩为m，其系数矩阵为,P1P2PmPm+1PjPnb100a1,m+1a1ja1nb1010a2,m+1a2ja2nb2001am,m+1amjamnbm,pjxj0=,j=1,n,pixi0=b(1),i=1,m,2006/08,-第1章线性规划-,-24-,又P1P2Pm为一个基，任意一个非基向量Pj可以以该组向量线性组合表示，即Pj=a1jP1+a2jP2+amjPm，即Pj=aijpi，移项，两端同乘0，有(Pj-aijpi)=0(2),i=1,m,i=1,m,(1)+(2)：(xi0-aij)Pi+Pj=b，取充分小，使所有xi0-aij0，从而,i=1,m,X1=(x10-a1j,x20-a2j,xm0-amj,0,0)T,也是可行解。,当取=minaij0=，则X1的前m个分量至少有一个xL1为0。,xi0,aij,alj,xL0,i,P1,P2,PL-1,PL+1,Pm,Pj线性无关。,2006/08,-第1章线性规划-,-25-,X1也为基本可行解。,3.最优解的判别,依题义,z0=cjxj0=cixi0,i=1,m,j=1,n,z1=cjxj1=ci(xi0-aij)+cj,i=1,m,j=1,n,=ci(xi0-aij)+(cj-ciaij)=z0+j,i=1,m,i=1,m,2006/08,-第1章线性规划-,-26-,单纯形法的思想,如何得到初始顶点千里之行,始于足下如何从一个顶点到另外一个顶点欲穷千里目，更上一层楼如何得到最优解会当临绝顶，一览众山小,2006/08,-第1章线性规划-,-27-,因0，所以有如下结论：,(1)对所有j，当j0，有z1z0，即z0为最优值，X0为最优解；(2)对所有j，当j0，但存在某个非基变量k=0，则对此Pk作为新基向量得出的解X1，应有z1=z0，故z1也为最优值，从而X1为最优解，且为基本可行解，X0、X1连线上所有的点均为最优解，因此该线性规划模型具有无穷多解；(3)若存在某个j0，但对应aij0，则因当时，有z1，该线性规划模型具有无界解。,2006/08,-第1章线性规划-,-28-,1.4单纯形法的计算及示例,1.4.1单纯形法几何解释-顶点寻优例：maxz=2x1+3x2maxz=2x1+3x2+0 x3+0 x4s.tx1+x23标准化s.tx1+x2+x3=3x1+2x24x1+2x2+x4=4x10,x20 xj0,(j=1,2,3,4),（1）初始基本可行解的选择：-坐标原点处,令x1=x2=0,由x1+x2+x3=3x1+2x2+x4=4,（2）是否为最优解的判定:-计算检验数,若x11,则x31,x41,1=2-（01+01）=2j=z=cj-zj=cj-ciaij，称j为检验数。,x3=3-(x1+x2)x4=4-(x1+2x2),解得X=(0,0,3,4)T,2006/08,-第1章线性规划-,-29-,若x21,则x31,x42,2=3-(01+02)=3,*当所有检验数均有j0时，则为最优解。*,（3）找新的顶点（基本可行解）：直观看，x21,则z3，应找A点，即增加x2。,x2可增加多少？需要保证x3=3-(x1+x2)0 x4=4-(x1+2x2)0，,x2=min（3/1，4/2），从而x3=1-(x1/2-x4/2）x2=2-(x1/2+x4/2),令x1=x4=0，则新的基本可行解为X=(0，2，1，0)T重复上述过程，直至所有检验数j0。,2006/08,-第1章线性规划-,-30-,继续迭代：,找新的顶点（基本可行解）：若x11,则z1/2，应找B点，即增加x1。x1可增加多少？需要保证x3=1-(x1/2-x4/2)0 x2=2-(x1/2+x4/2)0，x1=min（2，4），从而x1=2-(2x3-x4)x2=1-(-x3+x4),则新的基本可行解为X=(2，1，0，0)T,若x11,则x31/2,x21/2,1=2-（01/2+31/2）=1/2,若x41,则x3-1/2,x21/2,4=0-（0(-1/2)+31/2）=-3/2,3=-1,4=-1,zmax=7,2006/08,-第1章线性规划-,-31-,O,C,A,B,X1,X2,(0,2),(3,0),(2,1),3,4,2006/08,-第1章线性规划-,-32-,Cj,x1,x2,x3,x4,XB,b,CB,11101201,2300,34,x3x4,00,cj-zj,2,3,0,0,3/1=3,4/2=2,1/201-1/21/2101/2,x3x2,12,cj-zj,1/200-3/2,03,24,102-101-11,x1x2,21,cj-zj,00-1-1,23,1.4.2单纯形法计算：,i,2006/08,-第1章线性规划-,-33-,单纯形法计算过程总结：,（1）化标准形，列初始单纯形表；,（2）计算检验数：j=z=cj-zj=cj-ciaij,（3）最优性判断：当所有检验数均有j0时，则为最优解。否则迭代求新的基本可行解。,（4）迭代：入基变量：取maxj0=kxk出基变量：取mini=bi/aikaik0=lx(l)主元素：alk新单纯表：pk=单位向量,注：当所有检验数j0时，若存在非基变量检验数为0时，则有无穷多解，否则只有唯一最优解。,i=1,m,2006/08,-第1章线性规划-,-34-,例：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),maxz=-2x1-3x2+0 x3-Mx4-Mx5s.tx1+x2-x3+x4=3x1+2x2+x5=4xj0,(j=1,2,3,4,5),引进人工变量，及M非常大正系数，模型转变为,这种处理方法称为大M法，以下则可完全按单纯形法求解。,1大M法,1.5单纯形法进一步讨论,2006/08,-第1章线性规划-,-35-,Cj,x1,x2,x3,x4,XB,b,CB,11-11012001,-2-30-M-M,34,x4x5,-M-M,cj-zj,-2+2M,-3+3M,-M,0,3/1=3,4/2=2,1/20-11-1/21/21001/2,x4x2,12,cj-zj,-1/2+M/20-M03/2-M/2,-M-3,24,10-22-1011-11,x1x2,21,cj-zj,00-11-M1-M,-2-3,i,x5,0,2006/08,-第1章线性规划-,-36-,说明：当所有j0，但存在人工变量x人=0，则可以判定该模型有无可行解。,采用大M法求解线性规划模型时，如果模型中各个系数与M的值非常接近时，若手工计算时，不会出现任何问题。如果利用计算机程序求解，则大M表现为一个较大的数字，由于综合计算的影响，导致检验数出现符号误差，引起判断错误，从而使大M方法失效。在这种情况下，可采用下面的两阶段法进行计算。,2006/08,-第1章线性规划-,-37-,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),obj:maxz=-x4-x5s.tx1+x2-x3+x4=3x1+2x2+x5=4xj0,(j=1,2,3,4,5),(1)第一阶段，构造判断是否存在可行解的模型：,用单纯形法求解，若zmax=0，表明该模型有可行解，则可进入第二阶段，求原模型最优解。,2006/08,-第1章线性规划-,-38-,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,4/2=2,1/20-11-1/21/21001/2,x4x2,12,cj-zj,1/20-101,-10,24,10-22-1011-11,x1x2,21,cj-zj,000-1-1,00,i,x5,0,2006/08,-第1章线性规划-,-39-,(2)第二阶段，将原目标函数引入最终单纯形表，继续迭代：maxz=-2x1-3x2+0 x3,Cj,x1,x2,x3,XB,b,CB,11000-1,-2-30,21,x1x2,-2-3,cj-zj,0,0,-1,2006/08,-第1章线性规划-,-40-,1.4.3程序求解,（1）用LINDO软件求解,（2）用EXCEL工具求解,使用EXCEL中数据处理工具规划求解。,2006/08,-第1章线性规划-,-41-,1.6改进单纯形法,单纯形法迭代过程可用矩阵变换描述如下：设,maxz=CXstAXbX0,分解,maxz=CBXB+CNXN+0XSstBXB+NXN+IXS=bXB,XN,XS0,约束方程两端同乘B-1，则可得如下表达式：,式中，B最终表中基对应的矩阵，N初始表与最终表中均为非基对应的矩阵，I单位矩阵,A=BN,maxz=CBXB+CNXN+0XSstB-1BXB+B-1NXN+B-1XS=B-1bXB,XN,XS0,对应最终单纯形表的模型,2006/08,-第1章线性规划-,-42-,用单纯形表表示如下：,XS=b,BNI,XB=bINB-1,初始表XBXNXS,cj-zj0,0NS,最终表XBXNXS,cj-zjBN0,0,表中，b=B-1bN=B-1N或者Pj=B-1PjN=CN-CBB-1N或者j=Cj-CBB-1PjS=-CBB-1,2006/08,-第1章线性规划-,-43-,化标准形：B-1new=I，XB=b，求检验数：N=CN-CBB-1newN，S=-CBB-1new最优性判别：所有0，X人0，无可行解；所有0，X人=0，存在N=0，无穷多解；所有0，X人=0，不存在N=0，唯一解；否则(存在0)，转，取maxxk，为换入变量，计算Pk=B-1newPk，若Pk0无界解,否则，计算i=bi/aik|aik0，取minxL为换出变量，令,改进单纯形法计算步骤：,2006/08,-第1章线性规划-,-44-,D=,1-a1k/aLk001/aLk00-amk/aLk1,xL,计算B-1new=DB-1old，b=B-1newb,转。,注：D矩阵为单位矩阵中出基变量所在单位向量以上述列向量代换。,实例演算如下：,2006/08,-第1章线性规划-,-45-,例：maxz=2x1+3x2maxz=2x1+3x2+0 x3+0 x4s.tx1+x23标准化s.tx1+x2+x3=3x1+2x24x1+2x2+x4=4x10,x20 xj0,(j=1,2,3,4),x1x2x3x4