线性规划中可行域为什么一定是凸的--证明

线性规划中可行域为什么一定是凸的--证明

引用

CSDN

1.

https://m.blog.csdn.net/fair_li/article/details/142352219

线性规划中的凸性证明

线性规划中可行域是凸的，这是自然能够想到和容易理解的道理。直观上，线性约束定义的可行域是由半平面的交集构成的，这些半平面的交集总是形成凸区域。

这么一个自然想到、容易理解的道理，怎么从数学上完备地证明它？下面的内容为此作答。

准备知识：

凸集的定义：如果集合$C$中任意两点$X_1$和$X_2$，其连线上的所有点也都在集合$C$中，称$C$为凸集.

为了更好地理解凸集，下面给出一些凸集和凹集的示例：

线性规划的标准型：

$$max \quad z= \sum_{j=1}^{n}c_{j}x_j \
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$ 在可行域内。这证明了连线上的任意点均在可行域内，即可行域是凸集。

证毕！

参考资料：

• 胡运权主编的第五版《运筹学教程》