Question

简述线性规划模型中极点与最优解的关系

Answer 1

问：简述线性规划模型中极点与最优解的关系

答：线性规划问题中的最优解线性规划问题存在最优解的充要条件，其中为可行域的方向。线性规划问题的最优解在某个极点上取得。图上的极点集与图的基本可行解​​​​​​​集是等价的，即可以通过求解基本可行解集得到极点集，进而得到最优解。

答：解的存在性定理。因为凸函数的最大值必在边界处取得，凹函数的最小值必在边界处取得。因此线性规划的目标函数的最小值和最大值都在边界处取得。因此线性规划的最优解(如果有的话)一定能在极点处取得(当有多个最优解时，最优解的集合一定包含某个极点)。在两种情况下，LP无最优解：