计算机算法设计与分析-第8章 线性规划与网络流

《计算机算法设计与分析-第8章 线性规划与网络流》由会员分享，可在线阅读，更多相关《计算机算法设计与分析-第8章 线性规划与网络流（59页珍藏版）》请在金锄头文库上搜索。

1、计算机算法设计与分析 Design and Analysis of Computer Algorithms,第八章 线性规划与网络流 Linear Programming and Network Flow,2019年1月17日,2,提纲,一、线性规划问题和单纯形算法 二、最大网络流问题 三、最小费用流问题,2019年1月17日,3,提纲,一、线性规划问题和单纯形算法 二、最大网络流问题 三、最小费用流问题,2019年1月17日,4,1.1 线性规划问题及表示,例子：政治家选举问题 有三种不同类型的选区：市区、郊区和乡村，这些区域分别有100 000、200 000和50 000个登记选民。一个

2、政治家希望在每一个选区都赢得大多数的选票。主要政策有修路、枪械管理、农业补贴以及增加公共运输的汽油税。根据其竞选班子的研究，可以估计通过在某项政策上花费1000美元做广告，在每个选区可以赢取或输掉选民的千人数。右边表格给出这种信息：,任务：如何花费最少的钱，去赢得每个选区至少一半的选票。,2019年1月17日,5,1.1 线性规划问题及表示,问题表示 设 、 、 、 分别表示支出在修路、枪械管理、农业补贴以及汽油税广告上的千美元数 目标：最小化表达式 满足约束：,2019年1月17日,6,1.1 线性规划问题及表示,一般线性规划问题表示 s.t.,2019年1月17日,7,满足约束条件(8.2

3、)-(8.5)式的一组变量值称为线性规划问题的一个可行解。 使约束条件(8.2)-(8.5)式中的某n个约束以等号满足的可行解称为线性规划问题的基本可行解。 所有可行解构成的集合称为线性规划问题的可行区域。 使目标函数取得最值的可行解称为最优解。 在最优解处目标函数的值称为最优值。 有些情况下可能不存在最优解。通常有两种情况： (1)根本没有可行解，即给定的约束条件之间是相互排斥的； (2)目标函数没有极值，也就是说在n 维空间中的某个方向上，目标函数值可以无限增大或减小，而仍满足约束条件，此时目标函数值无界。,1.1 线性规划问题及表示,2019年1月17日,8,考察包含两个变量的线性规划

4、最大化： 满足约束：,1.1 线性规划问题及表示,2019年1月17日,9,考察包含两个变量的线性规划 最大化： 满足约束：,1.1 线性规划问题及表示,2019年1月17日,10,1.2 线性规划基本定理,定理1： 线性规划问题的可行区域是凸集； 定理2：线性规划问题有最优解的充要条件是它必有一基本可行最优解； 定理3：若线性规划问题有最优解，必在可行区域的某顶点上得到。,2019年1月17日,11,1.3 单纯形及单纯形算法,如果有 个变量，每个约束定义了 维空间中的一个半空间，这些半空间的交集形成的可行区域称作单纯形。 单纯形算法以一个线性规划作为输入，输出它的一个最优解。它从单纯形的某

5、个顶点开始，执行一系列迭代，在每次迭代中，它沿着单纯形的一条边从当前顶点移动到一个目标值大于（或小于）当前顶点的相邻顶点，当达到一个局部的最优值时，单纯形算法结束。 因为可行区域是凸的且目标函数是线性的，所以局部最优实际上是全局最优的。,2019年1月17日,12,1.4 约束标准型线性规划问题,标准型线性规划： s.t.,2019年1月17日,13,1.4 约束标准型线性规划问题,在标准型线性规划问题中，如果每一个等式约束中，至少有一个变量的系数为正，且这个变量只在该约束中出现。 在每一约束方程中选择一个这样的变量，并以它作为变量求解该约束方程。这样选出来的变量称为左端变量或基本变量，其总数

