线性规划是指在一组线性约束下寻求线性目标函数的最优解。
当问题形式为
AX<B ，X>=0 可行域为凸多面体
求<C,X>
一类不等式约束时
几何上理解为在凸多面体中寻求向量C（目标函数的梯度，函数值增加速度最快的方向）所指向的方向的,与C正交的超平面（目标函数值相同）与该多面体最远的交点。
当问题形式为
AX=B，X>=0
求<C,X>
一类不等式约束时，也即线性规划问题的标准型
几何上理解为被X>0限制的线性簇中，寻求向量C所指向的方向的,与C正交的超平面与该线性簇最远的的交点。这种线性簇的极点一定是几个维度为0的（被X>0限制），叫做基本可行解，也即几何上可行域的极点就是代数问题中的基本可行解。
至于线性规划基本定理，存在可行解，一定存在基本可行解，存在最优可行解，一定存在最优基本可行解，可以翻译为这样的几何语言：被限制的线性簇非空，一定有极点（顶点），目标函数的梯度方向（最优方向）指向极点，一定有极点是最远点（极值点）。
因为基本可行解与极点等价，又由线性规划基本定理可知如果存在最优可行解的话，一定是基本可行解中的某一个，所以逐个筛选极点，则可选取极值点。单纯形法在代数理解上实现了基本可行解的转换，它的几何意义就是极点间的跳跃。
网友评论