第02章-单纯形法120404

1、1第第2 2章章线性规划概念、建线性规划概念、建模与求解模与求解本章内容重点本章内容重点 线性规划模型结构线性规划模型结构 线性规划解的基本概念与性质线性规划解的基本概念与性质 线性规划单纯形法线性规划单纯形法 线性规划应用线性规划应用-建模建模 某工厂拥有某工厂拥有A A、B B、C C 三种类型的设备，三种类型的设备，生产甲、乙两种产品。每件产品在生产中需生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的要占用的设备机时数，每件产品可以获得的利润以及三设备可利用的时数如下表所示：利润以及三设备可利用的时数如下表所示：问题：工厂应如何安排生产可获得最大的总问题：工厂

2、应如何安排生产可获得最大的总利润？利润？例例4模型模型解：设变量解：设变量 xi 为第为第 i 种（甲、乙）产品种（甲、乙）产品的生产件数（的生产件数（i1，2）。）。目标函数目标函数 Max z =1500 x1+2500 x2约束条件约束条件 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0 5线性规划的一般模型结构：线性规划的一般模型结构：目标函数：目标函数： Max(Min) z = c1x1 + c2x2 + + cnxn约束条件：约束条件： a11x1+a12x2+a1nxn( =, )b1 a21x1+a22x2+a2nxn( =, )b

3、2 . . . am1x1+am2x2 +amnxn( =, )bm x1 ，x2 ， ，xn 06 a11x1+a12x2+ +a1n xn b1 a21x1+a22x2+ +a2n xn b2 . . . am1x1+am2x2 +amnxn bm x1 ，x2 ， ，xn 02.3.1 线性规划问题的规范形式和标准形式线性规划问题的规范形式和标准形式(1) 线性规划规范形式线性规划规范形式目标函数：目标函数： Max z = c1x1 + c2x2 + + cnxn约束条件：约束条件：7 线性规划规范形式的特点线性规划规范形式的特点规范形式有如下四个特点：规范形式有如下四个特点：目标最大

4、化目标最大化约束为小于等于的不等式约束为小于等于的不等式决策变量均非负决策变量均非负右端项非负右端项非负。 0.xbAxtsxczMaxT8Max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 . . .am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0线性规划的标准形式线性规划的标准形式 目标函数：目标函数： 约束条件：约束条件：9 线性规划标准形式的特点线性规划标准形式的特点标准形式有如下四个特点：标准形式有如下四个特点： 目标最大化目标

5、最大化 约束为等式约束为等式 决策变量均非负决策变量均非负 右端项非负右端项非负。 对于各种非标准形式的线性规划对于各种非标准形式的线性规划问题，总可以通过以下变换，将其转问题，总可以通过以下变换，将其转化为标准形式化为标准形式: :10设目标函数为设目标函数为 Min f = c1x1 + c2x2 + + cnxn 则可以令则可以令z-f ，该极小化问题与下面的极，该极小化问题与下面的极大化问题有相同的最优解，即大化问题有相同的最优解，即 Max z = -c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目

6、标函数值却相解相同，但他们最优解的目标函数值却相差一个符号，即差一个符号，即 Min f - Max z 线性规划标准形式的转化：线性规划标准形式的转化： 极小化目标函数的问题：极小化目标函数的问题：11设约束条件为设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量可以引进一个新的变量s ，使它等于，使它等于约束右边与左边之差约束右边与左边之差 s =bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，显然，s 也具有非负约束，即也具有非负约束，即s0， 这时新的约束条件成为这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn

7、+s = bi 约束条件不是等式（约束条件不是等式（）的问题）的问题12当约束条件为当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时，类似地令时，类似地令 s =(ai1 x1+ai2 x2+ +ain xn)- bi 显然，显然，s 也具有非负约束，即也具有非负约束，即s0，这时新的约束条件成为这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi约束条件不是等式（约束条件不是等式（）的问题）的问题13 为了使约束由不等式成为等式而为了使约束由不等式成为等式而引进的变量引进的变量 s 称为称为“松弛变量松弛变量”。 如果原问题中有若干个非等式约如

8、果原问题中有若干个非等式约束，则将其转化为标准形式时，必须束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。对各个约束引进不同的松弛变量。14Min f = 3.6 x1 - 5.2 x2 + 1.8 x3s.t. 2.3 x1 + 5.2 x2 - 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2+ x3 = 38 x1 , x2 , x3 0 例例2.6 将以下线性规划问题转化为标准形式将以下线性规划问题转化为标准形式解：首先解：首先, ,将目标函数转换成极大化：将目标函数转换成极大化：令令 z= -f = -3.6x1+5.2x2-1.8x3 1