6、为m个。剩下的n-m个变量称为右端变量或非基本变量。 这一类特殊的标准型线性规划问题称为约束标准型线性规划问题。,2019年1月17日,14,1.4 约束标准型线性规划问题,例如： 此例中，n=6，m=3；基本变量为 ， 和 ；非基本变量为 ， 和 。,2019年1月17日,15,1.5 将一般线性规划转换成约束标准型,对最小化线性规划问题，只要将目标函数乘以-1即可化为等价的最大化线性规划问题。 把(8.2)或(8.4)形式的不等式约束转换为等式约束。具体做法是，引入松弛变量，将不等式转化为等式，且引入的松弛变量具有非负性 。 在求解过程中，应当将松弛变量与原来变量同样对待。求解结束后，舍弃

7、松弛变量。,2019年1月17日,16,1.5 将一般线性规划转换成约束标准型,设不等式约束形式为： 引入一个松弛变量s： 使用 来表示与第i个不等式关联的松弛变量： 等式左边的变量称为基本变量，等式右边的变量称为非基本变量。,2019年1月17日,17,1.5 将一般线性规划转换成约束标准型,一个例子 最大化： 满足约束：,2019年1月17日,18,1.5 将一般线性规划转换成约束标准型,引入松弛变量 ， ， ，得到标准型： 最大化： 满足约束：,2019年1月17日,19,1.6 标准型的元组表示,标准型的元组表示： N表示非基本变量下标的集合； B表示基本变量下标的集合； b表示由等式

8、约束中的常数项组成的列向量； c表示目标函数中非基本变量系数组成的行向量； v表示目标函数中的常数项； 是一个矩阵，由所有等式约束中非基本变量 前系数的负值确定,2019年1月17日,20,1.7 单纯形表,标准型线性规划的单纯形表：,2019年1月17日,21,1.8 单纯形算法,第1步：选取入基变量。 选出使目标函数增加的非基本变量作为入基变量。 查看单纯形表的第1行（也称之为z行）中标有非基本变量的各列中的值，选择系数为正的变量作为入基变量。 本例中，选取x3作为入基变量。,2019年1月17日,22,1.8 单纯形算法,第2步：选取离基变量。 在单纯形表中考察由第1步选出的入基变量所相

9、应的列。 如果入基变量所在的列与基本变量所在行交叉处的表元素为负数，那么该元素将不受任何限制，相应的基本变量只会越变越大。 如果入基变量所在列的所有元素都是负值，则目标函数无界，已经得到了问题的无界解。 如果选出的列中有一个或多个元素为正数，要弄清是哪个数对入基变量值的增加限制更大。 受限的增加量可以用入基变量所在列的元素（称为主元素）来除主元素所在行的“常数列” 元素而得到。所得到数值越小说明受到限制越多。 应该选取受到限制最多的基本变量作为离基变量，才能保证将入基变量与离基变量互调位置后，仍满足约束条件。 本例中，应该选取x4为离基变量。,2019年1月17日,23,1.8 单纯形算法,第

10、3步：转轴变换（主元操作） 将入基变量与离基变量互调位置。 解离基变量所相应的方程，将入基变量x3用离基变量x4表示为：,2019年1月17日,24,1.8 单纯形算法,再将其代入其他基本变量所在的行中消去x3 ， 将其代入目标函数得到 形成新单纯形表,2019年1月17日,25,第4步：转回并重复第1步，进一步改进目标函数值。 不断重复上述过程，直到新单纯形表中z行的所有非基本变量系数都变成负值为止。这表明目标函数不可能再增加了，求解过程结束。 整个问题的解可以从最后一张单纯形表的常数列中读出。 目标函数的最大值为11； 最优解为： x*=(0,4,5,0,0,11) x=(4,5,0),1

11、.8 单纯形算法,2019年1月17日,26,任何约束标准型线性规划问题，只要将所有非基本变量都置为0，从约束方程式中解出满足约束的基本变量的值，可求得一个基本可行解。 单纯形算法的基本思想就是从一个基本可行解出发，进行一系列的基本可行解的变换，每次变换都使基本可行解的目标值不小于（通常是大于）前一次迭代中的目标值。 每次变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个与原问题完全等价的标准线性规划问题。,1.8 单纯形算法,2019年1月17日,27,1.9 单纯形算法的主元操作,2019年1月17日,28,1.10 单纯形算法描述,2019年1月17日,29,1.

