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

计算机算法设计与分析 Design and Analysis of Computer Algorithms 第八章 线性规划与网络流 Linear Programming and Network Flow 提纲 一、线性规划问题和单纯形算法 二、最大网络流问题 三、最小费用流问题 提纲 一、线性规划问题和单纯形算法 二、最大网络流问题 三、最小费用流问题 1.1 线性规划问题及表示 例子：政治家选举问题 有三种不同类型的选区：市区、郊区和乡村，这些区域分别有100 000、200 000和50 000个登记选民。一个政治家希望在每一个选区都赢得大多数的选票。主要政策有修路、枪械管理、农业补贴以及增加公共运输的汽油税。根据其竞选班子的研究，可以估计通过在某项政策上花费1000美元做广告，在每个选区可以赢取或输掉选民的千人数。右边表格给出这种信息： 1.1 线性规划问题及表示 问题表示 设 、 、 、 分别表示支出在修路、枪械管理、农业补贴以及汽油税广告上的千美元数 目标：最小化表达式 满足约束： 1.1 线性规划问题及表示 一般线性规划问题表示 s.t. 1.1 线性规划问题及表示 满足约束条件(8.2)-(8.5)式的一组变量值称为线性规划问题的一个可行解。 使约束条件(8.2)-(8.5)式中的某n个约束以等号满足的可行解称为线性规划问题的基本可行解。 所有可行解构成的集合称为线性规划问题的可行区域。 使目标函数取得最值的可行解称为最优解。 在最优解处目标函数的值称为最优值。 有些情况下可能不存在最优解。通常有两种情况： (1)根本没有可行解，即给定的约束条件之间是相互排斥的； (2)目标函数没有极值，也就是说在n 维空间中的某个方向上，目标函数值可以无限增大或减小，而仍满足约束条件，此时目标函数值无界。 1.1 线性规划问题及表示 考察包含两个变量的线性规划 最大化： 满足约束： 1.1 线性规划问题及表示 考察包含两个变量的线性规划 最大化： 满足约束： 1.2 线性规划基本定理 定理1： 线性规划问题的可行区域是凸集； 定理2：线性规划问题有最优解的充要条件是它必有一基本可行最优解； 定理3：若线性规划问题有最优解，必在可行区域的某顶点上得到。 1.3 单纯形及单纯形算法 如果有 个变量，每个约束定义了 维空间中的一个半空间，这些半空间的交集形成的可行区域称作单纯形。 单纯形算法以一个线性规划作为输入，输出它的一个最优解。它从单纯形的某个顶点开始，执行一系列迭代，在每次迭代中，它沿着单纯形的一条边从当前顶点移动到一个目标值大于（或小于）当前顶点的相邻顶点，当达到一个局部的最优值时，单纯形算法结束。 因为可行区域是凸的且目标函数是线性的，所以局部最优实际上是全局最优的。 1.4 约束标准型线性规划问题 标准型线性规划： s.t. 1.4 约束标准型线性规划问题 在标准型线性规划问题中，如果每一个等式约束中，至少有一个变量的系数为正，且这个变量只在该约束中出现。 在每一约束方程中选择一个这样的变量，并以它作为变量求解该约束方程。这样选出来的变量称为左端变量或基本变量，其总数为m个。剩下的n-m个变量称为右端变量或非基本变量。 这一类特殊的标准型线性规划问题称为约束标准型线性规划问题。 1.4 约束标准型线性规划问题 例如： 此例中，n=6，m=3；基本变量为 ， 和 ；非基本变量为 ， 和 。 1.5 将一般线性规划转换成约束标准型 对最小化线性规划问题，只要将目标函数乘以-1即可化为等价的最大化线性规划问题。 把(8.2)或(8.4)形式的不等式约束转换为等式约束。具体做法是，引入松弛变量，将不等式转化为等式，且引入的松弛变量具有非负性 。 在求解过程中，应当将松弛变量与原来变量同样对待。求解结束后，舍弃松弛变量。 1.5 将一般线性规划转换成约束标准型 设不等式约束形式为： 引入一个松弛变量s： 使用 来表示与第i个不等式关联的松弛变量： 等式左边的变量称为基本变量，等式右边的变量称为非基本变量。 1.5 将一般线性规划转换成约束标准型 一个例子 最大化： 满足约束： 1.5 将一般线性规划转换成约束标准型 引入松弛变量 ， ， ，得到标准型： 最大化： 满足约束： 1.6 标准型的元组表示 标准型的元组表示： N表示非基本变量下标的集合； B表示基本变量下标的集合； b表示由等式约束中