第8章 线性规划与网络流 计算机算法的设计与分析（第3版） .pptVIP

学习要点 理解线性规划算法模型 掌握解线性规划问题的单纯形算法 理解网络与网络流的基本概念 掌握网络最大流的增广路算法 掌握网络最大流的预流推进算法 掌握网络最小费用流的消圈算法 掌握网络最小费用流的最小费用路算法 掌握网络最小费用流的网络单纯形算法;8.1 线性规划问题和单纯形算法;变量满足约束条件(8.2)-(8.5)式的一组值称为线性规划问题的一个可行解。 所有可行解构成的集合称为线性规划问题的可行区域。 使目标函数取得极值的可行解称为最优解。 在最优解处目标函数的值称为最优值。 有些情况下可能不存在最优解。 通常有两种情况： (1)根本没有可行解，即给定的约束条件之间是相互排斥的，可行区域为空集； (2)目标函数没有极值，也就是说在n 维空间中的某个方向上，目标函数值可以无限增大，而仍满足约束条件，此时目标函数值无界。;这个问题的解为 (x1,x2,x3,x4) = (0,3.5,4.5,1)；最优值为16。 ;线性规划基本定理 ;任何约束标准型线性规划问题，只要将所有非基本变量都置为0，从约束方程式中解出满足约束的基本变量的值，可求得一个基本可行解。 单纯形算法的基本思想就是从一个基本可行解出发，进行一系列的基本可行解的变换。 每次变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个与原问题完全等价的标准线性规划问题。 基本可行解x=(7,0,0,12,0,10)。 单纯形算法的第1步：选出使目标函数增加的非基本变量作为入基变量。 查看单纯形表的第1行（也称之为z行）中标有非基本变量的各列中的值。 选出使目标函数增加的非基本变量作为入基变量。 z行中的正系数非基本变量都满足要求。 在上面单纯形表的z行中只有1列为正，即非基本变量相应的列，其值为3。 选取非基本变量x3作为入基变量。 单纯形算法的第2步：选取离基变量。 在单纯形表中考察由第1步选出的入基变量所相应的列。 在一个基本变量变为负值之前，入基变量可以增到多大。;如果入基变量所在的列与基本变量所在行交叉处的表元素为负数，那么该元素将不受任何限制，相应的基本变量只会越变越大。 如果入基变量所在列的所有元素都??负值，则目标函数无界，已经得到了问题的无界解。 如果选出的列中有一个或多个元素为正数，要弄清是哪个数限制了入基变量值的增加。 受限的增加量可以用入基变量所在列的元素（称为主元素）来除主元素所在行的“常数列”（最左边的列）中元素而得到。所得到数值越小说明受到限制越多。 应该选取受到限制最多的基本变量作为离基变量，才能保证将入基变量与离基变量互调位置后，仍满足约束条件。 上例中，惟一的一个值为正的z行元素是3，它所在列中有2个正元素，即4和3。 min{12/4,10/3}=4，应该选取x4为离基变量； 入基变量x3取值为3。 单纯形算法的第3步：转轴变换。 转轴变换的目的是将入基变量与离基变量互调位置。 给入基变量一个增值，使之成为基本变量； 修改离基变量，让入基变量所在列中，离基变量所在行的元素值减为零，而使之成为非基本变量。;解离基变量所相应的方程，将入基变量x3用离基变量x4表示为 再将其代入其他基本变量和所在的行中消去x3 ， 代入目标函数得到 形成新单纯形表;单纯形算法的第4步：转回并重复第1步，进一步改进目标函数值。 不断重复上述过程，直到z行的所有非基本变量系数都变成负值为止。这表明目标函数不可能再增加了。 在上面的单纯形表中，惟一的值为正的z行元素是非基本变量x2相应的列，其值为1/2。 因此，选取非基本变量x2作为入基变量。 它所在列中有惟一的正元素5/2，即基本变量x1相应行的元素。 因此，选取x1为离基变量。 再经步骤3的转轴变换得到新单纯形表。 新单纯形表z行的所有非基本变量系数都变成负值，求解过程结束。 整个问题的解可以从最后一张单纯形表的常数列中读出。 目标函数的最大值为11； 最优解为：x*=(0,4,5,0,0,11)。;单纯形算法计算步骤 ;单纯形算法计算步骤如下： 步骤1：选入基变量。 如果所有cj?0，则当前基本可行解为最优解，计算结束。 否则取ce0相应的非基本变量xe为入基变量。 步骤2：选离基变量。 对于步骤1选出的入基变量xe ，如果所有aie?0 ，则最优解无界，计算结束。 否则计算 选取基本变量xk为离基变量。 新的基本变量下标集为 新的非基本变量下标集为 步骤3：作转轴变换。 新单纯形表中各元素变换如下。; （8.10）