第2章线性规划

1、第二章第二章 线性规划线性规划Linear Programming线性规划线性规划线性规划是运筹学中研究较早、应用较广泛、发展较成线性规划是运筹学中研究较早、应用较广泛、发展较成熟的一个分支。它有效地解决了生产规划、任务分配以熟的一个分支。它有效地解决了生产规划、任务分配以及配料等的最优化问题。这种最优化方法在油气储运系及配料等的最优化问题。这种最优化方法在油气储运系统中的应用也较为广泛，如炼厂或商品油库油品调和的统中的应用也较为广泛，如炼厂或商品油库油品调和的最优化问题，最优月输油计划、商品油库的最优进货计最优化问题，最优月输油计划、商品油库的最优进货计划问题等，都可以用线性规划方法解决。单

2、纯形法是线划问题等，都可以用线性规划方法解决。单纯形法是线性规划的主要算法，虽然有人还提出过其他一些算法，性规划的主要算法，虽然有人还提出过其他一些算法，但到目前为止，单纯形法仍然是最有效的算法。本章重但到目前为止，单纯形法仍然是最有效的算法。本章重点介绍单纯形法的原理和算法。点介绍单纯形法的原理和算法。2.1 线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型线性规划问题是一类特殊的最优化问题，其目标函数是决线性规划问题是一类特殊的最优化问题，其目标函数是决策变量的线性函数，约束条件是关于决策变量的线性等式策变量的线性函数，约束条件是关于决策变量的线性等式或不等式。线性规划问题

3、的一般形式为：或不等式。线性规划问题的一般形式为：nnxcxcxcS 2211 max(min) 0,.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型 njjjxcSmax(min)1 简写为：简写为： njxmibxatsjijij1 01 .n1j在上述数学模型中，在上述数学模型中，的含义包括的含义包括、=、 。 为了便为了便于讨论和求解，通常把给定的线性规划问题都划成如于讨论和求解，通常把给定的线性规划问题都划成如下的标准形式：下的标准形式：线性规划问题

4、的一般形式及其标准型线性规划问题的一般形式及其标准型 njjjxcS1 max njxmibxatsjijij1 01 .n1j这种形式称为线性规划问题的标准型，其中这种形式称为线性规划问题的标准型，其中bi0(i=1m)。有些书上规定标准型的目标函数是求有些书上规定标准型的目标函数是求min ,但这对问题的但这对问题的求解没有本质的影响，因为求求解没有本质的影响，因为求min 也可以转化为求也可以转化为求max。线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型 标准型的向量形式：标准型的向量形式：CXS max 0 .1XbxPtsnjjj其中其中 ：C=(c1,c2, ,

5、cn) 称为目标系数行向量。称为目标系数行向量。线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型 mmjjjjnbbbbaaaPxxxX212121 (决策变量列向量决策变量列向量) (xj的系数列向量的系数列向量) (右端系数列向量右端系数列向量) 标准型的矩阵形式：标准型的矩阵形式：CXS max 0.XbAXts nmijmnmmnnaaaaaaaaaaA 212222111211 其其中中A称为约束系数矩阵。称为约束系数矩阵。线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型对于给定的线性规划问题，如果它不符合标准型的要求，对于给定的线性规划问题，如果它不

6、符合标准型的要求，则可通过下述途径将其化为标准型：则可通过下述途径将其化为标准型： SmaxSmaxSminSS ，则则令令 njijijbxa1 2、约约束束条条件件为为，使得，使得非负变量非负变量在不等式左边加上一个在不等式左边加上一个0 inx njiinjijbxxa1xn+i称为松弛变量称为松弛变量(slack variable)。1、目标函数为、目标函数为min S线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型 njijijbxa1 3、约约束束条条件件为为，使使得得非非负负变变量量在在不不等等式式左左边边减减去去一一个个0 inx njiinjijbxxa1xn

