§1-2线性规划问题的几何意义.ppt

1,第2节 线性规划问题 的几何意义,2.1 基本概念 2.2 几个定理,第1章 线性规划与单纯形法,2,1凸集,设K是n维欧氏空间的一点集，若任意两点X(1)K，X(2)K的连线上的所有点 X(1)+(1-)X(2) K(0 1)；则称K为凸集。,2.1 基本概念,实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。,X= X(1)+(1-)X(2) 就是以X(1), X(2)为端点的线段方程，点X的位置由的值确定，当 =0时，X=X(2)，当 =1时，X=X(1)。,3,任何两个凸集的交集是凸集。,凸集（续）,图1-2中的阴影部分是凸集。,4,2凸组合,凸组合,5,3顶点,设K是凸集，XK；若X不能用不同的两点X(1)K和X(2)K的线性组合表示为 X= X(1)+(1-)X(2)，01 则称X为K的一个顶点（或极点）。,顶点,图中0, Q1, Q2, Q3, Q4都是顶点。,X是凸集K的极点，即X不可能是K中某一线段的内点，只能是K中某一线段的端点。,6,2.2 几个定理,定理1 若线性规划问题存在可行域，则其可行域 是凸集。,证 为了证明满足线性规划问题的约束条件,的所有点（可行解）组成的集合是凸集，只要证明D中任意两点连线上的点必然在D内即可。,7,定理1（续）,定理1（续）,设 是D内的任意两点，X(1)X(2)。,则有,8,令X=(x1, x2, , xn)T为X (1), X(2)连线上的任意一点，即 X=X(1)+(1-)X(2) (01),将它代入约束条件，得到,定理1（续）,X的每一个分量是,9,定理1（续）,10,引理 1 线性规划问题的可行解X=(x1, x2, , xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。,引理1,证 必要性：由基可行解的定义可知。,充分性：若向量P1, P2, , Pk线性独立，则必有km；,当k=m时，它们恰构成一个基，从而X=(x1, x2, , xk, 0, , 0)为相应的基可行解。,当km时，则一定可以从其余的列向量中取出m-k个与P1, P2, , Pk构成最大的线性独立向量组，其对应的解恰为X，所以根据定义它是基可行解。,11,定理2 线性规划问题的基可行解X对应于可行域D的顶点。,证 不失一般性，假设基可行解X的前m个分量为正。故,现在分两步来讨论，分别用反证法。,定理2,(1) 若X不是基可行解，则它一定不是可行域D的顶点； (2) 若X不是可行域D的顶点，则它一定不是基可行解。,12,(1) 若X不是基可行解，则它一定不是可行域D的顶点。,根据引理1，若X不是基可行解，则其正分量所对应的系数列向量P1, P2, , Pm线性相关，即存在一组不全为零的数 i，i=1, 2, , m使得,定理2（续）,用一个0的数乘(2)式再分别与(1)式相加和相减。,13,定理2（续）,相加减后得到,现取,由X(1), X(2)可以得到 ，即X是X(1)，X(2)连线的中点。,14,此外，当 充分小时，可保证,即X(1), X(2)是可行解，即证明了X不是可行域 D 的顶点。,定理2（续）,15,使,定理2（续）,(2) 若X不是可行域D的顶点，则它一定不是基可行解。,因为X不是可行域D的顶点，故在可行域D中可找到不同的两点,16,定理2（续）,假设X是基可行解，对应向量组P1, P2, , Pm线性独立。当jm时，有xj=xj(1)=xj (2)=0。,由于X(1), X(2)是可行域的两点，应满足,将这两式相减，即得,17,因X(1)X(2)，所以上式系数不全为零，故向量组P1, P2, , Pm线性相关，与假设矛盾。即X不是基可行解。,定理2（续）,定理2刻划了可行解集的顶点与基本可行解的对应关系，顶点是基本可行解，反之，基本可行解一定是顶点。但它们并非一一 对应，有可能两个或几个基本可行解对应于同一顶点（退化基本可行解时）。,18,引理2 若K是有界凸集，则任何一点XK可表示为K的顶点的凸组合。,例1 设X是三角形中任意一点，X(1), X(2)和X(3)是三角形的三个顶点，试用三个顶点的坐标表示X。,引理2,解 任选一顶点X(2)，做一条连线XX(2)；并延长交于X(1)、X(3)连接线上一点X 。,19,因X 是X(1)、X(3)连线上一点，故可用X(1)、X(3)线性组合表示为,又因X是X 与X(2)连线上的一个点，故,引理2（续）,将X 的表达式代入(3)式得到,20,引理2（续）,令,即得,21,定理3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。,证 设X(1), X(2), , X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优z*=CX(0)（标准型是z=max z）。,定理3,因X(0)不是顶点，所以它可以用D的顶点线性表示为,22,将X(0)代入目标函数得,在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所有CX(i)中最大者，并且将X(m)代替(4)式中的所有X(i)，这就得到,定理3（续）,23,有时目标函数可能在多个顶点处达到最大，这时在这些顶点的凸组合上也达到最大值，称这种线性规划问题有无限多个最优解。,定理3（续）,根据假设CX(0)是最大值，所以只能有,即目标函数在顶点X(m)处也达到最大值。,24,定理3（续）,假设 是目标函数达到最大值的顶点，若 是这些顶点的凸组合，即,于是,设,则有,25,另外，若可行域为无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到。根据以上讨论，可以得到以下结论：,线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点； 若线性规划问