1.272线性规划问题的几何意义ppt课件

1、凸集凸集凸组合凸组合顶点顶点v实心圆，实心球体，实心立方体等都是凸集，圆环不实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图有空洞。图1-71-7中的中的(a)(b)(a)(b)是凸集，是凸集，(c)(c)不是凸集。不是凸集。v图图1-21-2中的阴影部分中的阴影部分v 是凸集。是凸集。 k1ii1 定理定理1 : 1 : 若线性规划问题存在可行域，若线性规划问题存在可行域， 则其可行域则其可行域 是凸集是凸集 n1jjjjn, 2 , 1j, 0 x,bxP n1jjjj0 x,bxPXD T

2、2n22212T1n12111x,x,xXx,x,xX 是是D D内任意两点；内任意两点；X(1) X(2)X(1) X(2)v则有则有v令令X=(x1X=(x1，x2x2，xn)Txn)T为为x(1) , x(2)x(1) , x(2)连线上的任连线上的任意一点，即意一点，即v X=X(1) +(1-)X(2) (01)X=X(1) +(1-)X(2) (01)vX X的每一个分量是的每一个分量是v将它代入约束条件，将它代入约束条件， n1j2j2jjn1j1j1jjn,2, 1j,0 x,bxPn,2, 1j,0 x,bxP 2j1jjx)1(xx 2j1jjx)1(xx bbbbxPxP

3、xPx1xPxPn1jn1j2jj2jjn1j1jjn1jn1j2j1jjjj n1jjjj0 x,bxPXD m1jjjbxP现在分两步来讨论，分别用反证法。现在分两步来讨论，分别用反证法。（1-81-8）v根据引理根据引理1 1，若，若X X不是基可行解，则其正分量所对不是基可行解，则其正分量所对应的系数列向量应的系数列向量P1P1，P2P2，PmPm线性相关，线性相关，v即存在一组不全为零的数即存在一组不全为零的数i,i=1,2,mi,i=1,2,m使得使得v1P1+2P2+mPm=0 (1-9)1P1+2P2+mPm=0 (1-9)v用一个用一个0 0的数乘的数乘(1-9)(1-9)式

4、再分别与式再分别与(1-8)(1-8)式相加式相加和相减，和相减，这样得到这样得到(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)Pm(x1+1)P1+(x2+2)P2+(xm+m)Pm=b=b xii0，i=1,2,m即X(1)，X(2)是可行解。这证明了X 不是可行域 D 的顶点。 现取现取X(1)=X(1)=(x1-1),(x2-2),(xm-m),0,(x1-1),(x2-2),(xm-m),0,，0 0X(2)=X(2)=(x1+1),(x2+2),(xm+m),0,(x1

5、+1),(x2+2),(xm+m),0,，0 0由由X(1),X(2)X(1),X(2)可以得到可以得到X=X=（1/21/2X(1) +X(1) +（1/21/2X(2)X(2)，即即X X是是X(1)X(1)，X (2)X (2)连线的中点连线的中点因为因为X X不是可行域不是可行域 D D 的顶点，故在可行域的顶点，故在可行域D D中可找到不同中可找到不同的 两 点的 两 点 X ( 1 ) = ( x 1 ( 1 ) , x 2 ( 1 ) , , x n ( 1 ) ) T X ( 1 ) = ( x 1 ( 1 ) , x 2 ( 1 ) , , x n ( 1 ) ) T X(2

6、)=(x1(2),x2(2),xn(2)TX(2)=(x1(2),x2(2),xn(2)T使使 X=X(1)+(1-) X(2) X=X(1)+(1-) X(2) ， 0 01 1设设X X是基可行解，对应向量组是基可行解，对应向量组P1PmP1Pm线性独立。线性独立。当当j jmm时，有时，有xj=xj(1)=xj(2)=0 xj=xj(1)=xj(2)=0，由于，由于X(1)X(1)，X(2)X(2)是可行是可行域的两点。应满足域的两点。应满足 m1jm1j2jj1jjbxPbxP与与将这两式相减，即得将这两式相减，即得 m1j2j1jj0 xxPv因因X(1)X(2)X(1)X(2)，所

7、以上式系数不全为零，故向量组，所以上式系数不全为零，故向量组P1,P2,P1,P2,，PmPm线性相关，与假设矛盾。即线性相关，与假设矛盾。即X X不是基可行解。不是基可行解。v本引理证明从略，用以下例子说明这引理。本引理证明从略，用以下例子说明这引理。v例例5 5： 设设X X是三角形中任意一点，是三角形中任意一点，X(1),X(2)X(1),X(2)和和X(3)X(3)是三角形的三个顶点，试用三个顶点是三角形的三个顶点，试用三个顶点的坐标表示的坐标表示X(X(见图见图1-8) 1-8) vX=X(1)+(1-)X(3) 0X=X(1)+(1-)X(3) 01 1v又因又因X X是是XX与与

8、X(2)X(2)连线上的一个点，故连线上的一个点，故vX=X+(1-)X(2) 0X=X+(1-)X(2) 01 1v将将XX的表达式代入上式得到的表达式代入上式得到vX=X=X(1)+(1-)X(3)X(1)+(1-)X(3)+(1-)X(2)+(1-)X(2)v=X(1)+(1-)X(3)+(1-)X(2)=X(1)+(1-)X(3)+(1-)X(2)v这就得到这就得到 X=1X(1)+2X(2)+3X(3)X=1X(1)+2X(2)+3X(3)vii=1,0ii=1,0ii1 1 k1ik1iiiii0CXXCCX k1ik1iiiiii01,0,xX（1- 101- 10）在所有的顶点

9、中必然能找到某一个顶点在所有的顶点中必然能找到某一个顶点X(m)X(m)，使，使CX(m)CX(m)是是所有所有CX(i)CX(i)中最大者。并且将中最大者。并且将X(m)X(m)替代替代(1-10)(1-10)式中的所有式中的所有X(i)X(i)，这就得到这就得到 mk1imik1iiiCXCXCX 由于：由于：v由此得到由此得到 CX(0)CX(m)CX(0)CX(m)v根据假设根据假设CX(0)CX(0)是最大值，所以是最大值，所以v只能有只能有 CX(0)=CX(m)CX(0)=CX(m)v即目标函数在顶点即目标函数在顶点X(m)X(m)处也达到最大值。处也达到最大值。)k()2()1

10、(X,X,X k1ik1iiiii1,0,XX于是于是 k1iiik1iiiXCXCXC k,2,1i,mXCi 设：设：，mmXCk1ii 可行域为非封闭的无界区域可行域为非封闭的无界区域zx1x2 唯一最优解唯一最优解x1x2 z 无穷多个最优解无穷多个最优解x1x2Z 无界解无界解线性规划问题的所有可行解构成的集合是凸集，线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必在某顶点上得到。若线性规划问题有最优解，必在某顶点上得到。虽然顶点数目是有限的虽然顶点数目是有限的( (它不大于个它不大于个) )，若采用，若采用“枚举法枚举法找