单纯形算法学习笔记

算法介绍

从 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 = b_i, \ x_{n + i} \geqslant 0\]

现在,定义一些名称:

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

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

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

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

算法过程:

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

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

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

关于它的限制有:

\[x_{B_i} + \sum_{j = 1}^{n} A_{i, j} x_{N_j} = b_i\]

\(A_{i, e} > 0\),则有:

\[A_{i, e} \leqslant \frac{b_i}{A_{i, e}}\]

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

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

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

转轴操作的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void pivot(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