【学习笔记】线性规划对偶定理

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

线性规划对偶定理:我们朴素的线性规划大致如下:

那么我们称它的对偶为形如下的线性规划:

换做矩阵表示就会是这样:

那其实比较显然的是,我们原来线性规划中的约束向量与目标函数里的系数向量交换,目标函数的最大化变成了最小化。现在我们思考对偶的意义。

首先假设我们有这么一个线性规划:

其实就是上面那个

我们的目的其实等价于确定目标函数的下界。我们观察每一组约束,假设有一组约束是

并且我们保证有:

好像写的很不规矩……意思就是对应项的系数,目标函数都比这个约束里的大。

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

更进一步,那么我们最后确定的下界一定会是这样的(此处一点也不严谨地使用了$\Omega$符号):

而因为我们对于原来的约束有

所以我们将其代回我们画好的式子里面:

那么……目标函数的下界就变成了一个和式的上界——又变成了一个求解目标函数最大值的问题。

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

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

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

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

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

$~$最大流问题

形式化的最大流问题的线性规划如下:

其中$e(u,v)$表示链接$u,v$的路径集合,$f$表示流量,$L$表示容量(Limit)。

其对偶过去就会是:

里面$d_{i\to j}$表示$i \to j$这条边有没有被割,同时假设我们割完之后,原来的图分成了两部分$S$和$T$,那么会有$p_i = [i \in S]$。这个限制是为了保证割的逻辑性——所有的割边都连接着$S,T$两个集合,且源点和汇点在不同的集合。

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

$\rm{Reference}$

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