算法设计第8章

《算法设计第8章》由会员分享，可在线阅读，更多相关《算法设计第8章（47页珍藏版）》请在金锄头文库上搜索。

1、1,学习要点 理解线性规划算法模型 掌握解线性规划问题的单纯形算法 理解网络与网络流的基本概念 掌握网络最大流的增广路算法 掌握网络最大流的预流推进算法 掌握网络最小费用流的消圈算法 掌握网络最小费用流的最小费用路算法 掌握网络最小费用流的网络单纯形算法,第8章 线性规划与网络流,2,8.1 线性规划问题和单纯形算法,线性规划问题及其表示 线性规划问题可表示为如下形式：s.t.,3,变量满足约束条件(8.2)-(8.5)式的一组值称为线性规划问题的一个可行解。 所有可行解构成的集合称为线性规划问题的可行区域。 使目标函数取得极值的可行解称为最优解。 在最优解处目标函数的值称为最优值。 有些情况

2、下可能不存在最优解。 通常有两种情况： (1)根本没有可行解，即给定的约束条件之间是相互排斥的，可行区域为空集； (2)目标函数没有极值，也就是说在n 维空间中的某个方向上，目标函数值可以无限增大，而仍满足约束条件，此时目标函数值无界。,4,这个问题的解为 (x1,x2,x3,x4) = (0,3.5,4.5,1)；最优值为16。,5,线性规划基本定理,约束条件(8.2)-(8.5)中n个约束以等号满足的可行解称为线性规划问题的基本可行解。 若nm，则基本可行解中至少有n-m个分量为0，也就是说，基本可行解中最多有m个分量非零。 线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优

3、解。 上述定理的重要意义在于，它把一个最优化问题转化为一个组合问题，即在(8.2) -(8.5)式的m+n个约束条件中，确定最优解应满足其中哪n个约束条件的问题。 由此可知，只要对各种不同的组合进行测试，并比较每种情况下的目标函数值，直到找到最优解。 Dantzig于1948年提出了线性规划问题的单纯形算法。 单纯形算法的特点是： （1）只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加； （2）一般经过不大于m或n次迭代就可求得最优解。,6,约束标准型线性规划问题的单纯形算法,当线性规划问题中没有不等式约束(8.2)和(8.4)式，而只有等式约束(8.3)和变量非负约束(8.5

4、)时，称该线性规划问题具有标准形式。 为便于讨论，不妨先考察一类更特殊的标准形式线性规划问题。这一类线性规划问题中，每一个等式约束中，至少有一个变量的系数为正，且这个变量只在该约束中出现。 在每一约束方程中选择一个这样的变量，并以它作为变量求解该约束方程。这样选出来的变量称为左端变量或基本变量，其总数为m个。剩下的n-m个变量称为右端变量或非基本变量。 这一类特殊的标准形式线性规划问题称为约束标准型线性规划问题。 虽然约束标准型线性规划问题非常特殊，但是对于理解线性规划问题的单纯形算法是非常重要的。 稍后将看到，任意一个线性规划问题可以转换为约束标准型线性规划问题。,7,8,任何约束标准型线性

5、规划问题，只要将所有非基本变量都置为0，从约束方程式中解出满足约束的基本变量的值，可求得一个基本可行解。 单纯形算法的基本思想就是从一个基本可行解出发，进行一系列的基本可行解的变换。 每次变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个与原问题完全等价的标准线性规划问题。 基本可行解x=(7,0,0,12,0,10)。 单纯形算法的第1步：选出使目标函数增加的非基本变量作为入基变量。 查看单纯形表的第1行（也称之为z行）中标有非基本变量的各列中的值。 选出使目标函数增加的非基本变量作为入基变量。 z行中的正系数非基本变量都满足要求。 在上面单纯形表的z行中只有1列为正

6、，即非基本变量相应的列，其值为3。 选取非基本变量x3作为入基变量。 单纯形算法的第2步：选取离基变量。 在单纯形表中考察由第1步选出的入基变量所相应的列。 在一个基本变量变为负值之前，入基变量可以增到多大。,9,如果入基变量所在的列与基本变量所在行交叉处的表元素为负数，那么该元素将不受任何限制，相应的基本变量只会越变越大。 如果入基变量所在列的所有元素都是负值，则目标函数无界，已经得到了问题的无界解。 如果选出的列中有一个或多个元素为正数，要弄清是哪个数限制了入基变量值的增加。 受限的增加量可以用入基变量所在列的元素（称为主元素）来除主元素所在行的“常数列”（最左边的列）中元素而得到。所得到

