首页 > 其他分享 >线性规划学习笔记

线性规划学习笔记

时间:2023-06-25 18:55:12浏览次数:40  
标签:geq 变量 limits 线性规划 sum 笔记 学习 对偶

线性规划学习笔记

1 线性规划

定义

定义 1.1 已知一组实数 \(a_1,a_2,\cdots,a_n\),以及一组变量 \(x_1,x_2,\cdots,x_n\),在这些变量的一个线性函数定义为 \(f(x_1,x_2,\cdots,x_n) = \sum_{i=1}\limits^n a_i x_i\)。

等式 \(f(x_1,x_2,\cdots,x_n)=b\),不等式 \(f(x_1,x_2,\cdots,x_n) \leq b\),\(f(x_1,x_2,\cdots,x_n) \geq b\) 统称为线性约束。

称满足所有限制条件的解 \(x_1,x_2,\cdots,x_n\) 为可行解,使目标函数达到最优的可行解为最优解,所有可行解构成的区域为解空间。

线性规划的性质

定义 1.2 标准型

标准型线性规划要求满足如下形式:

最大化 \(\sum\limits_{j=1}^n c_jx_j\),满足约束 \(\sum\limits_{j=1}^n a_{i,j}x_j \leq b_i\),\(x_j \geq 0\)。

所有线性规划问题都可以用标准型描述。

对于无限制的变量 \(x\),可以拆成两个变量 \(x_0,x_1\),使得 \(x=x_0-x_1\)。

标准型可以用矩阵表示。

为了方便地求解线性规划,需要所有约束都是等式。

定义 1.3 松弛型

松弛型线性规划要求满足如下形式

最大化 \(\sum\limits_{j=1}^n c_jx_j\),满足约束 \(x_{i+n} = b_i - \sum\limits_{j=1}^n a_{i,j}x_j\),\(x_j \geq 0\)。

标准型转化为松弛型是容易的。

由于每一个线性不等式的解空间都是一个凸型区域,所以整个解空间也是一个凸型区域。

所以只有一个局部最优解,因此使用一个类似爬山的算法就不用担心停滞在局部最优解。

所以就引出了单纯形法。

2 单纯形

算法描述

其核心是转轴操作,即变量的代换。

首先有一些定义:

基变量: 在松弛型等式左侧的所有变量。

非基变量: 在松弛型等式右侧的所有变量。

单纯形算法有两个主要的操作:转轴操作以及 simplex 操作。

转轴操作的作用是选择一个基变量 \(x_B\) 以及一个非基变量 \(x_N\),将其互换(称这个非基变量为 换入变量,基变量为 换出变量)。

具体地,一开始有 \(x_B = b_i - \sum\limits_{j=1}^n a_{i,j}x_j\),那么 \(x_N = (b_i - \sum\limits_{j\not=N} a_{i,j}x_j -x_B) / a_{i,N}\)。

当然,在选择 \(x_N\) 的时候要保证 \(a_{i,N} \not = 0\)。

simplex 操作是单纯形法的主过程,从一个基本解出发,经过一系列转轴操作达到最优解。通过选择特定的换入变量以及换出变量,可以使得每次转移操作都能使目标函数增大,直到达到最优解。

即进行一次转轴后,我们也同步的将新的等式带入其他等式,然后带入我们最大化的式子,常数项显然就是我们当前维护的松弛型线性规划基本解对应的答案。

如目标函数有正的系数,那么就意味着目标函数有可能可以被进一步增大,所以我们就持续进行转轴操作直到所有系数为负。

转轴 操作对换入和换出变量的选取,每次选择一个在目标函数中系数为正的增大,令其为换入变量,然后考虑增大他,但增大往往有限制,我们在这些限制中选一个最紧的限制,令其基变量为换出变量,然后进行代换。

如果我们无法找到约束条件,说明这个线性规划是无界的。

关于初始化,有时候我们可能无法通过将所有非基变量赋为 \(0\) 达到寻找初始解的目的。

我们可以通过引入一个辅助线性规划:

最大化 \(-x_0\)

满足约束 \(x_{i+n} = b_i - \sum\limits_{j=1}^n a_{i,j}x_j+x_0\),\(x_j \geq 0\)。

容易发现,这个线性规划的最优解中 \(x_0 = 0\),而达到之后,这一定构成原线性规划的可行解。

我们不能通过全部赋为 \(0\) 得到可行解,说明 \(b\) 中存在负数。我们找到最小的一个 \(b_l\),对第 \(l\) 个约束做转轴

之后,第 \(l\) 个约束变为 \(x_0 = -b_l + \sum\limits_{j=1}^n a_{i,j}x_j+x_{l+n}\),显然满足 \(-b_l > 0\)。

其余约束变为 \(b_{i+n} = -b_l + b_i + \sum\limits_{j=1}^n (a_{l,j} - a_{i,j})x_j+x_{l+n}\)。显然 \(b_i - b_l \geq 0\)。

