Wuyanru's blog
0%

[还没写完] 线性规划初探

发表于 分类于 ，

模拟赛感觉考了好几次，受不了了学一下。

与其说是学习笔记可能不如说是抄一遍集训队论文（大雾

前言

哪个傻逼天天往模拟赛塞这东西。

基本介绍

定义

有一组变量 ，以及若干个给定限制，每一组形如 。

然后你需要求 的最大值／最小值。

标准型

考虑称如下有 个变量和 个条件的线性规划为标准型：

  1. 目标求的是式子 的最大值；
  2. 第 个约束的形式为 ，即只有小于等于号的要求。
  3. 对于每一个变量 ，额外约束 。

对于一个不是标准型的线性规划：

  1. 若其不满足第一条，求 的最小值，则相当于求 的最大值。
  2. 若其不满足第二条，若出现了大于等于号，也像第一条一样反转一下；出现等于号就拆成一个大于等于和一个小于等于。
  3. 对于一个变量 ，将其拆成两个变量 ，并且要求 ，即可满足第三条。

也就是说，对于任意一个线性规划，我们都能将其转化成标准型。

接下来，我们只需要探讨标准型如何求解。

线性规划对偶

标准型的对偶

上述标准型的对偶为一个有 个变量与 个条件 的线性规划问题：

  1. 求式子 的最小值。
  2. 第 个条件为 。
  3. 额外要求 。

对偶定理

为什么会存在对偶这么个鬼东西呢，考虑这么一个问题。

现在有两个变量 ，我们现在想求 的最大值，这两个变量需要满足以下三个约束： 那么考虑计算 即 ，而我们知道 ，所以显然 。

这样我们就找到了 的一个上界，但显然他还有更紧的上界：

考虑计算 得到 。我们又找到了 的上界 。

现在回到上面的标准型，我们希望用这种方式，找到答案的一个上界。

如果我们将第 个约束选择了 次，我们会得到公式 。

显然我们需要有 以及 ，这样我们得到了答案的一个上界 。

而我们希望这个上界越紧越好，也就是说我们希望最小化 。

不难发现，这正好就是标准型的对偶形式。

至此我们证明了弱对偶定理：上述标准型的答案小于等于其对偶的答案。

当然还有一个强对偶定理：标准型的答案等于其对偶的答案。不会证。

同时，不难发现，标准型对偶的对偶也是标准型，后面要用。

拉格朗日对偶

我是鸽子谢谢。

最小费用流的线性规划

考虑现在有这么一个费用流模型，特殊的，这里的流为循环流。

这张图里，我们要求点 的流出减去流入为 ，其中 为已知的常量。

并且对于边 ，其有流量限制 和单位代价 。

其答案显然可以使用最小费用流跑出。

（如果图中可能会凭空出现负环的话，应该需要通过上下界网络流把费用全变成正边处理）。

（我这里的 定义似乎都与原论文相反，可能需要注意）。

那么考虑将这个最小费用流的模型用标准型对偶的形式表达出来，其中边 的流量为 。

那么我们想要求的是 ，限制为： 设 分别为上述三种约束的对偶变量，那么可以得到标准型：

求 ，有如下限制： 直接令 ，变成求 ，有限制： 而因为 是正的，所以满足其他变量不变的情况下，显然让 越小越好。

也就是说能得到 。

现在我们求的相当于是 。

或者说求 ，这两种问题都可以通过最小费用流来解决。

例题

[ZJOI2013] 防守战线

题意

现在有 个位置，每一个位置上可以建任意多个塔，在第 个位置上每造一个塔都需要 的代价。

现在有 个限制，第 个限制为 这个区间里面至少要有 个塔。

求最少的花费。

，。

题解

考虑设前 个位置总共有 个塔。

那么 上至少有 个塔就相当于 。

此外因为塔的个数不能是负数，所以有 和 。

花费就是 ，我们要让这个数字最小。

将要求的东西和限制写在一起，即求 的最小值。

这显然可以用上面说的最小费用流进行解决。

好那么脑瘫的事情来了，我们好像没有约束 。

不难发现，如果我们给 全都加上 ，那么方案的权值会变化 。

所以我们并不需要约束 ，求出来的答案直接就是对的。