7、数值越小说明受到限制越多。 应该选取受到限制最多的基本变量作为离基变量，才能保证将入基变量与离基变量互调位置后，仍满足约束条件。 上例中，惟一的一个值为正的z行元素是3，它所在列中有2个正元素，即4和3。 min12/4,10/3=4，应该选取x4为离基变量； 入基变量x3取值为3。 单纯形算法的第3步：转轴变换。 转轴变换的目的是将入基变量与离基变量互调位置。 给入基变量一个增值，使之成为基本变量； 修改离基变量，让入基变量所在列中，离基变量所在行的元素值减为零，而使之成为非基本变量。,10,解离基变量所相应的方程，将入基变量x3用离基变量x4表示为 再将其代入其他基本变量和所在的行中消去x

8、3 ，代入目标函数得到 形成新单纯形表,11,单纯形算法的第4步：转回并重复第1步，进一步改进目标函数值。 不断重复上述过程，直到z行的所有非基本变量系数都变成负值为止。这表明目标函数不可能再增加了。 在上面的单纯形表中，惟一的值为正的z行元素是非基本变量x2相应的列，其值为1/2。 因此，选取非基本变量x2作为入基变量。 它所在列中有惟一的正元素5/2，即基本变量x1相应行的元素。 因此，选取x1为离基变量。 再经步骤3的转轴变换得到新单纯形表。 新单纯形表z行的所有非基本变量系数都变成负值，求解过程结束。 整个问题的解可以从最后一张单纯形表的常数列中读出。 目标函数的最大值为11； 最优解

9、为：x*=(0,4,5,0,0,11)。,12,单纯形算法计算步骤,单纯形算法的计算过程可以用单纯形表的形式归纳为一系列基本矩阵运算。 主要运算为转轴变换，该变换类似解线性方程组的高斯消去法中的消元变换。 单纯形表：为基本变量， 为非基本变量。 基本变量下标集为B=1,2,m； 非基本变量下标集为N=m+1,m+2,n； 当前基本可行解为（ ）。,13,单纯形算法计算步骤如下： 步骤1：选入基变量。 如果所有cj0，则当前基本可行解为最优解，计算结束。 否则取ce0相应的非基本变量xe为入基变量。 步骤2：选离基变量。 对于步骤1选出的入基变量xe ，如果所有aie0 ，则最优解无界，计算结束

10、。 否则计算选取基本变量xk为离基变量。 新的基本变量下标集为 新的非基本变量下标集为 步骤3：作转轴变换。 新单纯形表中各元素变换如下。,14,（8.10）（8.11）（8.12）（8.13）步骤4：转步骤1。,15,将一般问题转化为约束标准型,有几种巧妙的办法可以将一般的线性规划问题转换为约束标准型线性规划问题。 首先，需要把(8.2)或(8.4)形式的不等式约束转换为等式约束。 具体做法是，引入松弛变量，利用松弛变量的非负性，将不等式转化为等式。 松驰变量记为yi，共有m1+m3个。 在求解过程中，应当将松弛变量与原来变量同样对待。求解结束后，抛弃松弛变量。 注意松弛变量前的符号由相应的

11、原不等式的方向所确定。,16,为了进一步构造标准型约束，还需要引入m个人工变量，记为zi。 至此，原问题已经变换为等价的约束标准型线性规划问题。 对极小化线性规划问题，只要将目标函数乘以-1即可化为等价的极大化线性规划问题。,17,一般线性规划问题的2阶段单纯形算法,引入人工变量后的线性规划问题与原问题并不等价，除非所有zi都是0 。 为了解决这个问题，在求解时必须分2个阶段进行。 第一阶段用一个辅助目标函数 替代原来的目标函数。 这个线性规划问题称为原线性规划问题所相应的辅助线性规划问题。 对辅助线性规划问题用单纯形算法求解。 如果原线性规划问题有可行解，则辅助线性规划问题就有最优解，且其最