7、+i称为剩余变量称为剩余变量(surplus variable)。）（、约约束束条条件件为为0 41 injijijbbxa在等式两端同乘以在等式两端同乘以-1，则，则)0( )(1 iinjijijbbbxa线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型可可正正可可负负。的的数数值值无无正正负负要要求求，为为自自由由变变量量，即即对对、 5jjjxxx关于松弛变量和剩余变量，有以下几点需要说明：关于松弛变量和剩余变量，有以下几点需要说明： 在标准型中，松弛（剩余）变量与原问题中的决策变量在标准型中，松弛（剩余）变量与原问题中的决策变量具有同等地位。具有同等地位。 对实际问题

8、而言，松弛（剩余）变量与原问题中的决策对实际问题而言，松弛（剩余）变量与原问题中的决策变量一样具有明确的物理和经济意义。变量一样具有明确的物理和经济意义。、，令，令为了满足标准型的要求为了满足标准型的要求0 jjjjjxxxxx线性规划问题的一般形式及其标准型线性规划问题的一般形式及其标准型 松弛（剩余）变量对目标函数无影响，因为它们在目松弛（剩余）变量对目标函数无影响，因为它们在目标函数中的系数均为标函数中的系数均为0。 从数学上讲，松弛变量与剩余变量无本质区别，故也从数学上讲，松弛变量与剩余变量无本质区别，故也可将两者统称为松弛变量。可将两者统称为松弛变量。2.2 线性规划的图解法线性规划

9、的图解法图解法是求解线性规划问题最简单、直观的方法，它的图解法是求解线性规划问题最简单、直观的方法，它的基本思想是将一个代数问题转化为一个几何问题求解。基本思想是将一个代数问题转化为一个几何问题求解。但这种方法只适用于有两个决策变量的情况，对于有三但这种方法只适用于有两个决策变量的情况，对于有三决策变量的情况，图解法原则上也是适用的，但由于作决策变量的情况，图解法原则上也是适用的，但由于作图复杂，一般不予采用。对于三维以上的情况，图解法图复杂，一般不予采用。对于三维以上的情况，图解法更是无能为力。尽管如此，图解法对我们从直观上了解更是无能为力。尽管如此，图解法对我们从直观上了解线性规划问题解的

10、性质还是很有启发的。下面通过一个线性规划问题解的性质还是很有启发的。下面通过一个例子说明图解法的解题步骤。例子说明图解法的解题步骤。线性规划的图解法线性规划的图解法例：例：某企业计划生产某企业计划生产I 、II两种产品，需要两种产品，需要A、B、C、D四四种不同的原料。已知生产每种产品需要各种原料的比种不同的原料。已知生产每种产品需要各种原料的比例、产品的单位利润和原料总量见下表。问该企业应例、产品的单位利润和原料总量见下表。问该企业应如何安排生产才能获得最大利润？如何安排生产才能获得最大利润？ABCD利润利润(千元千元/吨吨)III2212400423原料总量原料总量(吨吨)1281612线

11、性规划的图解法线性规划的图解法解：设解：设I、II两种产品的产量分别为两种产品的产量分别为x1、x2，总利润，总利润为为S，则可以列出以下数学模型：，则可以列出以下数学模型： 0124164821222.32 max2121212121xxxxxxxxtsxxS，显然这是一个线性规划问题。因为它只有两个决策变量，显然这是一个线性规划问题。因为它只有两个决策变量，故可以用图解法求解。图解法的具体步骤如下：故可以用图解法求解。图解法的具体步骤如下：线性规划的图解法线性规划的图解法1、在平面直角坐标系中作出问题的可行域、在平面直角坐标系中作出问题的可行域 可行域：可行域：对于一个数学规划来说，其可行

12、点的集合称为对于一个数学规划来说，其可行点的集合称为它的可行域。它的可行域。 可行解可行解(点点)：满足全部约束条件的一组决策变量值称为满足全部约束条件的一组决策变量值称为它的可行解它的可行解(点点)。 可行域与可行点的关系：可行域与可行点的关系： 可行域内的每个点都是可行点；可行域内的每个点都是可行点； 问题的任何一个可行点均在可行域内。问题的任何一个可行点均在可行域内。 显然问题的可行域是由它的约束条件确定的。下面介绍显然问题的可行域是由它的约束条件确定的。下面介绍一下如何作问题的可行域一下如何作问题的可行域(见下图见下图)。线性规划的图解法线性规划的图解法以以x1、x2为坐标轴作直角为坐

13、标轴作直角坐标系，因为问题中要坐标系，因为问题中要求求x1 、x20，故只需作，故只需作出第一象限。出第一象限。2468x1O2468x2约束条件约束条件2x1+2x212：作：作直线直线2x1+2x2=12，则满足，则满足约束条件的点在该直线的约束条件的点在该直线的左下方左下方(包括直线包括直线)。 约束条件约束条件x1+2x28：作直：作直线线x1+2x2=8，则满足约束条，则满足约束条件的点在该直线的左下方件的点在该直线的左下方(包括直线包括直线)。2x1+2x2=12x1+2x2=8线性规划的图解法线性规划的图解法约束条件约束条件4x116：作：作直线直线x1=4，则满足约，则满足约束

14、条件的点在该直线束条件的点在该直线的左方的左方(包括直线包括直线)。O2468x12468x22x1+2x2=12x1+2x2=8约束条件约束条件4x212：作直：作直线线x2=3，则满足约束，则满足约束条件的点在该直线的条件的点在该直线的下方下方(包括直线包括直线)。x1=4x2=3Q3Q4Q1Q2由此可见，该问题的可行域是由由此可见，该问题的可行域是由五个约束条件对应的直线围成的五个约束条件对应的直线围成的一个多边形区域一个多边形区域OQ1Q2Q3Q4。注。注意该多边形的每个顶点都是向外意该多边形的每个顶点都是向外凸出的，我们把这种多边形称为凸出的，我们把这种多边形称为凸多边形。凸多边形。

15、线性规划的图解法线性规划的图解法2、作一条目标函数等值线，使之、作一条目标函数等值线，使之与可行域相交。与可行域相交。 目标函数目标函数S=2x1+3x2，令，令S=k, 得等值线方程得等值线方程2x1+3x2=k。为使为使目标函数等值线与可行域相交，目标函数等值线与可行域相交，在可行域内取一点在可行域内取一点(0,2)，将其，将其代入目标函数等值线方程，得代入目标函数等值线方程，得k=6。于是可得一条过。于是可得一条过(0,2)点点的等值线方程的等值线方程2x1+3x2=6，它过，它过x1轴上的轴上的(3,0)点和点和x2轴上的轴上的(0,2)点。点。O2468x12468x22x1+2x2

16、=12x1+2x2=8x1=4x2=3Q3Q4Q1Q2线性规划的图解法线性规划的图解法3、平移目标函数等值线确定最优、平移目标函数等值线确定最优点点(解解) 将等值线将等值线2x1+3x2=6在坐标平面内作平在坐标平面内作平行移动，可得目标函数的最大值，其行移动，可得目标函数的最大值，其中每条等值线对应一个目标函数值。中每条等值线对应一个目标函数值。因为本例的目的是求目标函数的最大因为本例的目的是求目标函数的最大值，故应将等值线向目标函数增大的值，故应将等值线向目标函数增大的方向移动。将等值线方向移动。将等值线2x1+3x2=6向右上向右上方平行移动，可使目标函数值逐渐增方平行移动，可使目标函

17、数值逐渐增加，最后等值线与可行域相切于加，最后等值线与可行域相切于Q2点，点，在这一点处，将等值线继续向右上方在这一点处，将等值线继续向右上方平行移动，虽然目标函数值还可继续平行移动，虽然目标函数值还可继续增加，但直线上的点已不在可行域内，增加，但直线上的点已不在可行域内，这说明在可行域这说明在可行域OQ1Q2Q3Q4内，内，Q2点点对应的目标函数值最大，也就是说对应的目标函数值最大，也就是说Q2点是问题的最优点。点是问题的最优点。O2468x12468x22x1+2x2=12x1+2x2=8x1=4x2=3Q3Q4Q1Q2线性规划的图解法线性规划的图解法从图上可以看出：从图上可以看出：Q2点

18、点是可行域是可行域(凸多边形凸多边形) OQ1Q2Q3Q4的一个顶点的一个顶点, 其坐标为其坐标为(4,2)，于是该，于是该问题的最优解为：问题的最优解为：O2468x12468x22x1+2x2=12x1+2x2=8x1=4x2=3Q3Q4Q1Q2 142 , 4,*2*1* SxxXTT即生产第即生产第I种产品种产品4吨，第吨，第II种产品种产品2吨，可获最大利吨，可获最大利润润14000元。元。线性规划的图解法线性规划的图解法几种特殊情况的讨论：几种特殊情况的讨论：1、无穷多个最优解。、无穷多个最优解。若将目若将目标函数改为标函数改为S=2x1+4x2，则，则目标函数等值线刚好与约目标函

19、数等值线刚好与约束条件束条件x1+2x28对应的直线对应的直线x1+2x2=8平行。在这种情况平行。在这种情况下，当目标函数等值线从下，当目标函数等值线从可行域内部沿正法线方向可行域内部沿正法线方向平行移动时，最终与可行平行移动时，最终与可行域边界域边界x1+2x2=8重合，或者重合，或者说目标函数等值线与可行说目标函数等值线与可行域相切于直线段域相切于直线段Q2Q3。O2468x12468x22x1+2x2=12x1+2x2=8x1=4x2=3Q3Q4Q1Q2因为直线段因为直线段Q2Q3上的所有点上的所有点都使目标函数达到最大值都使目标函数达到最大值(S=16)，故称此问题有无穷，故称此问题

20、有无穷多个最优解。多个最优解。线性规划的图解法线性规划的图解法2、无有界最优解无有界最优解(无最优解无最优解)。如果只保留上述例题中的如果只保留上述例题中的一个约束条件一个约束条件4x116，则，则问题的可行域为一长条形问题的可行域为一长条形的无界区域。因为的无界区域。因为x2无上无上界约束，故目标函数等值界约束，故目标函数等值线可以无限向右上方平移，线可以无限向右上方平移，即即x2+，S+ 。这种。这种情况称为无有界最优解，情况称为无有界最优解，或无最优解。或无最优解。O2468x12468x2x1=4线性规划的图解法线性规划的图解法3、无可行解、无可行解(无解无解)。如果将上如果将上例改为

21、例改为 01421222.32 max21212121xxxxxxtsxxS，2468x1O2468x2x1+2x2=142x1+2x2=12则由于两个约束条件分别确则由于两个约束条件分别确定的闭半平面无公共部分，定的闭半平面无公共部分，即可行域不存在，这时问题即可行域不存在，这时问题无可行解。无可行解。线性规划的图解法线性规划的图解法一般来说，实际问题的数学模型很少出现无最优解或一般来说，实际问题的数学模型很少出现无最优解或无可行解的情况，当出现这两种情况时，应仔细检查无可行解的情况，当出现这两种情况时，应仔细检查所建立的数学模型是否正确。所建立的数学模型是否正确。无最优解与无解是两个完全不

22、同的概念。无最优解有无最优解与无解是两个完全不同的概念。无最优解有可行解，而无解是无可行解。可行解，而无解是无可行解。2.3 线性规划解的概念和基本定理线性规划解的概念和基本定理为了便于理解和掌握线性规划单纯形法的原理和算法，为了便于理解和掌握线性规划单纯形法的原理和算法，有必要先介绍一下线性规划问题的几个基本概念，这些有必要先介绍一下线性规划问题的几个基本概念，这些概念都是针对线性规划问题的标准型而言的。概念都是针对线性规划问题的标准型而言的。线性规划问题的标准型为：线性规划问题的标准型为：CXS max 0.XbAXts0 bnmA矩阵，矩阵，为为线性规划解的概念和基本定理线性规划解的概念

23、和基本定理 我们总是认为我们总是认为A是是非奇异矩阵非奇异矩阵，即，即A的秩等于的秩等于m。根据。根据该标准型，我们引入以下几个解的概念：该标准型，我们引入以下几个解的概念：1、基基(基矩阵基矩阵)：从约束系数矩阵：从约束系数矩阵A中选出的中选出的m个线性无关个线性无关的列向量构成的的列向量构成的mm阶矩阵称为线性规划问题的一个阶矩阵称为线性规划问题的一个基（或基矩阵），通常用基（或基矩阵），通常用B表示。表示。2、基向量基向量：构成基的每一个列向量称为基向量。设基矩：构成基的每一个列向量称为基向量。设基矩阵为阵为B=(P1,P2,.,Pm)，则，则P1,P2,.,Pm 都是基向量。都是基向量

24、。线性规划解的概念和基本定理线性规划解的概念和基本定理3、基变量与非基变量基变量与非基变量：与基向量：与基向量Pj对应的变量对应的变量xj称为基称为基变量，除基变量以外的其他变量称为非基变量。变量，除基变量以外的其他变量称为非基变量。 线性规划问题中有线性规划问题中有n个决策变量，个决策变量，m个约束等式，则有个约束等式，则有m个基变量，个基变量，n-m个非基变量。个非基变量。 注意：基向量与基变量都是相对于某个基而言的，不注意：基向量与基变量都是相对于某个基而言的，不是一成不变的。对于同一个线性规划问题，一般有许是一成不变的。对于同一个线性规划问题，一般有许多个基，随着基的变化，基变量也有所

25、不同。多个基，随着基的变化，基变量也有所不同。线性规划解的概念和基本定理线性规划解的概念和基本定理4、基本解基本解：对应于某一个给定的基，在约束方程组中令：对应于某一个给定的基，在约束方程组中令所有所有n-m个非基变量的值等于个非基变量的值等于0，则由此方程组可唯一，则由此方程组可唯一地解得地解得m个基变量的值，把这个基变量的值，把这m个基变量的值与个基变量的值与n-m个个非基变量的值非基变量的值(等于等于0)合在一起就得到约束方程组的一合在一起就得到约束方程组的一个完整解，称这个解为对应于给定基的基本解。个完整解，称这个解为对应于给定基的基本解。 基本解最多不超过基本解最多不超过Cnm 个个

26、(为什么？为什么？)。5、基本可行解基本可行解：满足变量非负条件的基本解称为基本可：满足变量非负条件的基本解称为基本可行解。基本可行解显然是可行解，若最优解存在，则行解。基本可行解显然是可行解，若最优解存在，则一定有一个基本可行解是最优解。一定有一个基本可行解是最优解。6、可行基可行基：对应于基本可行解的基称为可行基。：对应于基本可行解的基称为可行基。7、最优基最优基：对应于最优基本可行解的基称为最优基。：对应于最优基本可行解的基称为最优基。线性规划解的概念和基本定理线性规划解的概念和基本定理例：例：以下面的问题为例说明各种解的概念：以下面的问题为例说明各种解的概念： 012416482122

27、2.32 max61625142132121xxxxxxxxxxxxtsxxS线性规划解的概念和基本定理线性规划解的概念和基本定理约束系数矩阵为：约束系数矩阵为： 100040010004001021000122654321PPPPPPA显然显然P3、P4、P5、P6是线性无关的向量，故它们构成是线性无关的向量，故它们构成一个基，相应的基矩阵为：一个基，相应的基矩阵为：线性规划解的概念和基本定理线性规划解的概念和基本定理 10000100001000016543PPPPB相对应于相对应于B的基变量为的基变量为x3、x4、x5、x6，非基变量为，非基变量为x1、x2。在约束方程组中令非基变量在约

28、束方程组中令非基变量x1=x2=0，解得，解得x3=12、x4=8、x5=16、x6=12，则，则X=(0,0,12,8,16,12)T 是相应于基是相应于基B的基本解。的基本解。因为该基本解中的变量都满足非负条件，故它也是基本可因为该基本解中的变量都满足非负条件，故它也是基本可行解，行解，B是可行基。是可行基。线性规划解的概念和基本定理线性规划解的概念和基本定理从从A中我们还可以取另一个基：中我们还可以取另一个基： 100401000012000265421PPPPB相对应于相对应于B1的基变量为的基变量为x2、x4、x5、x6，非基变量为，非基变量为x1、x3。在约束方程组中令非基变量在约

29、束方程组中令非基变量x1=x3=0，解得，解得x2=6、x4=-4、x5=16、x6=-12，则相应于基则相应于基B1的基本解为的基本解为X1=(0,6,0,-4,16,-12)T。因为。因为x4、x6为负值，故为负值，故X1不是基本可行解，不是基本可行解，B1不是可行基。不是可行基。线性规划解的概念和基本定理线性规划解的概念和基本定理线性规划的基本定理：线性规划的基本定理： 在讨论单纯形法之前，还要介绍几个线性规划的基本在讨论单纯形法之前，还要介绍几个线性规划的基本定理，他们是构成线性规划单纯形法的理论基础。定理，他们是构成线性规划单纯形法的理论基础。定理定理1：LP问题的可行域一定是一个凸

30、集。问题的可行域一定是一个凸集。 凸集：凸集：如果一个集合内部任意两点之间的连线仍在这如果一个集合内部任意两点之间的连线仍在这个集合内部，则该集合为凸集。个集合内部，则该集合为凸集。 从几何直观上理解，凸集没有凹入部分，其内部没有从几何直观上理解，凸集没有凹入部分，其内部没有孔洞，任意两点之间的连线仍然在凸集内部。一个孤孔洞，任意两点之间的连线仍然在凸集内部。一个孤立的点、一段直线、凸多边形、凸多面体都是凸集。立的点、一段直线、凸多边形、凸多面体都是凸集。线性规划解的概念和基本定理线性规划解的概念和基本定理定理定理2：LP问题的基本可行解与可行域的顶点一一对应。问题的基本可行解与可行域的顶点一

31、一对应。定理定理3：LP问题如果有最优解，则最优解一定在可行域的问题如果有最优解，则最优解一定在可行域的一个顶点上达到。如前面图解法例题的最优解即为可行一个顶点上达到。如前面图解法例题的最优解即为可行域的顶点域的顶点Q2。判断下列几何图形是否凸集：判断下列几何图形是否凸集：2.4 线性规划的单纯形法线性规划的单纯形法一、单纯形法的基本思想一、单纯形法的基本思想 单纯形法的基本思想是：从一个基本可行解单纯形法的基本思想是：从一个基本可行解(初始基本初始基本可行解可行解)出发，检查其是否最优解，如果不是，则按一定出发，检查其是否最优解，如果不是，则按一定规则转换到另一个基本可行解，并使目标函数值有

32、所增规则转换到另一个基本可行解，并使目标函数值有所增加，如此继续，直到找到最优解为止。这是一个序列化加，如此继续，直到找到最优解为止。这是一个序列化(迭代迭代)的过程。的过程。*)()2()1()0(XXXXXk*)()2()1()0(SSSSSk 线性规划的单纯形法线性规划的单纯形法 在该过程中，有在该过程中，有3个问题需要解决：个问题需要解决： 如何确定如何确定X(0)? 如何检查所得的基本可行解是否为最优解如何检查所得的基本可行解是否为最优解? 转换规则，即如何实现转换规则，即如何实现X(k)到到 X(k+1) 的转换？的转换？二、单纯形法求解过程举例二、单纯形法求解过程举例 下面通过一

33、个例子说明单纯形法的解题过程。下面通过一个例子说明单纯形法的解题过程。 例：仍以前面的图解法的例题为例，数学模型为例：仍以前面的图解法的例题为例，数学模型为:线性规划的单纯形法线性规划的单纯形法 0124164821222.32 max2121212121xxxxxxxxtsxxS，解：化标准型解：化标准型 0124164821222.32 max61625142132121xxxxxxxxxxxxtsxxS其中其中x3x6为松驰变量。为松驰变量。线性规划的单纯形法线性规划的单纯形法约束系数矩阵为：约束系数矩阵为： 100040010004001021000122654321PPPPPPA 确

34、定确定X(0) 从约束系数矩阵从约束系数矩阵A中找出中找出m(m=4)个不同的单位列向量，个不同的单位列向量，以此构成初始基以此构成初始基B0 ，相应的基本解就是，相应的基本解就是X(0)。线性规划的单纯形法线性规划的单纯形法 显然可取显然可取P3、P4、P5、P6构成构成B0，基变量为，基变量为x3、x4、x5、x6，非基变量为，非基变量为x1 、x2 。 令令x1=x2=0, 由约束方程解得由约束方程解得x3=12，x4=8，x5=16，x6=12 ，则则X(0)=(0,0,12,8,16,12)T，S(0) =0 。 判断判断X(0)是否为最优解是否为最优解 将基变量用非基变量表示：将基

35、变量用非基变量表示：2615214213412416282212xxxxxxxxxx 线性规划的单纯形法线性规划的单纯形法 代入目标函数表达式得，代入目标函数表达式得，S=2x1+3x2 。 由于上式中由于上式中x1、x2 的系数均为正值的系数均为正值(2,3)，若，若x1、x2增大，增大，则则S也增大，说明也增大，说明X(0)不是最优解。不是最优解。检验数：检验数：把目标函数表达式中非基变量的系数称为检把目标函数表达式中非基变量的系数称为检验数。如本例中的检验数为验数。如本例中的检验数为2、3。如果检验数中有一。如果检验数中有一个大于个大于0，则该基本可行解不是最优解。，则该基本可行解不是最

36、优解。最优性检验准则：最优性检验准则：设设X(k)是基本可行解，如果其相应的是基本可行解，如果其相应的非基变量的检验数都不大于非基变量的检验数都不大于0，则，则X(k)就是最优解就是最优解(max问题问题)。思考题：思考题：min问题的最优性检验准则如何表达？问题的最优性检验准则如何表达？线性规划的单纯形法线性规划的单纯形法 从初始基本可行解从初始基本可行解X(0)转换到另一个基本可行解转换到另一个基本可行解X(1)，并使并使S(0) S(1)。 将原来的一个基向量与另一个非基向量对换，构将原来的一个基向量与另一个非基向量对换，构成一个新的基。成一个新的基。换换入入变变量量换换出出变变量量换换

37、入入向向量量换换出出向向量量一一个个非非基基向向量量一一个个基基向向量量对对换换 换入向量：进入新基的非基向量叫换入向量，对应的变量叫换入变量。换入向量：进入新基的非基向量叫换入向量，对应的变量叫换入变量。换出向量：从旧基中退出的向量叫换出向量，对应的变量叫换出变量。换出向量：从旧基中退出的向量叫换出向量，对应的变量叫换出变量。线性规划的单纯形法线性规划的单纯形法 问题的关键在于确定哪一个为换出向量，哪一个为问题的关键在于确定哪一个为换出向量，哪一个为换入向量，基本要求是：换入向量，基本要求是：得到一个新的基；得到一个新的基；对应新基的基本解是可行解；对应新基的基本解是可行解；S(1)S(0)

38、(S(k+1)S(k)1) 确定换入变量确定换入变量 在目标函数表达式在目标函数表达式S=2x1+3x2中，因为中，因为x1、x2的系数的系数均为正，且均为正，且x2的系数最大，故选的系数最大，故选x2(因其对目标函数因其对目标函数值的影响最大值的影响最大)为换入变量。为换入变量。 最大正检验数规则：最大正检验数规则：选择具有最大正检验数的非基选择具有最大正检验数的非基变量作为换入变量。变量作为换入变量。线性规划的单纯形法线性规划的单纯形法2) 确定换出变量确定换出变量 在用非基变量表示的基变量的表达式中，令非基变在用非基变量表示的基变量的表达式中，令非基变量量x1=0，得到下列不等式组：，得