操作之后,辅助线性规划就有一个将非基变量赋为 \(0\) 的基本解,然后对其 simplex 即可。

单纯形法的时间复杂度

不是多项式算法,但很快,不说了。

但一般线性规划问题可以在多项式复杂度解决。

3 对偶问题

论文的引入中给出了一个有意思的现象,我们尝试去用我们限制中的不等式去拟合我们的目标式子,然后可以将最小化转化为最大化的线性规划问题。

举个论文中的例子:

考虑下面的线性规划:

最小化

\[7x_1+x_2+5x_3 \]

满足约束:

\[x_1-x_2+3x_3 \geq 10 \\ 5x_1+2x_2-x_3 \geq 6 \\ x_i \geq 0 \]

这个可以变换成如下样子:

\[7x_1 + x_2+5x_3 \geq (y_1 + 5y_2)x_1+(-y_1+2y_2)x_2+(3y_1-y_2)x_3 = f(y_1,y_2) \geq 10y_1 + 6y_2 \]

然后我们的目标就是在满足相关限制的情况下最大化 \(10y_1+6y_2\),惊喜地发现这也是个线性规划问题:

最大化

\[10y_1+6y_2 \]

满足约束

\[y_1 + 5y_2 \leq 7 \\ -y_1 + 2y_2 \leq 1 \\ 3y_1 - y_2 \leq 5 \\ y_i \geq 0 \]

我们称初始的线性规划为 原问题,新得到的线性规划为 对偶问题。我们对对偶问题再对偶一次其实就是原问题。也就是说一个最大问题可以对偶成最小问题,最小问题也可以对偶成最大问题。

下面给出形式化定义:

**定义6.1 ** 对偶问题

给定一个原始线性规划:

最小化 \(\sum\limits_{j=1}^n c_jx_j\)

满足约束 \(\sum\limits_{j=1}^n a_{i,j}x_j \geq b_i\),\(x_j \geq 0\)。

定义它的对偶线性规划为:

最大化 \(\sum\limits_{i=1}^m b_iy_i\)

满足约束 \(\sum\limits_{i=1}^m a_{i,j}y_i \leq c_j\),\(y_i \geq 0\)。

结合引子中的例子,这是容易理解的。

线性规划对偶性

哦,这一段论文阐述了这个对偶过程正确性。我知道它很正确啦!

互松弛定理: 若 \(x,y\) 分别是原问题及对偶问题的可行解,那么 \(x,y\) 都是最优解 当且仅当 下列两个条件被同时满足:

  • 对于所有 \(1 \leq j \leq n\) 满足 \(x_j = 0\) 或 \(\sum\limits_{i=1}^m a_{i,j}y_i = c_j\)。
  • 对于所有 \(1 \leq i \leq m\) 满足 \(y_i = 0\) 或 \(\sum\limits_{j=1}^n a_{i,j}x_j = b_i\)。

一些经典问题的对偶

网络流最大流

这个可以由线性规划对偶直接得到。

定理:网络流最大流等于最小割。

二分图最大权匹配问题

我确实会推导力!

定理 在一张带权二分图中,最大权匹配等于最小顶标和。

定理 二分图中,最大匹配数等于最小点覆盖数。

一般来说,我们倾向于将最小顶标和转化为最大权匹配。

例题

「SHOI2004」最小生成树

一条非树边的权值必须大于与其形成圈的树边的权值,以此形成做限制形成对偶。

这实际上就是一个二分图最小顶标和问题,可以转化成二分图最大权匹配。

Orz the MST

这个与上道题很像,可以直接一样列出线性规划,然后就可以写出对偶式子,根据对偶式子可以直接建出最大费用可行流的模型了。

数据范围有点大,大概要使用势能dij。

「ZJOI2013」防守战线

容易发现,这个题目直接就是一个线性规划的形式,对偶完之后好看了一些,直接可以拆点费用流处理。

「BZOJ1283」序列

感觉会是一个典题。

先写出一个线性规划的形式,然后就可以直接扫一遍贪心力!

为什么不对捏。哦,原始线性规划少条件了。

对偶完其实就和志愿者招募是一样的,你说的对,但我网络流建图不太会了。

去复习了一轮!

「ZJOI2020」序列

条件是恰好变成 \(0\)。

先直接构造线性规划。首先会有 \(O(n^2)\) 个变量。形成 \(O(n)\) 个等于的限制,最小化变量和。

线性规划感觉还是用笔做着舒服。

对偶完只剩下 \(n\) 个变量,但这些变量的取值很抽象。

也不是那么抽象,因为一些特殊区间的限制,每个位置的取值变成了 \(\{-1,0,1\}\),因为不能更大,更小也没有意义。

考虑 \(dp\) 套 \(dp\),维护三个最大后缀和,显然取值范围是 \(\{0,1\}\)。于是就可以计算最大贡献。

