第1章-线性规划与单纯形法-第2节ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学,（,第三版）,运筹学教材编写组 编,清华大学出版社,第1章 线性规划与单纯形法,第2节 线性规划问题的几何意义,钱颂迪 制作,第1章 线性规划与单纯形法,1,第1章 线性规划与单纯形法,第2节线性规划问题的几何意义,2.1 基本概念,2.2 几个定理,第1章 线性规划与单纯形法 第2节线性规划问题的几,2,2.1 基本概念,凸集,凸组合,顶点,2.1 基本概念凸集,3,1.凸集,设K是n维欧氏空间的一点集，若任意两点X,(1),K，X,(2),K的连线上的所有点X,(1),+(1-)X,(2),K，(01)；则称K为凸集。,图1-7,1.凸集设K是n维欧氏空间的一点集，若任意两点X(1),4,实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图1-7中的(a)(b)是凸集，(c)不是凸集。,图1-2中的阴影部分,是凸集。,任何两个凸集的交集是凸集，见图1-7(d),实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观,5,2.凸组合,设X,(1),，X,(2),，X,(k),是n维欧氏空间E中的k个点。若存在,1,，,2,，,k,，且0i1,i=1,2,，k;,使X=,1,X,(1),+,2,X,(2),+,k,X,(k),则称X为X,(1),，X,(2),，X,(k),的凸组合。（当0,i,1时，称为严格凸组合）.,2.凸组合 设X(1)，X(2)，X(k)是n维欧氏空,6,3.顶点,设K是凸集，XK；若X不能用不同的两点X,(1),K和X,(2),K的线性组合表示为,X=X,(1),+(1-)X,(2),，(01),则称X为K的一个顶点(或极点)。,图中0，Q,1,2,3,4,都是顶点。,3.顶点设K是凸集，XK；若X不能用不同的两点X(1,7,2.2 几个定理,定理1 若线性规划问题存在可行域，则其可行域,是凸集,2.2 几个定理定理1 若线性规划问题存在可行域，则其可,8,证：为了证明满足线性规划问题的约束条件,的所有点(可行解)组成的集合是凸集，,只要证明D中任意两点连线上的点必然在D内即可。,设,是D内的任意两点；X,(1),X,(2),。,证：为了证明满足线性规划问题的约束条件的所有点(可行解)组,9,第1章-线性规划与单纯形法-第2节ppt课件,10,第1章-线性规划与单纯形法-第2节ppt课件,11,引理 1,线性规划问题的可行解X=(x,1,x,2,，x,n,),T,为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。,引理 1 线性规划问题的可行解X=(x1,x2,，x,12,定理2,线性规划问题的基可行解X对应于可行 D的顶点。,证：,不失一般性，假设基可行解X的前m个分量为正。故,现在分两步来讨论，分别用反证法。,（,1-8,）,定理2 线性规划问题的基可行解X对应于可行 D,13,若X不是基可行解，则它一定不是可行域D的顶点,根据引理1，若X不是基可行解，则其正分量所对应的系数列向量P,1,，P,2,，P,m,线性相关，即存在一组不全为零的数,i,i=1,2,m使得,1,P,1,+,2,P,2,+,m,P,m,=0 (1-9),用一个0的数乘(1-9)式再分别与(1-8)式相加和相减，。,若X不是基可行解，则它一定不是可行域D的顶点根据引理1，,14,这样得到(x,1,-,1,)P,1,+(x,2,-,2,)P,2,+(x,m,-,m,)P,m,=b(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,，0X,(2),=(x,1,+,1,),(x,2,+,2,),(x,m,+,m,),0,，0由X,(1),X,(2),可以得到X=（1/2）X,(1),+（1/2）X,(2),，,即X是X,(1),，X,(2),连线的中点,这样得到(x1-1)P1+(x2-2)P2+(,15,另一方面，当充分小时，可保证,x,i,i,0，i=1,2,m,即,X,(1),，,X,(2),是可行解。,这证明了,X,不是可行域,D,的顶点。,另一方面，当充分小时，可保证 xii0，i=1,2,16,(2)若X不是可行域D的顶点，则它一定不是基可行解,因为X不是可行域 D 的顶点，故在可行域D中可找到不同的两点,X,(1),=(x,1,(1),x,2,(1),x,n,(1),),T,X,(2),=(x,1,(2),x,2,(2),x,n,(2),),T,使 X=X,(1),+(1-),X,(2),，,01,设X是基可行解，对应向量组P,1,P,m,线性独立。当jm时，有x,j,=x,j,(1),=x,j,(2),=0，由于X,(1),，X,(2),是可行域的两点。应满足,(2)若X不是可行域D的顶点，则它一定不是基可行解因为X不,17,将这两式相减，即得,将这两式相减，即得,18,因X,(1),X,(2),，所以上式系数不全为零，故向量组P,1,P,2,，P,m,线性相关，与假设矛盾。即X不是基可行解。,因X(1)X(2)，所以上式系数不全为零，故向量组P1,P,19,引理2 若K是有界凸集，则任何一点XK可表示为K的顶点的凸组合。,本引理证明从略，用以下例子说明这引理。,例,5,设,X,是三角形中任意一点，,X,(1),X,(2),和,X,(3),是三角形的三个顶点，试用三个顶点的坐标表示,X(,见图,1-8),引理2 若K是有界凸集，则任何一点XK可表示为K的顶点,20,解 任选一顶点X,(2),，做一条连线XX,(2),；并延长交于X,(1),、X,(3),连接线上一点X。因X是X(1)、X(3)连线上一点，故可用X,(1),、X,(3),线性组合表示为,X=X,(1),+(1-)X,(3),01,又因X是X与X,(2),连线上的一个点，故,X=X+(1-)X,(2),01,将X的表达式代入上式得到,X=X,(1),+(1-)X,(3),+(1-)X,(2),=X,(1),+(1-)X,(3),+(1-)X,(2),解 任选一顶点X(2)，做一条连线XX(2)；并延长交于X,21,令,1,=,2,=(1-),3,=(1-),这就得到,X=,1,X,(1),+,2,X,(2),+,3,X,(3),i,i,=1,0,i,1,令 1=,2=(1-),3=(1-),22,定理 3,若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。,证,设X,(1),X,(2),，X,(k),是可行域的顶点，若X,(0),不是顶点，且目标函数在X,(0),处达到最优z,*,=CX,(0),(标准型是z=max z)。,因X,(0),不是顶点，所以它可以用D的顶点线性表示为,定理 3 若可行域有界，线性规划问题的目标函数一定可以在,23,定理3的证明：,证：,设X,(1),X,(2),，X,(k),是可行域的顶点，,若X,(0),不是顶点，且目标函数在X,(0),处达到,最优z,*,=CX,(0),(标准型是z=max z)。,定理3的证明：证：设X(1),X(2)，X(k)是,24,代入目标函数得,在所有的顶点中必然能找到某一个顶点,X,(m),，使,CX,(m),是所有,CX,(i),中最大者。并且将,X,(m),代替,(1-10),式中的所有,X,(i),，这就得到,（1-10）,代入目标函数得在所有的顶点中必然能找到某一个顶点X(m)，使,25,由此得到 X,(0),CX,(m),根据假设CX,(0),是最大值，所以只能有 CX,(0),=CX,(m),即目标函数在顶点X,(m),处也达到最大值。,有时目标函数可能在多个顶点处达到最大;,这时在这些顶点的凸组合上也达到最大值。,称这种线性规划问题有无限多个最优解。,由此得到 X(0)CX(m),26,假设是目标函数达到最大值的顶点，若是这些顶点的凸组合，即,于是,设：,假设是目标函数达到最大值的顶点，若是这些顶点的凸组合，即,27,于是：,于是：,28,另外，若可行域为无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到。根据以上讨论，可以得到以下结论：,线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；,若线性规划问题有最优解，必在某顶点上得到。虽然顶点数目是有限的(它不大于个)，若采用“枚举法”找所有基可行解，然后一一比较，最终可能找到最优解。但当n,m的数较大时，这种办法是行不通的，所以要继续讨论，如何有效地找到最优解，有多种方法，,这里仅介绍,单纯形法,。,另外，若可行域为无界，则可能无最优解，也可能有最优解，若有也,29,第2节 结束,第2节 结束,30,第1章-线性规划与单纯形法-第2节ppt课件,31,第1章-线性规划与单纯形法-第2节ppt课件,32,第1章-线性规划与单纯形法-第2节ppt课件,33,第1章-线性规划与单纯形法-第2节ppt课件,34,第1章-线性规划与单纯形法-第2节ppt课件,35,第1章-线性规划与单纯形法-第2节ppt课件,36,第1章-线性规划与单纯形法-第2节ppt课件,37,第1章-线性规划与单纯形法-第2节ppt课件,38,第1章-线性规划与单纯形法-第2节ppt课件,39,