39、到下列不等式组：3 0412- 0164 0286 02122265224223 xxxxxxxxxx不等式组的解为不等式组的解为x2min6,4,3=3，即当，即当x1=0时，只要时，只要0 x23，就可以得到一个可行解，就可以得到一个可行解:X=(0, x2, 12-2x2, 8-2x2, 16, 12-4x2)线性规划的单纯形法线性规划的单纯形法我们的目的是得到一个新的基本可行解我们的目的是得到一个新的基本可行解X(1)，这就要求从旧，这就要求从旧的基变量的基变量x3、x4、x5、x6中选出一个换出变量作为新的非基中选出一个换出变量作为新的非基变量，其在变量，其在X(1)中的值应等于中的

40、值应等于0。从以上可行解从以上可行解X的表达式及的表达式及0 x23这一条件可知，为了使这一条件可知，为了使X成为基本可行解，必须取成为基本可行解，必须取x2=3，此时旧基变量的值分别为，此时旧基变量的值分别为x36、x42、x516、x60。因为。因为x60 ，故在新的基本可，故在新的基本可行解行解X(1)中，中，x6成为非基变量，即选成为非基变量，即选x6为换出变量。为换出变量。规则：规则：设设xk是换入变量，令是换入变量，令 ，则与，则与相应的基相应的基变量为换出变量。变量为换出变量。 0minikaikiab 线性规划的单纯形法线性规划的单纯形法bi为第为第i个基变量表达式中的常数项，

