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

二、二、 线性规划的几何意义线性规划的几何意义 12.12.1基本概念基本概念凸集凸集：设：设K是是n维欧式空间的一个点集维欧式空间的一个点集, 若任意若任意 两点两点 X(1)K, X(2)K 的连线上一切点的连线上一切点 a a X (1) +(1-a a) X(2)K (0a1), 则称则称K为凸为凸集集.2顶点顶点：设：设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个点个点, 若存在若存在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) 的凸组合的凸组合32.2. 四个重要定理四个重要定理n n定理定理1 1 线性规划问题的可行解集线性规划问题的可行解集(可行域可行域) 是凸集。

是凸集 证明思路证明思路：根据凸集定义，采用直接法证明根据凸集定义，采用直接法证明具具体体步步骤骤：从从D中中任任取取两两个个不不同同的的点点X(1)和和 X(2)，二者应满足可行解定义中的，二者应满足可行解定义中的等式条件等式条件； 设设X是是点点X(1)和和X(2) 连连线线上上的的任任意意一点，有一点，有X=X(1)+(1-)X(2)，证明证明XD 4证明证明：X(1)和和X(2)满足可行解定义中的满足可行解定义中的等式条件等式条件，则有；，则有；设设X是是点点X(1)和和X(2) 连连线线上上的的任任意意一一点点，有有X=X(1)+(1-)X(2)，那么有，那么有56n n引引理理1 1 若若X是是LP问问题题的的可可行行解解，则则X是是基基本本可可行行解解的的充充分分必必要要条条件件是是X的的正正分分量量所所对对应应的的系系数数列向量线性独立列向量线性独立.证证证证明明明明思思思思路路路路：X X为为为为LPLP的的的的基基基基本本本本可可可可行行行行解解解解XX的的的的正正正正分分分分 量所对应的系数列向量线性无关量所对应的系数列向量线性无关量所对应的系数列向量线性无关量所对应的系数列向量线性无关. . 证证证证 必必必必要要要要性性性性对对对对于于于于有有有有着着着着秩秩秩秩为为为为mm的的的的mnmn阶阶阶阶系系系系数数数数矩矩矩矩阵阵阵阵的的的的LPLP问问问问题题题题，由由由由基基基基本本本本可可可可行行行行解解解解定定定定义义义义可可可可知知知知，其其其其基基基基本本本本可可可可行行行行解解解解X X的的的的非非非非零零零零分分分分量量量量数数数数目目目目k=mk=m，且且且且全全全全部部部部为为为为正正正正。

当当当当k=mk=m，这这这这mm个个个个正正正正分分分分量量量量所所所所对对对对应应应应的的的的系系系系数数数数列列列列向向向向量量量量线线线线性性性性无无无无关关关关，并并并并恰恰恰恰好好好好构构构构成成成成一一一一个个个个基基基基；当当当当kmkm，这这这这k k个个个个正正正正分分分分量量量量所所所所对对对对应应应应的的的的系系系系数数数数列列列列向向向向量量量量线线线线性性性性无无无无关关关关，且且且且有有有有其其其其他他他他（m-km-k）个个个个0 0分分分分量量量量所所所所对对对对应应应应的的的的系系系系数数数数列列列列向向向向量量量量和和和和这这这这k k个个个个列列列列向量构成一个基向量构成一个基向量构成一个基向量构成一个基 7 充充充充分分分分性性性性对对对对于于于于有有有有着着着着秩秩秩秩为为为为mm的的的的mnmn阶阶阶阶系系系系数数数数矩矩矩矩阵阵阵阵的的的的LPLP问问问问题题题题，X X为为为为其其其其可可可可行行行行解解解解，则则则则X X中中中中所所所所有有有有元元元元素素素素大大大大于于于于等等等等于于于于0 0设设设设其其其其中中中中的的的的正正正正分分分分量量量量数数数数目目目目为为为为k k，且且且且其其其其对对对对应应应应的的的的系系系系数数数数列列列列向向向向量量量量P P1 1, , P P2 2, , P Pk k线线线线性性性性独独独独立立立立，则则则则必必必必有有有有k k =m=m（否否否否则则则则系系系系数数数数矩矩矩矩阵阵阵阵的的的的秩秩秩秩必必必必然要求大于然要求大于然要求大于然要求大于mm）。

