线性规划

最近数学课学习了线性规划.

虽然在NOI前学习过OI中的线性规划,但是当时也只是背下来代码(背了就忘了,根本不理解.

就跟之前学的SAM和主席树一样,虽然打过板子,但是没有深入的理解,到了考场上还是打不出来.所以,今天还是重新学习一下LP.

简介

线性规划Linear programming,也称作linear optimization,因为复杂度玄妙在OI中不是特别普及(假的),但是因为可以解决很多不同最优化的问题作用很大.但是,在网络流多商品流等问题中,可能只有这一种解决方法.同样,线性规划在生活中运用也十分广泛.

标准型

就如同数学书中所述,问题要求最大化
$$
z=ax+by
$$
但是对于$x$和$y$的取值需要满足约束
$$
\begin{cases}
a_1x+b_1y+c_1 \leq 0\\
a_2x+b_2y+c_2 > 0\\
….
\end{cases}
$$
同样还需要满足都是非变量
$$
x\geq 0, y \geq 0
$$
对应到坐标系中,满足限制的点的集合构成了可行的区域.也就是$x,y$可以取到的所有值.

我们把这一块满足称作可行域.
$$
y=-\frac{a}{b}x+\frac{1}{b}z
$$
相当于平行于$y=-\frac{a}{b}x$的直线在坐标系上平移,求一个最优的$z$.

以上是数学课上讲的做法

归纳一下,极大化$c_1x_1+c_2x_2+….+c_nb_n$

约束如下
$$
\begin{cases}
a_{11}x_1+a_{12}x_2+…a_{1n}x_{n} \\
a_{21}x_1+a_{22}x_2+…a_{2n}x_{n} \\
…\\
a_{m1}x_1+a_{m2}x_2+…a_{mn}x_{n}
\end{cases}
$$
变量非负
$$
x_1\geq 0 \\
x_2\geq 0
$$
如果用矩阵来表示
$$
\text{maxsize}~c^Tx\\
\text{subject to}~Ax\leq b, x\geq0
$$
其中$A=(a_i,j)$,是一个$m\times n$的矩阵,$b=(b_i)$是一个$m$维向量,$c=(c_j)$和$x=(x_j)$是$n$维向量.
$$
{max~c^T x|Ax ≤ b, x i ≥ 0}
$$

松弛型

同样,最大化$c_1x_1+c_2x_2+….+c_nbx_n$

$$
\text{maxsize}~c^Tx\\
\text{subject to}~Ax= b, x\geq0
$$

算法简述

如何解决线性规划问题?单纯性算法就是解决这一问题的方法.

考虑一个$n$维凸多胞体

可行域就对应一个$n$维凸多胞体.

首先先找到一个初始的可行解.找不到则无解,然后对于这个解,在这个凸多胞体上进行转轴(Pivot),相当于走到单纯形上的另一个顶点.如果找到的新点最优,就走过去.如果每个收益为负就停止.

可以证明

  • 一定会停止(凸多胞体的顶点个数有限)

  • 算法一定正确

算法过程

  • 将标准型转换为松弛型
  • 找到初始解,否则无解
  • 不停地找,判断无界

转换为松弛型


$$
x_i=b_i-\sum_{j=1}^{n} a_{ij}x_i\\
x_i\geq 0
$$
定义$x_1…x_n$为非基变量,$x_{n+1}…x_{m+n}$为基变量.

Pivot

例如要交换$x_{n+l},x_e$.

因为
$$
x_{n+l}=b_l-\sum_{j=1}^{n}a_{ij}x_j\\
a_{ie}x_e=b_l-\sum_{j!=e}a_{ij}x_j-x_{n+l}\\
x_e=\frac{b_l-\sum_{j!=e}a_{ij}x_j-x_{n+l}}{a_{ie}}
$$
实现则用一个$id$数组记录编号即可.

关于代码

关于为什么这样写,它究竟是什么意思.我当然就不知道了

UOJ179 线性规划

参考资料

几乎全是抄的上面的

  • 2016IOI国家集训队论文 邹逍遥《浅谈线性规划在信息竞赛中的应用》

练习题

光说不练假把式,先写点论文题.

UVA10498 Happiness

题意

有$n$种食物和$m$个人,Nasa要每个人买相同数量的食物,但是对于每一个人食物的满意度和每个人的满意度限制.求最大花费.

题解

模板题.因为一定有一解是${0,0…,0}$,那么Init都不用写.

(震惊:调一晚上是因为读物品单价的时候把$n$写成了$m$

BZOJ3112 防守战线 

题意

有一个长度为$n$的序列,第$i$个点上权值每加一的代价是$a_i$,$m$个限制要求区间$L,R$的权值不小于$q_i$,问最小花费.

题解

根据线性规划的对偶性质(LP duality).

${max~c^T x| Ax \leq b,x_i\geq0}$的最优解等于${min ~b^Tx|A^Tx \geq c, x_i\geq 0}$

简单来说就是把原来的矩阵顺时针旋转90度,$b \rightarrow c$即可.

BZOJ3118 Orz the MST

题意

给出一个图,指定一个生成树,现在把一条边权加一的代价是$a_i$,减少1代价是$b_i$,求给出的生成树是最小生成树的最小代价。

题解

首先树边只会减,非树只会加,设一个边的修改量为$w_i$,原始量为$v_i$

对于边$i,j$在一个环上,$i$ 是树边,$j$是非树边。
$$
v_i-w_i \leq v_j + w_j\\
w_i+wj\geq v_j-v_i
$$
题目里要最小化的是$\sum_{i=1}^{|e|} w_i$,按照方程建出来。

因为限制是大于号,求最小值,转化为对偶矩阵即可。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*