41、个基变量表达式中的常数项，aik为第为第i个基变量表个基变量表达式中换入变量达式中换入变量xk的系数。根据的系数。根据规则，上述不等式组中规则，上述不等式组中各个旧基变量对应的各个旧基变量对应的值如下：值如下： 3min312/4 3 0412- - 01648/2 4 028612/2 6 021266226542243223 ixxxxxxxxxx对应的变量为对应的变量为x6。线性规划的单纯形法线性规划的单纯形法将换入变量将换入变量x2与换出变量与换出变量x6对换，得到一组新的基变量对换，得到一组新的基变量x3、x4、x5、x2，相应的基矩阵为：，相应的基矩阵为： 400001002010

42、2001,2543PPPPB从约束方程组中解出新的基变量（用新的非基变量表示从约束方程组中解出新的基变量（用新的非基变量表示新的基变量）：新的基变量）：线性规划的单纯形法线性规划的单纯形法64121562114621133416226xxxxxxxxxx 将上式代入目标函数表达式，得：将上式代入目标函数表达式，得：643129xxS 令非基变量令非基变量x1=x6=0, 则则x3=6，x4=2，x5=16，x2=3，X(1)=(0,3,6,2,16,0)T，S(1) =9S(0)=0 。线性规划的单纯形法线性规划的单纯形法 检查检查X(1)是否最优解是否最优解 从目标函数表达式从目标函数表达式