12、11一般线性规划问题的2阶段单纯形算法,首先通过引入松弛变量，将一般线性规划问题的不等式约束转化为等式约束，构造成标准型。 再引入m个人工变量，记为zi，构造成约束标准型。 例如，一个一般线性规划问题：,2019年1月17日,30,1.11一般线性规划问题的2阶段单纯形算法,上例中引入松弛变量和人工变量后，约束条件变为：,2019年1月17日,31,1.11一般线性规划问题的2阶段单纯形算法,第一阶段： 用一个辅助目标函数 替代原来的目标函数。 这个线性规划问题称为原线性规划问题所相应的辅助线性规划问题。 对辅助线性规划问题用单纯形算法求解。 单纯形算法第一阶段的任务就是构造一个初始基本可行解

13、。 如果在辅助线性规划问题最后的单纯形表中， zi不全为0，则原线性规划问题没有可行解，从而原线性规划问题无解。,2019年1月17日,32,1.11一般线性规划问题的2阶段单纯形算法,第二阶段： 第二阶段的目标是求解由第一阶段导出的问题。 此时要用原来的目标函数进行求解。,2019年1月17日,33,1.12退化情形的处理,用单纯形算法解一般的线性规划问题时，可能会遇到退化的情形，即在迭代计算的某一步中，常数列中的某个元素的值变成0，使得相应的基本变量取值为0。 如果选取退化的基本变量为离基变量，则作转轴变换前后的目标函数值不变。在这种情况下，算法不能保证目标函数值严格递增，因此，可能出现无

14、限循环。 Bland提出在单纯形算法迭代中可以避免循环的2个简单规则。 规则1：设 ，取xe为入基变量。 规则2：设 ，取xk为离基变量。,2019年1月17日,34,提纲,一、线性规划问题和单纯形算法 二、最大网络流问题 三、最小费用流问题,2019年1月17日,35,2.1 基本概念和术语,网络 G是一个简单有向图，G=(V,E)，V=1，2，n。 有向图G的每一条边(v,w)E，对应有一个值cap(v,w)0，称为边的容量。如果(v,w)E，则假定cap(v,w)0。 G中有两个特殊的顶点s和t，称为源点s和汇点t。一般情况下，满足s没有入边，t没有出边。 这样的有向图G称作一个网络。,

15、2019年1月17日,36,2.1 基本概念和术语,网络流 网络上的流是定义在网络的边集合E上的一个非负函数flow=flow(v,w)，并称flow(v,w)为边(v,w)上的流量。,2019年1月17日,37,可行流 满足下述条件的流flow称为可行流： 容量约束：对每一条边(v,w)E，0flow(v,w)cap(v,w)。 平衡约束：对于中间顶点：流出量=流入量。即对每个vV(vs,t)有：顶点v的流出量顶点v的流入量=0。 对于源s：s的流出量s的流入量=源的净输出量f。 对于汇t：t的流入量t的流出量的=汇的净输入量f。 式中f 称为这个可行流的流量，即源的净输出量(或汇的净输入量

16、)。 可行流总是存在的。 例如，让所有边的流量flow(v,w)=0，就得到一个其流量f=0的可行流(称为0流)。,2.1 基本概念和术语,2019年1月17日,38,边流 对于网络G的一个给定的可行流flow，将网络中满足flow(v,w)=cap(v,w)的边称为饱和边；flow(v,w)0的边称为非零流边。当边(v,w)既不是一条零流边也不是一条饱和边时，称为弱流边。 最大流 最大流问题即求网络G的一个可行流flow，使其流量f达到最大。即flow满足：0flow(v,w)cap(v,w)，(v,w)E；且,2.1 基本概念和术语,2019年1月17日,39,2.1 基本概念和术语,流的费用 对于网络的每一条边(v,w) ，定义一个单位流量费用cost(v,w)。对于网络中一个给定的流flow，其费用定义为：,20