【摘要】：三角形、矩形、圆面等都是二维凸集，球体、长方体、圆柱体等是三维凸集。从直观上讲，一个无凹、无洞的几何实体才能为凸集。有时目标函数可能在多个顶点处达到最大值，这时在这些顶点的凸组合上也达到最大值，则称这种线性规划问题有无限多个最优解。线性规划问题所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必定在某个顶点上得到。
1.基本概念
三角形、矩形、圆面等都是二维凸集，球体、长方体、圆柱体等是三维凸集。而圆周、圆环、空心球等都不是凸集。从直观上讲，一个无凹、无洞的几何实体才能为凸集。例如，图1-5中的（a）是凸集，（b）（c）均不是凸集。
图 1-5
2.几个定理
定理1-1线性规划问题的所有可行解的集合（即可行域）S= ｛X|AX=b，X≥0｝是凸集。
证明：要证明可行域S为凸集，只要证明S中任意两点连线上的一切点均在S内即可。
证明：①必要性。由基可行解的定义可知。
定理1-2线性规划问题的基可行解X对应于可行域S的顶点。
证明：为了不失一般性，假设基可行解X的前m个分量为正。故下面采用反证法分两步来讨论。
①若X不是基可行解，则它一定不是可行域S的顶点。
引理2若M是有界凸集，则任何一点X∈M可表示为的M顶点的凸组合。
定理1-3若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点达到最优。
有时目标函数可能在多个顶点处达到最大值，这时在这些顶点的凸组合上也达到最大值，则称这种线性规划问题有无限多个最优解。
另外，若可行域无界，则可能没有最优解，也可能有最优解。如果有最优解也一定可以在某个顶点上达到。
综合以上讨论的定理，可得到如下重要结论：
线性规划问题所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必定在某个顶点上得到。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