43、 可知，可知，x1的系数仍的系数仍为正，所以为正，所以X(1)不是最优解。不是最优解。643129xxS 2min- 03 4/461 041622/1 0236/2 02642515414313 ixxxxxxx X(1) X(2) 显然应取显然应取x1为换入变量；为换入变量； 确定换出变量：令非基变量确定换出变量：令非基变量x6=0，则，则 线性规划的单纯形法线性规划的单纯形法故应选故应选x4为换出变量。将为换出变量。将x1与与x4对换，得到新的基变量为对换，得到新的基变量为x3、x1、x5、x2，非基变量为，非基变量为x4、x6。从约束方程组中解出基变量：从约束方程组中解出基变量：641

44、264562141621433248222xxxxxxxxxxx 将上式代入目标函数表达式，得：将上式代入目标函数表达式，得：6414213xxS 线性规划的单纯形法线性规划的单纯形法 令非基变量令非基变量x4=x6=0, 则则x3=2，x1=2，x5=8，x2=3， X(2)=(2,3,2,0,8,0)T，S(2) =13S(1)=9 。 检查检查X(2)是否最优解是否最优解 目标函数表达式中，目标函数表达式中，x6的系数仍为正，所以的系数仍为正，所以X(2)不是不是最优解。最优解。 X(2) X(3) 显然应取显然应取x6为换入变量；为换入变量； 根据同样的方法可确定换出变量为根据同样的方