9、5 x4，x5 0。于是，我们可以得到以下标准形式的线于是，我们可以得到以下标准形式的线性规划问题：性规划问题： Max Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3s.t. s.t. 2.3x1+5.2x2-6.1x3+x4 = 15.7 4.1x1 +3.3x3 -x5= 8.9 x1+ x2+ x3 = 38 x1 ,x2 ,x3 ,x4 ,x5 0其次考虑约束，有其次考虑约束，有2 2个不等式约束，引进个不等式约束，引进松弛变量松弛变量16 当某一个变量当某一个变量xj没有非负约束时，没有非负约束时，可以令可以令 xj = xj- xj”其中其中 xj0，xj”

10、0即用两个非负变量之差来表示一个无符即用两个非负变量之差来表示一个无符号限制的变量，当然号限制的变量，当然xj的符号取决于的符号取决于xj和和xj”的大小。的大小。变量无符号限制的问题变量无符号限制的问题 在标准形式中，必须每一个变量均在标准形式中，必须每一个变量均有非负约束。有非负约束。17 当某一个右端项系数为负时，如当某一个右端项系数为负时，如果果 bi m， 秩秩(A) = m，b Rm 。约束等式实质上是一个由约束等式实质上是一个由m个方程个方程n个变个变量构成的方程组，有无穷多组解。记：量构成的方程组，有无穷多组解。记： x = (x1，x2，xn)T 25 如果令其中如果令其中n

11、-m个变量为零，当其个变量为零，当其他他 m个变量在线性方程组中有唯一解时，个变量在线性方程组中有唯一解时，则这则这 n个变量的值构成此方程组的一个个变量的值构成此方程组的一个解。若进一步有这解。若进一步有这 n 个变量的值都非负个变量的值都非负时，这个解就是线性规划可行域的一个时，这个解就是线性规划可行域的一个极点。极点。 根据以上分析，我们建立以下概念根据以上分析，我们建立以下概念 基；基； 基变量、非基变量基变量、非基变量 基本解、基本可行解（极点）基本解、基本可行解（极点） 可行基、最优基可行基、最优基(1) 线性规划的基：线性规划的基： 对于线性规划的约束条件对于线性规划的约束条件