提交记录，懒得卡常了。感觉改成原始对偶包能过的。

欸我怎么忘了原始对偶怎么写的，复习一下。

原始对偶 yyds。

[Aizu2230] How to Create a Good Game

题意

给定一张边权为正的 DAG，现在你可以进行若干次操作，每一次操作可以给一条边边权加上 。

要求所有操作结束之后点 到点 的最长路长度不变，问最多可以进行多少次操作。

对于每一个点 ，保证存在一条从 到 且经过 的路径。

，。

题解

设初始时点 到点 最长路长度为 ，结束时点 到点 最长路为 。

那么我们需要最大化 ，且对于 存在如下限制： 还是前面两个限制与常量有关，不太好弄。

不难发现，若将 中所有值一起 或 则方案权值不变且第三个条件依然满足。

所以我们直接将前两个条件重写为 。

列出式子，。

显然还是可以用网络流解决，很牛。

提交记录。

[Utpc2012] じょうしょうツリー

题意

给定 个点的有根树，第 个点初始有一个点权 。

每一次可以花费 的代价，给一个点权 或 。

现在要让每一个点的点权都严格小于父亲的点权，求最小操作次数。

。

题解

设最终点权为 。

则需要最小化 。

存在限制 。

不难发现，。

那么可以直接写出式子 。

还是一样，发现前面两个部分只有一个变量，所以考虑引入 。

式子变为 。

这样变完之后，相当于每一个点 的代价都变成了 ，即所有点的代价会同时变化一个值。

这样操作显然是没用的，因为我们只要求了 ，所以直接求就是最优解。

但是这个题比较特殊，首先 是 ，直接网络流大概率是过不去的。

其次，图里面根本没有出现源点和汇点，所以这还是一个循环流。

首先观察这个图长什么样子，首先一共有 一共 个点，然后有三种边：

  1. 对于 ， 到 有边权为 的边。
  2. 对于 ，有 到 的边权为 的边。
  3. 对于 ，有 到 的边权为 的边。

我们需要求出这张图的最小费用循环流。

第一种边的代价很烦，我们直接初始给每一个点点权加上自己的深度，这样第一种边就没有代价了。

不难发现，这相当于需要找出若干对点，其中一对点 的贡献是 ，并且需要满足 是 的祖先。

现在的目标是让所有点对的贡献之和最小。

那么先考虑，如果整棵树是一条链，怎么做。

不难发现，这其实是一个原题。（大雾

这可以简单的使用模拟费用流解决，只需要用一个堆来维护就好了。

放到树上我们发现直接把堆变成可并堆或者直接启发式合并就对了。

提交记录，超级好写。

[核桃周赛052] 构造

题意

给定一张 个点 条边的有向图，你需要给每一条边赋一个点权 ，满足 ，并且对于每一条边 都有 。

求 的最小值，输出最小值并构造方案。

，，。

题解

首先如果原图有环肯定无解，否则一定存在解。

先写成线性规划的形式，求的是 的最小值。

对于 有限制 。

式子是 。

那么我们直接把图建出来，然后跑费用流就能求出最小值。

问题在于怎么构造方案呢，一般的线性规划式子是并不支持构造方案的。

重新观察我们建出来的图长什么样，为方便起见我们将上面的边全部反向建，那么原图存在两种边：

  1. 对于 ，有 连向 的 边。
  2. 对于点 ，若 ，则从源点 向 连 的边。
  3. 对于点 ，若 ，则从 向汇点 连 的边。

考虑，若一条网络中的边 有流量，能说明什么。

手玩一下，发现这代表着 。

（证明的话，不会，但自己手玩一下就能感觉到它很有道理）。

那么我们直接跑一个差分约束就好了。

提交记录。

QOJ4213 Circles

题意

给定一个长度为 的非负整数序列 。

称非负（不一定是整数）序列 是平衡的当且仅当对于每一个 都有 。

令 为所有平衡的序列中序列和的最大值。

给定序列 ，对于所有 求出 。

。

题解

首先考虑怎么求单组的 。

先写成线性规划的形式，求 。

有限制 和 两个限制。

令 为第一种限制的对偶变量。

写出对偶形式，求 。

限制是 以及 。

那么显然不可能出现 的情况，所以 为 间的实数。