单纯形算法学习笔记

算法介绍

从 Po 姐那里看到的 wyfcyx 大佬的《线性规划与单纯形算法》，推荐去看一看。

以下内容来自于那个课件。

规定一个线性规划的标准型：

在条件 (Ax leqslant b) 下，最大化 (c^T x)。

其中各字符均为矩阵，其意义如下（(n) 为变量数，(m) 为限制条件数）：

(A)：限制条件的系数矩阵，大小为 (m times n)。

(x)：变量矩阵，大小为 (n times 1)。

(b)：限制条件的常数矩阵，大小为 (m times 1)。

(c)：目标函数的系数矩阵，大小为 (n times 1)。

下面考虑如何把不是标准型的线性规划转化为标准型。

• 目标函数最小化：所有系数取反，转化为最大化，最后对答案取反。
• 限制条件为大于等于：系数取反。
• 限制条件为等于：拆成大于等于、小于等于两个限制。
• 变量限制条件为 (x geqslant a)：转化为(x' geqslant 0, x' = x - a)。
• 变量限制条件为 (x leqslant a)：转化为(x' geqslant 0, x' = a- x)。
• 变量无限制：转化为 (x' geqslant 0, x'' geqslant 0, x = x' - x'')。

线性规划的松弛型：

给第i个变量添加辅助变量 (x_{n + i})，把不等号转化为等号。

[x{n + i} + sum{j = 1}^{n} A_{i, j}x_j = bi, x{n + i} geqslant 0]

现在，定义一些名称：

基变量：把标准型转化为松弛型的辅助变量，有 (m) 个，其集合记为 (B)。

原变量：原来的变量，有 (n) 个，其集合记为 (N)。（这个在那个课件里叫“非基变量”）

可行解：使所有限制满足的一组原变量。

最优解：使目标函数最优的一组可行解。

算法过程：

先假定所有的原变量为 (0) 为一组可行解，考虑目标函数中某个原变量，若其系数大于 (0) ，那我们增大那个原变量会使目标函数值增大。

若所有原变量的系数均小于等于 (0)，则当前解为最优解，目标函数值的最大值即为目标函数的常数。

若我们已经找到了一个系数大于 (0) 的原变量，假设是第 (e) 个，记为 (x_{N_e})。

关于它的限制有：

[x_{Bi} + sum{j = 1}^{n} A{i, j} x{N_j} = b_i]

若 (A_{i, e} > 0)，则有：

[A_{i, e} leqslant frac{bi}{A{i, e}}]

记找到的最紧的限制条件为第 (l) 个，其对应基变量为 (x_{B_l})。

之后进行转轴操作，即交换找到的基变量与原变量，同时进行换元之类的操作使得新基变量的系数为 (1)。操作完毕后，我们发现，目标函数的常数项增大了。

注意：选择原变量时，应选择编号最小的，否则容易被特殊数据卡出死循环。

转轴操作的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void (int l, int e) {
 b[l] /= A[l][e];
 for (int i = 1; i <= n; i++) if (i != e) A[l][i] /= A[l][e];
   A[l][e] = 1 / A[l][e];
   for (int i = 1; i <= m; i++) {
      if (i != l && abs(A[i][e]) > EPS) {
            b[i] -= A[i][e] * b[l];
          for (int j = 1; j <= n; j++) if (j != e) A[i][j] -= A[i][e] * A[l][j];
         A[i][e] = -A[i][e] * A[l][e];
        }
    }
    v += c[e] * b[l];
    for (int i = 1; i <= n; i++) if (i != e) c[i] -= c[e] * A[l][i];
   c[e] = -c[e] * A[l][e];
}

一次转轴操作的时间复杂度为 (O(nm))。

之后，我们只要能转轴就转轴，不能时，目标函数的常数项就是答案。

再说一个对偶原理，可以用于转化线性规划到标准型（很常用的样子），其内容如下：

有两个线性规划：

• 在条件 (Ax leqslant b)下，最大化 (c^T x)。

• 在条件 (A^Ty geqslant c)下，最小化 (b^T y)。

它们的最优解相同。

模板题

原课件：单纯形算法只能做裸题！（以及网络流相关的黑科技。。。）

BZOJ 1061

BZOJ 3112