12、Ax=b， x0 设设B是是A矩阵中的一个非奇异矩阵中的一个非奇异（可逆）的（可逆）的mm子矩阵，则称子矩阵，则称B为线性规划的一个基。为线性规划的一个基。 A=( p1 ，p2 ，pn ) ，其中，其中 pj=( a1j ，a2j ，amj )T Rm ， 任取任取 A 中的中的 m 个线性无关列向量个线性无关列向量构成矩阵构成矩阵那么那么B为线性规划的一个基。为线性规划的一个基。 称对应于基称对应于基B的变量的变量为为基变量基变量；其余变量称为；其余变量称为非基变量非基变量。27mjjjjRPpppBim ),(21mjjjxxx,21矩阵描述矩阵描述 设设B是线性规划的一个基，则是线性规

13、划的一个基，则A可以可以表示为表示为 A= B , N x 也可相应地分成也可相应地分成 xB 和和 xN 其中其中xB为为m维列向量，它的各分量维列向量，它的各分量称为基变量，与基称为基变量，与基B的列向量对应；的列向量对应；xN为为n-m列向量，它的各分量称为非基变列向量，它的各分量称为非基变量，与非基矩阵量，与非基矩阵N的列向量对应。的列向量对应。(2) 线性规划问题的基本可行解：线性规划问题的基本可行解：对应于基对应于基B，约束等式，约束等式 Ax = b 可表示为可表示为 xB B,N = b 或或 BxB + NxN = b xN则基变量则基变量 xB = B-1b - B-1Nx

14、N 当取当取 xN = 0，这时有，这时有xB = B-1b 。称。称这类特别的解为这类特别的解为基本解基本解。30 进一步，若得到的基变量进一步，若得到的基变量的值均非负，即的值均非负，即 B-1 b 0 ，则称为则称为基本可行解基本可行解，同时称这，同时称这个基个基 B 为为可行基可行基。例例2.8 把例把例2.1的线性规划模型标准化，的线性规划模型标准化，引入松驰变量引入松驰变量 x3 ，x4 ，x5 0，得到，得到Max z = 1500 x1 + 2500 x2s.t. 3x1+2x2+x3 = 65 (A) 2x1+ x2 +x4 = 40 (B) 3x2 +x5= 75 (C)

15、x1 , x2 , x3 , x4 , x5 0 用用(D), (E), (F), (G), (H) 分别表示分别表示 x1=0、x2=0、x3=0、x4=0、x5=0 这里一共有这里一共有8 8个约束条件，其中个约束条件，其中 3 3 个等式约束。对此，任意固定两个变个等式约束。对此，任意固定两个变量为零，通过解等式构成的方程组（量为零，通过解等式构成的方程组（相当于求解由其中相当于求解由其中 5 5 个方程构成的方个方程构成的方程组），可解得一个点。程组），可解得一个点。 由于当由于当 x2 = x5 = 0 时，即由时，即由(A), (B), (C), (E), (H)构成的方程组无解。

16、构成的方程组无解。故总故总共可求得共可求得9 9个点。个点。33 问题图示中的约束直线交点与此对应问题图示中的约束直线交点与此对应34约束条件约束条件(A)、(B)、(C)、(F)、(G)的解的解对应于对应于直线直线A、B的交点的交点，即：，即： x(1) = (15,10,0,0,45)T约束条件约束条件(A)、(B)、(C)、(F)、(H)的的解对应于解对应于直线直线A、C的交点的交点，即：，即： x(2) = (5,25,0,5,0)T约束条件约束条件(A)、(B)、(C)、(D)、(F)的解的解对应于对应于直线直线A、D的交点的交点，即：，即： x(3) = (0,32.5,0,7.5

17、,-22.5)T35约束条件约束条件(A)、(B)、(C)、(E)、(F)的解对的解对应于应于直线直线A、E的交点的交点，即：，即： x(4) = (65/3,0,0,-10/3,75)T约束条件约束条件(A)、(B)、(C)、(G)、(H)的解对的解对应于应于直线直线B、C的交点的交点，即：，即： x(5) = (7.5,25,-7.5,0,0)T约束条件约束条件(A)、(B)、(C)、(D)、(G)的解对的解对应于应于直线直线B、D的交点的交点，即：，即： x(6) = (0,40,-15,0,-45)T36约束条件约束条件(A)、(B)、(C)、(E)、(G)的解的解对应于对应于直线直线

18、B、E的交点的交点，即：，即： x(7) = (20,0,5,0,75)T约束条件约束条件(A)、(B)、(C)、(D)、(H)的解的解对应于对应于直线直线C、D的交点的交点，即：，即： x(8) = (0,25,15,15,0)T约束条件约束条件(A)、(B)、(C)、(D)、(E)的解的解对应于对应于直线直线D、E的交点的交点，即：，即： x(9) = (0,0,65,40,75)T37 如果交点的坐标如果交点的坐标 (x1 , x2 , x3 , x4 , x5 )T均非负，则该交点就对应于线性规划均非负，则该交点就对应于线性规划可行域的极点可行域的极点 ( 约束多边形的顶点，约束多边形

19、的顶点，如图中如图中A, B; A, C; B, E; C, D和和D, E的的交点交点)；否则，该交点不在可行域内。；否则，该交点不在可行域内。 我们令我们令2个决策变量为零，可以将个决策变量为零，可以将 5 个线性方程组个线性方程组的求解转化为的求解转化为 3 个方个方程组程组的求解，简便且更有价值。的求解，简便且更有价值。例如，例如，A、B交点对应于交点对应于x3 = 0， x4 = 0；在等式约束中令在等式约束中令x3 = 0，x4 = 0，解，解3个等个等式约束方程：式约束方程：可得到可得到 x1 =15，x2 = 10，x5 = 45。即。即A, B交点对应的极点交点对应的极点 x

20、 = (15, 10, 0, 0, 45)T。 由于所有分量都为非负，因此由于所有分量都为非负，因此A, B交点是可行域的极点交点是可行域的极点 ( 顶点顶点 )。 7534026523522121xxxxxx39又知，又知，B, C交点对应于交点对应于 x4= 0，x5= 0，在等式约束中令在等式约束中令x4 = 0，x5 = 0，求，求得到得到 x1 =7.5, x2 = 25, x3 = -7.5。即。即B, C交点对应于点交点对应于点 x = ( 7.5, 25, -7.5, 0, 0 )T。B, C交点不是可行域的极点。交点不是可行域的极点。 同样可以讨论其他交点的情况同样可以讨论其

21、他交点的情况 7534026523221321xxxxxx40可以证明：可以证明：线性规划的基本可行解就是线性规划的基本可行解就是可行域的极点可行域的极点。 这个结论被称为这个结论被称为线性规划的基本定线性规划的基本定理理，重要性在于，重要性在于下列的联系：下列的联系： 可行域极点可行域极点 几何概念几何概念 最优解特征最优解特征 基本可行解基本可行解 代数概念代数概念 可代数求解可代数求解 为求解线性规划问题提供有效途径为求解线性规划问题提供有效途径41例例2.9考虑例考虑例2.82.8的线性规划模型的线性规划模型 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 +

22、2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0 注意，注意，线性规划的基本解、基本可行线性规划的基本解、基本可行 解（极点）和可行基解（极点）和可行基只与线性规划问只与线性规划问 题标准形式的约束条件有关题标准形式的约束条件有关。42 3 2 1 0 0A = （P1 , P2 , P3 , P4 , P5）= 2 1 0 1 0 0 3 0 0 1 A矩阵包含以下矩阵包含以下10个个33的子矩阵：的子矩阵： B1=（p1 ，p2 ，p3） B2=（p1 ，p2 ，p4） B3=（p1 ，p2

23、 ，p5） B4=（p1 ，p3 ，p4） B5=（p1 ，p3 ，p5） B6=（p1 ，p4 ，p5） B7=（p2 ，p3 ，p4） B8=（p2 ，p3 ，p5） B9=（p2 ，p4 ，p5） B10=（p3 ，p4 ，p5） 43 其中其中 B4 = 0，因而，因而B4不是该线性规划不是该线性规划问题的基。其余均为非奇异方阵，因此该问题的基。其余均为非奇异方阵，因此该问题共有问题共有9个基。个基。 例：对于基例：对于基B3=p1 ，p2 ，p5，令非基，令非基变量变量x3 = 0， x4 = 0，解等式约束构成的线，解等式约束构成的线性方程组：性方程组： 3 x1 + 2 x2 +

24、 0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x2 + x5 = 75 44 得到得到 x1 =15，x2 = 10，x5 = 45，对应，对应的基本可行解：的基本可行解：x = (15, 10, 0, 0, 45)T。于是，它对应的基于是，它对应的基B3是一个可行基。是一个可行基。类似可得到类似可得到 x(2) = (5,25,0,5,0)T （对应（对应B2） x(7) = (20,0,5,0,75)T （对应（对应B5） x(8) = (0,25,15,15,0)T （对应（对应B7） x(9) = (0,0,65,40,75)T （对应（对应B10

25、）是是基本可行解基本可行解；45而而x(3)= (0,32.5,0,7.5,-22.5)T（对应（对应B9） x(4)= (65/3,0,0,-10/3,75)T （对应（对应B6） x(5)= (7.5,25,-7.5,0,0)T （对应（对应B1） x(6) = (0,40,-15,0,-45)T （对应（对应B8） 是是基本解基本解。 因此，对应基本可行解（极点）因此，对应基本可行解（极点） 的的B2 B3 B5 B7 B10都是可行基。都是可行基。46 这里指出了这里指出了一种求解线性规划问一种求解线性规划问题的可能途径题的可能途径： 确定线性规划问题的基；确定线性规划问题的基； 若是

26、可行基，则计算相应的基本可若是可行基，则计算相应的基本可行解以及相应解的目标函数值；行解以及相应解的目标函数值； 比较各基本可行解的目标函数值，比较各基本可行解的目标函数值，求得最优解。求得最优解。 由于基的个数是有限的由于基的个数是有限的( ( 个个),),因此必定可以从有限个基本可行解中因此必定可以从有限个基本可行解中找到最优解。找到最优解。mnC 472.4 2.4 线性规划单纯形法线性规划单纯形法2.4.12.4.1单纯形法的基本思路及其实现单纯形法的基本思路及其实现、单纯形法的基本思路、单纯形法的基本思路 通过求线性规划问题基本可行解通过求线性规划问题基本可行解( (极点极点) )寻

27、找最优解的方法称寻找最优解的方法称穷举法穷举法，计算量非常，计算量非常大，造成困难。大，造成困难。 一种很自然的想法是，能否不求所有的一种很自然的想法是，能否不求所有的基本可行解，按照一定规则只求部分基本基本可行解，按照一定规则只求部分基本可行解来达到最优解呢？可行解来达到最优解呢？ 单纯形法提供了单纯形法提供了一种这样的思路和准则一种这样的思路和准则。48单纯形法的基本思路单纯形法的基本思路 首先找到一个基本可行解首先找到一个基本可行解( (极点极点) )； 利用给定准则判断该极点的最优性：利用给定准则判断该极点的最优性： 若该极点是最优解，或得出无有限最优解的若该极点是最优解，或得出无有限

28、最优解的结论则停止；否则，结论则停止；否则， 沿着可行域的边界搜索一个相邻的极沿着可行域的边界搜索一个相邻的极点：点：要求新极点的目标函数值不比原目标函数值要求新极点的目标函数值不比原目标函数值差；差； 再对新极点进行最优性判断。重复再对新极点进行最优性判断。重复此过程。此过程。49单纯形法单纯形法计算流程计算流程3个问题：初始基本可行解的确定？判断？个问题：初始基本可行解的确定？判断？ 求新的基本可行解？求新的基本可行解？初始基本可行解初始基本可行解是否最优解或是否最优解或无限最优解无限最优解? ?结束结束沿边界找新沿边界找新的基本可行解的基本可行解NY单纯形法的基本原理单纯形法的基本原理

29、对于一个基，当非基变量确定以后，基变对于一个基，当非基变量确定以后，基变量和目标函数的值也随之确定。可以得到量和目标函数的值也随之确定。可以得到用非基变量表示的基变量和目标函数的表用非基变量表示的基变量和目标函数的表达式，这时非基变量是自由变量。特别称达式，这时非基变量是自由变量。特别称这时的目标函数为这时的目标函数为典式典式。 对应的基本可行解对应的基本可行解中非基变量均为零中非基变量均为零。 换基换基：从一个极点沿可行域边界移动到相：从一个极点沿可行域边界移动到相邻的极点时，所有非基变量中只有一个变邻的极点时，所有非基变量中只有一个变量的值从量的值从0 0增加，其他非基变量的值都保持增加，

30、其他非基变量的值都保持0 0不变，直至有一个基变量下降为不变，直至有一个基变量下降为0 0。502 2、线性规划的典式形式、线性规划的典式形式 考虑标准形式的线性规划问题考虑标准形式的线性规划问题：51 Max z = c1x1 + c2x2 + + cnxn s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 . . . . . . am1 x1 + am2 x2 + + amn xn = bm x1 , x2 , , xn 0 x1 c1 b1 a11 a12 . a1n x2 c2 b2 a21 a22

31、 . a2nx = . c = . B = . A = . . . . . . . . . xn cn bm am1 am2 . amn 一些符号表示：一些符号表示： 通过运算，所有的基变量都可以用非基变通过运算，所有的基变量都可以用非基变量来表示：量来表示：52矩阵矩阵A可表示为：可表示为：A = ( p1 ，p2 ，pn ) ， 其中其中 pj = ( a1j ，a2j ，amj )T Rm。若找到一个可行基，无防设若找到一个可行基，无防设 B = ( p1 ，p2 ，pm ) ，则则m个基变量为个基变量为 x1 , x2 , , xm，n-m个非基变个非基变量为量为 xm+1 ，xm+2

32、 ，xn 。基变量与目标函数的表达式基变量与目标函数的表达式 我们把由非基变量表示的目标函数形式称我们把由非基变量表示的目标函数形式称为基为基B B相应的目标函数相应的目标函数典式典式。53 x1=b1 (a1m+1xm+1+a1m+2xm+2+a1nxn） x2=b2 (a2m+1xm+1+a2m+2xm+2+a2nxn） . . . xm=bm (amm+1xm+1+amm+2xm+2+amnxn） 把它们代入目标函数，得把它们代入目标函数，得 z = z+ m+1xm+1+ m+2xm+2+ nxn其中其中 j = cj (c1a1j + c2a2j + + cm amj )基变量与目标

33、函数表达式的矩阵形式基变量与目标函数表达式的矩阵形式 矩阵形式：矩阵形式： 向量形式：向量形式：54NTBTNTBNBxNBccbBczNxBbBx)(1111 nmjjjTBjTBnmjjjBxpBccbBczxpBbBx111111)(55、初始基本可行解、初始基本可行解 初始基本可行解应该初始基本可行解应该容易得到容易得到。 对规范形式的线性规划问题，确定初始基本可行对规范形式的线性规划问题，确定初始基本可行解的方法是：解的方法是：以松驰变量为基变量，其余以松驰变量为基变量，其余变量为非基变量。变量为非基变量。 说明：在化标准形式时，在每个约束条件的左端说明：在化标准形式时，在每个约束条

34、件的左端增加了一个松驰变量，这些松驰变量的系数构成了增加了一个松驰变量，这些松驰变量的系数构成了一组单位向量，令非基变量（原变量）全部为零，一组单位向量，令非基变量（原变量）全部为零，求解约束线性方程组，各松驰变量的取值就是其对求解约束线性方程组，各松驰变量的取值就是其对应的右端项的值，而右端项非负，所以这一基本解应的右端项的值，而右端项非负，所以这一基本解是可行解，即极点。是可行解，即极点。、单纯形法的基本步骤、单纯形法的基本步骤(1) (1) 寻找一个初始的可行基和相应寻找一个初始的可行基和相应基本可行解（极点），基本可行解（极点），确定基变量确定基变量、非基变量以及基变量、非基变量、非基

35、变量以及基变量、非基变量（全部等于（全部等于0 0）和目标函数的值，并）和目标函数的值，并将目标函数和基变量分别用非基变将目标函数和基变量分别用非基变量表示量表示; ;56(2) 在目标函数典式表达式中，我们称非在目标函数典式表达式中，我们称非基变量基变量 xj 的系数为检验数记为的系数为检验数记为 j 。 若若 j 0，那么相应的非基变量，那么相应的非基变量 xj 的的值从当前值值从当前值0开始增加时，目标函数值随开始增加时，目标函数值随之增加。这个选定的非基变量之增加。这个选定的非基变量 xj 称为称为“进基变量进基变量”，转，转(3)； 如果任何一个非基变量的值增加都不如果任何一个非基变

36、量的值增加都不能使目标函数值增加，即所有能使目标函数值增加，即所有 j 非正，非正，则当前的基本可行解就是最优解，计算则当前的基本可行解就是最优解，计算结束；结束；57 (3) 观察非基变量表示的基变量表达式观察非基变量表示的基变量表达式:当进基变量增加时，若有基变量的取值当进基变量增加时，若有基变量的取值下降，确定这些基变量的值在进基变量下降，确定这些基变量的值在进基变量增加过程中首先减少到增加过程中首先减少到0的变量的变量xr ，令，令 = min bi /aij aij 0 = br /arj这个基变量这个基变量xr称为称为“出基变量出基变量”。当进。当进基变量的值增加到基变量的值增加到

37、 时，出基变量时，出基变量xr的的值降为值降为0时，当前极点就移动到了相邻的时，当前极点就移动到了相邻的基本可行解（极点），转基本可行解（极点），转(4) ；58 如果当进基变量的值增加时，所有如果当进基变量的值增加时，所有基变量的值都不减少，即所有基变量的值都不减少，即所有aij 非正，非正，则表示可行域是不封闭的，且目标函数则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此值随进基变量的增加可以无限增加，此时，时，不存在有限最优解不存在有限最优解，计算结束；，计算结束；(4) (4) 将进基变量作为新的基变量，出基将进基变量作为新的基变量，出基变量作为新的非基变量，确定新

38、的基本变量作为新的非基变量，确定新的基本可行解和新的目标函数值。在新的基变可行解和新的目标函数值。在新的基变量、非基变量的基础上重复量、非基变量的基础上重复(1)(1)。59例例 用单纯形法的基本思路解线性规划问题用单纯形法的基本思路解线性规划问题60 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 061第一次迭代：第一次迭代：（1）取初始可行基）取初始可行基B10= (p3 , p4 , p5)，那么，那么x3 ，x4

39、 ，x5为基变量，为基变量，x1 ，x2为非基变量。将基为非基变量。将基变量和目标函数用非基变量表示：变量和目标函数用非基变量表示： z =1500 x1+2500 x2 x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2当非基变量当非基变量x1，x2=0时，相应的基变量和目时，相应的基变量和目标函数值为标函数值为x3=65，x4=40，x5= 75，z = 0，得到当前的基本可行解：得到当前的基本可行解：x=(0,0,65,40,75)T，z = 0 。这个解对应于。这个解对应于2.3.2中相应图中的中相应图中的D、E交点。交点。

40、62（2）选择）选择进基变量进基变量。在目标函数在目标函数z = 1500 x1 + 2500 x2中，非基变量中，非基变量x1，x2的系数都是正数，因此的系数都是正数，因此 x1 ，x2进基进基都可以使目标函数都可以使目标函数z增大，但增大，但x2的系数的系数为为2500，绝对值比，绝对值比x1的系数的系数1500大，大，因此把因此把x2作为进基变量可以使目标函作为进基变量可以使目标函数数z增加更快。选择增加更快。选择x2为进基变量，使为进基变量，使x2的值从的值从0开始增加，另一个非基变量开始增加，另一个非基变量x1保持零值不变。保持零值不变。63（3）确定）确定出基变量出基变量。在约束条

41、件在约束条件 x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2中，由于进基变量中，由于进基变量x2在在3个约束条件中的系个约束条件中的系数都是负数，当数都是负数，当x2的值从的值从0开始增加时，基开始增加时，基变量变量x3 、x4 、x5的值分别从当前的值的值分别从当前的值65、40和和75开始减少，当开始减少，当x2增加到增加到25时，时，x5首首先下降为先下降为0成为非基变量。这时，新的基变成为非基变量。这时，新的基变量为量为x3 、x4 、x2 ，新的非基变量为新的非基变量为x1 、x5 ，当前的基本可行解和目标函数值为：当

42、前的基本可行解和目标函数值为：x = (0，25，15，15，0)T，z = 62500。这个。这个解对应于图中的解对应于图中的C、D交点。交点。64第二次迭代：第二次迭代： （1）当前的可行基为）当前的可行基为B7 = (p2 , p3 , p4)，那么那么x2 ，x3 ，x4为基变量，为基变量，x1 ，x5为非为非基变量。将基变量和目标函数用非基变基变量。将基变量和目标函数用非基变量表示：量表示： z = 62500 + 1500 x1 (2500/3) x5 x2 = 25 (1/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3)

43、 x5 65 （2）选择进基变量。在目标函数）选择进基变量。在目标函数z = 62500 + 1500 x1 (2500/3) x5 中，非基变中，非基变量量x1的系数是正数，因此的系数是正数，因此 x1进基可以使目标进基可以使目标函数函数z增大，于是选择增大，于是选择x1进基，使进基，使x1的值从的值从0开始增加开始增加, 另一个非基变量另一个非基变量x5保持零值不保持零值不变。变。 (3)确定出基变量。在约束条件确定出基变量。在约束条件 x2 = 25 (1/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5 66中，由于进基

44、变量中，由于进基变量x1在两个约束条件中的系在两个约束条件中的系数都是负数，当数都是负数，当x1的值从的值从0开始增加时，基变开始增加时，基变量量x3 、x4的值分别从当前的值的值分别从当前的值15、15开始减开始减少，当少，当x1增加到增加到5时，时，x3首先下降为首先下降为0成为非成为非基变量。这时，新的基变量为基变量。这时，新的基变量为x1 、x2 、x4 ，新的非基变量为新的非基变量为x3 、x5 ，当前的基本可行解当前的基本可行解和目标函数值为：和目标函数值为：x = (5，25，0，5，0)T，z = 70000。这个解。这个解对应于图中的对应于图中的A、C交点。交点。 67第三次

45、迭代：第三次迭代： （1）当前的可行基为）当前的可行基为B2 = (p1 , p2 , p4 )，那么，那么x1 ，x2 ，x4为基变量，为基变量，x3 ，x5为非基变量。将基变量和目标函为非基变量。将基变量和目标函数用非基变量表示：数用非基变量表示： z = 70000 500 x3 500 x5 x1 = 5 (1/3) x3 + (2/9) x5 x2 = 25 (1/3) x5 x4 = 5 + (2/3) x3 (1/9) x5 68 （2）选择进基变量。在目标函数）选择进基变量。在目标函数 z = 70000 500 x3 500 x5 中，非基变量中，非基变量x3 、x5的系数均

46、不是正数，因的系数均不是正数，因此进基都不可能使目标函数此进基都不可能使目标函数z增大，于是得增大，于是得到最优解，到最优解， x* = (5，25，0，5，0)T，最优目标值为最优目标值为 z* = 70000。 这个解对应于图这个解对应于图2-7的的A、C交点。我们也交点。我们也称相应的基称相应的基B2 = (p1 , p2 , p4)为最优基。计算结束。为最优基。计算结束。 692.4.2 单纯形法的表格计算单纯形法的表格计算 考虑规范形式的线性规划问题考虑规范形式的线性规划问题, ,为了避为了避免退化情况，设免退化情况，设 bi 0 i = 1 , , m Max z = c1 x1

47、+ c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn b2 . . am1 x1 + am2 x2 + + amn xn bm x1 ，x2 ， ，xn 070加入松弛变量化为标准形式加入松弛变量化为标准形式 Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 . . am1 x1 + am2 x2 + + amn

48、 xn+ xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0显然，显然，xj = 0 j = 1, , n ; xn+i = bi i = 1 , , m 是基本可行解是基本可行解, , 对对应的基是单位矩阵。应的基是单位矩阵。71初始单纯形表：初始单纯形表：mm m m其中其中 f = - cn+i bi j = cj - cn+i aij 为检验数为检验数 i = i =1 cn+i = 0 i= 1,m an+i,i = 1 , an+i,j = 0 ( ji ) i , j = 1, , m722.4.3 单纯形法计算实例单纯形法计算实例 例例 Max z =

49、1500 x1+2500 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0 化标准形式：化标准形式： Max z =1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 073求解求解单纯形表单纯形表74 在单纯形法计算过程中在单纯形法计算过程中1、运算中使用矩阵初等行变换；、运算中使用矩阵初等行变换；2、表中矩阵总含各单位向量（表明当前、表中矩阵总含各单位向量（表明当前为基本解）；为基本解）；3

50、、表中第、表中第3列的数总应保持非负（表明列的数总应保持非负（表明当前基本解可行）；当前基本解可行）；4、当所有检验数均非正（、当所有检验数均非正（ 0）时，得）时，得到最优单纯形表。到最优单纯形表。注意：注意：75多解情况多解情况 线性规划问题可能存在无穷多解的情线性规划问题可能存在无穷多解的情况，利用单纯形表亦可求出。况，利用单纯形表亦可求出。例例 Max z = x1 + 5x2 + 4x3 - x5 - 2x6 s.t. x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2

51、, x3 , x4 , x5 , x6 076用单纯形法求解用单纯形法求解得到解为得到解为 x ( 0, 15/7, 25/7, 52/7, 0 , 0 )T由于由于 x1 的检验数为零，可继续迭代，的检验数为零，可继续迭代，77继续求解继续求解另一解为另一解为 x” ( 25/3, 10/3, 0, 11, 0 , 0 )T于是于是 x，x” 线段上的任一点均为最优解。线段上的任一点均为最优解。 此线性规划的最优解可表示为：此线性规划的最优解可表示为： x = x + (1- ) x” ，其中其中 0 178练习：练习：2.18 单纯形法计算实例单纯形法计算实例 例例 Max z =1500

52、 x1+1000 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0 化标准形式：化标准形式： Max z =1500 x1 + 1000 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 079求解求解单纯形表单纯形表80无有限最优解的情况无有限最优解的情况 线性规划问题可能存在无有限最优线性规划问题可能存在无有限最优解解(目标函数取向目标函数取向 + )的情况，利用单的情况，利用单纯形表亦可得出此结论。纯形表亦可得出此结

53、论。 例例 Max z = 15x1 + 18x2 2x3 +5x5 s.t. x1 - 1/3x3 + 2/3x5 = 7 -2/3x3 + x4 + 1/9x5 = 5 x2 - 1/6x5 = 5 x1 , x2 , x3 , x4 , x5 081用单纯形法求解得到用单纯形法求解得到表中表中 x3 的检验数大于零，而其的检验数大于零，而其对应的约束矩阵元素均非正，说明对应的约束矩阵元素均非正，说明此线性规划无有限最优解。此线性规划无有限最优解。拿到题目后先化为标准形式用表格法计算（迭代方法太复杂）表格法计算停止后，写出如下结论：最优解&最优值，并注明是唯一最优解还是有无穷多最优

54、解还是无有限最优解。作业作业P51-52 1-(3)， 3-(3)83842.4.4 2.4.4 一般线性规划问题的处理一般线性规划问题的处理 一般情况下，初始基本可行解不一般情况下，初始基本可行解不明显。常用的方法是通过引入人工明显。常用的方法是通过引入人工变量，得到初始约束矩阵中含有各变量，得到初始约束矩阵中含有各单位向量，然后考虑如何使引入的单位向量，然后考虑如何使引入的人工变量取值为人工变量取值为0。 考虑一般问题：考虑一般问题： bi 0 i = 1 , , m85Max z = c1x1 + c2x2 + + cnxn s.t. a11x1+a12x2 +a1nxn = b1 a2

55、1x1+a22x2 +a2nxn = b2 . . . am1x1+am2x2+amnxn = bm x1 ，x2 ， ，xn 0大大M法：法：引入引入人工变量人工变量 xn+i 0 （i = 1 , , m）及）及充分大正数充分大正数 M 。得到：。得到：Max z = c1x1 +c2x2 +cnxn -Mxn+1 -Mxn+m s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 . . . am1 x1 + am2 x2 + + amn xn + xn+m = bm x1，x

56、2，xn，xn+1，xn+m 086注意区分： 人工变量 松弛变量88显然，显然，xj = 0 j =1 , , n ; xn+i = bi i =1 , , m 是基本可行解。是基本可行解。对应的基是单位矩阵。对应的基是单位矩阵。 结论：若得到的最优解满足结论：若得到的最优解满足 xn+i = 0, i = 1 , , m 则是原问题的最优解；否则，原问则是原问题的最优解；否则，原问题无可行解。题无可行解。两阶段法：两阶段法：引入人工变量引入人工变量 xn+i 0，i = 1 , m；构造构造: Max z = - xn+1 - xn+2 - - xn+m s.t. a11x1+ a12x2+ + a1nxn+xn+1 = b1 a21x1+ a22x2+ + a2nxn+xn+2 = b2 . . . am1x1+am2x2+ +amnxn+xn+m = bm x1,x2 . xn ,xn+1,xn+m 08990第一阶段：求解上述问题：第一阶段：求解上述问题： 显然显然 xj = 0 j =1,n ; xn+i = bi i =1,m 是基本可行解是基本可行解, 对应的基是由单位向量对应的基是由单位向量构成的矩阵。构成的矩阵。结论：若得到的最优解满足结论：若得到的最优解满足 xn+i = 0 , i =1 , , m 则是原问题的基本可行解则是原问题的基本可行解;否则，原问