线性规划入门·对偶定理

$\rm{Preface:} About~Duality~Theorm$

首先要说的是线性规划对偶定理。我们朴素的线性规划大致如下:
$$
\text{最大化}\quad \sum c_ix_i \quad(i = 1, 2,3 \cdots n) \\
\text{满足约束} \quad \sum \limits_{j=1}^{n} a_{i,j}x_{j} \leq b_i\quad (i = 1,2,3\cdots m) \\ \qquad \qquad \qquad \quad x_j \geq 0\quad (j=1,2,3\cdots n)
$$
那么我们称它的对偶为形如下的线性规划:
$$
\text{最小化}\quad \sum b_iy_i \quad(i = 1, 2,3 \cdots m) \\
\text{满足约束} \quad \sum \limits_{j=1}^{m} a_{i,j}y_{j} \geq c_i\quad (i = 1,2,3\cdots n) \\ \qquad \qquad \qquad \quad y_j \geq 0\quad (j=1,2,3\cdots m)
$$
换做矩阵表示就会是这样:
$$
\text{最小化}\quad \boldsymbol{b^Ty} \\
\text{满足约束} \quad A^T\boldsymbol{y\geq c} \\\
\it{\qquad \qquad \quad} \boldsymbol {y} \geq 0
$$
那其实比较显然的是,我们原来线性规划中的约束向量与目标函数里的系数向量交换,目标函数的最大化变成了最小化。现在我们思考对偶的意义。

首先假设我们有这么一个线性规划:
$$
\text{最小化}\quad \sum b_iy_i \quad(i = 1, 2,3 \cdots m) \\
\text{满足约束} \quad \sum \limits_{j=1}^{m} a_{i,j}y_{j} \geq c_i\quad (i = 1,2,3\cdots n) \\ \qquad \qquad \qquad \quad y_j \geq 0\quad (j=1,2,3\cdots m)
$$
其实就是上面那个

我们的目的其实等价于确定目标函数的下界。我们观察每一组约束,假设有一组约束是
$$
\quad \sum \limits_{j=1}^{m} a_{p,j}y_{j} \geq c_p\quad (i = 1,2,3\cdots n)
$$
并且我们保证有:
$$
\forall a_{p,j} \in \boldsymbol{a_p},\forall b_i \in{\boldsymbol{b}},\quad i=j \Longrightarrow b_i\geq a_{p,j}
$$
好像写的很不规矩……意思就是对应项的系数,目标函数都比这个约束里的大。

那么因为$\forall x\geq 0$,所以我们可以保证目标函数的最小值一定会是$c_p$。这个结论是显然的。

更进一步,那么我们最后确定的下界一定会是这样的(此处一点也不严谨地使用了$\Omega$符号):
$$
\Omega(\rm{Aim}) = \it{\sum \limits_{j = 1}^{n}t_j\cdot\sum\limits_{i=1}^{n}\sum \limits_{k=1}^{m}a_{i,k}y_k}\\\
\forall t_j \geq 0
$$

而因为我们对于原来的约束有
$$
\quad \sum \limits_{j=1}^{m} a_{i,j}y_{j} \geq c_i\quad (i = 1,2,3\cdots n)
$$
所以我们将其代回我们画好的式子里面:
$$
\Omega(\rm{Aim}) \geq \it{\sum\limits_{j=1}^{n}t_jc_j}
$$
那么……目标函数的下界就变成了一个和式的上界——又变成了一个求解目标函数最大值的问题。

那么这或许感性证明了对偶定理的正确性?

$\rm{Afterword:}Some~Typical~Problem$

没见过吧,一篇文章只有前言和总结

其实博主就是在疯狂划水/摸鱼

其实常见的对偶问题有很多,博主功力不够,于是只能整理一个比较形式化的结论:

$~$最大流问题

形式化的最大流问题的线性规划如下:
$$
\text{最大化}\quad \quad \quad ~f_{s\to t} \quad ~ \quad \quad \quad \quad \quad \quad \\
\text{满足约束} \quad \quad f_{u\to v} \leq L_{u \to v}\qquad (u,v) \in E \\
\qquad \quad \quad ~\sum\limits_{u}f_{u \to v} = \sum\limits_{v}f_{v \to u}\qquad u\in V
\\ \qquad \qquad \qquad ~~\quad f_{u\to v} \geq 0 \qquad (u,v) \in E ~\cup \text{e(s,t)}
$$
其中$e(u,v)$表示链接$u,v$的路径集合,$f$表示流量,$L$表示容量(Limit)。

其对偶过去就会是:
$$
\text{最小化}\quad \quad \quad \sum_{(u,v)\in E}L_{u\to v}d_{u \to v} \quad ~ \quad \quad \quad\\
\text{满足约束} \quad \quad d_{u\to v}-p_u+p_v \geq 0\qquad (u,v) \in E \\
\qquad \quad \quad \quad \quad \quad ~~p_s - p_t \geq 1\qquad u\in V
\\ \qquad \qquad \qquad \quad p_i,d_{i\to j}\in\{0,1\} ~\qquad
$$
里面$d_{i\to j}$表示$i \to j$这条边有没有被割,同时假设我们割完之后,原来的图分成了两部分$S$和$T$,那么会有$p_i = [i \in S]$。这个限制是为了保证割的逻辑性——所有的割边都连接着$S,T$两个集合,且源点和汇点在不同的集合。

emmm我实在不想再整理了(写式子太麻烦),等什么时候我退完役闲下来再说吧233

$\rm{Reference}$

  • $[1]$ :2016国家集训队论文《浅谈线性规划与对偶问题》董克凡· $^{^{[\nearrow]}}$ 提取码:vua4
-------------本文结束感谢您的阅读-------------