当当当当k=mk=m，这这这这k k个个个个列列列列向向向向量量量量恰恰恰恰好好好好构构构构成成成成一一一一个个个个基基基基，从从从从而而而而可可可可行行行行解解解解X X为其相应的基解，则为其相应的基解，则为其相应的基解，则为其相应的基解，则X X是一个基可行解是一个基可行解是一个基可行解是一个基可行解 当当当当kmkm，除除除除了了了了P P1 1, , P P2 2, , PPk k线线线线性性性性独独独独立立立立外外外外，必必必必然然然然可可可可以以以以在在在在其其其其他他他他n-kn-k个个个个列列列列向向向向量量量量中中中中找找找找出出出出m-km-k个个个个列列列列向向向向量量量量，与与与与P P1 1, , P P2 2, , PPk k构构构构成成成成最最最最大大大大的的的的线线线线性性性性独独独独立立立立向向向向量量量量组组组组（否否否否则则则则系系系系数数数数矩矩矩矩阵阵阵阵的的的的秩秩秩秩必必必必然然然然要要要要求求求求小小小小于于于于m m ），其其其其对对对对应应应应的的的的解解解解为为为为X X，所所所所有有有有X X是是是是一一一一个个个个基可行解基可行解。

基可行解基可行解8n n定理定理2 2 （线性规划几何理论基本定理）线性规划几何理论基本定理） X是是LP问问题题的的可可行行解解（可可行行域域中中的的一一点点），如如果果它是基可行解，则它必然对应于可行域它是基可行解，则它必然对应于可行域D的顶点证明思路证明思路： X X为为为为LPLP的基本可行解的基本可行解的基本可行解的基本可行解 X X是是是是D D的一个顶点的一个顶点的一个顶点的一个顶点可可可可以以以以利利利利用用用用引引引引理理理理1 1（X X为为为为LPLP的的的的基基基基本本本本可可可可行行行行解解解解XX的的的的正正正正分分分分量量量量所所所所对应的系数列向量线性无关）进行证明对应的系数列向量线性无关）进行证明对应的系数列向量线性无关）进行证明对应的系数列向量线性无关）进行证明9证明思路证明思路： X是基可行解是基可行解X是是D的一个顶点的一个顶点X不是不是基可行解基可行解X不是不是D的顶点的顶点10必要性必要性X不是不是基可行解基可行解X不是不是D的顶点的顶点证明：证明：证明：证明：（1 1）X X是是是是可可可可行行行行解解解解，则则则则其其其其所所所所有有有有元元元元素素素素大大大大于于于于等等等等于于于于0 0。

假假假假定定定定其其其其前前前前mm个分量为正，则有式（个分量为正，则有式（个分量为正，则有式（个分量为正，则有式（1 1）成立 （1 1）（2 2）此此此此外外外外，由由由由引引引引理理理理1 1可可可可知知知知，如如如如果果果果X X不不不不是是是是基基基基可可可可行行行行解解解解，则则则则其其其其正正正正分分分分量量量量所所所所对对对对应应应应的的的的系系系系数数数数列列列列向向向向量量量量P P1 1, , P P2 2, , PPmm线线线线性性性性相相相相关关关关，即即即即存存存存在在在在一一一一组组组组不不不不全全全全为为为为0 0的的的的数数数数a ai i(i=1,2,m)(i=1,2,m)使使使使得得得得式式式式（2 2）成成成成立立立立 （2 2）11必要性必要性X不是基可行解不是基可行解X不是不是D的顶点的顶点（3 3）用用用用一一一一个个个个u0u0的的的的数数数数乘乘乘乘以以以以式式式式（2 2），然然然然后后后后与与与与式式式式（1 1）相相相相加减，得加减，得加减，得加减，得现取现取现取现取则则则则X X(1)(1),X,X(2)(2)是是是是该该该该LPLP问问问问题题题题的的的的可可可可行行行行解解解解（对对对对应应应应可可可可行行行行域域域域上上上上的两点）的两点）的两点）的两点）12必要性必要性X不是基可行解不是基可行解X不是不是D的顶点的顶点（4 4）由）由）由）由X, XX, X(1)(1), X, X(2)(2)的分量表达可知，的分量表达可知，的分量表达可知，的分量表达可知，即即即即X X是是是是X X(1)(1)和和和和X X(2)(2)连线的中点，一定不是连线的中点，一定不是连线的中点，一定不是连线的中点，一定不是D D的顶点。