线性规划是强大的。

「雅礼集训 2018 Day8」B

安装时间其实是这个有向无环图的一条最长路。这意味着所需时间其实很难描述。

这个最长路大概也可以用线性规划描述。就是按照边和每个软件包的结束时间描述,建立超源超汇即可表示答案。

于是我们就得到了一个有 \(2n\) 个变量的线性规划。不妨将其对偶一下。对偶完有 \(m + n + 1\) 个变量。

考虑二分那个单独存在的不等式的系数,那是不是可以构造费用流?

特别扭曲的形式。换个办法,我们二分最小的时间,计算最小的代价。

然后给线性规划对偶一下就可以容易地进行费用流的构建。

标签:geq,变量,limits,线性规划,sum,笔记,学习,对偶
From: https://www.cnblogs.com/Reanap/p/17503714.html

相关文章

  • Verilog 呼吸灯学习心得体会
    2023-06-25 呼吸灯设计思路:系统时钟25MHz→20us定时器→20ms定时器→2s定时器/占空比计数器→输出设计流程:1.设置时间单位、全局参数和input/output端口定义;2.设置本模块参数3.设置reg变量;4.设置wire型变量5.设置assign赋值语句4.always语句实现功能:......
  • Android学习第一书
    大家好,我是一名Facebook的工程师,同时也是《第一行代码——Android》的忠实读者。虽然我最近几年是在国外读书和工作的,但是和很多人一样,我也非常喜欢郭霖的博客以及他写的《第一行代码——Android》。事实上,这本书在我面试Facebook的时候给我提供了很大的帮助。为此,我专门为这本书......
  • 热度直逼TensorFlow的深度学习框架,我用它画下女朋友最美的脸
    这不,又一个程序员为爱变身灵魂画手,看得我都想学画画了。阿华是幸运的,因为他找到了对的方法,事半功倍,最终有情人终成眷属。这也得益于PyTorch的易学易用,大多数人第一次使用PyTorch几乎可以做到无痛上手。就连深度学习三巨头之一,图灵奖得主YannLeCun都在Twit......
  • opencv学习笔记(十二)
    harris角点检测:#角点检测importcv2importnumpyasnp"""cv2.cornerHarris()img:数据类型为float32bolckSize:角点检测中指定区域的大小ksize:Sobel求导中使用的窗口大小,一般为3K:取值参数为[0.04,0.06]"""img=cv2.imread('C:/Users/hellou/Deskt......
  • SSM学习第八天
    MyBatisPlus今日目标基于MyBatisPlus完成标准Dao的增删改查功能掌握MyBatisPlus中的分页及条件查询构建掌握主键ID的生成策略了解MyBatisPlus的代码生成器1,MyBatisPlus入门案例与简介这一节我们来学习下MyBatisPlus的入门案例与简介,这个和其他课程都不太一样,其他的课程都......
  • HEVC官方代码学习_1
    HM是HEVC(H.265)的开源实现,可以从网上直接下载。下载网址:https://hevc.hhi.fraunhofer.de/svn/svn_HEVCSoftware/tags/文件整体调用流程图 各类文件功能AccessUnit.h定义了存取单元(或者访问单元),实质是一个类型为NALUnitEBSP的list扩展比特流的不同数据类型SODB:数据比特串,......
  • 浅析AI深度学习计算机视觉技术在智能监控领域的场景应用
    计算机视觉技术是一种模拟人类视觉功能的技术,通过数字图像处理、模式识别、机器学习等方法,自动分析和理解图像和视频中的信息,从而实现图像和视频的自动理解、识别、分类、检测和跟踪等任务。计算机视觉技术的使用场景非常广泛,包括但不限于以下几个方面:1)智能监控:利用计算机视觉技......
  • P5JS学习笔记
    //启动方法,自动执行functionsetup(){createCanvas(400,400);}//绘画执行方法,自动执行,按设定好的帧数绘制functiondraw(){background(25);ellipse(50,50,80,80);//画圆//鼠标按下事件if(mouseIsPressed){//改变背景色fill(0);}else{fill(255......
  • Java学习之Mysql基础问题整理
    Mysql常见存储引擎命令:SHOWENGINES; Mysql版本5.5以后默认引擎是InnoDB,5.5版本以前的是MyISAMInnoDB和MyISAM的区别1、InnoDB支持事务,MyISAM不支持。对于InnoDB每一条SQL语言都默认封装成事务,自动提交,这样会影响速度,所以最好把多条SQL语言放在begin和commit之间,组成一个......
  • 前端学习C语言 - 初级指针
    初级指针本篇主要介绍:指针和变量的关系、指针类型、指针的运算符、空指针和野指针、指针和数组、指针和字符串、const和指针、以及gdb调试段错误。基础概念指针是一种特殊的变量。存放地址的变量就是指针。intnum=1;会申请4个字节的内存来存放数字1,每次访问num就是......