线性规划求解课件1

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,99/08,第 1 章 线性规划,-,*,-,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,99/08,第 1 章 线性规划,*,线性规划求解,（优选）线性规划求解,99/08,2,第 1 章 线性规划,（,4,）基：设,A,为线性规划模型约束条件系数矩阵（,m,n,，,mn,），而,B,为其,m,m,子矩阵，若,|B|,0,，则称,B,为该线性规划模型的一个基。,（,5,）基变量：基中每个向量所对应的变量称为基变量。,（,6,）非基变量：模型中基变量之外的变量称为非基变量。,（,7,）基解（基解）：令模型中所有非基变量,X,非基,=0,后，由模型约束方程组,n,a,ij,x,j,=b,i,(i=1,2,m),得到的一组解。,j=1,（,8,）基本可行解（基可行解）：在基解中，同时又是可行解的解称为基可行解。,（,9,）可行基：对应于,基可行解,的基称为可行基。,99/08,3,第 1 章 线性规划,Max z=2x,1,+3x,2,st.x,1,+x,2,3 x,1,+2x,2,4 x,1,x,2,0,Max z=2x,1,+3x,2,+0 x,3,+0 x,4,st.x,1,+x,2,+x,3,=,3 x,1,+2x,2,+x,4,=,4 x,1,x,2,x,3,x,4,0,A=,x,1,x,2,x,3,x,4,1 1 1 0,1 2 0 1,可行解：,X=(0,，,0),T,，,X=(0,，,1),T,，,X=(1/2,，,1/3),T,等。,设,B=,1 0,0 1,，令,，则,|B|=1,0,令,x,1,=x,2,=0,，则,x,3,=3,x,4,=4,，,X=(0,0,3,4),T,例：,x,3,x,4,基变量,令,B=,1 1,1 0,x,1,x,3,，则,令,x,2,=x,4,=0,，则,x,3,=-1,x,1,=4,，,X=(4,0,-1,0),T,|B|=-1,0,非基本可行解,基本可行解,标准化,99/08,4,第 1 章 线性规划,复习思考题：,1.,可行解和可行域有怎样的关系？,2.,一个标准化,LP,模型，最多可有多少个基？,3.,基解是如何定义的？怎样才能得到基解？,4.,可行解、基解、基可行解三者之间有什么关系？在,LP,模型中是否一定存在？,5.,什么是可行基？,99/08,5,第 1 章 线性规划,1.2,线性规划问题的图解方法,*利用作图方法求解。,例：,max z=2x,1,+3x,2,s.t 2x,1,+2x,2,12 -,x,1,+2x,2,8 -,4x,1,16 -,4x,2,12 -,x,1,0,x,2,0,99/08,6,第 1 章 线性规划,x,1,x,2,2,2,4,6,8,4,6,0,Z=6,Z=0,(4,2),Z,max,99/08,7,第 1 章 线性规划,A,A,B,唯一解,无穷多解,无界解,无可行解,99/08,8,第 1 章 线性规划,步骤：,（,1,）作平面直角坐标系，标上刻度；（,2,）做出约束方程所在直线，确定可行域；（,3,）做出一条目标函数等值线，判定优化方向；（,4,）沿优化方向移动，确定与可行域相切的点，确定最优 解，并计算最优值。,讨论一：模型求解时，可得到如下几种解的状况：（,1,）唯一最优解：只有一点为最优解点，简称唯一解；（,2,）无穷多最优解：有许多点为最优解点，简称无穷多解；（,3,）无界最优解：最优解取值无界，简称无界解；（,4,）无可行解：无可行域，模型约束条件矛盾。,讨论二：,LP,模型求解思路：（,1,）若,LP,模型可行域存在，则为一凸形集合；（,2,）若,LP,模型最优解存在，则其应在其可行域顶点上找到；（,3,）顶点与基本解、基本可行解的关系：,99/08,9,第 1 章 线性规划,复习思考题：,1.LP,模型的可行域是否一定存在,?,2.,图解中如何去判断模型有唯一解、无穷多解、无界解和无可行解？,3.LP,模型的可行域的顶点与什么解具有对应关系？,4.,你认为把所有的顶点都找出来，再通过比较目标函数值大小的方式找出最优解，是否是最好的算法？为什么？,99/08,10,第 1 章 线性规划,具有无穷多解；,或者 Pj=B-1Pj,P1 P2 Pm Pm+1 Pj Pn b,引进人工变量，及M非常大正系数，模型转变为,XC=(4,2,0,0,4)T,对应最终单纯形表的模型,x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x40,1 0 -2 2 -1 0 1 1 -1 1,或者，任给X1C，X2 C，X=X1+(1-)X2 C (01)，则C为凸集。,令 x2=x4=0，则 x3=-1,x1=4，X=(4,0,-1,0)T,max z=CBXB+CNXN+0XS,xj0 （j=1,2,n),xj0，xsi0 （j=1,2,n;i=1,2,m),由(1)+(2)得 (x1+1)P1+(x2+2)P2+(xm+m)Pm=b,对应最终单纯形表的模型,第 1 章 线性规划,1.3,单纯形法,的基本原理,（,Simplex Method,）,1.3.1,两个概念：,（,1,）凸集：对于集合,C,中任意两点连线上的点，若也在,C,内，则称,C,为凸集。,或者,，,任给,X,1,C,，,X,2,C,，,X=,X,1,+(1-,)X,2,C (0,1),，则,C,为凸集。,凸集,非凸集,99/08,11,第 1 章 线性规划,（,2,）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。,或者,，,设,C,为凸集，,对于,X,C,，不存在任何,X,1,C,，,X,2,C,，且,X,1,X,2,，使得,X=,X,1,+(1-,)X,2,C,，,(0,1),，则,X,为凸集顶点。,X,X,X,X,X,99/08,12,第 1 章 线性规划,定理,1,：,若线性,LP,模型存在可行解，则可行域为凸集。,证明：,设,max z=CX,st.AX=b,X,0,并设其可行域为,C,，若,X,1,、,X,2,为其可行解，,且,X,1,X,2,，,则,X,1,C,，,X,2,C,，即,AX,1,=,b,，,AX,2,=b,，,X,1,0,，,X,2,0,，,又,X,为,X,1,、,X,2,连线上一点，即,X=,X,1,+(1-,)X,2,C,，,(0,1),，,A,X=,A,X,1,+(1-,)AX,2,=,b+(1-,)b=b,(,0,1),，且,X,0,，,X,C,，,C,为凸集。,1.3.2 三个基本定理,99/08,13,第 1 章 线性规划,引理：,线性规划问题的可行解,X=,(,x,1,x,2,x,n,),T,为基本可行解的充要条件是,X,的正分量所对应的系数列向量线性独立。,证：,（,1,）必要性：,X,基本可行解,X,的正分量所对应的系数列向量线性独立,可设,X=,(,x,1,x,2,x,k,0,0,0,),T,，若,X,为基本可行解，,显然，由,基本可行解,定义可知,x,1,x,2,x,k,所对应,的系数列向量,P,1,P,2,P,k,应该线性独立。,（,2,）充分性：,X,的正分量所对应的系数列向量线性独立,X,为基本可行解,若,A,的秩为,m,，则,X,的正分量的个数,k,m,；,当,k=m,时，则,x,1,x,2,x,k,的系数列向量,P,1,P,2,P,k,恰好构成基，,X,为基本可行解。,当,km,时，则必定可再找出,m-k,个列向量与,P,1,P,2,P,k,一起构成基，,X,为基本可行解。,99/08,14,第 1 章 线性规划,证：用反证法,X,非基本可行解,X,非凸集顶点,（,1,）必要性,：,X,非基本可行解,X,非凸集顶点,不失一般性，设,X=,(,x,1,x,2,x,m,0,0,0,),T,，为非基本可行解，,X,为可行解，,p,j,x,j,=b,，,j=1,n,即,p,j,x,j,=b(1),j=1,m,又,X,是非基本可行解，,P,1,P,2,P,m,线性相关，即有,1,P,1,+,2,P,2,+,m,P,m,=0,，其中,1,，,2,，,，,m,不全为,0,，两端同乘,0,，得,1,P,1,+,2,P,2,+,m,P,m,=0,，,（,2,）,定理,2,：,线性规划模型的基本可行解对应其可行域的顶点。,99/08,15,第 1 章 线性规划,由,(1)+(2),得,(x,1,+,1,),P,1,+,(x,2,+,2,),P,2,+,(x,m,+,m,),P,m,=b,由,(1),-,(2),得,(x,1,-,1,),P,1,+,(x,2,-,2,),P,2,+,(x,m,-,m,),P,m,=b,令,X,1,=,(x,1,+,1,，,x,2,+,2,，,，,x,m,+,m,，,0,，,，,0),T,X,2,=,(x,1,-,1,，,x,2,-,2,，,，,x,m,-,m,，,0,，,，,0),T,取,充分小,使得,x,j,j,0,，则,X,1,、,X,2,均为可行解，,但,X=0.5X,1,+(1-0.5)X,2,，,X,是,X,1,、,X,2,连线上的点，,X,非凸集顶点。,99/08,16,第 1 章 线性规划,xj0 （j=1,2,n),第 1 章 线性规划,B-1 new=I，XB=(x3,，x4)T=(3，4)T,N=(1，2)=(2，3)，,n,第 1 章 线性规划,s.,stBXB+NXN+IXS=bXB,XN,XS0,第 1 章 线性规划,t x1+x2-x3+x4=3 x1+2x2 +x5=4 xj0,(j=1,2,3,4,5),（1）凸集：对于集合C中任意两点连线上的点，若也在C内，则称 C为凸集。,3单纯形法的基本原理（Simplex Method）,第 1 章 线性规划,S=-CB B-1,（2）计算检验数：j=z=cj-zj=cj-ciaij,LP模型的可行域的顶点与什么解具有对应关系？,pjzj=b(2),设模型 n,则 X1C，X2 C，即AX1=b，AX2=b，X10，X20，,x1 x3,（,2,）充分性：,X,非凸集顶点,X,非基本可行解,设,X=,(,x,1,x,2,x,r,0,0,0,),T,为,非凸集顶点，则必存在,Y,、,Z,两点，使得,X=,Y+(1-,)Z,，,(0,1),，且,Y,、,Z,为可行解,或者,x,j,=,y,j,+(1-,)z,j,(0,0,1-,0,，当,x,j,=0,，必有,y,j,=z,j,=0,p,j,y,j,=,j=1,n,p,j,y,j,=b(1),j=1,r,p,j,z,j,=,j=1,n,p,j,z,j,=b(2),j=1,r,(y,j,-,z,j,)p,j,=0,j=1,r,(,1,)-(2),得,即,(y,1,-z,1,),P,1,+,(y,2,-,z,2,),P,2,+,(y,r,-z,r,),P,r,=0,99/08,17,第 1 章 线性规划,Y,、,Z,为不同两点，,y,j,-,z,j,不全为,0,，,P,1,P,2,P,r,线性相关，,X,非基本可行解。,99/08,18,第 1 章 线性规划,3,4,O,(3,3),C(4,2),6,6,2X1+2X2+X3=12,4X2+X5=12,4X1+X4=16,X,A,=(0,3,6,16,0),T,X,O,=(0,0,12,16,12),T,X,B,=(3,3,0,4,0),T,X,C,=(4,2,0,0,4),T,X,D,=(4,0,4,0,12),T,A,D,B,X1,X2,99/08,19,第 1 章 线性规划,z,1,=CX,1,=CX,0,-C,=z,max,-C,，,z,2,=CX,2,=CX,0,+C,=z,max,+C,z,0,=,z,max,z,1,，,z,