单纯形算法学习笔记

算法介绍

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

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

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

在条件 AxbAx \leqslant b 下,最大化 cTxc^T x

其中各字符均为矩阵,其意义如下(nn 为变量数,mm 为限制条件数):

AA:限制条件的系数矩阵,大小为 m×nm \times n

xx:变量矩阵,大小为 n×1n \times 1

bb:限制条件的常数矩阵,大小为 m×1m \times 1

cc:目标函数的系数矩阵,大小为 n×1n \times 1

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

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

线性规划的松弛型

给第i个变量添加辅助变量 xn+ix_{n + i},把不等号转化为等号。

xn+i+j=1nAi,jxj=bi, xn+i0x_{n + i} + \sum_{j = 1}^{n} A_{i, j}x_j = b_i, \ x_{n + i} \geqslant 0

现在,定义一些名称:

基变量:把标准型转化为松弛型的辅助变量,有 mm 个,其集合记为 BB

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

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

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

算法过程:

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

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

若我们已经找到了一个系数大于 00 的原变量,假设是第 ee 个,记为 xNex_{N_e}

关于它的限制有:

xBi+j=1nAi,jxNj=bix_{B_i} + \sum_{j = 1}^{n} A_{i, j} x_{N_j} = b_i

Ai,e>0A_{i, e} > 0,则有:

Ai,ebiAi,eA_{i, e} \leqslant \frac{b_i}{A_{i, e}}

记找到的最紧的限制条件为第 ll 个,其对应基变量为 xBlx_{B_l}

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

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

转轴操作的代码:

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)O(nm)

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

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

有两个线性规划:

  • 在条件 AxbAx \leqslant b下,最大化 cTxc^T x

  • 在条件 ATycA^Ty \geqslant c下,最小化 bTyb^T y

它们的最优解相同。

模板题

原课件:单纯形算法只能做裸题!(以及网络流相关的黑科技。。。)

【NOI 2008】志愿者招募 - Luogu 3980

【ZJOI 2013】防守阵线 - Luogu 3337