Mengzelev's Blog

算法导论学习笔记-线性规划

Word count: 2,179 / Reading time: 8 min
2019/02/13 Share

知识背景

  • 一个线性规划问题是一个线性函数最小化或最大化的问题,该线性函数服从一组有限个线性约束,分为最小化线性规划和最大化线性规划
  • 可行解:所有满足约束条件的自变量的取值
  • 可行区域:所有可行解在二维空间中构成的凸区域
  • 目标函数:希望最大化的函数
  • 目标值:目标函数在一个特定点上的值
  • 最优解:所有目标值中最大的一个,其目标值为最优目标值
  • 不可行的:一个线性规划没有可行解
  • 无界的:一个线性规划有可行解但没有有限的最优目标值

标准型和松弛型

标准型

  • 所有的约束都是不等式
  • 标准型=目标函数+约束+非负约束

  • 重写为向量与矩阵的形式,可以用一个元组$(A,b,c)$来表示一个标准型的线性规划

最大化$$c^Tx$$
满足约束$$Ax\le b$$
$$x\ge 0$$

  • 线性规划的等价:对两个最大化线性规划$L$和$L’$,如果对$L$的每个目标值为$z$的可行解$\overline{x}$,都存在一个对应的$L’$的目标值为$z$的可行解的$\overline{x}’$;(反过来同理),则称$L$和$L’$是等价的。
    • 最小化线性规划和目标函数取负后得到的最大化线性规划是等价的

非标准型的标准化

  • 目标函数是最小化:取负
  • 某些变量不具有非负约束:假设$x_j$无非负约束,则将所有出现的$x_j$替换为$x_{j}’-x_{j}’’$,并令$x_{j}’\ge 0, x_{j}’’\ge 0$
  • 存在等式约束:$\ge + \le$
  • 存在大于等于约束:取负

松弛型

  • 松弛变量$s=b_i-\sum\limits_{j=1}^{n}a_{ij}x_i,s\ge 0$
  • 只有非负约束是不等式,其余都是等式
  • 当从标准型转换到松弛型时,我们将使用$x_{n+i}$表示与第$i$个不等式相关的松弛变量$$x_{n+i}=b_i-\sum\limits_{j=1}^{n}a_{ij}x_i,x_{n+i}\ge 0$$

  • 基本变量:等式左边的变量

  • 非基本变量:等式右边的变量
  • 有时描述时会省略词语“最大化”和“满足约束”以及明显的非负约束要求
  • 简洁记号
    • $N$:非基本变量下标的集合
    • $B$:基本变量下标的集合
    • $N\cup B={1,2,…,n+m}$
    • 用一个元组$(N,B,A,b,c,v)$来表示松弛型
    • 这里的$a_{ij}$是“出现”在松弛型中的 负数
    • $A,b,c$的小标不必是连续整数的集合,依赖于索引集合$B$和$N$

将问题表达为线性规划

单对最短路径

如下的线性规划可以计算从$s$到$t$的最短路径权值

之所以是最大化目标函数,是因为最短路径问题的一个最优解把每一个$\overline{d}_v$设置成所有$\overline{d}_u+w(u,v)$的最小值,使得$\overline{d}_v$是小于等于集合${\overline{d}_u+w(u,v)}$所有值的最大值;而最小化目标函数会使所有$\overline{d}_v=0$,这个解显然没有意义

最大流

最大流问题表示为一个线性规划

这个线性规划可以重写为有$O(V+E)$个约束的表示,这样计算起来会更高效

最小费用流

问题描述

  • 最大流的推广
  • 每条边除了容量还有费用值$a(u,v)$。如果通过边$(u,v)$传送了$f_{uv}$个单位的流,那么产生了一个费用$a(u,v)f_{uv}$。
  • 求从$s$到$t$发送$d$个单位的流(流目标),使得流上发生的总费用$\sum\limits_{(u,v)\in E}a(u,v)f_{uv}$最小

最小费用流有专门设计的多项式时间算法,但算导上没有涉及到

线性规划建模

这不是很直观吗

多商品流

问题描述

  • 在最小费用流问题的基础上,有$k$种不同的商品$K_1,K_2,…,K_k$,其中用三元组$K_i=(s_i,t_i,d_i)$来详细说明商品的源点、汇点和需求
  • 定义商品$i$的流$f_i$,汇聚流为各种商品流的总和$f_{uv}=\sum\limits_{i=1}^{k}f_{iuv}$
  • 不用最小化任何目标函数,只需要确定是否存在这样的一个流

线性规划建模

