【优化理论与方法】线性规划的基本定理

一、凸集

上式表示：   连接凸集内任意两点的线段在凸集内。            

   D表示：      连接两点的线段上所有的点

凸集图片

非凸集

二、凸组合

三、极点

四、线性规划的基本定理

定理1.1：若标准线性规划问题存在可行域，则其可行域是凸集。

定理1.2： 标准线性规划问题的可行解 为基可行解的充分必要条件是

的正分量所对应的 系数列向量线性无关。

定理1.3：    X 为标准线性规划问题的基可行解的充分必要条件是    X为标准线性规划问题可行域的极点。

定理1.4：若标准线性规划问题有可行解，则必有基可行解。

定理1.5： 若标准线性规划问题存在最优解，则必存在 基可行解为最优解

注意：

不是所有基可行解都最优，但是至少存在一个

有可行解=>有基可行解=>某个基可行解最优

可以在所有的基可行解里面找一个最有解

总结：

从定理1.5的证明过程可知，若目标函数在多个极点上去的最优值，则在这些极点的凸组合上也去得最优值。

由定理1.5的结论可知，仇线性规划问题的最优解，可用穷取法考察基可行解处的函数值来完成，虽然基可行解的个数不超过

个，但当m，n较大时穷举法的工作量非常之大。

【优化理论与方法】线性规划的基本定理

一、凸集

上式表示：   连接凸集内任意两点的线段在凸集内。            

   D表示：      连接两点的线段上所有的点

凸集图片

非凸集

二、凸组合

三、极点

四、线性规划的基本定理

定理1.1：若标准线性规划问题存在可行域，则其可行域是凸集。

定理1.2： 标准线性规划问题的可行解 为基可行解的充分必要条件是

的正分量所对应的 系数列向量线性无关。

定理1.3：    X 为标准线性规划问题的基可行解的充分必要条件是    X为标准线性规划问题可行域的极点。

定理1.4：若标准线性规划问题有可行解，则必有基可行解。

定理1.5： 若标准线性规划问题存在最优解，则必存在 基可行解为最优解

注意：

不是所有基可行解都最优，但是至少存在一个

有可行解=>有基可行解=>某个基可行解最优

可以在所有的基可行解里面找一个最有解

总结：

从定理1.5的证明过程可知，若目标函数在多个极点上去的最优值，则在这些极点的凸组合上也去得最优值。

由定理1.5的结论可知，仇线性规划问题的最优解，可用穷取法考察基可行解处的函数值来完成，虽然基可行解的个数不超过

个，但当m，n较大时穷举法的工作量非常之大。