线性规划与网络流课件

1、华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件1 第8章 线性规划与网络流 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件2 学习要点学习要点 理解线性规划算法模型理解线性规划算法模型 掌握解线性规划问题的单纯形算法掌握解线性规划问题的单纯形算法 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件3 8.1 8.1 线性规划问题和单纯形算法线性规划问题和单纯形算法 n线性规划问题及其表示线性规划问题及其表示 n线性规划问题可表示为如下形式线性规划问题可表示为如下形式： )1.8(max 1 n j jjx c 1 1 112 1 1212

2、3 1 1,2,(8.2) 1,(8.3) 1,(8.4) 01,2,(8.5) n itti t n jttj t n kttk t t a xbim a xbjmmm a xbkmmmmm xtn s.t. 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件4 n变量满足约束条件变量满足约束条件(8.2)-(8.5)(8.2)-(8.5)式的一组值称为线性规划式的一组值称为线性规划 问题的一个问题的一个可行解可行解。 n所有可行解构成的集合称为线性规划问题的所有可行解构成的集合称为线性规划问题的可行区域可行区域。 n使目标函数取得极值的可行解称为使目标函数取得极值的可行解称

3、为最优解最优解。 n在最优解处目标函数的值称为在最优解处目标函数的值称为最优值最优值。 n有些情况下可能不存在最优解。有些情况下可能不存在最优解。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件5 n通常有两种情况：通常有两种情况： (1)(1)根本没有可行解，即给定的约束条件之间是相互排斥的，根本没有可行解，即给定的约束条件之间是相互排斥的， 可行区域为空集；可行区域为空集； (2)(2)目标函数没有极值，也就是说在目标函数没有极值，也就是说在n n 维空间中的某个方向维空间中的某个方向 上，目标函数值可以无限增大，而仍满足约束条件，此时上，目标函数值可以无限增大，而仍满

4、足约束条件，此时 目标函数值无界。目标函数值无界。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件6 n这个问题的解为这个问题的解为 (x1,x2,x3,x4) = (0,3.5,4.5,1)(x1,x2,x3,x4) = (0,3.5,4.5,1)； 最优值为最优值为1616。 4321 3maxxxxxz 12 9 072 182 432 4321 42 31 xxx xxxx xx xx 4 , 3 , 2, 10ixi 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件7 线性规划基本定理线性规划基本定理 n约束条件约束条件(8.2)-(8.5)(8

5、.2)-(8.5)中中n n个约束以等号满足的可行解称为个约束以等号满足的可行解称为 线性规划问题的线性规划问题的基本可行解基本可行解。 n若若nmnm，则基本可行解中至少有，则基本可行解中至少有n-mn-m个分量为个分量为0 0，也就是说，也就是说， 基本可行解中最多有基本可行解中最多有m m个分量非零。个分量非零。 n线性规划基本定理：线性规划基本定理：如果线性规划问题有最优解，则必有如果线性规划问题有最优解，则必有 一基本可行最优解。一基本可行最优解。 n上述定理的重要意义在于，它把一个最优化问题转化为一上述定理的重要意义在于，它把一个最优化问题转化为一 个组合问题，即在个组合问题，即在

6、(8.2) -(8.5)(8.2) -(8.5)式的式的m+nm+n个约束条件中，个约束条件中， 确定最优解应满足其中哪确定最优解应满足其中哪n n个约束条件的问题。个约束条件的问题。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件8 线性规划基本定理线性规划基本定理 n由此可知，只要对各种不同的组合进行测试，并比较每种由此可知，只要对各种不同的组合进行测试，并比较每种 情况下的目标函数值，直到找到最优解。情况下的目标函数值，直到找到最优解。 nDantzigDantzig于于19481948年提出了线性规划问题的单纯形算法。年提出了线性规划问题的单纯形算法。 n单纯形算法

7、的特点是：单纯形算法的特点是： n（1 1）只对约束条件的若干组合进行测试，测试的每一步）只对约束条件的若干组合进行测试，测试的每一步 都使目标函数的值增加；都使目标函数的值增加； n（2 2）一般经过不大于）一般经过不大于m m或或n n次迭代就可求得最优解。次迭代就可求得最优解。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件9 约束标准型线性规划问题的单纯形算法约束标准型线性规划问题的单纯形算法 n当线性规划问题中没有不等式约束当线性规划问题中没有不等式约束(8.2)(8.2)和和(8.4)(8.4)式，式， 而只有等式约束而只有等式约束(8.3)(8.3)和变量非负

8、约束和变量非负约束(8.5)(8.5)时，称该时，称该 线性规划问题具有线性规划问题具有标准形式标准形式。 n为便于讨论，不妨先考察一类更特殊的标准形式线性为便于讨论，不妨先考察一类更特殊的标准形式线性 规划问题。这一类线性规划问题中，每一个等式约束规划问题。这一类线性规划问题中，每一个等式约束 中，至少有一个变量的系数为正，且这个变量只在该中，至少有一个变量的系数为正，且这个变量只在该 约束中出现。约束中出现。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件10 约束标准型线性规划问题的单纯形算法约束标准型线性规划问题的单纯形算法 n在每一约束方程中选择一个这样的变量，并

9、以它作为在每一约束方程中选择一个这样的变量，并以它作为 变量求解该约束方程。这样选出来的变量称为左端变变量求解该约束方程。这样选出来的变量称为左端变 量或量或基本变量基本变量，其总数为，其总数为m m个。剩下的个。剩下的n-mn-m个变量称为个变量称为 右端变量或右端变量或非基本变量非基本变量。 n这一类特殊的标准形式线性规划问题称为这一类特殊的标准形式线性规划问题称为约束标准型约束标准型 线性规划问题线性规划问题。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件11 约束标准型线性规划问题的单纯形算法约束标准型线性规划问题的单纯形算法 n虽然约束标准型线性规划问题非常特殊

10、，但是对于理虽然约束标准型线性规划问题非常特殊，但是对于理 解线性规划问题的单纯形算法是非常重要的。解线性规划问题的单纯形算法是非常重要的。 n稍后将看到，任意一个线性规划问题可以转换为约束稍后将看到，任意一个线性规划问题可以转换为约束 标准型线性规划问题。标准型线性规划问题。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件12 532 23maxxxxz 10834 1242 723 5326 324 5321 xxxx xxx xxxx 6 , 5 ,4, 3 ,2, 10ixi x2x3x5 z0-13-2 x173-12 x412-240 x610-438 华南理工

11、大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件13 n任何约束标准型线性规划问题，只要将所有非基本变量都置任何约束标准型线性规划问题，只要将所有非基本变量都置 为为0 0，从约束方程式中解出满足约束的基本变量的值，可求，从约束方程式中解出满足约束的基本变量的值，可求 得一个基本可行解。得一个基本可行解。 n单纯形算法的基本思想就是从一个基本可行解出发，进行一单纯形算法的基本思想就是从一个基本可行解出发，进行一 系列的基本可行解的变换。系列的基本可行解的变换。 n每次变换将一个非基本变量与一个基本变量互调位置，且保每次变换将一个非基本变量与一个基本变量互调位置，且保 持当前的线性规划

12、问题是一个与原问题完全等价的标准线性持当前的线性规划问题是一个与原问题完全等价的标准线性 规划问题。规划问题。 n基本可行解基本可行解x=(7,0,0,12,0,10)x=(7,0,0,12,0,10)。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件14 n单纯形算法的第单纯形算法的第1 1步：步：选出使目标函数增加的非基本变量作选出使目标函数增加的非基本变量作 为为入基变量入基变量。 n查看单纯形表的第查看单纯形表的第1 1行（也称之为行（也称之为z z行）中标有非基本变量的行）中标有非基本变量的 各列中的值。各列中的值。 n选出使目标函数增加的非基本变量作为入基变量。

13、选出使目标函数增加的非基本变量作为入基变量。 nz z行中的正系数非基本变量都满足要求。行中的正系数非基本变量都满足要求。 n在上面单纯形表的在上面单纯形表的z z行中只有行中只有1 1列为正，即非基本变量相应的列为正，即非基本变量相应的 列，其值为列，其值为3 3。 n选取非基本变量选取非基本变量x x3 3作为入基变量。作为入基变量。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件15 n单纯形算法的第单纯形算法的第2 2步：步：选取选取离基变量离基变量。 n在单纯形表中考察由第在单纯形表中考察由第1 1步选出的入基变量所相应的列。步选出的入基变量所相应的列。 n在一个

14、基本变量变为负值之前，入基变量可以增到多大。在一个基本变量变为负值之前，入基变量可以增到多大。 n如果入基变量所在的列与基本变量所在行交叉处的表元素为如果入基变量所在的列与基本变量所在行交叉处的表元素为 负数，那么该元素将不受任何限制，相应的基本变量只会越负数，那么该元素将不受任何限制，相应的基本变量只会越 变越大。变越大。 n如果入基变量所在列的所有元素都是负值，则目标函数无界，如果入基变量所在列的所有元素都是负值，则目标函数无界， 已经得到了问题的无界解。已经得到了问题的无界解。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件16 n如果选出的列中有一个或多个元素为正数

15、，要弄清是哪个数如果选出的列中有一个或多个元素为正数，要弄清是哪个数 限制了入基变量值的增加。限制了入基变量值的增加。 n受限的增加量可以用入基变量所在列的元素（称为主元素）受限的增加量可以用入基变量所在列的元素（称为主元素） 来除主元素所在行的来除主元素所在行的“常数列常数列”（最左边的列）中元素而得（最左边的列）中元素而得 到。所得到数值越小说明受到限制越多。到。所得到数值越小说明受到限制越多。 n应该选取受到限制最多的基本变量作为离基变量，才能保证应该选取受到限制最多的基本变量作为离基变量，才能保证 将入基变量与离基变量互调位置后，仍满足约束条件。将入基变量与离基变量互调位置后，仍满足约

16、束条件。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件17 n上例中，惟一的一个值为正的上例中，惟一的一个值为正的z z行元素是行元素是3 3，它所在列中有，它所在列中有2 2 个正元素，即个正元素，即4 4和和3 3。 nmin12/4,10/3=4min12/4,10/3=4，应该选取，应该选取x x4 4为离基变量；为离基变量； n入基变量入基变量x x3 3取值为取值为3 3。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件18 n单纯形算法的第单纯形算法的第3 3步：转轴变换步：转轴变换。 n转轴变换的目的是将入基变量与离基变量互调位置。转轴

17、变换的目的是将入基变量与离基变量互调位置。 n给入基变量一个增值，使之成为基本变量；给入基变量一个增值，使之成为基本变量； n修改离基变量，让入基变量所在列中，离基变量所在行的元修改离基变量，让入基变量所在列中，离基变量所在行的元 素值减为零，而使之成为非基本变量。素值减为零，而使之成为非基本变量。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件19 n解离基变量所相应的方程，将入基变量解离基变量所相应的方程，将入基变量x x3 3用离基变量用离基变量x x4 4表示表示 为为 n再将其代入其他基本变量和所在的行中消去再将其代入其他基本变量和所在的行中消去x x3 3 ，

18、n代入目标函数得到代入目标函数得到 n形成新单纯形表形成新单纯形表 3 4 1 2 1 423 xxx 18 4 3 2 5 102 4 1 2 5 5426 5421 xxxx xxxx 542 2 4 3 2 1 9xxxz x2x4x5 z91/2 -3/4 -2 x1105/21/22 x33-1/21/40 x61-5/2-3/48 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件20 n单纯形算法的第单纯形算法的第4 4步：步：转回并重复第转回并重复第1 1步，进一步改进目标函步，进一步改进目标函 数值。数值。 n不断重复上述过程，直到不断重复上述过程，直到z z

19、行的所有非基本变量系数都变成行的所有非基本变量系数都变成 负值为止。这表明目标函数不可能再增加了。负值为止。这表明目标函数不可能再增加了。 n在上面的单纯形表中，惟一的值为正的在上面的单纯形表中，惟一的值为正的z z行元素是非基本变行元素是非基本变 量量x x2 2相应的列，其值为相应的列，其值为1/21/2。 n因此，选取非基本变量因此，选取非基本变量x x2 2作为入基变量。作为入基变量。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件21 n它所在列中有惟一的正元素它所在列中有惟一的正元素5/25/2，即基本变量，即基本变量x x1 1相应行的元相应行的元 素。素。

20、n因此，选取因此，选取x x1 1为离基变量。为离基变量。 n再经步骤再经步骤3 3的转轴变换得到新单纯形表。的转轴变换得到新单纯形表。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件22 n新单纯形表新单纯形表z z行的所有非基本变量系数都变成负值，求解过行的所有非基本变量系数都变成负值，求解过 程结束。程结束。 n整个问题的解可以从最后一张单纯形表的常数列中读出。整个问题的解可以从最后一张单纯形表的常数列中读出。 n目标函数的最大值为目标函数的最大值为1111； n最优解为：最优解为：x x* *=(0,4,5,0,0,11)=(0,4,5,0,0,11)。 x1x4x

21、5 z11-1/5 -4/5 -12/5 x245/21/104/5 x351/53/102/5 x6111-1/210 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件23 单纯形算法计算步骤单纯形算法计算步骤 n单纯形算法的计算过程可以用单纯形表的形式归纳为一系列单纯形算法的计算过程可以用单纯形表的形式归纳为一系列 基本矩阵运算。基本矩阵运算。 n主要运算为转轴变换，该变换类似解线性方程组的高斯消去主要运算为转轴变换，该变换类似解线性方程组的高斯消去 法中的消元变换。法中的消元变换。 n单纯形表中变量说明：单纯形表中变量说明： n 为基本变量，为基本变量， 为非基本变量。

22、为非基本变量。 n基本变量下标集为基本变量下标集为B=1,2,m； 非基本变量下标集为非基本变量下标集为 N=m+1,m+2,n； n当前基本可行解为（当前基本可行解为（ ）。）。 m xxx, 21 nmm xxx, 21 0,0, 21 m bbb 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件24 单纯形算法计算步骤单纯形算法计算步骤 xm+1xm+2xn zc0cm+1cm+2cn x1b1a1m+1a1m+2a1n x2b2a2m+1a2m+2a2n xmbmamm+1amm+2amn 单纯形表单纯形表 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络

23、流课件25 n单纯形算法计算步骤单纯形算法计算步骤如下：如下： n步骤步骤1 1：选入基变量选入基变量。 n如果所有如果所有c cj j 0 0，则当前基本可行解为最优解，计算结束。，则当前基本可行解为最优解，计算结束。 n否则取否则取c ce e00相应的非基本变量相应的非基本变量x xe e为入基变量。为入基变量。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件26 n步骤步骤2 2：选离基变量选离基变量。 n对于步骤对于步骤1 1选出的入基变量选出的入基变量x xe e ，如果所有，如果所有a aie ie 0 0 ，则最优解 ，则最优解 无界，计算结束。无界，计算结

24、束。 n否则计算否则计算 n选取基本变量选取基本变量x xk k为离基变量。为离基变量。 n新的基本变量下标集为新的基本变量下标集为 n新的非基本变量下标集为新的非基本变量下标集为 ke k ie i a a b a b ie 0 min keBB ekNN 单纯形算法计算步骤单纯形算法计算步骤(续续)： 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件27 n步骤步骤3 3：作转轴变换作转轴变换。 n新单纯形表中各元素变换如下新单纯形表中各元素变换如下。 ke k e ke k iei i a b b Bi a b abb （8.10） ke ie ik ke kj iei

25、j ij a a a NjBi a a aaa, （8.11） 单纯形算法计算步骤单纯形算法计算步骤(续续)： 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件28 ke ek ke kj ej a a Nj a a a 1 ke e k ke ki ei i a c c Ni a a ccc （8.13） （8.12） n步骤步骤4 4：转步骤转步骤1 1。 单纯形算法计算步骤单纯形算法计算步骤(续续)： 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件29 将一般问题转化为约束标准型将一般问题转化为约束标准型 n有几种巧妙的办法可以将一般的线性规划问题转

26、换为约束标有几种巧妙的办法可以将一般的线性规划问题转换为约束标 准型线性规划问题。准型线性规划问题。 n首先，需要把首先，需要把(8.2)(8.2)或或(8.4)(8.4)形式的不等式约束转换为等式约形式的不等式约束转换为等式约 束。具体做法是，引入束。具体做法是，引入松弛变量松弛变量，利用松弛变量的非负性，利用松弛变量的非负性， 将不等式转化为等式。松驰变量记为将不等式转化为等式。松驰变量记为y yi i，共有，共有m m1 1+m+m3 3个。个。 n在求解过程中，应当将松弛变量与原来变量同样对待。求解在求解过程中，应当将松弛变量与原来变量同样对待。求解 结束后，抛弃松弛变量。结束后，抛弃

27、松弛变量。 n注意松弛变量前的符号由相应的原不等式的方向所确定。注意松弛变量前的符号由相应的原不等式的方向所确定。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件30 将一般问题转化为约束标准型将一般问题转化为约束标准型 12 9 072 182 432 4321 42 31 xxx xxxx xx xx 12 9 072 182 3432 4321 242 131 yxxx xxxx yxx yxx 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件31 n为了进一步构造标准型约束，还需要引入为了进一步构造标准型约束，还需要引入m m个个人工变量人工变量，

28、记，记 为为z zi i。 n至此，原问题已经变换为等价的约束标准型线性规划问题。至此，原问题已经变换为等价的约束标准型线性规划问题。 n对极小化线性规划问题，只要将目标函数乘以对极小化线性规划问题，只要将目标函数乘以-1-1即可化为等即可化为等 价的极大化线性规划问题。价的极大化线性规划问题。 12 9 072 182 34324 43213 2422 1311 yxxxz xxxxz yxxz yxxz 将一般问题转化为约束标准型将一般问题转化为约束标准型 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件32 一般线性规划问题的一般线性规划问题的2 2阶段单纯形算法阶段单

29、纯形算法 n引入人工变量后的线性规划问题与原问题并不等价，除非所引入人工变量后的线性规划问题与原问题并不等价，除非所 有有z zi i都是都是0 0 。 n为了解决这个问题，在求解时必须分为了解决这个问题，在求解时必须分2 2个阶段进行。个阶段进行。 n第一阶段用一个辅助目标函数第一阶段用一个辅助目标函数 替代原来的目替代原来的目 标函数。标函数。 n这个线性规划问题称为原线性规划问题所相应的辅助线性规这个线性规划问题称为原线性规划问题所相应的辅助线性规 划问题。划问题。 m i i zz 1 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件33 一般线性规划问题的一般线性规

30、划问题的2 2阶段单纯形算法阶段单纯形算法 n对辅助线性规划问题用单纯形算法求解。对辅助线性规划问题用单纯形算法求解。 n如果原线性规划问题有可行解，则辅助线性规划问题就有最如果原线性规划问题有可行解，则辅助线性规划问题就有最 优解，且其最优值为优解，且其最优值为0 0，即所有，即所有z zi i都为都为0 0。 n在辅助线性规划问题最后的单纯形表中，所有在辅助线性规划问题最后的单纯形表中，所有z zi i均为非基本均为非基本 变量。变量。 n划掉所有划掉所有z zi i相应的列，剩下的就是只含相应的列，剩下的就是只含x xi i和和y yi i的约束标准型的约束标准型 线性规划问题了。线性规

31、划问题了。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件34 一般线性规划问题的一般线性规划问题的2 2阶段单纯形算法阶段单纯形算法 n单纯形算法第一阶段的任务就是构造一个初始基本可行解。单纯形算法第一阶段的任务就是构造一个初始基本可行解。 n单纯形算法第二阶段的目标是求解由第一阶段导出的问题。单纯形算法第二阶段的目标是求解由第一阶段导出的问题。 n此时要用原来的目标函数进行求解。此时要用原来的目标函数进行求解。 n如果在辅助线性规划问题最后的单纯形表中，如果在辅助线性规划问题最后的单纯形表中， z zi i不全为不全为0 0， 则原线性规划问题没有可行解，从而原线性规划

32、问题无解。则原线性规划问题没有可行解，从而原线性规划问题无解。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件35 退化情形的处理退化情形的处理 n用单纯形算法解一般的线性规划问题时，可能会遇到退化的用单纯形算法解一般的线性规划问题时，可能会遇到退化的 情形，即在迭代计算的某一步中，常数列中的某个元素的值情形，即在迭代计算的某一步中，常数列中的某个元素的值 变成变成0 0，使得相应的基本变量取值为，使得相应的基本变量取值为0 0。 n如果选取退化的基本变量为离基变量，则作转轴变换前后的如果选取退化的基本变量为离基变量，则作转轴变换前后的 目标函数值不变。在这种情况下，算法不

33、能保证目标函数值目标函数值不变。在这种情况下，算法不能保证目标函数值 严格递增，因此，可能出现无限循环。严格递增，因此，可能出现无限循环。 n考察下面的由考察下面的由BealeBeale在在19551955年提出的退化问题的例子。年提出的退化问题的例子。 n按照按照2 2阶段单纯形算法求解该问题将出现无限循环。阶段单纯形算法求解该问题将出现无限循环。 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件36 退化情形的处理退化情形的处理 4321 6 2 1 20 4 3 maxxxxxz 1 03 2 1 12 2 1 098 4 1 3 4321 4321 x xxxx xxxx 4 , 3 , 2, 10ixi 华南理工大学 计算机科学与工程学院 郑运平. 线性规划与网络流课件37 nBlandBland提出避免循环的一个简单易行的方法。提出避免循环的一个简单易行的方法。 nBlandBland提出在单纯