12、优值为0，即所有zi都为0。 在辅助线性规划问题最后的单纯形表中，所有zi均为非基本变量。 划掉所有zi相应的列，剩下的就是只含xi和yi的约束标准型线性规划问题了。 单纯形算法第一阶段的任务就是构造一个初始基本可行解。 单纯形算法第二阶段的目标是求解由第一阶段导出的问题。 此时要用原来的目标函数进行求解。 如果在辅助线性规划问题最后的单纯形表中， zi不全为0，则原线性规划问题没有可行解，从而原线性规划问题无解。,18,退化情形的处理,用单纯形算法解一般的线性规划问题时，可能会遇到退化的情形，即在迭代计算的某一步中，常数列中的某个元素的值变成0，使得相应的基本变量取值为0。 如果选取退化的基

13、本变量为离基变量，则作转轴变换前后的目标函数值不变。在这种情况下，算法不能保证目标函数值严格递增，因此，可能出现无限循环。 考察下面的由Beale在1955年提出的退化问题的例子。 按照2阶段单纯形算法求解该问题将出现无限循环。,19,Bland提出避免循环的一个简单易行的方法。 Bland提出在单纯形算法迭代中，按照下面的2个简单规则就可以避免循环。规则1：设 ，取xe为入基变量。规则2：设 取xk为离基变量。算法leave(col)已经按照规则2选取离基变量。 选取入基变量的算法enter(objrow) 中只要加一个break语句即可。,20,仓库租赁问题,某企业计划为流通的货物租赁一批

14、仓库。必须保证在时间段i=1,2,n，有bi的仓库容量可用。现有若干仓库源可供选择。设cij是从时间段i到时间段j租用1个单位仓库容量的价格，1ijn。应如何安排仓库租赁计划才能满足各时间段的仓库需求，且使租赁费用最少。 设租用时间段i到时间段j的仓库容量为yij，1ijn。则租用仓库的总费用为： 在时间段k可用的仓库容量为： 仓库租赁问题可表述为下面的线性规划问题：,21,设 m=n(n+1)/2； （ ）=（ ）； （ ）=（ ）； 上述线性规划问题可表述为n个约束和m个变量的标准线性规划问题如下。,22,8.2 最大网络流问题,1 基本概念和术语（1） 网络 G是一个简单有向图，G=(V

15、,E)，V=1，2，n。 在V中指定一个顶点s，称为源和另一个顶点t，称为汇。 有向图G的每一条边(v,w)E，对应有一个值cap(v,w)0，称为边的容量。 这样的有向图G称作一个网络。（2） 网络流 网络上的流是定义在网络的边集合E上的一个非负函数flow=flow(v,w)，并称flow(v,w)为边(v,w)上的流量。,23,（3） 可行流 满足下述条件的流flow称为可行流： (3.1)容量约束：对每一条边(v,w)E，0flow(v,w)cap(v,w)。 (3.2)平衡约束： 对于中间顶点：流出量=流入量。 即对每个vV(vs,t)有：顶点v的流出量顶点v的流入量=0，即对于源s

16、：s的流出量s的流入量=源的净输出量f，即对于汇t：t的流入量t的流出量的=汇的净输入量f，即式中f 称为这个可行流的流量，即源的净输出量(或汇的净输入量)。 可行流总是存在的。 例如，让所有边的流量flow(v,w)=0，就得到一个其流量f=0的可行流(称为0流)。,24,（4） 边流 对于网络G的一个给定的可行流flow，将网络中满足flow(v,w)=cap(v,w)的边称为饱和边；flow(v,w)0的边称为非零流边。当边(v,w)既不是一条零流边也不是一条饱和边时，称为弱流边。 （5） 最大流 最大流问题即求网络G的一个可行流flow，使其流量f达到最大。即flow满足： 0flow(v,w)cap(v,w)，(v,w)E；且（6） 流的费用 在实际应用中，与网络流有关的问题，不仅涉及流量，而且还有费用的因素。此时网络的每一条边(v,w)除了给定容量cap(v,w)外，还定义了一个单位流量费用cost(v,w)。对于网络中一个给定的流flow，其费用定义为：,