单纯形算法

  • 求解线性规划的经典方法
  • 在最坏情况下执行时间非多项式
  • 在实际中次算法通常相当快速
  • 可以看成不等式上的高斯消元法

主要思想

  • 每轮迭代都关联一个“基本解”
    • 从松弛型中得到“基本解”
    • 将每个非基本变量设为0,并从等式约束中计算基本变量的值
  • 每轮迭代把一个松弛型转换成一个等价的松弛型
  • 如果一个非基本变量从0开始增加时目标值也增加(目标函数中系数为正),则增加该非基本变量直到某基本变量为0
  • 重写松弛型,交换此基本变量和选定的非基本变量,这个操作称为转动
    • 一个转动选取一个非基本变量$x_e$(替入变量)和一个基本变量$x_l$(替出变量)

单纯型算法执行了两个操作

  1. 重写等式使得变量在等式的左边与右边之间移动
  2. 替换一个等式为另一个等式

这两个操作都建立了等价的问题

步骤

  1. 在目标函数中选一个最大正系数非基本变量$x_1$,尝试增大$x_1$,使得$z$增大(增大时必须满足约束条件)
  2. 找到最紧的约束,解出$x_1$
  3. 将$x_1$代入系统中其他约束和目标函数【转动】
  4. 找到新系统的基本解

转动

  • 输入:元组$(N,B,A,b,c,v)$,替出变量$x_l$的下标$l$(从左边调到右边),以及替入变量$x_e$的下标$e$(从右边调到左边)出入是相对非基本变量集合$N$而言的
  • 输出:新松弛的元组$(\hat{N},\hat{B},\hat{A},\hat{b},\hat{c},\hat{v})$

正式的单纯形算法

SIMPLEX

  • 输入:一个标准型的线性规划
  • 输出:一个$n$维向量,表示该线性规划的一个最优解
  • 假设INITIALIZE-SIMPLEX过程返回一个初始基本解可行的松弛型或不可解信息
  • 3~12行:算法主体
    • 如果都是目标函数所有系数为负,则while循环终止,否则第4行选择替入变量$x_e$
    • 5~9行检查每个约束,然后挑出一个最严格限制$x_e$增加幅度的约束相关联的基本变量$x_l$,如果没有约束能够限制替入变量增加的幅度,则在第11行返回无界
    • 调用PIVOT交换替入变量和替出变量
    • 13~16行吧所有非基本变量设为0,把基本变量$\overline{x_i}$设为$b_i$
    • 17行返回这些值

循环不变式

while循环每次迭代开始:

  • 此松弛型等价于调用INITIALIZE-SIMPLEX返回的松弛型
  • 对每个$i\in B$,有$b_i\ge 0$(保证新系统的基本解可行)
  • 此松弛型相关的基本解是可行的

需要保证while循环终止,可以通过第4行和第9行总是选择具有最小下标的变量来打破目标值不变的局面

假设INITIALIZE-SIMPLEX返回一个基本解可行的松弛型,那么SIMPLEX要么报告一个线性规划是无界的,要么以一个可行解结束,且至多$(^{m+n}_{m})$次循环内终止

对偶性

对偶性:给定一个最大化问题,我们定义一个相关的最小化问题,使得这两个问题具有同样的最优目标值(e.g.最大流最小割)

给定一个标准型的原式线性规划,我们定义其对偶线性规划为(将最大化改为最小化,交换右边系数与目标函数的系数)

弱对偶性:原式线性规划的任意可行解的值不大于此对偶线性规划的任意可行解的对应值

引理 29.8:线性规划对偶性

证明涉及大量数学推导

对偶问题都可以像最大流最小割一样,用来转移火力,找到一个等价的问题来求解原来的问题

CATALOG
  1. 1. 知识背景
  2. 2. 标准型和松弛型
    1. 2.1. 标准型
      1. 2.1.1. 非标准型的标准化
    2. 2.2. 松弛型
  3. 3. 将问题表达为线性规划
    1. 3.1. 单对最短路径
    2. 3.2. 最大流
    3. 3.3. 最小费用流
      1. 3.3.1. 问题描述
      2. 3.3.2. 线性规划建模
    4. 3.4. 多商品流
      1. 3.4.1. 问题描述
      2. 3.4.2. 线性规划建模
  4. 4. 单纯形算法
    1. 4.1. 主要思想
    2. 4.2. 步骤
    3. 4.3. 转动
    4. 4.4. 正式的单纯形算法
      1. 4.4.1. 循环不变式
  5. 5. 对偶性