第一章线性规划及单纯形法

1、第一章第一章 线性规划及单纯形法线性规划及单纯形法是运筹学的一个重要分支。是运筹学的一个重要分支。自自1947年美国数学家丹捷格（年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规）提出了求解线性规划问题的方法划问题的方法单纯形法之后，线性规划在理论上趋于成熟，在单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它的适用领域更万个约束条件和变量的大规模线性规划问题之后，它的适用领域更广泛了。广泛了。第一章第一章 线性规划及单纯形法线性

2、规划及单纯形法是一种合理利用资源、合理调配资源的应用数学是一种合理利用资源、合理调配资源的应用数学方法。其中：方法。其中：就是利用某种数学方法使得有效资源的运用就是利用某种数学方法使得有效资源的运用最优化；最优化；就是用来描述变量之间关系的函数是线性函数。就是用来描述变量之间关系的函数是线性函数。 （1）计划任务的确定，如何统筹安排，精心筹划，用最少的资源来）计划任务的确定，如何统筹安排，精心筹划，用最少的资源来实现。实现。这方面的问题涉及到系统的这方面的问题涉及到系统的和和（2）资源的确定，如何合理利用，合理规划，使得完成的任务最大。）资源的确定，如何合理利用，合理规划，使得完成的任务最大。

3、这方面的问题涉及到系统的这方面的问题涉及到系统的和和线性规划研究和应用的内容是实现系统的投入产出的问题，就是线性规划研究和应用的内容是实现系统的投入产出的问题，就是用最少的劳力和物力消耗，获利更多更好的社会需求产品。用最少的劳力和物力消耗，获利更多更好的社会需求产品。1.1 线性规划问题及其数学模型线性规划问题及其数学模型 1.1.1 1.1.1 问题的提出问题的提出( (一一) ) 设设 备备原原 料料A A原原 料料B B 1 4 0 2 0 4 8台时 16kg 12kg 例例 某工厂在计划期内要安排生产某工厂在计划期内要安排生产、两种产品，两种产品，已知生产单位产品所需的设备台时和原料

4、已知生产单位产品所需的设备台时和原料A、B的消的消耗量如下表。耗量如下表。 该工厂每生产一件该工厂每生产一件产品产品可获利可获利2元，每生产一件产元，每生产一件产品品可获利可获利3元，问应如何安排生元，问应如何安排生产计划能使该厂获利最多？产计划能使该厂获利最多？ 这个问题可以用下面的数这个问题可以用下面的数学模型来描述，设计划期内产学模型来描述，设计划期内产品品、的产量分别为的产量分别为x1，x2，可获利润用可获利润用z表示，则有：表示，则有：Max Z=2x1+3x2x1+2x284x1 16 4x212x1, x20 1.1.1 1.1.1 问题的提出问题的提出( (二二) ) 例例 靠

5、近某河流有两个化工厂，靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天流经第一化工厂的河流流量为每天500万万m3，两工厂之间有一条流量，两工厂之间有一条流量为每天为每天200万万m3的支流（见图）。的支流（见图）。 第一化工厂每天排放污水第一化工厂每天排放污水2万万m3，第二化工厂每天排放污水第二化工厂每天排放污水 1.4万万m3。污水从工厂污水从工厂1流到工厂流到工厂2前会有前会有20%自然净化。根据环保要求，河水中自然净化。根据环保要求，河水中污水的含量应不大于污水的含量应不大于0.2%。而工。而工厂厂1和工厂和工厂2处理污水的成本分别为处理污水的成本分别为1000元元/m3和和8

6、00元元/m3。问两工厂。问两工厂各应处理多少污水才能使处理污水各应处理多少污水才能使处理污水的总费用最低？的总费用最低？ 设工厂设工厂1和工厂和工厂2每天分别处理污水每天分别处理污水x1和和x2万万m3，则有，则有：Min z=1000 x1+800 x2(2-x1)/5000.0020.8(2-x1)+1.4-x2/700 0.002x12, x21.4 x1, x201.1.1 1.1.1 问题的提出问题的提出( (三三) )例例 某养鸡场所用的混合饲料是由某养鸡场所用的混合饲料是由 n 种配料组成。要求这种混合种配料组成。要求这种混合饲料必须含有饲料必须含有 m 种不同的营养成份，而且

