线性规划

阐述

$$\min c^Tx,~\mathrm{s.t.}~x\in P$$

$P$ 是一个多面体，

• 标准形式：$Ax=b,x\ge0$
• 几何形式：$Ax\ge b$

其中 $c,x\in\mathbb R^n, b\in\mathbb R^m, A\in\mathbb R^{m\times n}$。

形式化

一个好的线性规划描述应该具有比较少的变量数量和约束数量，并且矩阵 A 尽可能稀疏。

非标准情形

• 最大化：翻转 $c$ 的符号
• 变量 $x_i$ 可正可负：替换为 $x_i^+-x_i^-$
• 相等约束：替换为两个等于的约束
• ……

实例

性质

凸性

• 凸组合：$\sum_i\lambda_iv_i$，其中 $\sum_i\lambda_i=1$ 且 $\lambda_i\ge0$
• 集合内若干个点进行凸组合之后仍然在集合内的称为凸集
• 凸集的交集仍然是凸集

几何结构

• 超平面：$\{x:a^Tx=b\}$
• 半空间：$\{x:a^Tx\ge b\}$
• 多面体（几何形式）：有限多半空间的交集 $\{x:Ax\ge b\}$
  • 线性规划的可行域是一个凸集
  • 如果这个多面体是有界的，则称为「多胞体」。
  • 多胞体上任何一个点都是顶点的凸组合。
• 多面体（标准形式）：$\{x:Ax=b,x\ge0\}$
  • 此处 $A$ 必须为满行秩的，$m<n$
  • 此多面体是 $\mathbb R^{n-m}$ 维度子空间的一部分
• 极值点：不存在两个不同的点 $y,z$ 使得 $x=\lambda y+(1-\lambda)z,0<\lambda<1$
• 顶点：该点是 $\min c^Tx;x\in P$ 的唯一极小值

基本可行解（几何形式）

对于几何形式的多面体 $P:Ax\ge b$，记 $I=\{i|a_i^Tx=b_i\}$ 是活跃的约束，则

• 基本解：在 $x$ 处，由 $\{a_i,i\in I\}$ 张成的空间为 $\mathbb R^n$
• 基本可行解：$x\in P$
• 简并：多于 $n$ 个约束是活跃的

极值点、顶点、基本可行解这三者等价。

一个非空的多面体是否含有极值点？有如下定理：对于一个非空的多面体来说，下列等价：

• $P$ 有至少一个极值点
• $P$ 不含有直线
• $A$ 中可以找出 $n$ 个线性无关的向量

基本可行解（标准形式）

对于标准形式的多面体 $P:\{x|Ax=b,x\ge0\}$，

• 基本解：$Ax=b$，并且存在一组指标 $B$，$A[:,B]$ 是可逆矩阵，并且 $x$ 除了 $x_B$ 之外的部分都是 0
• 基本可行解：$x\ge 0$
• 简并：$x$ 包含多于 $n-m$ 个 0（也可以认为是多于 $n$ 个约束）

解的存在性

有界的非空多面体，或者用标准形式定义的非空多面体，都有极值点。

对于有极值点的多面体来说，要么问题无界，要么至少一个最优解是极值点。

一个简单的算法是，生成所有的基本可行解，然后逐一验证他们是不是可行的，并找出最优解。

上述关系可以表示为：

$$A_Bx_B+A_Nx_N=b$$

也即

$$x_B=A_B^{-1}b-A_B^{-1}A_Nx_N$$

若定义 $p=c_BA_B^{-1}$，则可以把目标函数写成

$$c^Tx=p^Tb+(c-p^TA)x$$

当 $c-p^TA\ge0$ 时，系统就达到最优，且此时 $c^Tx=p^Tb$。

相关内容

参考文献