单纯形法之几何直观简述

单纯形法解决如下问题：
给定一个 $N$ 维实数向量空间 $\{x_i\}$ ，再给定一组线性组合等式约束条件
$\sum_{i=1}^pc_{ij}x_i=b_j \tag{1}$
和一组线性组合不等式的约束条件
$\sum_{i=1}^qu_{ij}x_i\le v_j \tag{2}$
求线性组合式 $s=\sum_ik_ic_i$ 的最小值 $\min s$ 。

几何直观如下：

$N$ 维实数向量空间为欧几里德空间 $R^n$
在 $R^n$ 中的线性组合等式(1)对应了一个线性子空间 $V$ ，维度为 $m=n-p$ ，子空间是一个超平面。
子空间 $V$ （超平面）中的不等式约束可以对应于一个超多面体，超多面体内为可行解（同时满足等式条件和不等式条件），超多面体外部仅满足等式条件，超多面体边界处至少存在一个不等式的等号成立。
理论上可以证明，满足线性组合最小值条件的可行解，或者不存在（如超多面体无下界），或者超多面体的某个顶点为最小值的解，同或者最小值解恰好是一条超多面提的一个棱边、或者一个边界面上（等等）。
最小化目标线性组合函数确定了一个平行超平面族，每一个特定的组合值决定了一个超平面，该值 $s=0$ 时超平面过原点，该值也等于超平面距离原点的矢量距离（带符号）。使用这一族超平面与约束条件超多面体相交，其中 $s$ 最小时显然或者落在超多面体的顶点或者棱边或者边界面（边界体等等）上。

单纯形法之几何直观简述

推荐阅读更多精彩内容