1-2线性规划问题几何意义与解的性质定理-zff课件.ppt

1、122.12.1基本概念基本概念凸集凸集：设：设K是是n维欧式空间的一个点集维欧式空间的一个点集,若任意若任意 两点两点 X(1)K,X(2)K 的连线上一切点的连线上一切点 a a X(1)+(1-a a)X(2)K(0a1),则称则称K为凸集为凸集.3顶点顶点：设：设K是凸集是凸集,X K。若若X不能用不同的不能用不同的两点两点x(1)K,x(2)K 的线性组合表示，即的线性组合表示，即 Xa x(1)+(1-a)x(2)(0a1),则称则称X为为K的一个顶点的一个顶点(极极/角点角点).凸组合凸组合：设：设 X(1),X(2),X(k)是是n维欧式空间的维欧式空间的 k个点个点,若存在若

2、存在k个数个数u u1 1,u u2 2,u uk k满足满足0ui1,则称则称 X=u u1 1X(1)+u u2 2X(2)+u uk kX(k)为为 X(1),X(2),X(k)的凸组合。的凸组合。11kiiu42.2.四个重要定理四个重要定理 线性规划问题的可行解集线性规划问题的可行解集(可行域可行域)是凸集。是凸集。njjjjxbxPXD10,：从从D中任取两个不同的点中任取两个不同的点X(1)和和 X(2)，二者应满足可行解定义中的二者应满足可行解定义中的等式条件等式条件；设设X是点是点X(1)和和X(2)连线上的任意连线上的任意一点，有一点，有X=X(1)+(1-)X(2)，证明

3、证明XD。5：X(1)和和X(2)满足可行解定义中的满足可行解定义中的等式条件等式条件，则有；，则有；设设X是点是点X(1)和和X(2)连线上的任意一点，有连线上的任意一点，有X=X(1)+(1-)X(2)，那么有，那么有;1)2(1)1(bxPbxPnjjjnjjj)2()1()1(jjjxaxax6bbaabxaPxaPxaPxaPxaxaPxPnjjjnjjjjjnjjjjnjjjnjjj)1()1()1()1(1)2(1)1()2(1)1()2(1)1(17 若若X是是LP问题的可行解，则问题的可行解，则X是基本可是基本可行解的充分必要条件是行解的充分必要条件是X的正分量所对应的系数的

4、正分量所对应的系数列向量线性独立列向量线性独立.8 9 （线性规划几何理论基本定理）线性规划几何理论基本定理）X是是LP问题的可行解（可行域中的一点），如果问题的可行解（可行域中的一点），如果它是基可行解，则它必然对应于可行域它是基可行解，则它必然对应于可行域D的顶点。的顶点。：10 X是基可行解是基可行解X是是D的一个顶点的一个顶点X不是不是基可行解基可行解X不是不是D的顶点的顶点11X不是不是基可行解基可行解X不是不是D的顶点的顶点0.2211mmPaPaPamjjjbxP112X不是基可行解不是基可行解X不是不是D的顶点的顶点bPuaxPuaxPuaxbPuaxPuaxPuaxmmmmm

5、m)(.)()()(.)()(2221112221110,.,0),(),.,(),(0,.,0),(),.,(),(2211)2(2211)1(mmmmuaxuaxuaxXuaxuaxuaxX13X不是基可行解不是基可行解X不是不是D的顶点的顶点)2()1(2121XXX必要性证毕必要性证毕14X不是不是D的顶点的顶点 X不是基可行解不是基可行解)2()2(2)2(1)2()1()1(2)1(1)1(,.,.,nnxxxXxxxX0)2()1(jjjxxx15X不是不是D的顶点的顶点 X不是基可行解不是基可行解mjjjbxP1)1(mjjjbxP1)2(mjjjjxxP1)2()1(0)(充

6、分性证毕充分性证毕16若若K是有界凸集，则此凸集上的任何是有界凸集，则此凸集上的任何一点一点X可表示为可表示为K的顶点的凸组合。的顶点的凸组合。根据凸组合的定义证明。根据凸组合的定义证明。17 若可行域若可行域有界有界，则线性规划问题的目标，则线性规划问题的目标函数函数一定一定可以在可行域的可以在可行域的顶点顶点上达到最优值。上达到最优值。1)首先首先,可行域有界就能够找到最优解可行域有界就能够找到最优解;在在非顶点非顶点X处取得最优值，则存在处取得最优值，则存在顶点顶点X(m)也取得相同的最优值。也取得相同的最优值。18kiiikiiiaaXaX11)(010且；kiiikiiiCXaXaCCX1)(1)(019kikimmimikiiiCXXaCCXaCXa11)()()(1)()()0(mCXCX20上述定理的一些有意义的启示：上述定理的一些有意义的启示：（为什么？能举例说明吗？为什么？能举例说明吗？）（类似于坐标与点的对（类似于坐标与点的对应关系！）应关系！）21顶点个数顶点个数基本可行解个数基本可行解个数基的个数基的个数mnC