线性规划问题

问题

LP(Linear Programming)问题即线性规划问题, 本质是在满足一组线性约束条件的前提下, 令某个线性目标函数取到最大或者最小值. 其数学表达式为\(\max{c^T x}\), 当\(Ax<b\), \(x\geq 0\), 其中, \(x\in R^n\)是一切决策变量的向量, \(c\)是目标函的系数, \(A\in R^{m\times n}, b\in R^m\)用来刻画全部约束. 上面的读起来可能比较压缩... 所以写为展开式:

\[ \max \sum_{i=1}^n c_ix_i, \text{满足}\sum_{i=1}^n A_{ji}x_i \leq b_j (1\leq j\leq m)\text{以及}x_i\geq 0(1\leq i\leq n) \]

4个核心事实

1.LP被归为\(\mathcal{P}\)-complete. 意思是, 只要某个问题存在多项式时间的算法, 就能够把它可化为某个线性规划问题. 2.在理论层面, 任何线性规划问题都能在多项式时间内求得任意精度的最优解. 3.在工程实践中, 各种商业或者开源求解器已经把这些理论算法优化到极高效率, 因此可以完全把LP当做一个黑盒直接调用. 4.围绕LP的发展形成了一套极其丰富的理论体系, 是后面离散优化课程的内容.

首先, 在这个章节开始之前, 需要先做一个假设, 只要我们把一个问题写成含有多项式个变量\(n\)和约束\(m\), 就可以念咒语一般在多项式时间内得到最优解, 而不再纠结具体的算法. 因为根据上面的第一个核心事实, 它理论上可以解决所有属于\(\mathcal{P}\)的任务, 但是在现实中我们更常面对的是问题"不确定是否在\(\mathcal{P}\)里面". 这些难问题往往无法在多项式规模内直接写成LP, 却仍然希望得到近似解, 所以, LP是否还能派上用场呢?

我们将目标精确化为所谓的\(\alpha\)-approximation: 给定一个难任务T的实例I, 算法输出方案\(S(I)\), 其结果\(\text{val}(S)\)满足\(\alpha\cdot \text{OPT}(I)\leq \text{val}(S) \leq \text{OPT}(I)\), 其中, \(\text{OPT}(I)\)是最优结果, \(0< \alpha \leq 1\)是近似因子. 如果算法带有随机性, 则要求该不等式在高概率或者期望意义上成立.