45、法可确定换出变量为x3。 线性规划的单纯形法线性规划的单纯形法从约束方程组中解出基变量：从约束方程组中解出基变量：432124354314362444424xxxxxxxxxxxx 将上式代入目标函数表达式，得：将上式代入目标函数表达式，得：432114xxS 令非基变量令非基变量x3=x4=0, 则可得到新的基本可行解为，则可得到新的基本可行解为， X(3)=(4,2,0,0,0,4)T，S(3) =14S(2)=13 。线性规划的单纯形法线性规划的单纯形法 检查检查X(3)是否最优解是否最优解 目标函数表达式中所有目标函数表达式中所有非基变量的系数均小于非基变量的系数均小于0，故故X(3)

46、是最优解。是最优解。 上述求解过程的每一个上述求解过程的每一个基本可行解均对应可行基本可行解均对应可行域的顶点：域的顶点：234)3()2()1()0( QQQOXXXXO2468x12468x22x1+2x2=12x1+2x2=8x1=4x2=3Q3Q4Q1Q2在前面讲过，松弛变量与原问题的决策变量一样在前面讲过，松弛变量与原问题的决策变量一样具有明确的物理意义。在本例中，四个松弛变量具有明确的物理意义。在本例中，四个松弛变量的物理意义是的物理意义是4种虚拟产品的产量。在最优解中，种虚拟产品的产量。在最优解中，x6不为零，表示第不为零，表示第4种原料有剩余，即用剩余的种原料有剩余，即用剩余的

47、4吨第吨第4种原料生产种原料生产4吨第吨第6种产品。种产品。线性规划的单纯形法线性规划的单纯形法三、单纯形表三、单纯形表 由上面的求解过程可以看出，在找到一个初始基后，由上面的求解过程可以看出，在找到一个初始基后，单纯形法的主要步骤就是进行基本可行解的转换，而单纯形法的主要步骤就是进行基本可行解的转换，而实现这种转换的基础工作实际上就是对约束方程组的实现这种转换的基础工作实际上就是对约束方程组的系数增广矩阵进行行初等变换。如果对约束方程组的系数增广矩阵进行行初等变换。如果对约束方程组的系数增广矩阵作适当的补充，就可以得到一种计算表系数增广矩阵作适当的补充，就可以得到一种计算表格，整个单纯形法的

48、计算、转换和判断过程都可以在格，整个单纯形法的计算、转换和判断过程都可以在这个表格上进行，这种表格称为单纯形表。这个表格上进行，这种表格称为单纯形表。 单纯形表的优点：整齐明了，便于检查，便于实现计单纯形表的优点：整齐明了，便于检查，便于实现计算机求解。算机求解。线性规划的单纯形法线性规划的单纯形法下面仍然以上面问题为例说明利用单纯形表求解的过程。下面仍然以上面问题为例说明利用单纯形表求解的过程。 0124164821222.32 max61625142132121xxxxxxxxxxxxtsxxS例：例：线性规划的单纯形法线性规划的单纯形法1、构造初始单纯形表、构造初始单纯形表T(0) 将目

49、标函数表达式转化为线性方程：将目标函数表达式转化为线性方程：S=2x1+3x2 -S+2x1+3x2=0 将目标函数方程与约束方程组合在一起，可得到将目标函数方程与约束方程组合在一起，可得到一个有一个有7个变量、个变量、5个方程组成的线性方程组，其个方程组成的线性方程组，其中中-S也作为一个变量。也作为一个变量。 列出约束系数增广矩阵：列出约束系数增广矩阵：线性规划的单纯形法线性规划的单纯形法121000400160100040800102101200012200000032 1 bxxxxxxS654321 6543xxxx00000321j 在增广矩阵左侧增加一在增广矩阵左侧增加一列，在这

50、一列中分别标出列，在这一列中分别标出各约束方程中的基变量。各约束方程中的基变量。在增广矩阵的下边增加一在增广矩阵的下边增加一行，称为检验数行。即将行，称为检验数行。即将目标函数行中各基变量的目标函数行中各基变量的系数均化为系数均化为0(通过行初等通过行初等变换变换)，并将得到的新行，并将得到的新行写在矩阵的下面，即为检写在矩阵的下面，即为检验数行。本例中，目标函验数行。本例中，目标函数行中各基变量的系数已数行中各基变量的系数已均为均为0，不需要变换，直，不需要变换，直接将其抄写到检验数行即接将其抄写到检验数行即可。可。线性规划的单纯形法线性规划的单纯形法12100040016010004080

51、0102101200012200000032 1 bxxxxxxS654321 6543xxxx00000321j 由由T(0)可可得到基本初始得到基本初始可行解为可行解为:X(0)=(0,0,12,8,16,12)TS(0)=0因为因为1=20，2=30,故故X(0)不是最优解。不是最优解。按最大正检验数规则：按最大正检验数规则：max1 ,2= 2=3,故选故选x2为换入变量。为换入变量。线性规划的单纯形法线性规划的单纯形法121000400160100040800102101200012200000032 1 bxxxxxxS654321 341242862126543xxxx00000

52、321j 在增广矩阵的右侧增加在增广矩阵的右侧增加一列，对应每个约束方一列，对应每个约束方程，该列中的数字等于程，该列中的数字等于右端常数项与换入变量右端常数项与换入变量系数的比值。系数的比值。根据根据规则确定规则确定x6为换为换出变量。出变量。主元素：换入变量所主元素：换入变量所在列与换出变量所在在列与换出变量所在行相交处的元素称为行相交处的元素称为主元素。主元素。2、T(0) T(1) 利用行初等变换将换入利用行初等变换将换入变量所在列化为单位列变量所在列化为单位列向量，使主元素变为向量，使主元素变为1，其他元素变为其他元素变为0，从而可，从而可得到单纯形表得到单纯形表T(1)。 变换过程

53、：变换过程： 主元素行除以主元素行除以4，使主元，使主元素变为素变为1； x3行：加主元素行乘行：加主元素行乘-2； x4行：加主元素行乘行：加主元素行乘-2； 检验数行：加主元素行检验数行：加主元素行乘乘-3。 T(0)中增加第中增加第1行第行第1列的列的目的是为了计算初始检目的是为了计算初始检验数行，在以后的单纯验数行，在以后的单纯形表中即可去掉第形表中即可去掉第1行和行和第第1列。列。121000400160100040800102101200012200000032 1 bxxxxxxS654321 34/1242/ 862/12 6543xxxx00000321j 300010160

54、10004201001600102412121 bxxxxxx 654321 2543xxxx90000243 j 线性规划的单纯形法线性规划的单纯形法由由T(1)可可得到得到:X(1)=(0,3,6,2,16,0)TS(1)=9因为因为1=20，故，故X(1)不是最不是最优解。优解。3000101601000420100160010 2 412121 bxxxxxx 654321 4416222326 2543xxxx90000 243 j 按最大正检验数规则按最大正检验数规则选选x1为换入变量。为换入变量。根据根据规则确定规则确定x4为为换出变量。换出变量。3、T(1) T(2) 利用行初

55、等变换将利用行初等变换将x1所在列化为单位列向所在列化为单位列向量，可得到量，可得到T(2)。由。由T(2)得到：得到：X(2)=(2,3,2,0,8,0)TS(2)=13 因为因为6=1/40，故，故X(2)不是最优解。不是最优解。300010821400020100120210 0 412121 bxxxxxx 654321123428424121 2513xxxx13 0 200 041 j 3000101601000420100160010 2 412121 bxxxxxx 654321 4416212326 2543xxxx90000 243 j 显然应选显然应选x6为换入变量。为换

56、入变量。根据根据规则可选规则可选x3或或x5为为换出变量。该情况下应换出变量。该情况下应优先取松弛变量作为换优先取松弛变量作为换出变量，由于出变量，由于x3和和x5均均为松弛变量，可任取一为松弛变量，可任取一个作为换出变量，这里个作为换出变量，这里取取x5作为换出变量。作为换出变量。300010821400020100120210 0 412121 bxxxxxx 654321123428424121 2513xxxx13 0 200 041 j 利用行初等变换将利用行初等变换将x6所在列化为单位列向所在列化为单位列向量，可得到量，可得到T(3)。2001041200040000100110

57、0 8121214141 bxxxxxx654321 2613xxxx140 0 0 08123 j 4、T(2) T(3)由由T(3)得到：得到：X(3)=(4,2,0,0,0,4)TS(3)=14 所有的检验数均不大于所有的检验数均不大于0，故，故X(3)是最优解。是最优解。X*=(4,2,0,0,0,4)TS*=14线性规划的单纯形法线性规划的单纯形法四四 、单纯形法的一般步骤、单纯形法的一般步骤(max问题问题)1、将、将LP问题化为标准型问题化为标准型(n个变量，个变量，m个约束方程个约束方程)2、从约束方程组的系数增广矩阵中选出、从约束方程组的系数增广矩阵中选出m个不同的单位列向个

58、不同的单位列向量构成初始基，列出初始单纯形表量构成初始基，列出初始单纯形表T(0)，并由，并由T(0)确定确定X(0)。如果不能直接找到如果不能直接找到m个不同的单位列向量，可用个不同的单位列向量，可用“人工变人工变量法量法”构造初始基。构造初始基。3、最优性检验。判别已得到的基本可行解、最优性检验。判别已得到的基本可行解X(k)是否最优解。是否最优解。 所有非基变量的检验数所有非基变量的检验数j0，则，则X(k)是最优解是最优解(对于对于min问问题，应当是题，应当是j 0)。 如果存在一个检验数如果存在一个检验数j00，且相应的系数列向量的各元，且相应的系数列向量的各元素素aij00(i=

59、1m)，则问题无有界最优解，即，则问题无有界最优解，即S+。线性规划的单纯形法线性规划的单纯形法 k =maxj|j0 ，选，选xk为换入变量，转下一步。为换入变量，转下一步。4、确定换出变量、确定换出变量，则则应应选选第第。设设，令令lklaikiabmiabminik 10l行对应的变量行对应的变量xl作为换出变量。作为换出变量。5、将、将xk与变量与变量xl对换，将对换，将xk的系数列向量化为单位列的系数列向量化为单位列向量，向量，从而得从而得，令，令，,kkmiaaiklk1)101( 到一个新的单纯形表到一个新的单纯形表T(k)，T(k)中的元素按下列公中的元素按下列公式计算：式计算

60、：线性规划的单纯形法线性规划的单纯形法6、计算、计算T(k)的检验数行，转第的检验数行，转第3步。步。说明：对于说明：对于min问题：问题：最优性检验准则：所有非基变量的检验数均不小于最优性检验准则：所有非基变量的检验数均不小于0为为最优解；最优解；选择有最小负检验数的非基变量作为换入变量。选择有最小负检验数的非基变量作为换入变量。)(主元行主元行，liaaalkljij liaaaaaiklkljijij ， l ibaabliabbllkikilkii 2.5 人工变量法人工变量法大大M法法当系数矩阵中找不出当系数矩阵中找不出m个线性无关的单位列向量时，采用个线性无关的单位列向量时，采用人