第1章 线性规划及单纯形法-线性规划及几何意义.ppt

第2节 线性规划问题的几何意义 2.1 基本概念1. 凸集 2.2 几个定理定理1 若线性规划问题存在可行域，则其可行域 是凸集 引理1 线性规划问题的可行解X=(x1,x2,…，xn)T为基可行解的充要条件是X的正分量所对应的系数列向量线性无关。 即： X是可行解, X是基可行解←→X的正分量对应的系数列向量线性无关 定理2 线性规划问题的基可行解X对应于可行域D的顶点。 即： X是可行解, X是可行域顶点←→X是基可行解 X不是可行域顶点←→X不是基可行解 引理2 若K是有界凸集，则任何一点X∈K可表示为K的顶点的凸组合。定理3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。命题线性规划问题的目标函数若在多个顶点处达到最大值，则在这些顶点的凸组合上也达到最大值。 * 2. 凸组合 3. 顶点 *