线性规划问题

导数点为 $0$，Lagrange 乘数法。但是没有不等式约束。

$\max\,S=CX\tag{1.1}$

$AX=b\tag{1.2}$

$X\ge0\tag{1.3}$

1. 满足约束条件式 1.2 的 X，称为线性规划问题的解；
2. 满足约束条件式 1.2 与式 1.3 的 X，称为线性规划问题的可行解；
3. 满足目标函数式 1.1 的可行解 X，称为线性规划问题的最优解。

问题的可行解是凸集，若 $X_1$ 和 $X_2$ 都是问题的可行解，那么 $X_1,X_2$ 连线上的所有解，即：

$\forall \alpha \in [0,1],X=\alpha X_1+(1-\alpha)X_2$

都是问题的可行解。

成为顶点的条件：$X$ 是问题的可行解，$X_1,X_2$ 是问题的任意不同可行解，则：

$\forall \alpha\in(0,1),X\not=\alpha X_1+(1-\alpha)X_2$

为什么要求顶点，原因是最优解一定在顶点或者相邻顶点的连线。

若 $\forall X',CX\ge CX'$，而且，$\exists \alpha \in (0,1),X=\alpha X_1+(1-\alpha)X_2$，两端同乘 ，则 $CX=\alpha CX_1+(1-\alpha)CX_2$。

1. （不妨）$CX_1<CX_2$，则 $CX<CX_2$。矛盾。
2. $CX_1=CX_2$，则最优解在顶点的连线上。