线性规划

Introduction

线性规划，粗糙地看来就是对于线性的约束(等、不等)和线性的目标求极值。

可以写成以下形式:

1. 标准形

   \[\forall i, \sum_{j} a_{i, j}x_{j} \le b_i \\ \forall i, x_i \ge 0 \\ \max \sum_{i} c_ix_i \]

   亦(向量形式)

   \[AX \le B \\ X \ge 0 \\ \max C^{T}X \]

2. 松弛形

   \[AX=B \\ X \ge 0 \\ \max C^{T}X \]

   关于标准形与松弛形的转化：
   对于小于号，添加一个系数为负的自变量，
   大于号则系数为正。

   \[\sum_{j} a_{i, j}x_{j} \le b_i \\ \Leftrightarrow \sum_{j} a_{i, j}x_{j} + x_{new} = b_i x_{new} \ge 0 \]

3. 单纯形

   \[\forall i \in [1, m], x_{n+i} = b_i-\sum_{j=1}^{n} a_{i, j}x_j \\ \forall i \in [1, n+m], x_i \ge 0 \\ \max \sum_{j=1}^{n}c_ix_i \]

   我们称\(x_{1}\)~\(x_{n}\)为非基本变量，\(x_{n+1}\)到\(x_{n+m}\)为基本变量
   事实上是松弛形的另一种写法

单纯形法

若\(\forall i,b_i>0\)
我们对于非基本变量全部取0是一个可行解，
当此时\(\forall i, c_i \le 0\)时达到最优，

如果并非最优，我们要更换一组基本变量，

\[x_{n+l} = b_l - \sum_{j=1, j \neq e}^{n}a_{l, j}x_j - a_{l, e}x_e \\ \Rightarrow x_e = \frac{1}{a_{l, e}}(b_l - \sum_{j=1, j \neq e}^{n} a_{l, j}x_j - x_{n+l}) \]

方法是选出\(c_e\)最大的非基变量\(x_{e}\)，
用\(a_{l, e} > 0\)且\(\frac{b_l}{a_{l, e}}\)最小的\(x_{n+l}\)替换，
这样可以保证变化后\(b_i \ge 0\),
同时使目标变化最大(\(c_{e}\frac{b_l}{a_{l,e}}\))
上述操作成为转轴

若初始时\(b_i < 0\)，找到一个负的\(a_{i, j}\)对其转轴，
不知道为什么一定会停下来。

对偶

我们有一组线性规划互为对偶:

\[AX \le B \\ X \ge 0 \\ \max C^{T}X \\ \]

\[A^{T}Y \ge C \\ Y \ge 0 \\ \min B^{T}Y \]

则

\[\max C^{T}X = \min B^{T}Y \]

大概长成这样:

	\(x_{1}\)	\(x_{2}\)	\(\cdots\)	\(x_{n}\)
\(y_1\)	\(a_{1, 1}\)	\(a_{1, 2}\)	\(\cdots\)	\(a_{1, n}\)	\(b_{1}\)
\(y_2\)	\(a_{2, 1}\)	\(a_{2, 2}\)	\(\cdots\)	\(a_{2, n}\)	\(b_{2}\)
\(\cdots\)	\(\cdots\)	\(\cdots\)	\(\cdots\)	\(\cdots\)	\(\cdots\)
\(y_m\)	\(a_{m, 1}\)	\(a_{m, 2}\)	\(\cdots\)	\(a_{m, n}\)	\(b_{m}\)
	\(c_{1}\)	\(c_{2}\)	\(\cdots\)	\(c_n\)	\(z\)

网络流模型

网络流本质也是一类线性规划问题，有部分线性规划问题可以通过网络流解决

流量守恒

对于线性规划问题我们写成松弛形式，
再通过线性变换使得每个变量只出现两次，符号相反，
那么我们将这些变量视为弧，将限制视为点，根据流量守恒构图。

对于区间类问题来说通常有变量连续出现的情况，
那么我们将相邻两个限制相减，
最后新添一条最后限制取反的限制，开头限制不变，
通常可以得到美妙的结果。

对偶

对于费用流，流量为\(f_{u,v}\)，最大流量为\(c_{u,v}\),代价为\(w_{u, v}\)，每个点的流出减去流入\(\le b_{u}\),我们有:

\[\forall u, \sum_{v} f_{v, u} - \sum_{v}f_{u, v} \ge -b_{u} \\ \forall u, v, -f_{u, v} \ge -c_{u, v} \\ \forall u, v, f_{u, v} \ge 0 \\ \min \sum_{u, v} f_{u, v}w_{u, v} \]

令对于边的对偶变量为\(z_{u, v}\)，对于点的为\(p_{u}\),对偶得到

\[\forall u, v, p_v - p_u - z_{u, v} \le w_{u, v} \\ \forall u, v, z_{u, v} \ge 0 \\ \forall u, p_u \ge 0 \\ \max \sum_{u} -p_{u}b_{u} - \sum_{u, v} z_{u, v}c_{u, v} \]

因为\(c_{u, v} \ge 0\),且\(z_{u, v}\)只有一条限制，我们令其取下界，得\(z_{u, v} = \max(0, p_v - p_u - w_{u, v})\)

\[\max \sum_{u} -p_u b_u - \sum_{u, v} c_{u, v} \max(0, p_v - p_u - w_{u, v}) \\ \Leftrightarrow -\min \sum_{u} p_u b_u + \sum{u, v} c_{u, v} \max(0, p_v - p_u - w_{u, v}) \]

对于一个线性规划问题，若能化为上述形式，则必定可以通过费用流解决（只是方案难搞...

我们可以通过在目标式中添加若干\(\infty\)的项来做到加入限制

参考资料

单纯形法学习笔记 by p_b_p_b
《再探线性规划对偶在信息学竞赛中的应用》 - 学习笔记 by p_b_p_b

2021国家集训队论文