的顶点必要性证毕必要性证毕13充分性充分性X不是不是D的顶点的顶点 X不是基可行解不是基可行解证明：证明：证明：证明：（1 1）X X在在在在可可可可行行行行域域域域中中中中，但但但但不不不不是是是是顶顶顶顶点点点点，则则则则在在在在可可可可行行行行域域域域D D中中中中可可可可找到不同的两点使找到不同的两点使找到不同的两点使找到不同的两点使X=aXX=aX(1)(1)+(1-a)X+(1-a)X(2) (2) (0a1) (0amjm时，有时，有时，有时，有14充分性充分性X不是不是D的顶点的顶点 X不是基可行解不是基可行解（3 3）因为因为因为因为X X(1)(1)和和和和X X(2)(2)是可行解是可行解是可行解是可行解，又有下两式成立，又有下两式成立，又有下两式成立，又有下两式成立将两式相减，可得将两式相减，可得将两式相减，可得将两式相减，可得 成立成立成立成立 因因因因为为为为X X(1)(1)和和和和X X(2)(2)是是是是两两两两个个个个不不不不同同同同可可可可行行行行解解解解，上上上上式式式式中中中中系系系系数数数数不不不不全全全全为为为为0 0，所所所所以以以以向向向向量量量量组组组组P P1 1, , P P2 2, , PPmm线线线线性性性性相相相相关关关关，否否否否定定定定（2 2）的假设，即）的假设，即）的假设，即）的假设，即X X不应该是基可行解。

不应该是基可行解不应该是基可行解不应该是基可行解充分性证毕充分性证毕15 引引理理2 2 若若K是是有有界界凸凸集集，则则此此凸凸集集上上的的任任何何一点一点X可表示为可表示为K的顶点的凸组合的顶点的凸组合 证明思路：证明思路： 根据凸组合的定义证明根据凸组合的定义证明16定定理理3 3 若若可可行行域域有有界界，则则线线性性规规划划问问题题的的目目标标函数函数一定一定可以在可行域的可以在可行域的顶点顶点上达到最优值上达到最优值 证明思路：证明思路： 1)首先首先, 可行域有界就能够找到最优解可行域有界就能够找到最优解; 2)如如果果在在非非顶顶点点X处处取取得得最最优优值值，则则存存在在顶点顶点X(m)也取得相同的最优值也取得相同的最优值17 证明：证明： 设设设设X X(1)(1) , , X X(2) (2) , , X X(k)(k)是是是是可可可可行行行行域域域域D D的的的的顶顶顶顶点点点点若若若若X X(0)(0)是是是是可可可可行行行行域域域域中中中中的的的的一一一一点点点点，但但但但不不不不是是是是顶顶顶顶点点点点，而而而而LPLP的的的的目目目目标标标标函函函函数数数数在在在在X X(0)(0)处达到最优值处达到最优值处达到最优值处达到最优值Z Z* *=CX=CX(0)(0)。

首首首首先先先先，X X(0)(0)是是是是可可可可行行行行域域域域中中中中的的的的一一一一点点点点，则则。