《线性规划求解》PPT课件.ppt
99/08,-第 1 章 线性规划-,-1-,线性规划的求解Linear Programming,二维线性规划的图解法,2.线性规划的单纯形法,99/08,-第 1 章 线性规划-,-2-,1.1.4线性规划问题解的有关概念,设模型 n max z=cjxj j=1 n s.t.aijxj=bi（i=1,2,m)j=1 xj0（j=1,2,n),（1）可行解：满足所有约束方程和变量符号限制条件的一组变量的取值。,（2）可行域：全部可行解的集合称为可行域。,（3）最优解：使目标函数达到最优值的可行解。,99/08,-第 1 章 线性规划-,-3-,（4）基：设A为线性规划模型约束条件系数矩阵（m n，mn），而B为其mm子矩阵，若|B|0，则称B为该线性规划模型的一个基。,（5）基变量：基中每个向量所对应的变量称为基变量。,（6）非基变量：模型中基变量之外的变量称为非基变量。,（7）基解（基解）：令模型中所有非基变量X非基=0后，由模型约束方程组 n aijxj=bi(i=1,2,m)得到的一组解。j=1,（8）基本可行解（基可行解）：在基解中，同时又是可行解的解称为基可行解。,（9）可行基：对应于基可行解的基称为可行基。,99/08,-第 1 章 线性规划-,-4-,Max z=2x1+3x2 st.x1+x23 x1+2x24 x1,x20,Max z=2x1+3x2+0 x3+0 x4 st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x40,A=,x1 x2 x3 x4,1 1 1 01 2 0 1,可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。,设,B=,1 0 0 1,，令,，则,|B|=10,令 x1=x2=0，则 x3=3,x4=4，X=(0,0,3,4)T,例：,x3 x4,基变量,令,B=,1 1 1 0,x1 x3,，则,令 x2=x4=0，则 x3=-1,x1=4，X=(4,0,-1,0)T,|B|=-10,非基本可行解,基本可行解,标准化,99/08,-第 1 章 线性规划-,-5-,复习思考题：1.可行解和可行域有怎样的关系？2.一个标准化LP模型，最多可有多少个基？3.基解是如何定义的？怎样才能得到基解？4.可行解、基解、基可行解三者之间有什么关系？在LP模型中是否一定存在？5.什么是可行基？,99/08,-第 1 章 线性规划-,-6-,1.2线性规划问题的图解方法,*利用作图方法求解。例：max z=2x1+3x2 s.t 2x1+2x212-x1+2x2 8-4x116-4x2 12-x10,x20,99/08,-第 1 章 线性规划-,-7-,x1,x2,2,2,4,6,8,4,6,0,Z=6,Z=0,(4,2),Zmax,99/08,-第 1 章 线性规划-,-8-,A,A,B,唯一解,无穷多解,无界解,无可行解,99/08,-第 1 章 线性规划-,-9-,步骤：（1）作平面直角坐标系，标上刻度；（2）做出约束方程所在直线，确定可行域；（3）做出一条目标函数等值线，判定优化方向；（4）沿优化方向移动，确定与可行域相切的点，确定最优 解，并计算最优值。,讨论一：模型求解时，可得到如下几种解的状况：（1）唯一最优解：只有一点为最优解点，简称唯一解；（2）无穷多最优解：有许多点为最优解点，简称无穷多解；（3）无界最优解：最优解取值无界，简称无界解；（4）无可行解：无可行域，模型约束条件矛盾。,讨论二：LP模型求解思路：（1）若LP模型可行域存在，则为一凸形集合；（2）若LP模型最优解存在，则其应在其可行域顶点上找到；（3）顶点与基本解、基本可行解的关系：,99/08,-第 1 章 线性规划-,-10-,复习思考题：1.LP模型的可行域是否一定存在?2.图解中如何去判断模型有唯一解、无穷多解、无界解和无可行解？3.LP模型的可行域的顶点与什么解具有对应关系？4.你认为把所有的顶点都找出来，再通过比较目标函数值大小的方式找出最优解，是否是最好的算法？为什么？,99/08,-第 1 章 线性规划-,-11-,1.3单纯形法的基本原理（Simplex Method）,两个概念：（1）凸集：对于集合C中任意两点连线上的点，若也在C内，则称 C为凸集。,或者，任给X1C，X2 C，X=X1+(1-)X2 C(01)，则C为凸集。,凸集,非凸集,99/08,-第 1 章 线性规划-,-12-,（2）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。,或者，设C为凸集，对于XC，不存在任何X1C，X2 C，且X1X2，使得X=X1+(1-)X2C，(01)，则X为凸集顶点。,X,X,X,X,X,99/08,-第 1 章 线性规划-,-13-,定理1：若线性LP模型存在可行解，则可行域为凸集。,证明：设 max z=CX st.AX=b X0,并设其可行域为C，若X1、X2为其可行解，且X1X2，则 X1C，X2 C，即AX1=b，AX2=b，X10，X20，,又 X为X1、X2连线上一点，即 X=X1+(1-)X2C，(01)，AX=AX1+(1-)AX2=b+(1-)b=b,(01)，且 X 0，X C，C为凸集。,三个基本定理：,99/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为基本可行解。,99/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：线性规划模型的基本可行解对应其可行域的顶点。,99/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)T X2=(x1-1，x2-2，xm-m，0，0)T取充分小,使得 xj j0，则 X1、X2均为可行解，但 X=0.5X1+(1-0.5)X2，X是X1、X2连线上的点，X非凸集顶点。,99/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(01)，（j=1,2,n)，yj0，zj0,0,1-0，当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,99/08,-第 1 章 线性规划-,-18-,Y、Z为不同两点，yj-zj不全为0，P1,P2,Pr线性相关，X非基本可行解。,99/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,99/08,-第 1 章 线性规划-,-20-,z1=CX1=CX0-C=zmax-C，z2=CX2=CX0+C=zmax+C z0=zmax z1，z0=zmax z2，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为可行解，,99/08,-第 1 章 线性规划-,-21-,单纯形法的计算步骤：,初始基本可行解,新的基本可行解,最优否？,STOP,Y,N,99/08,-第 1 章 线性规划-,-22-,1初始基本可行解的确定：,设模型 n max z=cjxj j=1 n s.t.aijxjbi（i=1,2,m)j=1 xj0（j=1,2,n),n m max z=cjxj+0 xsi j=1 I=1 n s.t.aijxj+xsi=bi（i=1,2,m)j=1 xj0，xsi0（j=1,2,n;i=1,2,m),化标准形,初始基本可行解 X=(0,0,0,b1,b2,bm)T，,n个0,99/08,-第 1 章 线性规划-,-23-,2从一个基本可行解向另一个基本可行解转换,不失一般性，设基本可行解X0=(x10,x20,xm0,0,0)T，前m个分量为正值，秩为m，其系数矩阵为,P1 P2 Pm Pm+1 Pj Pn b 1 0 0a 1,m+1 a1j a 1n b1 0 1 0 a 2,m+1 a2j a 2nb2 0 0 1a m,m+1 amj a mn bm,pjxj0=,j=1,n,pixi0=b(1),i=1,m,99/08,-第 1 章 线性规划-,-24-,又P1 P2 Pm为一个基，任意一个非基向量Pj可以以该组向量线性组合表示，即Pj=a1j P1+a2j P2+amj Pm，即 Pj=aij pi，移项，两端同乘0，有(Pj-aij pi)=0(2),i=1,m,i=1,m,(1)+(2)：(xi 0-aij)Pi+Pj=b，取充分小，使所有xi 0-aij 0，从而,i=1,m,X1=(x1 0-a1j,x2 0-a2j,xm 0-amj,0,0)T,也是可行解。,当取=min aij 0=，则X1的前m个分量至少有一个xL1为0。,xi 0,aij,alj,xL 0,i,P1,P2,PL-1,PL+1,Pm,Pj 线性无关。,99/08,-第 1 章 线性规划-,-25-,X1 也为基本可行解。,3.最优解的判别,依题义,z0=cjxj0=ci xi0,i=1,m,j=1,n,z0=cjxj1=ci(xi 0-aij)+cj,i=1,m,j=1,n,=ci(xi 0-aij)+(cj-ciaij)=z0+j,i=1,m,i=1,m,99/08,-第 1 章 线性规划-,-26-,因0，所以有如下结论：,(1)对所有j，当 j0，有z1 z0，即z0为最优值，X0为最优解；(2)对所有j，当j0，但存在某个非基变量k=0，则对此Pk作 为新基向量得出的解X1，应有z1=z0，故z1 也为最优值，从而 X1为最优解，且为基本可行解，X0、X1 连线上所有的点均为最优解，因此该线性规划模型 具有无穷多解；(3)若存在某个j 0，但对应aij0，则因当 时，有z1，该线性规划模型具有无界解。,99/08,-第 1 章 线性规划-,-27-,1.4单纯形法的计算及示例,1.4.1 单纯形法几何解释-顶点寻优 例：max z=2x1+3x2 max z=2x1+3x2+0 x3+0 x4 s.t x1+x23 标准化 s.t x1+x2+x3=3 x1+2x2 4 x1+2x2+x4=4 x10,x20 xj0,(j=1,2,3,4),（1）初始基本可行解的选择：-坐标原点处,令 x1=x2=0,由 x1+x2+x3=3 x1+2x2+x4=4,（2）是否为最优解的判定:-计算检验数,若 x11,则 x31,x41,1=2-（01+01）=2 j=z=cj-zj=cj-ciaij，称 j为检验数。,x3=3-(x1+x2)x4=4-(x1+2x2),解得 X=(0,0,3,4)T,99/08,-第 1 章 线性规划-,-28-,若 x21,则 x31,x42,2=3-(01+02)=3,*当所有检验数均有j 0时，则为最优解。*,（3）找新的顶点（基本可行解）：直观看，x21,则 z 3，应找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重复上述过程，直至所有检验数 j 0。,99/08,-第 1 章 线性规划-,-29-,继续迭代：,找新的顶点（基本可行解）：若x11,则 z 1/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,99/08,-第 1 章 线性规划-,-30-,O,C,A,B,X1,X2,(0,2),(3,0),(2,1),3,4,99/08,-第 1 章 线性规划-,-31-,Cj,x1,x2,x3,x4,XB,b,CB,1 1 1 0 1 2 0 1,2 3 0 0,34,x3 x4,00,cj-zj,2,3,0,0,3/1=3,4/2=2,1/2 0 1-1/2 1/2 1 0 1/2,x3 x2,12,cj-zj,1/2 0 0-3/2,03,24,1 0 2-1 0 1-1 1,x1 x2,21,cj-zj,0 0-1-1,23,1.4.2 单纯形法计算：,i,99/08,-第 1 章 线性规划-,-32-,单纯形法计算过程总结：,（1）化标准形，列初始单纯形表；,（2）计算检验数：j=z=cj-zj=cj-ciaij,（3）最优性判断：当所有检验数均有j 0时，则为最优解。否则迭代求新的基本可行解。,（4）迭代：入基变量：取maxj 0=kxk出基变量：取min i=bi/aik aik0=l x(l)主元素：alk新单纯表：pk=单位向量,注：当所有检验数j 0时，若存在非基变量检验数为0时，则有无穷多解，否则只有唯一最优解。,i=1,m,99/08,-第 1 章 线性规划-,-33-,例：min z=2x1+3x2 max z=-2x1-3x2+0 x3 s.t x1+x2 3 标准化 s.t x1+x2-x3=3 x1+2x2=4 x1+2x2=4 x10,x20 xj0,(j=1,2,3,4),max z=-2x1-3x2+0 x3-M x4-M x5 s.t x1+x2-x3+x4=3 x1+2x2+x5=4 xj0,(j=1,2,3,4,5),引进人工变量，及M非常大正系数，模型转变为,这种处理方法称为大M法，以下则可完全按单纯形法求解。,1大M法,1.5 单纯形法进一步讨论,99/08,-第 1 章 线性规划-,-34-,Cj,x1,x2,x3,x4,XB,b,CB,1 1-1 1 0 1 2 0 0 1,-2-3 0-M-M,34,x4 x5,-M-M,cj-zj,-2+2M,-3+3M,-M,0,3/1=3,4/2=2,1/2 0-1 1-1/2 1/2 1 0 0 1/2,x4 x2,12,cj-zj,-1/2+M/2 0-M 0 3/2-M/2,-M-3,24,1 0-2 2-1 0 1 1-1 1,x1 x2,21,cj-zj,0 0-1 1-M 1-M,-2-3,i,x5,0,99/08,-第 1 章 线性规划-,-35-,说明：当所有j0，但存在人工变量x人=0，则可以判定该模型有无可行解。,采用大M法求解线性规划模型时，如果模型中各个系数与M的值非常接近时，若手工计算时，不会出现任何问题。如果利用计算机程序求解，则大M表现为一个较大的数字，由于综合计算的影响，导致检验数出现符号误差，引起判断错误，从而使大M方法失效。在这种情况下，可采用下面的两阶段法进行计算。,99/08,-第 1 章 线性规划-,-36-,2两阶段法：,例：min z=2x1+3x2 max z=-2x1-3x2+0 x3 s.t x1+x2 3 标准化 s.t x1+x2-x3=3 x1+2x2=4 x1+2x2=4 x10,x20 xj0,(j=1,2,3,4),obj:max z=-x4-x5 s.t x1+x2-x3+x4=3 x1+2x2+x5=4 xj0,(j=1,2,3,4,5),(1)第一阶段，构造判断是否存在可行解的模型：,用单纯形法求解，若zmax=0，表明该模型有可行解，则可进入第二阶段，求原模型最优解。,99/08,-第 1 章 线性规划-,-37-,Cj,x1,x2,x3,x4,XB,b,CB,1 1-1 1 0 1 2 0 0 1,0 0 0-1-1,34,x4 x5,-1-1,cj-zj,2,3,-1,0,3/1=3,4/2=2,1/2 0-1 1-1/2 1/2 1 0 0 1/2,x4 x2,12,cj-zj,1/2 0-1 0 1,-1 0,24,1 0-2 2-1 0 1 1-1 1,x1 x2,21,cj-zj,0 0 0-1-1,0 0,i,x5,0,99/08,-第 1 章 线性规划-,-38-,(2)第二阶段，将原目标函数引入最终单纯形表，继续迭代：max z=-2x1-3x2+0 x3,Cj,x1,x2,x3,XB,b,CB,1 1 0 0 0-1,-2-3 0,21,x1 x2,-2-3,cj-zj,0,0,-1,99/08,-第 1 章 线性规划-,-39-,1.4.3 程序求解,（1）用LINDO软件求解,（2）用EXCEL工具求解,使用EXCEL中数据处理工具规划求解。,99/08,-第 1 章 线性规划-,-40-,1.6 改进单纯形法,单纯形法迭代过程可用矩阵变换描述如下：设,max z=CX stAXbX0,分解,max z=CBXB+CNXN+0XS stBXB+NXN+IXS=bXB,XN,XS0,约束方程两端同乘B-1，则可得如下表达式：,式中，B最终表中基对应的矩阵，N初始表与最终表中均为非基对应的矩阵，I 单位矩阵,A=B N,max z=CBXB+CNXN+0XS st B-1 BXB+B-1 NXN+B-1 XS=B-1 b XB,XN,XS0,对应最终单纯形表的模型,99/08,-第 1 章 线性规划-,-41-,用单纯形表表示如下：,XS=b,B N I,XB=b I N B-1,初始表 XB XN XS,cj-zj 0,0 N S,最终表 XB XN XS,cj-zj B N 0,0,表中，b=B-1b N=B-1N 或者 Pj=B-1PjN=CN-CB B-1 N或者j=Cj-CBB-1 PjS=-CB B-1,99/08,-第 1 章 线性规划-,-42-,化标准形：B-1 new=I，XB=b，求检验数：N=CN-CB B-1 new N，S=-CB B-1 new 最优性判别：所有 0，X人0，无可行解；所有 0，X人=0，存在 N=0，无穷多解；所有 0，X人=0，不存在N=0，唯一解；否则(存在 0)，转，取max xk，为换入变量，计算Pk=B-1 new Pk，若 Pk 0 无界解,否则，计算i=bi/aik|aik 0，取min xL为换出变量，令,改进单纯形法计算步骤：,99/08,-第 1 章 线性规划-,-43-,D=,1-a1k/aLk 00 1/aLk 00-amk/aLk 1,xL,计算 B-1 new=D B-1old，b=B-1 newb,转。,注：D矩阵为单位矩阵中出基变量所在单位向量以上述列向量代换。,实例演算如下：,99/08,-第 1 章 线性规划-,-44-,例：max z=2x1+3x2 max z=2x1+3x2+0 x3+0 x4 s.t x1+x23 标准化 s.t x1+x2+x3=3 x1+2x2 4 x1+2x2+x4=4 x10,x20 xj0,(j=1,2,3,4),x1x2x3 x4 b111 0 3 120 1 4,初始解：B-1 new=I，XB=(x3,，x4)T=(3，4)T,N=(1，2)=(2，3)，计算 P2=B-1 new P2=(1，2)T，换入变量：max x2，换出变量：i=bi/ai2|ai2 0=(3，2)，min x4，,99/08,-第 1 章 线性规划-,-45-,第二次计算：,1-1/20 1/2,D=,，B-1 new=D B-1old=,1-1/20 1/2,1 00 1,1-1/20 1/2,=,XB=(x3,，x2)T=B-1 new b=(1，2)T,N=(1，4)=CN-CB B-1 N=(2，0)-(0，3),1-1/20 1/2,1 01 1,=(1/2，-3/2),换入变量：max x1，计算 P1=B-1 new P1=(1/2，1/2)T，换出变量：i=bi/ai1|ai1 0=(2，4)，min x3，,99/08,-第 1 章 线性规划-,-46-,2 0-1 1,D=,，B-1 new=D B-1old=,2 0-1 1,2-1-1 1,1-1/20 1/2,=,XB=(x1，x2)T=B-1 new b=(2，1)T,N=(3，4)=CN-CB B-1 N=(0，0)-(2，3),2-1-1 1,1 00 1,=(-1，-1),第三次计算：,所有 0，故为最优解，XB=(x1，x2)T=(2，1)T,z max=7,99/08,-第 1 章 线性规划-,-47-,例 用单纯形法解目标规划问题时，有如下二个单纯形表，试把表中数字补全。,Cj,x1,x2,x3,x4,XB,b,CB,1 0 0 1,0 0,3,x3 x4,00,cj-zj,CB XB b,x1 x2 x3 x4,2-1-1 1,x1 x2,1,cj-zj,-1-1,23,99/08,-第 1 章 线性规划-,-48-,S=(-1，-1)=(3，4)=CS-CB B-1=-(c1，c2),2-1-1 1,1 00 1,=-(2c1-c2，-c1+c2),c1=2c2=3,又 b=B-1 b，,b1 1,2-1-1 1,3 b2,6-b2-3+b2,=,=,b1=2b2=4,2-1-1 1,1 00 1,=,a11 a12 a21 a22,1 0 0 1,=,2a11-a21-2a12-a22-a11+a21-a12+a22,a11=1，a12=1，a21=1，a22=2,解：,