7、要求每单位混合饲料中第种不同的营养成份，而且要求每单位混合饲料中第 i 种营养成份的含量不能低于种营养成份的含量不能低于 bi ( i= 1,2, , m）。已知第）。已知第 i 种营养成种营养成份在每单位的第份在每单位的第 j 种配料中的含量为种配料中的含量为 aij , j = 1,2, , n，每单位的第，每单位的第 j 种配料的价格为种配料的价格为 cj 。现在要求在保证营养条件的前提下，应采用。现在要求在保证营养条件的前提下，应采用何种配方，使混合饲料的成本最小何种配方，使混合饲料的成本最小.配料配料营养成份营养成份B1 B2 Bn含量含量A1A2Am a11 a12 a1n a21

8、 a22 a2n am1 am2 amnb1b2 bm单价单价 c1 c2 cn1x1 + 2x2 + + nxn 设设xj 表示在单位混合饲料中，第表示在单位混合饲料中，第j 种配料的含量（种配料的含量（ j =1,2,n）则有如下的数学模型：）则有如下的数学模型：配料配料营养成份营养成份B1 B2 Bn含量含量A1A2Am a11 a12 a1n a21 a22 a2n am1 am2 amnb1b2bm价格价格 c1 c2 cn11x1 + 12x2 + + 1nxn b1 21x1 + 22x2 + + 2nxn b2m1x1 + m2x2 + + mnxn bmx1 0, x2 0

9、, , xn0 1.1.2 线性规划问题的数学模型线性规划问题的数学模型 线性规划问题的共同特征线性规划问题的共同特征（1 1）每个问题都用一组每个问题都用一组(x(x1 1 , x , x2 2 , , , x , xn n ) )表示某一表示某一方案方案 , ,这组未知数的值就代表一个这组未知数的值就代表一个具体的方案具体的方案, ,通常要求这些未知数取值是非负的。通常要求这些未知数取值是非负的。 （2）存在一定的限制条件）存在一定的限制条件( (称为称为),),这些这些条件都可条件都可以用关于决策变量的一组线性等式或不等式来表示。以用关于决策变量的一组线性等式或不等式来表示。（3）都有一

10、个目标要求）都有一个目标要求, ,并且这个目标可表示为这组决策变量并且这个目标可表示为这组决策变量的线性函数的线性函数( (称为称为),),按研究问题按研究问题的不同的不同, ,要要求目标函数实现最大化或最小化。求目标函数实现最大化或最小化。 max(min)Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn (或或, ) b1 a21x1+a22x2+a2nxn (或或, ) b2 am1x1+am2x2+amnxn (或或, ) bm x1,x2,xn ()01.1.3 线性规划问题的数学模型有各种不同的形式，如 目标函数有和； 约束条件有“”、“”和“”三种情况； 决策

11、变量一般有要求，有的则没有。为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型计算 目标函数目标函数 约束条件为约束条件为 右端常数项右端常数项 决策变量决策变量 maxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn b1a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbmx1,x2,xn 0标准型的表达方式有代数式、矩阵式：标准型的表达方式有代数式、矩阵式： maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,

12、x2,xn 0简记maxZ= cjxj aijxjbi ( i=1,2,m) xj0 ( j=1,2,n)nj1nj10. .maxXbAXtsXCZTncccC 价值向量21mnmmnnaaaaaaaaaA212222111211技术矩阵mbbbb21资源向量nxxxX21决策向量化为化为maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn 0只需将等式两端乘以只需将等式两端乘以-1即即问题。因为问题。因为minZ=max(Z)=CTX，令令Z= -Z，则，则两端同

13、乘以两端同乘以 -1 当约束方程为当约束方程为“”时，左端加入一个非负的时，左端加入一个非负的，就把不，就把不等式变成了等式；如等式变成了等式；如当约束条件为当约束条件为“”时，不等式左端减去一个非负的时，不等式左端减去一个非负的(也可称松弛变量也可称松弛变量)，就把不等式变成了等式就把不等式变成了等式。 令令xk=xk-xk， 其中令其中令xk，xk 0，用，用xk、xk 取代模型中取代模型中xkmaxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t. maxZ= 3x1 +5 x2 +0 x3 x1 +x3 =8 2x2 12 3x1

14、+4 x2 36 x1, x2 , x3 0 maxZ= 3x1 +5 x2 +0 x3 + 0 x4 x1 +x3 =8 2x2 +x4 =12 3x1 +4 x2 36 x1, x2 , x3 , x4 0 maxZ= 3x1 +5 x2 +0 x3 + 0 x4+ 0 x5 x1 +x3 = 8 2x2 +x4 =12 3x1 +4 x2 + x5 = 36 x1, x2 , x3 , x4 ,x5 0 maxZ= 3x1 +5 x2 +0 x3 + 0 x4+ 0 x5 x1 +x3 = 8 2x2 +x4 =12 3x1 +4 x2 + x5 = 36 x1, x2 , x3 , x

15、4 ,x5 0引进一引进一 x3引进一引进一 x4引进一引进一 x5 minZ= x1 +2 x2 -3 x3 x1 +2 x2 - x3 5 2x1 +3 x2 - x3 6 -x1 - x2 - x3 -2 x1 0 , x3 0S.t. minZ= x1 +2 x2 +3 x3 x1 +2 x2 + x3 5 2x1 +3 x2 + x3 6 -x1 - x2 + x3 -2 x1 0 , x3 0 minZ= x1 +2 (x2-x 2 ) +3 x3 x1 +2 (x2-x 2 ) + x3 5 2x1 +3 (x2-x 2 ) + x3 6 -x1 - (x2-x 2 ) + x3

16、 -2 x1, x2, x 2, x3 0 minZ= x1 +2 (x2-x 2 ) +3 x3 x1 +2 (x2-x 2 ) + x3 5 2x1 +3 (x2-x 2 ) + x3 6 x1 + (x2-x 2 ) - x3 2 x1, x2, x 2, x3 0 maxZ= -x1 -2 (x2-x 2 ) -3 x3 +0 x4 x1 +2 (x2-x 2 ) + x3 + x4 =5 2x1 +3 (x2-x 2 ) + x3 6 x1 + (x2-x 2 ) - x3 2 x1, x2, x 2, x3 , x4 0 maxZ= - x1 -2 (x2-x 2 ) -3 x3

17、+0 x4 +0 x5 x1 +2 (x2-x 2 ) + x3 + x4 =5 2x1 +3 (x2-x 2 ) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 2 x1, x2, x 2, x3 , x4 , x50 maxZ= -x1 -2 (x2-x 2 ) -3 x3 +0 x4 +0 x5 + 0 x6 x1 +2 (x2-x 2 ) + x3 + x4 =5 2x1 +3 (x2-x 2 ) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6 = 2 x1, x2, x 2, x3 , x4 , x5 , x6 0 maxZ=- x1

18、 -2 (x2-x 2 ) -3 x3 x1 +2 (x2-x 2 ) + x3 5 2x1 +3 (x2-x 2 ) + x3 6 x1 + (x2-x 2 ) - x3 2 x1, x2, x 2, x3 0 maxZ= -x1 -2 (x2-x 2 ) -3 x3 +0 x4 +0 x5 + 0 x6 x1 +2 (x2-x 2 ) + x3 + x4 =5 2x1 +3 (x2-x 2 ) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6 = 2 x1, x2, x 2, x3 , x4 , x5 , x6 0 令令 x3 x3令令 x2 x2x2令令 -Z

19、 Z引进一引进一 x4引进一引进一 x5引进一引进一 x6无限制321321321321321,0,)3(523)2(2)1(732xxxxxxxxxxxxxxxZMin0,5223270033272154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxZMax（1）maxZ= -x1 +3 x3 +4 x4 2 x1 +4 x2 + x3 - 2 x4 13 6 x1 + x3 + 8 x4 50 - x1 +4 x2 -5 x3 - 3 x4 = - 10 xi 0 , i=1,2,3,4S.t.（2）minZ= 6 x1 +7 x2 - x3 3 x1

20、+2 x2 - x3 10 x2+ x3 15 x1 3 x2 2 x1 , x2 0 ，x3 无限制无限制S.t.（1）maxZ= -x1 +3 x3 +4 x4 +0 x5 +0 x6 2 x1 +4 x2 + x3 - 2 x4 + x5 =13 6 x1 + x3 + 8 x4 - x6 =50 x1 -4 x2 +5 x3+ 3 x4 = 10 xi 0 , i=1,2,3,4,5,6S.t.（2）maxZ= - 6 x1 -7 x2 + x3x4 +0 x5 + 0 x6 + 0 x7 + 0 x8 3 x1 +2 x2 - x3 + x4+ x5 =10 x2+ x3x4 + x

21、6 = 15 x1 - x7 =3 x2 - x8=2 x1 , x2 , x3 , x4 , x5 , x6 , x7 , x80S.t.1.1.4 在讨论线性规划问题的求解之前在讨论线性规划问题的求解之前,先要了解线性规划问题的解先要了解线性规划问题的解的概念。由前面讨论可知线性规划问题的标准型为：的概念。由前面讨论可知线性规划问题的标准型为： ）（1njjjxcZMax1）（）（32), 2 , 1(0), 2 , 1(1njxmibxajnjjjij求解线性规划问题就是从满足约束条件求解线性规划问题就是从满足约束条件(2)、(3)的方程组中找出的方程组中找出一个解，使目标函数（一个解，

22、使目标函数（1）达到最大值。）达到最大值。若设矩阵若设矩阵A的秩的秩R(A)=m；根据线性代数定理可知，当；根据线性代数定理可知，当R(A)=mn，则方程组有无穷多个解，这也正是线性规划寻求最优解的则方程组有无穷多个解，这也正是线性规划寻求最优解的。 与 满足约束条件（满足约束条件（2 2）和非负条件（）和非负条件（3 3）的解）的解 X 称为称为，满足约，满足约束条件（束条件（2 2）但不满足非负条件（）但不满足非负条件（3 3）的解）的解 X 称为称为组成的集合叫做组成的集合叫做：使目标函数使目标函数(1)(1)达到最大的解称为最优达到最大的解称为最优解解)1(1njjjxcZMax)3(

23、), 2 , 1(0)2(), 2 , 1(1njxmibxajnjjjij 在标准型中，约束方程组的系数矩阵有在标准型中，约束方程组的系数矩阵有 n n 列，即列，即 A = ( P1, P2 , , Pn ) 设设A A的秩为的秩为m m ，当当R(A)=mn ，A A中必有线性独立的中必有线性独立的m m列，构成列，构成该标准型的一个该标准型的一个，即即 B = ( P1 , P2 , , Pm )， | B | 0 P1 , P2 , , Pm 称为称为 与与对应的变量称为对应的变量称为，记为，记为XB = ( x1 , x2 , , xm )T其余的变量称为其余的变量称为，记为，记为

24、XN = ( xm+1 , xm+2 , , xn ) T ， 故有故有 X = XB + XN，mnC最多有最多有 个基个基0. .maxXbAXtsXCZT令令非基变量非基变量 XN = 0，求得求得基变量基变量XB的值称为的值称为基解，基解，即即XB = B 1 b基解是有限的基本解基本解XB 的非零分量都的非零分量都 0 时，称为时，称为基本可行解基本可行解，否则为，否则为基非基非可行解可行解基本可行解基本可行解的非零分量个数的非零分量个数 m m 时，称为退化时，称为退化解解对应于基本可行解对应于基本可行解的基的基，称为，称为可行基可行基约束方程的约束方程的解空间解空间基本解基本解可

25、行解可行解非可行解非可行解基本基本可行解可行解退化解退化解例例1 的标准型为的标准型为 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 036101201800043020101Ax1x2x3x4x5还原为maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5x3 =- x1 + 8 x4 = -2x2 + 12 x5= -3x1 -4 x2+ 36 基变量是x3, x4, x5， 令非基变量x1=x2=0，得到x3=8，x4=12， x5=

26、36基解。非基变量是x1, x2，对于简单的线性规划问题对于简单的线性规划问题(只有两个决策变量的线性规划只有两个决策变量的线性规划问题问题)，可以通过图解法对它进行求解。可以通过图解法对它进行求解。即是用图示的方法来求解线性规划问题。即是用图示的方法来求解线性规划问题。图解法图解法简单直观，有助于了解线性规划问题求解的基本原理简单直观，有助于了解线性规划问题求解的基本原理。一个二维的线性规划问题，可以在平面图上求解，三维一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能用图示了。

27、高以后就不能用图示了。 满足所有约束条件的解叫可行解，解的集合称之为满足所有约束条件的解叫可行解，解的集合称之为。即所。即所有约束条件共同围成的区域。有约束条件共同围成的区域。x1 =82x2 =123x1 +4 x2 =36x1x24812369五边形五边形OABCD内内(含边界含边界)的任意一点的任意一点 (x1，x2) 都是满足所有约都是满足所有约束条件的一个解，称之束条件的一个解，称之 。maxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 02. 最优解的确定最优解的确定确定确定x1、x2希望希望目标函数目标函数 Z= 3x1 +5 x2

28、达到最大，图形中达到最大，图形中Z= 3x1 +5 x2 代表以代表以Z为参数的一族平行线，即等值线。为参数的一族平行线，即等值线。等值线：位于同一直线上的点的目标函数值相同。等值线：位于同一直线上的点的目标函数值相同。 Z=3x1+5x20 x1 =82x2 =123x1 +4 x2 =36x1x24812369最优解：可行解中使目标函数最优最优解：可行解中使目标函数最优( (极大或极小极大或极小) )的解的解本题中：满足目标函数最大的极点是离原点距离最远的点（本题中：满足目标函数最大的极点是离原点距离最远的点（4,6）Z=3x1+5x224Z=3x1+5x230Z=39Z=42即即x1=4

29、，x2=6时时Z的值最大为的值最大为42。 （二）解的几种可能性（二）解的几种可能性只有一个最优点。如上题的最优解（只有一个最优点。如上题的最优解（4,64,6）无穷多个最优解。若在两个顶点同时得到最优解，无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。则它们连线上的每一点都是最优解。x1 =82x2 =123x1 +4 x2 =36x1x24812369如例如例1的数学模型变为的数学模型变为 maxZ= 3x1 +4 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t.Z=24Z=36Z=12线性规划问题的可行域无界，使目标函数无限

30、增大而无界。线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）（缺乏必要的约束条件） 例如例如 maxZ= 3x1 +2 x2 -2x1 + x2 2 x1 -3 x2 3 x1 0, x2 0-2x1 + x2 =2x1 -3 x2 =3x2123-1x1123-1Z=6Z=12S.t. 例如例如 maxZ= 3x1 +2 x2 -2x1 + x2 2 x1 -3 x2 3 x1 0, x2 0-2x1 + x2 =2x1 -3 x2 =3x2123-1x1123-1S.t.若约束条件相互矛盾，则可行域为空集。若约束条件相互矛盾，则可行域为空集。四边形四边形OBQC内

31、内(含边界含边界)的任意一点的任意一点 (x1，x2) 都是满足所有约束都是满足所有约束条件的一个解，称之可行解条件的一个解，称之可行解 。maxZ= 8x1 +6x24x1 +2 x2 60 2x1 +4 x2 48 2x1 +3 x2 36 x1 0, x2 02x1 +3 x2 =36x1x2510510154x1 +2 x2 =602x1 +4x2 =48Z=0Z=72Z=120Z=126设有某林场需配制某种灭虫药水设有某林场需配制某种灭虫药水500500公斤，该药水系由甲公斤，该药水系由甲与乙两种药水混合而成。甲种药水每公斤与乙两种药水混合而成。甲种药水每公斤5 5元，乙种药水每公元

32、，乙种药水每公斤斤8 8元。按照两种药水的化学性质，在混合时，元。按照两种药水的化学性质，在混合时，500500公斤混合公斤混合药水中含甲种药水最多不能超过药水中含甲种药水最多不能超过400400公斤，含乙种药水最少不公斤，含乙种药水最少不能少于能少于200200公斤。问如何配制可使该药水配制成本最低？公斤。问如何配制可使该药水配制成本最低？.minZ= 5x1 +8x2 x1 400 x2 200 x1+x2 =500 x1 0, x2 0设：设：500500公斤混合药水中，甲种药水公斤混合药水中，甲种药水x1公斤公斤，乙种药水乙种药水x2公斤公斤线段线段BC上的任意一点上的任意一点 (x1

33、，x2) 都是满足所有约束条件的一个解，都是满足所有约束条件的一个解，称之可行解称之可行解 。minZ= 5x1 +8x2 x1 400 x2 200 x1+x2 =500 x1 0, x2 0Z= 5x1 +8x2 = 4000Z=3100 x2 =200 x1+x2 =500 x1x250200400100300500 x1 =400100200300 400 x2y2 x2y 6x y 3x3y 3x0, y 0（1）max Z= 4x+y画出可行域图形，求下面几种情况下的最优解画出可行域图形，求下面几种情况下的最优解（2）minZ= 2x-3y（3）max Z= x+2y（4）maxZ

34、= 2x-3yx2y2 x2y 6x y 3x3y 3x0, y 0（1）max Z= 4x+y求下面几种情况下的最优解求下面几种情况下的最优解（2）minZ= 2x-3y（4）max Z= x+2y（3）maxZ= 2x-3yx+3y=3x+2y =2xy =3x1x2161234523x+2y =6(2,2)(4,1)(3,0)(0,1)Z= 4x+y =1Z=10Z=12 Z=17Z=-3Z=-2Z=5Z=6最优解最优解 x=4,y=1 max Z= 17最优解最优解 x=0,y=1 min Z= -3Z= 2x+y =1Z= 3Z= 6有无穷多最优解有无穷多最优解 max Z= 6最优

35、解最优解 x=3,y=0 max Z= 6基本概念基本概念1、凸集、凸集: 假设假设 K 是是 n 维欧氏空间的一个点集维欧氏空间的一个点集,若对于若对于K 中的任中的任意两点意两点 X1、X2 ,其连线上的所有点其连线上的所有点 X1+(1- )X2 ( 0 1)都在集合都在集合 K 中中,即即: X1+(1- )X2 K ( 0 1),则称则称 K 为凸集。为凸集。2. 顶点顶点: 假设假设 K 是凸集是凸集, X K ; 若不能用不同的两个点若不能用不同的两个点X1、 X2 K 的线性组合表示为的线性组合表示为: X = X1+(1- )X2 ， ( 0 0=b0=bl l/a/alkl

36、k, 对应的第对应的第l行行的基变量为换出变量的基变量为换出变量. 第三第三, 旋转运算旋转运算. 换入变量所在换入变量所在的行与换出变量所在的列交叉点的元素称为中心元的行与换出变量所在的列交叉点的元素称为中心元素素,用高斯消去法把中心元素化成用高斯消去法把中心元素化成1, 同列的其他元素同列的其他元素化成化成0, 得到一个新的单纯形表得到一个新的单纯形表,也就得到一个新的基也就得到一个新的基本可行解本可行解. maxZ=3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x

37、5000035000 maxZ=3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 标准型Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000令非基变量x1=0，x2=0，找到一个初始基可行解 ： Z=3x1+5x20 x1 =82x2 =123x1 +4 x2 =36x1x24812369X0=(0,0,8,12,36) T一个可行解就是一个生产方案，上述方案表明两种一个可行解就是一个生产方案，上述方案表明两种产品都不生产产品都不生产

38、x1=0，x2=0 ，利润，利润Z=0 。Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9 出基选择行列46212436,212,minminxabi入基选择列255 , 3maxmaxxj中心元素检验数j81010060101/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb检验数jx1x2x3x4x5350008101001200103634001x3x4x5000035000-12/2=636/4=9Z=3x1+5x230 x1 =82x2 =123x1

39、+4 x2 =36x1x24812369X1=(0,6,8,0,12) TCj比值CBXBb检验数jx1x2x3x4x53500081010060101/201200-21x3x2x5050-30300-5/208-4检验数j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1j0 x1 =82x2 =123x1 +4 x2 =36x1x24812369X0=(0,0,8,12,36)T, Z0X1=(0,6,8,0,12)T, Z30X1=(4,6,4,0,0)T, Z42Cj比值CBXBb检验数jx1x2x3x4x5230008121001

40、6400101204001x3x4x5000023000 Max z=2x1+3x2 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1, x2, x3 0标准型Max z=2x1+3x2 x1+2x2 8 4x1 16 4x2 12 x1, x2, x3 0Cj比值CBXBb检验数jx1x2x3x4x52300081210016400101204001x3x4x50000230004-3中心元素检验数j21010-2/41640010301001/4x3x4x2003-92000-3/4Cj比值CBXBb检验数jx1x2x3x4x52300021010-2/4164

41、0010301001/4x3x4x2003-92000-3/424中心元素检验数j21010-2/4800412301001/4x1x4x22031300201/4Cj比值CBXBb检验数jx1x2x3x4x52300021010-2/4800412301001/4X1X4X22031300201/4-412检验数j41001/4040021/212011/2-1/80 x1x5x220314003/2-1/8 0将线性规划问题化成标准型。将线性规划问题化成标准型。找出或构造一个找出或构造一个作为初始可行基，建立初始单纯形表。作为初始可行基，建立初始单纯形表。计算各计算各的检验数的检验数 j=

42、Cj-CBPj ，若所有，若所有 j0，则问题已得到，则问题已得到最优解，停止计算，否则转入下步。最优解，停止计算，否则转入下步。在大于在大于0的检验数中，若某个的检验数中，若某个 k所对应的系数列向量所对应的系数列向量Pk0，则此问题，则此问题是无界解，停止计算，否则转入下步。是无界解，停止计算，否则转入下步。根据根据max j j0= k原则，确定原则，确定xk为换入变量为换入变量(进基变量进基变量)，再按，再按 规则计算：规则计算： =minbi/aik| aik0=bl/ alk 确定确定xBl为换出变量。为换出变量。建立新的单纯形表，此时基变量中建立新的单纯形表，此时基变量中xk取代

43、了取代了xBl的位置。的位置。以以aik为中心元素进行迭代，把为中心元素进行迭代，把xk所对应的所对应的，即，即，同列中其它元素为，同列中其它元素为0，转第，转第 步。步。 用单纯用单纯形形法求解线性规划问题后，应回答法求解线性规划问题后，应回答下面几个问题：下面几个问题： 是否解无界？上面的步骤已作出回答。是否解无界？上面的步骤已作出回答。 是否无可行解？求解后，若人工变量都是否无可行解？求解后，若人工变量都已取已取0 0，则有可行解；否则，无可行解。，则有可行解；否则，无可行解。 唯一最优解还是无穷多最优解？在最后唯一最优解还是无穷多最优解？在最后的单纯形表中，若所有非基变量的检验数都严格

44、小的单纯形表中，若所有非基变量的检验数都严格小于于0 0，则为唯一最优解；若存在某个非基变量的检验，则为唯一最优解；若存在某个非基变量的检验数等于数等于0 0，则有无穷多最优解。，则有无穷多最优解。用单纯形法解题时，需要有一个单位阵作为用单纯形法解题时，需要有一个单位阵作为。当约束条件都是当约束条件都是“”时，加入松弛变量就形成了初始基。时，加入松弛变量就形成了初始基。但实际存在但实际存在“”或或“”型的约束，型的约束，。采用人造基的办法：采用人造基的办法：处理方法有两种：处理方法有两种：maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 +

45、x3 =4 x1 , x2 , x3 0S.t. 没有单位矩阵，不符合构造初始基的条件， 。 maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0 人工变量最终必须等于0才能保持原问题性质不变。 为保证人工变量为0，在。 M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须逐步从基变量中。 如若到，那么这个问题就没有可行解，当然亦。 按大按大M法构造人造基，引入人工变量法构造人造基，引入人工变量x4

46、, x5 的辅助问题如下：的辅助问题如下： maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0Cj比值CBXBb检验数jx1x2x3x4x53-1-2-M-M632-31041-2101x4x5-M-M0-M -2+M-1-2M3+M4M00 -2-2M-13+4M10MmiijBjjaCCi1-M-M -2-13 检验数jbXBCB比值Cjx5x4x3x2x1-M-M-2-1301-3236101-21400-2-2M-110Mx5x

47、4-M-M42-1检验数j212/3-11/3020-8/32-1/31-7 0-3-8M/3-1-4M/3 0 x1x53-M检验数j31-2/301/61/210-4/31-1/61/2-70-5/30-M-5/6-M-1/2x1x33-2按大按大M法构造人造基，引入人工变量法构造人造基，引入人工变量x4 , x5 的辅助问题如下：的辅助问题如下： maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0 例如例如 maxZ= 3x1 -

48、 x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 + x3 =4 x1 , x2 , x3 0S.t. 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 -Z +3x1 - x2 -2 x3 -M x4 -M x5=0 x1 , x2 , x3 , x4 , x5 00-M-2-13-Z411-21060-3230-M0110M0-2-2M-13+4M-Z411-21060-323000110M0-2-2M-13+4M-Z411-21060-3230001-6+2M0 1+2M-3-8M/30-Z212-8/30020

49、-12/310-1-4M/3-1/31/3-7-M-1/20-5/30-Z11/21-4/30031/20-2/310-M-5/6-1/61/6按大按大M法构造人造基，引入人工变量法构造人造基，引入人工变量x4 , x5 的辅助问题如下：的辅助问题如下：0,12324112332131321321321xxxxxxxxxxxxxxZMin0,12324112003717316532143217654321xxxxxxxxxxxxxxMxMxxxxxxZMax松驰变量松驰变量剩余变量剩余变量人工变量人工变量惩罚项惩罚项0-M0-1-13-Z11010-2030021-4011011-21000-

50、10-M0104M00 -1+3M-1+M3-6M-Z11010-2030021-4011011-210-M0-1000100003123241127654321731653214321MxMxxxxxxZxxxxxxxxxxxxx1=0,x2 =0,x5=0,x3 =0,x5 =0,x4=11,x6=3, x7=1即 , Z=0-Z x1 x2 x3 x4 x5 x6 x7 bM+1-3M+10 0-1+M1-Z1100-201-20010010-110-230-M0-1000102-M-10 001-Z11010-201-2000012-51000-10-1-21-M012-2-M+23-

51、1/3 000-Z9-7/32/310001-2001004-5/31/30010-1/3-4/3-1-2/31/3-M4/312/3令x4=0，x5 =0，x6=0, x7 =0, 得x1=4,x2=1,x3,=9即 此时为最大为最小按大按大M法构造人造基，引入人工变量法构造人造基，引入人工变量x5 , x6 的辅助问题如下：的辅助问题如下：0,122316423421212121xxxxxxxxZMin0,1223164200346164215321654321xxxxxxxxxxMxMxxxxxZMax000-3-4-Z12-10230160-1420-M01-M100,12231642

52、00346164215321654321xxxxxxxxxxMxMxxxxxZMax28M-M-M-3+6M-4+5M-Z12-10230160-142000101012+4M-M-3/4+M/20-5/2+2M-Z4-11/202040-1/411/203/4-3M/2-1/21/401017-3/4-1/8 0 0-Z2-1/21/401031/4-3/81001/8-M-1/43/85/4-M1/2-1/4非正 令x3=0，x4 =0，x5=0, x6 =0, 得x1 =2，x2 =3，即 此时为最大为最小 这种方法是在约束条件中加入人工变量这种方法是在约束条件中加入人工变量，将将线性规

53、划问题分为两阶段进行求解线性规划问题分为两阶段进行求解。 第一阶段是先求出基本可行解第一阶段是先求出基本可行解(或判断出原线或判断出原线性规划问题无解性规划问题无解), 第二阶段利用已求出的初始基本可行解来求第二阶段利用已求出的初始基本可行解来求最优解。最优解。解：先在以上问题的约束条件中加入松弛变量、剩余变量、人工变量，给出第一阶段的线性规划问题： 0,12324112332131321321321xxxxxxxxxxxxxxZMin0,12324112717316532143217676xxxxxxxxxxxxxxxxWMaxxxZMin0-10000-W11010-2030021-401

54、1011-21000-10-10100,12324112717316532143217676xxxxxxxxxxxxxxxxWMaxxxZMin40031-6-Z11010-2030021-4011011-210-10-1000100-10000-Z11010-201-20010012-51003000-1-2-10121-30010-Z11010-201-20010010-110-230-10-100010 令x1=0，x5 =0，x6=0, x7 =0,得 x2 =1，x3 =1，x4 =12 ， 这里 x6、x7 是人工变量。第一阶段我们已求得 W = 0 ，最优解 x5 = 0， x6

55、 = 0， x7 = 0。因人工变量 x6 =x7 = 0, 所以( 0, 1, 1 ,12, 0 )T 是原问题的基可行解。于是可以开始第二阶段的计算。将第一阶段的人工变量列取消将第一阶段的人工变量列取消, 并将目标函数并将目标函数系数换成原问题的目标函数系数系数换成原问题的目标函数系数, 重新计算检验重新计算检验数行数行, 可得如下第二阶段的初始单纯形表；应用可得如下第二阶段的初始单纯形表；应用单纯形算法求解得最终表。单纯形算法求解得最终表。 0-10000-Z11010-201-20010012-51003000-1-2-1012 3 -1 -1 0 032132133xxxMaxZxx

56、xZMin00-1-13-Z1010-20100100121003000-1-2-2-1/3000-Z92/3100010010041/30010-1/3-4/3-1-2/320001-Z1010-201001001210030-10-1-2试用试用:(1)大大M法法;(2)两阶段法求解上述线性规划模型两阶段法求解上述线性规划模型0,46278102132121321xxxxxxxxxxZMin0,462007810717632154217654321xxxxxxxxxxxMxxMxxxxxZMax00-7-8-10-Z4011106-10120 -M010-10-M 1 010M-M -7+

57、M -8+2M-10+3M-Z4011106-10120001-M-100 1 01/2M-5 -7+M -3+1/2M 0-Z11/211/2003-1/201/210 5-3/2M-1/21/2-M-100 1 0M+30-3/2 0 1/2 0-Z11/211/2003-1/201/210 3/2-M-1/21/2-7-107-M 1 037-2 -1 0 0-Z2121002-1-10102-M-11-6-216-M 2 -1360,4627176321542175xxxxxxxxxxxxxZMin00000-Z4011106-10120 -1010-10-1 1 010-1 1 2

58、3-Z4011106-10120001-1-100 1 01/2 1 1/2 0-Z11/211/2003-1/201/210-3/2-1/21/2-1-100 1 0175xxMaxZ0 00 0-Z11/211/2003-1/201/210-1-1/21/20-10-1 1 00-Z -10 -8 -7 0 -3/2 0 1/2 0 -Z11/211/2003-1/201/2101/2-1/21/2-7-10-1 1 037-2-1 0 0 -Z2121002-11-10101/2-1/21/2-6-21-1 1 03632132178107810 xxxZMaxxxxZMin 单纯形法运

59、算过程中，单纯形法运算过程中，同时出现多个同时出现多个相同的相同的 j最大。最大。 在符合要求的在符合要求的 j(目标为目标为max： j0，min： j0)中，选取中，选取下标下标为换入变量；为换入变量； 单纯形法运算过程中，同时出现多个相同的最小单纯形法运算过程中，同时出现多个相同的最小值。值。 继续迭代，便有基变量为继续迭代，便有基变量为0，称这种情况为，称这种情况为。 选取其中下标选取其中下标做为换出变量。做为换出变量。多重最优解：多重最优解： 最优单纯形表中，最优单纯形表中，存在非基变量的检验数存在非基变量的检验数 j=0。 让这个让这个非基变量作为换入变量，非基变量作为换入变量，继

60、续迭代，得另一个最优解。继续迭代，得另一个最优解。无界解：无界解： 在大于在大于0的检验数中，若某个的检验数中，若某个 k所对应的系数列向量所对应的系数列向量Pk0，则此问题，则此问题是无界解。是无界解。无无可行解：可行解： 最终表中存在人工变量是基变量最终表中存在人工变量是基变量。 解的判别：情况解的判别：情况1无穷最优解无穷最优解Cj比值CBXBb检验数jx1x2x3x4x5x6240000221000120100 x3X4X5X6000040001064-3Max z=2x1+4x2 2x1+2x2 12 x1+2x2 8 4x1 16 4x2 12 x1, x2, x3 0标准化标准化