线性规划

线性规划(Linear Programming,LP),指目标函数与约束条件皆为线性的最优化问题。

定义的矩阵和向量

线性规划通常可以用矩阵的形式表示为:

每个线性规划问题,称为原问题,都可以变换为一个对偶问题。上述问题的对偶问题为:

弱对偶定理:的任意一组解小于等于

强对偶定理:的最优解等于的最优解(可以取等)。

理解线性规划与对偶

经济学角度

原问题:企业 A 拥有种资源,计划生产种产品(有个变量),目标是最大化总收入,但使用资源的预算不能超过资源总数(有个约束);

对偶问题:企业 B 想要收购这些资源,需要确定种资源的报价(有个变量),目标是最小化总成本,但企业 A 只有在卖资源的收益不低于卖产品的时候才会同意卖资源(个约束)。

当然,你事先知道每种产品在单位数量下所耗资源的数量。

数学角度

原问题:给出的矩阵(每一列的向量表示该产品所耗资源的数量),向量(产品成本),向量(每项资源的总量)。求向量(生产产品的数量),在

的条件下,求

对于任意一个非负向量和可行解,有

而对于任意一个满足

的非负向量,有

这意味着,是原问题的一个上界。而最小的上界就是原问题目标函数的最优值。

把他们都置换一下,可以得到原问题的对偶问题:

对偶问题推论

我们知道会对偶成,且。那么对于的条件又如何对偶?

可以写成,那么就可以照常对偶。

对于,我们可以写成两个条件。这样会对偶出两个变量。而他们的系数是恰好相反的,因此可以合并成乘系数的形式。而没有的限制。因此会对偶出变量,且没有的限制。

解题技巧

接下来介绍一点在 LP 问题转化过程中会用到的技巧。

引理 1:若,那么。用不等式组的话说,如果左右加起来相等,那么每个等式都取等。反之亦然。

经典线性规划问题及其对偶

最大流最小割定理

最大流和最小割问题是一对对偶问题。

最大流问题

变量:

约束:

。(这里只是变量名,没有特别的运算意义)。

这里要说一点。原本的流量平衡是。在上面的约束中,把 2,3,4 的左边(实际上一共个条件)加起来,可以发现每条边被算了两次,和为。而一堆小于等于的数加起来是,那么这些数全都是。于是这个与流量平衡条件是等价的。

转化为对偶形式

转化为对偶问题时,约束条件会对偶成变量,而条件的上界(右边)是变量的系数。

对于对偶变量系数向量,则是一个变量在每个约束中的系数顺次组成的向量。对偶变量乘上系数向量就构成了对偶约束条件(有变量个)的左部,而右部由原问题的变量系数(最大化中的系数)构成。

设条件 1 的对偶变量为。条件 2,3,4 的对偶变量分别为

  • 对于变量,它对偶出来的约束条件是
  • 对于变量,它对偶出来的约束条件是
  • 对于变量,它对偶出来的约束条件是
  • 对于变量,它对偶出来的约束条件是
  • 对于变量,它对偶出来的约束条件是

上述都可以总结为,变量,它对偶出来的约束条件是

然后是变量,它对偶出来的约束条件是

于是我们就得到了对偶形式的问题:

变量:

约束:

转化为最小割问题

首先结合 1,4 可以得到。而,为了最小化答案,不妨设。并且只会取整数(可以证明存在这样的最优解)。那么我们定义,显然是原图的割。

,若,则有;其他情况,这说明割边的贡献是 1,则就是最小割的定义。因此对偶问题等价于最小割问题。

二分图最大权匹配

给出一个二分图,边权为,求最大权匹配。

原问题

变量:

约束:

容易证明只会取整数。因为是线性函数且始终过整点。因此最大值也一定是一个整点。另一个理解方式是,假设,连了一个爪,那么我们一定可以找到一条边使得其边权大于等于总边权和的,那么我们选这条边作为匹配即可。

因此上述 LP 形式与最大权匹配问题等价。

对偶问题

变量:

约束:

容易证明一定存在的解。证明简单,对于所有,设,那么把,把,答案不变。

因此上述对偶问题可以简化。

简化对偶问题

变量:

约束:

这就是我们熟悉的 KM 算法的形式了。

最大费用循环流

给出一个无源汇网络图,每条边容量是,费用是,求最大费用循环流。

原问题

变量:

约束:

注:条件 2(代表了个约束)可以使用相等来对偶。但我们将其简化为。因为左边的式子加起来是等于的,因此左边的所有数都是

对偶问题

变量:

约束:

.

注:其实如果使用等号来对偶的话,那么对偶的结果就是少了的限制,这也是说得通的,因为我们只关心(相对大小)。

事实上,上述不等式等价于。而在确定了的变量后,显然令能取到。因此我们可以不要的变量了。

简化对偶问题

变量:

事实上我们只关心的差,因此也是可以不要的。

写成也是等价的。因为在原问题中把等号松弛成或者都是一样的。从网络流的角度,相当于是反图和原图的最大费用循环流是对称的,也是相等的。

因此我们就得到了描述最大费用循环流的一个极简模型:

网络流算法

如何具体地求出最大费用循环流?我们分析对偶问题的目的是,将题目转化为的 LP 形式,然后对偶成最大费用循环流。因此接下来介绍如何求出最大费用循环流。

首先我们是有直接求最小(大)费用循环流的算法的,参见 最大费用循环流的论文 or 这道题。速度甚至比普通的有源汇费用流算法更快。

接下来我们讨论把循环流转化为有源汇的费用流的算法。

我们的大致思路是,先把所有正权边满流。这样可以发现一定是最大费用,但不一定满足流量平衡。那么我们把多于的流给退回去,求出最小费用的退流,就得到了最大费用循环流。

具体地,设

  1. 如果,则点流量平衡。

  2. 如果,那么点就多流出了的流量,需要收流。

  3. 如果,那么点就多流入了的流量,需要退流。

考虑建立新的图,新建源点和汇点。表示,原本的不平衡流减去从的流,就变成了最大费用循环流。

  • 对于的点,建立的边。
  • 对于的点,建立的边。
  • 对于原图上的边
    • 如果,那么就直接在新图上建立它,表示我可以退这么多流。
    • 否则,这条就在新图上建立它的反向边,容量不变,费用变成相反数。因为它只能加流。也可以理解为,在新图上建立它,然后让它满流。

然后在新图上求出最小费用最大流,再用不平衡最大费用减去它就是答案。

例题

Freelancer’s Dreams

种物品,第个物品买份有收益(可以买实数份)。问最少买多少份物品使得属性的和超过,属性的和超过

.

先写出原问题的 LP 形式:

变量:

约束:

对偶一下得到:

变量:

约束:

容易发现,约束就是半平面交,因此的凸函数,则也是凸的。则三分即可。

代码

ZJOI2013 防守战线

战线可以看作一个长度为的序列,现在需要在这个序列上建塔来防守敌兵,在序列第号位置上建一座塔有的花费,且一个位置可以建任意多的塔,费用累加计算。有个区间,在第个区间的范围内要建至少座塔。求最少花费。

.

表示第个位置上放了多少塔,表示前个位置上一共放了多少塔。可以写出原问题的 LP 形式为

变量:

约束:

首先我们可以把等于改成,与原问题等价。

,则我们把问题形式改成最大循环费用流的对偶形式:

变量:

约束:

其中

那么建模跑最大费用循环流即可。

代码

Cow and Exercise

给定个点的带权有向简单图,次询问(独立),每次给定,可以把每条边增加一定的长度,但总共至多增加,问点到点的最短路最大能是多少。

单组询问

首先写出原问题的 LP 形式。对于的询问:

发现这个形式不太容易转化为最大费用循环流的模型。因为第二个条件比较烦。

则考虑二分,即求出最小代价使得最短路长度

那么显然可以不要了,我们要求的就是

这个可以用最大费用循环流解决。

多组询问

考虑到増广路算法中最大流对应最大费用的函数是凸的,因此我们把这个函数求出来。

具体地,我们发现上述模型在去掉了连到容量为的边后,实际上就是一个最大费用最大流的问题。可以使用増广路算法。

而最大流显然不会超过。因此设表示最大流为时的最大费用。这样很容易求。在増广的时侯每次只增加一个单位的流就可以求出。那么原图的最大流就是

因此我们的问题就变成了,二分,判断是否成立。由于这个函数也是凸的,无脑是可以的。

更高明的做法是把上式化为。这时相当于,于是做一次三分(导数上二分)即可。时间复杂度

代码

小结

在解决线性规划的问题中,要灵活运用对偶问题以及经典模型求解。

参考文献

https://www.zhihu.com/question/26658861/answer/631753103

https://zh.wikipedia.org/zh/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92