线性规划中可行域为什么一定是凸的--证明
线性规划中可行域为什么一定是凸的--证明
线性规划中的凸性证明
线性规划中可行域是凸的，这是自然能够想到和容易理解的道理。直观上，线性约束定义的可行域是由半平面的交集构成的，这些半平面的交集总是形成凸区域。
这么一个自然想到、容易理解的道理，怎么从数学上完备地证明它？下面的内容为此作答。
准备知识：
凸集的定义：如果集合$C$中任意两点$X_1$和$X_2$，其连线上的所有点也都在集合$C$中，称$C$为凸集。
为了更好地理解凸集，下面给出一些凸集和凹集的示例：
线性规划的标准型：
$$
\text{max} \quad z= \sum_{j=1}^{n}c_{j}x_j \
\text{s.t.} \left{
\begin{array}{l}
{\sum_{j=1}^{n}a_{ij}x_j=b_j} \
x_j \ge 0 \
\end{array}
\right.
$$
证明
命题：如果线性规划中存在可行解，则可行解组成的可行域是凸集。
证明思路：任意假设两个可行解，证明其连线上的所有点仍属于可行域，即满足约束。
证明过程
步骤一：设任意两点，并给出满足约束的方程
- 设$X_1=(x_{11},x_{12},\dots,x_{1n})^T$,$X_2=(x_{21},x_{22},\dots,x_{2n})^T$为可行域内任意两点，其满足
$$
\left{
\begin{array}{l}
\sum_{j=1}^n a_{ij}x_{1j}=b_j \
\sum_{j=1}^n a_{ij}x_{2j}=b_j \
\end{array}
\right.
$$
步骤二：设连线上的任意一点，并给出与两点的关系方程
- 连线上的任意点 $X=(x_{1},x_{2},\dots,x_{n})^T$ 的表示
$$
X=k(X_1-X_2)+X_2, \quad 0 \leq k \leq1
$$
这一步如果不好理解，可以看下面的解释：
步骤三：判断 $X$ 是否满足约束条件
$$
\begin{aligned}
\sum_{j=1}^n a_{ij}x_{j}&=\sum_{j=1}^n a_{ij}(k(x_{1j}-x_{2j})+x_{2j}) \
&= k\sum_{j=1}^n a_{ij} x_{1j} - k\sum_{j=1}^n a_{ij} x_{2j} + \sum_{j=1}^n a_{ij} x_{2j} \
&= k b_j - k b_j + b_j \
& = b_j
\end{aligned}
$$
因此，$X$ 在可行域内。这证明了连线上的任意点均在可行域内，即可行域是凸集。
证毕！
参考资料：
- 胡运权主编的第五版《运筹学教程》