2第一章线性规划(教案)[1].3.21 修改模板修改

《2第一章线性规划(教案)[1].3.21 修改模板修改》由会员分享，可在线阅读，更多相关《2第一章线性规划(教案)[1].3.21 修改模板修改（119页珍藏版）》请在装配图网上搜索。

1、,,,,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,单击此处编辑母版标题样式,,,,*,,,,运筹学 熊中楷 教授,/,博士生导师,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,单击此处编辑母版标题样式,,,,*,运筹学,重庆大学 经济与工商管理学院,熊中楷 教授,/,博士生导师,,,联系方式：,023-65111708 bearelm,1,,个人介绍：,,顶级斯坦福大学,顶级伯克利大学,著名约克大学,著名俄亥俄大学,著

2、名俄亥俄大学,下乡种地,山区犁田,改变命运靠运筹,一 本章内容：,,1,线性规划的引例，标准形式,,2,线性规划图解法,,3,线性规划单纯形方法（代数方法和表格方法）,,4,线性规划的应用（建立模型）,,二 教学目的：,,掌握线性规划的引例，标准形式和几种解法的原理,,三 本章重点：,,几种解法和线性规划的应用（建立模型）,,四 本章难点：,单纯形方法（代数方法和表格方法）,,五 计划学时：,12,学时,,第一章：线性规划,,甲产品,,乙产品,,资源量,,设备,,1,2,,8,台时,,原材料,A,,4,0,,16,公斤,,原材料,B,,0,4,,12,公斤,,产生的收益,,2,元,,3,元,,

3、,问题：如何计划使得工厂利润最大？,,分析：决策中的关键变量是什么？变量中的相互因果关系是什么？,,怎样用数学公式来建立有用的模型？,第一章：线性规划（,1,）,,第一章 线性规划及单纯形法,,1.1,一般线性规划问题的数学模型,,典,型引例： 某工厂在计划期内安排甲，乙两种产品，已知生产单位产品所消耗资源以及产生的利润如下表：,,思路：收益最大,,资源有约束,,Max 2X,1,+3X,2,,X,1,+ 2X,2,<= 8,,4X,1,<=16,,4X,2,<=12,,X,1,>=0,,X,2,>=0,第一章：线性规划（,1,）,一般形式,,Max CX,,AX<=b,,X>=0,,,

4、1 2,,,,4 0,,,0 4,,A=,,,,X,1,,,X,2,,,,8,,,16,,12,,b=,,,c=,2 3,,A,是技术矩阵，,b,是资源向量，,C,是利润向量,,A=[A1A2] Ai,表示生产,I,种产品消耗的资源,1,．线性规划定义,,求一组变量,x,1,，,x,2,，,…,，,x,n,的值，使之满足关于这组变量的若干个线性等式或不等式的约束条件，而且使这组变量的一个线性函数取到极大值（或极小值）。这些变量称为决策变量，所要优化的函数称为目标函数，决策变量是取实数值的连续变量。这样的问题称为线性规划。,,2,．线性规划的一般形式与标准形式,,3,．线性规划的解

5、的相关定义,,可行解,满足线性规划所有约束条件的各变量的一组值,X=,（,x,1,，,x,2,，,…,，,x,n,）,T,，称为线性规划问题的可行解。全部可行解的集合称为可行域。,,最优解,使线性规划的目标函数达到以最优值（依照具体问题，或者是极大值，或者是极小值）的可行解称为线性规划问题的最优解。,,上述两个概念，对于一般形式、标准形式都适用，而下述五个概念，仅适用于标准形式。,第一章：线性规划（,1,）,,图解法,,引例：,,目标函数：,MAX Z= X,1,+,3X,2,,,满足的 约束条件：,,,5 X,1,+10 X,2,<=50,,X,1,+ X,2,>=1,,X,

6、2,<=4,,X,1,,X,2,>=0,,X,1,+3X,2,=,常数 ： 目标函数的等值线,,由右图知，在,D,点得最优解。,D,点坐标（,2,，,4,），此时,max Z=14,,,画出各种情况对应的图形,：,第一章：线性规划（,1,）,,5 10,,1 1,,0 1,,A=,,X,1,+X,2,= 1,X,2,= 4,,,,,,,,,,,,,,,,,,,,,,,,,,,,,X,1,+3X,2,=,常数,5X,1,+10X,2,= 50,,,,,,,,,,,,,目标函数等值线,可行域和它的顶点,,,,,第一章：线性规划（,1,）,D,第一章：线性规划（,1,）,从

7、图解法猜想,:,,LP,最优解是可行域的顶点之一,,因此，我们更关注可行域的顶点（有限个）,图解法,基本要求,,能正确地按图解法的步骤画出图来解答题目，并会判定解的类型。,,知识要点,,（,1,）图解法仅适用于两个变量的线性规划问题，求解时按原来题目对目标函数的优化要求去求解即可，不必将求极小值化为求极大值。,,三个变量的线性规划问题用图解法求解时，可行域是三维空间的多面体，很难用平面上的图形画得清晰准确，目标函数对应的是三维空间中的平面，难以通过平面上画出的立体图形求出最优解。所以，从理论上讲，三个变量的线性规划也有图解法，但实际上不可行。多于三个变量的线性规划涉及到在高于三维的向量空间中求

8、解优化问题，而三维以上的空间已无直观的几何意义，故不存在相应的图解法。,,（,2,）线性规划问题的解的情况共有四种：,,（,3,）线性规划问题如果有最优解，则可行域的某个顶点必定是最优解。为求最优解，可以先计算可行域某个顶点处的目标函数值，再考察它周围相邻顶点的目标函数值是否比这个值更优，如果为否，则该顶点就是最优解（或最优解之一），否则转到比这个点的目标函数值更优的另一顶点，重复上述过程，直到找出对应最优解的顶点。,第一章：线性规划（,1,）,已知几何图形上判断线性规划解各种类型。,从图解法猜想,,,LP,最优解是可行域的顶点之一,,,,,,,,,,,运筹学,线性规划（,2,）,.,线性规划

9、问题的解的基本概念,,对于标准型,LP,问题,,,,,,,,,可行解：,满足约束条件的解称为可行解。,,,基：,A,中任何一组,m,个线性无关的列向量构成的子矩阵,,,称为该问题的一个基（,basis,）,,,与中的这些列向量对应的变量称为基变量（,basic variable,）,研究思路： 几何图形的点,----------------,对应代数式子,可行域的点有什么特点？,可行域的点就是满足约束条件的点，因此从约束条件出发,最优解：,若基本可行解又是最优解（也称基本最优解），这个基就称为最优基,（,optimal basis,）,基本解：,对于基,,,令非基变量为零,,,求得满足约束条

10、件,(1),的解，称为基对应的基本解,（,basic solution,）。,基本可行解：,满足非负条件的基本解称为基本可行解（,basic feasible solution,）；,基本可行解所对应的基称为可行基,（,feasible basis,）。,线性规划问题的解的基本概念,,AX=b,A=[BN] B,存在逆，,B XB + N XN = b,,XB = B-1b - B-1 N XN,,如果,XN = 0,，,XB = B-1b,，这个叫基解。,,这个解不一定满足非负。,,如果,XB = B-1b >= 0,,那么,XB = B-1b,，,XN = 0,是基

11、可行解，也就是可行域的点,,重要结论：,如果,XB = B-1b >= 0,,那么,XB = B-1b,，,XN = 0,不仅是可行域的点,,,,而且是可行域的顶点。,,,线性规划的基本理论,,,由图解法的步骤，可以从几何的角度得出以下两个猜想：,,（,1,）线性规划问题的可行域是一个有界或无界的凸多边,,形，其顶点个数是有限个。,,（,2,）若线性规划问题有最优解，那么最优解一定可在可,,行域的某个顶点上找到。,,第一章：线性规划（,2,）,与猜想相关的几个基本概念,,（,1,）凸集：设,k,是,n,维欧式空间的一个点集，若任意两点,,,X,(1),∈k, X,(2),∈k,的连线上的

12、一切点,αX,(1),+ (1-α)X,(2),∈k,,,( 0<α<1),,则称,k,为凸集。,,,,,,,,,连接几何形体中任意两点的线段仍完全在该几何形体之中。,,有限个凸集的交集仍然是凸集。,有限个凸集的交集仍然是凸集吗？,,,,,,,,,,,,,第一章：线性规划（,2,）,（,2,）凸组合：设,X,(1),，,X,(2),，,…,，,X,(k),是,n,维欧式空间中的,k,个点，,,若存在,μ,1,,μ,2,,…, μ,k,满足,0≤μ,i,≤1,(,i=1,2,…,k),,,,使,X=μ,1,X,(1),+μ,2,X,(2),+…μ,k,X,(k),，,,则称,X,为,X,(1),

13、，,X,(2),，,…,，,X,(k),的凸组合。,,凸集,k,中任意两点,X,(1),，,X,(2),连线上的任一点,X,都是,X,(1),与,X,(2),的一个凸组合。,,,(3),顶点：设,k,为凸集，,X∈k,,若,X,不能用,X,(1),∈k,X,(2),∈k,两点的,,一个凸组合表示为,X=αX,(1),+ (1-α)X,(2),,,其中,0<α<1,，,,则称,X,为,k,的一个顶点。,与猜想相关的几个基本概念,,第一章：线性规划（,2,）,定理,1,：若线性规划问题存在可行域，则其可行域,,是一个凸集。,证明：为了证明满足ＡＸ,=,ｂ，Ｘ≥,0,的所有点（可行解）组成的几何体是

14、凸集，只要证明Ｄ中任意两点任意两点　　　　连线上的一切点均满足线性约束条件既可。,,任取　　　　　　　，满足,,则对任意的　　　　　　　　　　　　　有,,线性规划的基本定理,,又因为　　　　　　　均≥,0,，所以,,由此可知，　　　　　　　　　　即Ｄ是凸集。,第一章：线性规划（,2,）,证明：,必要性：,因为Ｘ是基本解，由基本解的定义，Ｘ的非零分量所对应的系数列向量线性无关，又因为Ｘ是可行解，由基本可行解的定义，非零分量均是正的，所以Ｘ的正分量所对应的系数列向量线性无关。,,,充分性,：设Ｘ是线性规划问题的可行解，且正分量　　　　　　所对应的列向量　　　　　也线性无关，则必有,k≤m,,若,k

15、=m,，则,,刚好构成一个基，　　　　　　　　　　　为相应的基本可行解。若,k

16、。,现在证明如果,x,不是基可行解，则它一定不是顶点。只要证明它在,2,个可行解的连线上,,由引理,1,，,x,不是基可行解，它的正分量对应的系数列向量线性相关，,即,x(1),x(2),是可行解，因此,x,不是顶点,第一章：线性规划（,2,）,充分性：若Ｘ是线性规划的一个基本可行解，要证明Ｘ是可行域Ｄ的一个顶点，,,仍用反证法，倘若Ｘ不是可行域Ｄ的顶点,，,Ｘ的基变量所对应的系数列向量　　　　　线性相关，与,X,是基本可行解矛盾。,,第一章：线性规划（,2,）,例 已知线性规划问题的约束条件为,试讨论可行域顶点和基本可行解之间的对应关系。,,解,:,可行域,,,,为四维凸多面体，可以推得

17、在四维空间中有,3,个顶点，,,Ａ,=(0,0,10,10),，Ｂ,=(0,10,0,10),，Ｃ,=(10,0,0,0),。,,这,3,个顶点与线性规划的,5,个基本可行解的对应关系如下：,,顶点Ａ对应以,x,3,,x,4,为基变量的基本可行解；,,顶点Ｂ对应以,x,2,,x,4,为基变量的基本可行解；,,顶点Ｃ对应,x,1,,x,2,;x,1,,x,3,和,x,1,,x,4,为基变量的退化基本可行解,（退化即存在基变量为,0),第一章：线性规划（,2,）,,一,个线性规划问题，如果它的所有基本可行解都是非退化的，那么 称这个线性规划是非退化的，只有在这种情况下，顶点和基本可行解 之间才是一

18、一对应的。,,,,,定理,3,,若可行域,D,非空有界，那么线性规划问题的目标函数一定可以在可行域,D,的顶点上达到最优值。,,证明的思路是：因为可行域非空有界，所以线性规划一定有最优解，,,倘若 不是顶点，且目标函数在该点处取到最优值 ，则这个点可以表示成为顶点的凸组合，,线性规划的基本定理,,定理,3,并不排除在一个非顶点上有一个最优解的可能性。但是在一个 给定的线性规划问题的所有最优解中，至少有一个是顶点。,,,如果可行域无界，则线性规划问题可能无最优解。,,如果目标函数同时在两个顶点上达到最优解，那么不难证明在这两个 点的凸组合上也达到最优解，这时线性规划问题有无穷多最优解。,

19、,第一章：线性规划（,2,）,为什么要学习线性规划基本定理,----------------,研究求解 可行域顶点的代数表达,基本可行解就是可行域的顶点,-------------------,基本可行解代入目标函数值,AX=b,,B X,B,+ N X,N,= b,,X,B,= B,-1,b - B,-1,N X,N,,相应的目标函数值：,Z= CX = C,B,X,B,+ C,N,X,N,,,= C,B,(B,-1,b - B,-1,N X,N,),,+ C,N,X,N,,= C,B,B,-1,b +( C,N,- C,B,B,-1,N) X,N,,＋,0 X,B,目标函数值中非基变量

20、,X,N,的系数,,C,N,- C,B,B,-1,N) X,N,有几种情况,,Z=54-3X1-5X4,,Z=39+X3-4X5+8X6,目标函数值中非基变量,X,N,的系数,,C,N,- C,B,B,-1,N) X,N,有检验作用，叫检验数,( C,N,- C,B,B,-1,N),是非基变量检验数,,如果 非基变量,X,N,,＝,0,,则,Z,,= C,B,B,-1,b,X,B,,X,B,,基变量,,X,N,,非基变,量,,B,-1,b,,基解,,,,,,,,,,,,目标函数中基变量系数,0,,目标函数中非基变量系数,,C,N,- C,B,B,-1,N,,目标值相反数,,－,C,B,B,-1

21、,b,,技术矩阵,A,中基变量系数,B,技术矩阵,A,中,,非基变量系数,N,X,B,,X,B,,基变量,,X,N,,非基变,量,,B,-1,b,,基解,,,,,,,,,,,,目标函数中基变量系数,0,,目标函数中非基变量系数,,C,N,- C,B,B,-1,N,,目标值相反数,,－,C,B,B,-1,b,,技术矩阵,A,中基变量系数,B,技术矩阵,A,中,,非基变量系数,N,如果,B=I,单位矩阵，那么直接可以看出一个基本可行解,=,顶点,检验数可以判别是否最优解,例,,,Max,z,= 1500,x,1,,+ 2500,x,2,,s.t. 3,x,1,,+ 2,x,2,,+,x,3,=

22、65,,2,x,1,,+,x,2,,+,x,4,= 40,,3,x,2,,+,x,5,,= 75,,,x,1,, x,2,, x,3,, x,4,, x,5,,≥ 0,,,注意，线性规划的基本解、基本可行,,解（极点）和可行基只与线性规划问,,题标准形式的约束条件有关。,理解线性规划基本定理,第一章：线性规划（,2,）,,3 2 1 0 0,,A,= [,P1 ,P2 ,P3 ,P4 ,P5,] =,2 1 0 1 0,,0 3 0 0 1,,,A,矩阵包含以下,10,个,3×3,的子矩阵：,,,B,1,=[,p,1,，,p,2,，,p,3,],B,2,=[,p,1,，,p,2,，

23、,p,4,],,,B,3,=[,p,1,，,p,2,，,p,5,],B,4,=[,p,1,，,p,3,，,p,4,],,,B,5,=[,p,1,，,p,3,，,p,5,],B,6,=[,p,1,，,p,4,，,p,5,],,,B,7,=[,p,2,，,p,3,，,p,4,],B,8,=[,p,2,，,p,3,，,p,5,],,,B,9,=[,p,2,，,p,4,，,p,5,],B,10,=[,p,3,，,p,4,，,p,5,],,,,第一章：线性规划（,2,）,其中,,B,4,,= 0,，因而,B,4,不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有,9,个基。,,对于基,B,3

24、,=[,p,1,，,p,2,，,p,5,],，令非基变量,x,3,,= 0,，,x,4,= 0,，在等式约束中令,x,3,= 0,，,x,4,,= 0,，解线性方程组：,,,3,x,1,,+ 2,x,2,,+ 0,x,5,,= 65,,2,x,1,,+,x,2,,+ 0,x,5,,= 40,,0,x,1,,+ 3,x,2,,+,x,5,,= 75,,,得到,x,1,,=15,，,x,2,,= 10,，,x,5,= 45,，对应的基本可行解：,,,x,=(,x,1,，,x,2,，,x,3,，,x,4,，,x,5,),T,=(15,，,10,，,0,，,0,，,45),T,。于是对应的基,B,3,

25、是一个可行基。,第一章：线性规划（,2,）,类似可得到,,,x,(2),= (5,25,0,5,0),T,（对应,B,2,）,,,x,(7),= (20,0,5,0,75),T,（对应,B,5,）,,,x,(8),= (0,25,15,15,0),T,（对应,B,7,）,,,x,(9),= (0,0,65,40,75),T,（对应,B,10,）,,是,基本可行解,；,,而,x,(3),= (0,32.5,0,7.5,-22.5),T,（对应,B,9,）,,,x,(4),= (65/3,0,0,-10/3,75),T,（对应,B,6,）,,,x,(5),= (7.5,25,-7.5,0,0),T

26、,（对应,B,1,）,,,x,(6),= (0,40,-15,0,-45),T,（对应,B,8,）,,是,基本解,。,第一章：线性规划（,2,）,因此，对应基本可行解（极点） 的,B,2,,B,3,,B,5,B,7,,B,10,都是可行基。,,这里指出了一种求解线性规划问题的可能途径，就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的（最多个），因此必定可以从有限个基本可行解中找到最优解。,,,第一章：线性规划（,2,）,利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解

27、，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。,,,求解线性规划的单纯形法,第一章：线性规划（,2,）,求解线性规划的单纯形法,初始基本可行解,是否最优解或,,无限最优解,?,结束,沿边界找新,,的基本可行解,N,Y,从几何图解法猜想,：,LP,最优解是可行域的顶点之一,现在从代数上看可行域的点的特点,,可行域的点就是满足约束条件的点，因此从约束条件出发,,AX=b,,B X,B,+ N X,N,= b,,X,B,= B,-1,b - B,-1,N X,N,,相应的目标函数值：,Z= CX = C,B,X,B,+ C,N,X,N,

28、,,= C,B,(B,-1,b - B,-1,N X,N,),,+ C,N,X,N,,= C,B,B,-1,b +( C,N,- C,B,B,-1,N) X,N,,＋,0 X,B,,如果,X,N,= 0,，,X,B,= B,-1,b,，,,相应的目标函数值：,Z= C,B,B,-1,b,，这个解不一定满足非负。,,如果,X,B,= B,-1,b >= 0,,那么,X,B,= B,-1,b,，,X,N,= 0,是可行解，也就是可行域的点,,重要结论：,如果,X,B,= B,-1,b >= 0,,那么,X,B,= B,-1,b,，,X,N,= 0,不仅是可行域的点， 而且是可行域的顶点。,第

29、一章：线性规划（,2,）,例：用单纯形法的基本思路解线性规划问题,,,,,Max,z,= 1500,x,1,,+ 2500,x,2,,,,s.t. 3,x,1,,+ 2,x,2,,+,x,3,,= 65,,2,x,1,,+,x,2,,+,x,4,= 40,,3,x,2,,+,x,5,,= 75,,,x,1,, x,2,, x,3,, x,4,, x,5,,≥ 0,第一章：线性规划（,2,）,第一次迭代：,,（,1,）取初始可行基,B,10,= (,p,3,, p,4,, p,5,),，那么,x,3,，,x,4,，,x,5,为基变量，,x,1,，,x,2,为非基变量。将基变量和目标函数用非

30、基变量表示：,,,z,=1500,x,1,+2500,x,2,,,,x,3,= 65 - 3,x,1,,- 2,x,2,,,,,x,4,= 40 - 2,x,1,,-,x,2,,,,,x,5,= 75 - 3,x,2,,当非基变量,x,1,，,x,2,=0,时，相应的基变量和目标函数值为,x,3,=65,，,x,4,=40,，,x,5,= 75,，,z,= 0,，得到当前的基本可行解：,,x,=(0,0,65,40,75),T,，,z,= 0,。,第一章：线性规划（,2,）,（,2,）选择进基变量。在目标函数,,z,,= 1500,x,1,,+ 2500,x,2,中，非基变量,x,1,，,x,

31、2,的系数都是正数，因此,x,1,，,x,2,进基都可以使目标函数,z,增大，但,x,2,的系数为,2500,，绝对值比,x,1,的系数,1500,大，因此把,x,2,作为进基变量可以使目标函数,z,增加更快。选择,x,2,为进基变量，使,x,2,的值从,0,开始增加，另一个非基变量,x,1,保持零值不变。,第一章：线性规划（,2,）,（,3,）确定出基变量。在约束条件,,,x,3,= 65 - 3,x,1,,- 2,x,2,,,,,x,4,= 40 - 2,x,1,,-,x,2,,,,,x,5,= 75 - 3,x,2,,中，由于进基变量,x,2,在,3,个约束条件中的系数都是负数，当,x,

32、2,的值从,0,开始增加时，基变量,x,3,、,x,4,、,x,5,的值分别从当前的值,65,、,40,和,75,开始减少，当,x,2,增加到,25,时，,x,5,首先下降为,0,成为非基变量。这时，新的基变量为,x,3,、,x,4,、,x,2,，,新的非基变量为,x,1,、,x,5,，,当前的基本可行解和目标函数值为：,,x,= (0,，,25,，,15,，,15,，,0),T,，,z,= 62500,。,第一章：线性规划（,2,）,第二次迭代：,,（,1,）当前的可行基为,B,7,= (,p,2,, p,3,,,,p,4,),，那么,x,2,，,x,3,，,x,4,为基变量，,x,1,，,

33、x,5,为非基变量。将基变量和目标函数用非基变量表示：,,z,= 62500 + 1500,x,1,,– (2500/3),x,5,,,x,2,= 25 – (1/3),x,5,,x,3,= 15 - 3,x,1,,+ (2/3),x,5,,,x,4,= 15 - 2,x,1,,+ (1/3),x,5,,,,,第一章：线性规划（,2,）,（,2,）选择进基变量。在目标函数,,z,= 62500 + 1500,x,1,,– (2500/3),x,5,,中，非基变量,x,1,的系数是正数，因此,x,1,进基可以使目标函数,z,增大，于是选择,x,1,进基，使,x,1,的值从,0,开始增加,,,另一

34、个非基变量,x,5,保持零值不变。,,,(3),确定出基变量。,,x,2,= 25 – (1/3),x,5,,x,3,= 15 - 3,x,1,,+ (2/3),x,5,,,,x,4,= 15 - 2,x,1,,+ (1/3),x,5,,第一章：线性规划（,2,）,在约束条件,中，由于进基变量,x,1,在两个约束条件中的系数都是负数，当,x,1,的值从,0,开始增加时，基变量,x,3,、,x,4,的值分别从当前的值,15,、,15,开始减少，当,x,1,增加到,5,时，,x,3,首先下降为,0,成为非基变量。这时，新的基变量为,x,1,、,x,2,、,x,4,，新的非基变量为,x,3,、,x,

35、5,，,当前的基本可行解和目标函数值为：,,x,= (5,，,25,，,0,，,5,，,0),T,，,z,= 70000,。,,第三次迭代：,,（,1,）当前的可行基为,B,2,= (,p,1,,,p,2,, p,4,),，那么,x,1,，,x,2,，,x,4,为基变量，,x,3,，,x,5,为非基变量。将基变量和目标函数用非基变量表示：,,z,= 70000 – 500,x,3,– 500,x,5,,x,1,= 5 – (1/3),x,3,,+ (2/9),x,5,,,,x,2,= 25 – (1/3),x,5,,x,4,= 5 + (2/3),x,3,,– (1/9),x,5,,,第一章：

36、线性规划（,2,）,（,2,）选择进基变量。在目标函数,,z,= 70000 – 500,x,3,– 500,x,5,,中，非基变量,x,3,、,x,5,的系数均不是正数，因此进基都不可能使目标函数,z,增大，于是得到最优解，,x,*,= (5,，,25,，,0,，,5,，,0),T,，最优目标值为,z,* = 70000,。我们也称相应的基,B,2,= (,p,1,,,p,2,,,p,4,),为,最优基,。计算结束。,,,以下定义结合上面讲的图解法理解,（对应可行域的顶点,）,,基,,设标准形式线性规划的约束方程组为,AX=b,。若,B,是系数矩阵,A,的,m,阶满秩子矩阵，则称,B,是线性

37、规划问题的一个基。,B,中的每一个列向量称为基向量，共,m,个，与基向量对应的变量称为基变量。,B,以外的列向量称为非基向量，,共（,n,－,m,）个,,,对应的变量称为非基变量。,,基解,在标准形式线性规划的约束方程组中，对应基,B,，令所有非基变量都等于零，求解约束方程组,AX=b,，可惟一得出基变量的一组值，这些值和取零的非基变量的值合起来，称为线性规划问题的基解或基本解。,,基的个数不超过从,n,中取,m,的组合数 ，一个基对应一个基解，故基解的个数也不超过从,n,中取,m,的组合数 。基解中非零分量的个数不会大于约束方程的个数,m,。若一个基解的基变量中有取零值的，则此基解称为退化

38、的，否则称为非退化的。,,基可行解,对于标准形式的线性规划，如果一个基解,X,还满足变量取值非负性的约束条件,X≥0,，则称此基解为基可行解或基本可行解。,,最优基,如果一个基可先行解是最优解，则它所对应的可行基叫做最优基。,,第一章：线性规划（,1,）,根据下图，具体给出,,可行域，,ABFHE,（阴影部分）,,基可行解：点,A,，,B,，,F,，,H,，,E,（可行,=,非负）,,基解：全部基可行解,+,点,D,，,C,，,I,，,J,，,G,,,,,,,,,,,A,B,C,D,E,F,G,H,I,J,,思路：几何－顶点（计算机不可识别）－,,如何用计算机可以识别的代数方法找到顶点,下面讲

39、的单纯形法求解过程本质是从可行域的一个顶点转到另一个顶点,,单纯形法与,George Dantzig,加州大学大二学生创新,,（,90,岁）,,AX=b,,B X,B,+ N X,N,= b,,X,B,= B,-1,b - B,-1,N X,N,,Z= CX = C,B,X,B,+ C,N,X,N,,,= C,B,(B,-1,b - B,-1,N X,N,),,+ C,N,X,N,,= C,B,B,-1,b +( C,N,- C,B,B,-1,N) X,N,,＋,0 X,B,,如果,X,N,= 0,，,X,B,= B,-1,b,,Z= C,B,B,-1,b,,如果,X,B,= B,-1,b

40、>= 0,,那么,X,B,= B,-1,b,，,X,N,= 0,是可行解,代数方法,基,B,非基,N,我们想知道满足约束条件的点有什么特点 ，因此从约束方程出发,第一章：线性规划（,2,）,Max 2X,1,+3X,2,,X,1,+ 2X,2,<= 8,,4X,1,<=16,,4X,2,<=12,,X,1,>=0,,X,2,>=0,,加入松驰变量,X,3,,，,X,4,,，,X,5,,变成等式约束,,Max 2X,1,+3X,2,+0X,3,+0X,4,+0X,5,,X,1,+ 2X,2,+ X,3,= 8,,4X,1,+ X,4,=16,,4X,2,+X,5,=12,,X,1,>=0 X

41、,2,>=0 X,3,>=0 X,4,>=0 X,5,>=0,,1 2,1 0 0,,,4 0,0 1 0,,0 4,0 0 1,,A=,,X,B,=,,,X,3,,X,4,X,5,,,1 2,,,4 0,,0 4,,N=,,X,N,=,,,X,1,,X,2,,第一章：线性规划（,2,）,Max 2X,1,+3X,2,,X,1,+ 2X,2,<= 8,,4X,1,<=16,,4X,2,<=12,,X,1,>=0,,X,2,>=0,,加入松驰变量,X,3,,，,X,4,,，,X,5,,变成等式约束,,Max 2X,1,+3X,2,+0X,3,+0X,4,+0X,5,

42、,X,1,+ 2X,2,+ X,3,= 8,,4X,1,+ X,4,=16,,4X,2,+X,5,=12,,X,1,>=0 X,2,>=0 X,3,>=0 X,4,>=0 X,5,>=0,,基变量,X,3,，,X,4,，,X,5,,令非基变量取零值，得,：,,,,X,3,= 8,－,2X,2,－,X,1,,+ X,4,=16,－,4X,1,,+X,5,=12,－,4X,2,,如果令非基变量取零值，得：,,,,X,3,= 8,,+ X,4,=16,,+X,5,=12,,第一个可行解， 对应利润为零， 显然不是最优解，,在,X,1,,，,X,2,,平面上对应的可行域的顶点是 （,0,，,0,）,

43、第一章：线性规划（,2,）,代数求解,,1,经济上分析,,2,几何图形上分析,,3,表上分析,,如何寻找下一个可行域的顶点？显然我们希望把,利润比较高,的第,2,种产品尽可能多地生产,,,我们看，,,,X,3,= 8,－,2X,2,－,X,1,>=0,得：,,如果,X,1,= 0,，则,X,2,<= 4,,如果,X,2,= 0,，则,X,1,<= 8,,+ X,4,=16,－,4X,1,>=0,得,X,1,<= 4,,+X,5,=12,－,4X,2,>=0,得,X,2,<= 3,,就是说：产品,1,最大产量为,4,；这时原材料,A,用完，（,X,1,<= 8,，并且,X,1,<= 4,）；产品

44、,2,最大产量为,3,；这时原材料,B,用完 （,X,2,<= 4,，并且,X,2,<= 3,）；由于产品,2,的单位利润大于产品,1,的单位利润，因此我们首先考虑尽可能多地生产产品,2,，,X,2,= 3,变成基变量， 这时,X,5,= 0,，变成非基变量。,第一章：线性规划（,2,）,,,2,3,0,0,0,,,C,B,基变量,X,1,X,2,X,3,X,4,X,5,B,-1,b,,0,X,3,1,2,1,0,0,8,8/2,0,X,4,4,0,0,1,0,16,,0,X,5,0,4,0,0,1,12,12/4,,,2,3,0,0,0,,,第,1,张单纯形 表：,检验数,( C,N,-

45、C,B,B,-1,N) =,（,2 3,）,-,（,0 0 0,）,=,（,2 3,）,1,2,4,0,0,4,N,是,A,中去掉单位矩阵,第一章：线性规划（,2,）,,5,分钟练习：如何得到第,1,张单纯形 表：,,Max 5X,1,- 2X,2,,s.t. 4X,1,+ 7X,2,<= 18,,2X,1,- 3X,2,<=22,,X,1,>=0,,X,2,>=0,,检验数,( C,N,- C,B,B,-1,N) =,我们希望把上面分析放在表中： 表的结构,第一章：线性规划（,2,）,生产各种产品产生的利润，选择利润最大者,基变量,,X,1,,X,2,,X,3,,X,4,,X,5,

46、,B,-1,b,,,,X,3,,1,,2,,1,,0,,0,,8,,8÷2,,X,4,,4,,0,,0,,1,,0,,16,,,,X,5,,0,,4,,0,,0,,1,,12,,12÷4,,,2,,3,,0,,0,,0,,0,,,,生产第,2,种产品，受第,3,种资源约束的最大生产量,总资源约束,单位产品的资源数量,上面分析放在表内：,,基变量,,X,1,,X,2,,X,3,,X,4,,X,5,,B,-1,b,,X,3,,1,,2,,1,,0,,0,,8,,X,4,,4,,0,,0,,1,,0,,16,,X,5,,0,,4,,0,,0,,1,,12,,,,2,,3,,0,,0,,0,,0,,检

47、验数,:,经济含义 正中取大（相应产品产生的利润最大）,,2,,3,,0,,0,,0,,0,,1,,0,,0,,0,,1,,0,,0,,0,,1,,基：,第一章：线性规划（,2,）,X,5,,X,5,,X,5,,X,5,,X,5,,X,5,,基变量,,X,1,,X,2,,X,3,,X,4,,X,5,,B,-1,b,,,,X,3,,1,,2,,1,,0,,0,,8,,8÷2,,X,4,,4,,0,,0,,1,,0,,16,,,,X,5,,0,,4,,0,,0,,1,,12,,12÷4,,检验数,,2,,3,,0,,0,,0,,0,,,,,转轴元：,,确定先订列 检验数正中取大（相应产品利润最大

48、）,,再定行相除后正中取小（相应资源约束最厉害 总资源,/,单位产品消耗资源）,第一章：线性规划（,2,）,基变量,,X,1,,X,2,,X,3,,X,4,,X,5,,B,-1,b,,,,X,3,,1,,2,,1,,0,,0,,8,,8÷2,,X,4,,4,,0,,0,,1,,0,,16,,,,X,5,,0,,4,,0,,0,,1,,12,,12÷4,,检验数,,2,,3,,0,,0,,0,,0,,,,,转轴的代数意义：,,把转轴元变成,1,：表示解出基变量,X,2,,把这一列的检验数变成,0,：表示把基变量,X,2,代入目标函数（加减消元方法）,,把这一列的其他系数变成,0

49、,：表示基变量,X,2,代入其他方程（加减消元方法）,,把转轴元所在方程的多少倍加到另外一个方程实现,加减消元,第一章：线性规划（,2,）,再看完整的一个例,,A.,图解法,:,,max Z=2X,1,+X,2,,3X,1,+5X,2,<=15,,6X,1,+2X,2,<=24,,X,1,,X,2,>=0,,∴,由右图知,,,在,G,2,点能得到最优解,,,,其中,G,2,点坐标,(15/4,3/4),,max Z=33/4,,第一章：线性规划（,2,）,3X,1,+5X,2,= 15,6X,1,+2X,2,= 24,,,,,,,,,,,,,,,,,,,,G,2,B.,单纯形法,:,,Max

50、Z=2X,1,+X,2,+0X,3,+0X,4,,3X,1,+5X,2,+X,3,=15,,6X,1,+2X,2,+X,4,=24,,X,1,,X,2,,X,3,,X,4,>=0,,,其初始单纯形表为,,,C,i,,2,,1,,0,,0,,,,,,C,B,,,X,B,,,X,1,,X,2,,X,3,,X,4,,B,-1,b,,Θ,i,,0,,X,3,,3,,5,,1,,0,,15,,15/3,,0,,X,4,,6,,2,,0,,1,,24,,24/6,,检验数,,2,,1,,0,,0,,,,,,第一章：线性规划（,2,）,转轴元：,,3 5,1 0,,,6 2,0 1,,A=,,(

51、 C,N,- C,B,B,-1,N),,,=,（,2 1,）,-,（,0 0,）,,,=,,,N,B,3 5,,6 2,,,C,i,,2,,1,,0,,0,,,,,,C,B,,X,B,,,X,1,,X,2,,X,3,,X,4,,B,-1,b,,Θ,i,,0,,X,3,,0,,[4],,1,,-1/2,,3,,3/4,,2,,X,1,,1,,1/3,,0,,1/6,,4,,12,,检验数,,0,,1/3,,0,,-1/3,,-8,,,,于是得到新的基可行解,X(1)=(4,0,3,0),-T,,,此时,Z=8,,相当于图形上,G,3,;,将上表,X,2,替换,X,3,得,：,第一章：线性规

52、划（,2,）,下一步： 把转轴元相应列变为单位向量,,,C,i,,2,,1,,0,,0,,,,C,B,,X,B,,X,1,,X,2,,X,3,,X,4,,B,-1,b,,1,,,X,2,,0,,1,,1/4,,-1/8,,3/4,,2,,,X,1,,1,,0,,-1/12,,5/24,,15/4,,检验数,,0,,0,,-1/12,,-7/24,,-33/4,,所有检验数,<=0, ∴,得到最优解下,X(2)=(15/4,3/4,0,0),T,,,此时,,max Z=33/4,,相当于图形上的,G,2,点,.,,第一章：线性规划（,2,）,,,单纯形法求解过程及其经济含意,,单纯形法求解过程

53、本质是从可行域的一个顶点转到另一个顶点,,确定转轴元 先订列 检验数正中取大（相应产品利润最大）,,再定行 相除后正中取小（相应资源约束最厉害）,,,思路：几何－顶点（计算机不可识别）－代数－基解（计算机可识别）,,基－－,----------- -,基解－－,-----------,基可行解,,,A=(B, N) X,非负,,AX=b,,B X,B,+ N X,N,= b,,X,B,= B,-1,b - B,-1,N X,N,,Z= CX = C,B,X,B,+ C,N,X,N,,,= C,B,(B,-1,b - B,-1,N X,N,),,+ C,N,X,N,,=

54、 C,B,B,-1,b +( C,N,- C,B,B,-1,N) X,N,,＋,0 X,B,第一章：线性规划（,2,）,( C,N,- C,B,B,-1,N),是非基变量检验数,,如果 非基变量,X,N,,＝,0,,则,Z,,= C,B,B,-1,b,X,B,,X,B,,基变量,,X,N,,非基变,量,,B,-1,b,,基解,,,,,,,,,,,,目标函数中基变量系数,0,,目标函数中非基变量系数,,C,N,- C,B,B,-1,N,,目标值相反数,,－,C,B,B,-1,b,,第一章：线性规划（,2,）,3,．,单纯形法计算的实质就是用矩阵的初等行变换求解约束方组,AX,=,b,，但求出的是

55、基本解，这与线性代数中解方程组不同。另外，用单纯形法求出的这个基本解还是可行解，这由初始单纯形表对应的问题的标准形式以及最小比值原则加以保证，而且单纯形法的迭代计算还能保证后面得到的基可行解比前面的好（即使目标函数值越来越大），这缘于选换入变量时是选其检验数为正数的变量。这些技巧，是通常线性代数中线性方程组的理论方法中所未涉及的，也正是单纯形法的独特贡献。,,【,例,】,线性规划问题是否可算作条件极值问题，它与微积分中讲的条件极值问题有何不同？解：线性规划问题也可以看成是条件极值问题，即要在满足所有约束的条件下，求目标函数的极值。它与微积分中讲到的条件极值是不同的：,,（,1,）它的约束条件中

56、可以有,不等式约束,，而后者的限制条件都是等式；（,2,）   它的,约束条件的个数,一般地都多于变量的个数，而后者恰恰相反；（,3,）   它的目标函数与约束条件都是,线性的,，而后者不必如此。,,,第一章：线性规划（,2,）,,,,,,,,,,运筹学,线性规划（,3,）,第一章：线性规划（,3,）,,一 如何从单纯形表判断线性规划解各种类型,,二 人工变量法求线性规划的初始可行基,：,第一章：线性规划（,3,）,一 已知几何图形上判断线性规划解各种类型。,,,如何从单纯形表判断线性规划解各种类型,?,第一章：线性规划（,3,）,,第一章：线性规划（,3,）,基变量,,基,X,1,,基,X,

57、2,,非基,X,3,,基,X,4,,非基,X,5,,B,-1,b,,,,X,2,,,,,,,,,,,,＋,,,,X,1,,,,,,,,,,,,＋,,,,X,4,,,,,,,,,,,,＋,,,,检验数,,0,,0,,负,,0,,负,,,,,,1,．唯一最优解,,第一章：线性规划（,3,）,基变量,,基,X,1,,基,X,2,,非基,X,3,,基,X,4,,非基,X,5,,B,-1,b,,,,X,2,,,,,,0,,,,,,＋,,,,X,1,,,,,,负,,,,,,＋,,,,X,4,,,,,,负,,,,,,＋,,,,检验数,,0,,0,,正,,0,,负,,,,,,2,无界最优解：,,注意：这时找不

58、到“转轴元” 因为无法进行“再定行相除后正中取小”，,,非基,X,3,,产生利润而不消耗资源， 越多越好,,,X,5,,基变量,,X,1,,X,2,,X,3,,X,4,,X,5,,B,-1,b,,,,X,3,,1,,2,,1,,0,,0,,8,,8÷2,,X,4,,4,,0,,0,,1,,0,,16,,,,0,,4,,0,,0,,1,,12,,12÷4,,检验数,,2,,3,,0,,0,,0,,0,,,,X,5,,基变量,,X,1,,X,2,,X,3,,X,4,,X,5,,B,-1,b,,,,X,3,,1,,2,,1,,0,,0,,8,,8÷2,,X,4,,4,,0,,0,,1,,0,,16

59、,,,,0,,4,,0,,0,,1,,12,,12÷4,,检验数,,2,,3,,0,,0,,0,,0,,,,X,5,,基变量,,X,1,,X,2,,X,3,,X,4,,X,5,,B,-1,b,,,,X,3,,1,,2,,1,,0,,0,,8,,8÷2,,X,4,,4,,0,,0,,1,,0,,16,,,,0,,4,,0,,0,,1,,12,,12÷4,,检验数,,2,,3,,0,,0,,0,,0,,,,X,5,,基变量,,X,1,,X,2,,X,3,,X,4,,X,5,,B,-1,b,,,,X,3,,1,,2,,1,,0,,0,,8,,8÷2,,X,4,,4,,0,,0,,1,,0,,16,,

60、,,0,,4,,0,,0,,1,,12,,12÷4,,检验数,,2,,3,,0,,0,,0,,0,,,,X,5,,基变量,,X,1,,X,2,,X,3,,X,4,,X,5,,B,-1,b,,,,X,3,,1,,2,,1,,0,,0,,8,,8÷2,,X,4,,4,,0,,0,,1,,0,,16,,,,0,,4,,0,,0,,1,,12,,12÷4,,检验数,,2,,3,,0,,0,,0,,0,,,,X,5,,基变量,,X,1,,X,2,,X,3,,X,4,,X,5,,B,-1,b,,,,X,3,,1,,2,,1,,0,,0,,8,,8÷2,,X,4,,4,,0,,0,,1,,0,,16,,,,

61、0,,4,,0,,0,,1,,12,,12÷4,,检验数,,2,,3,,0,,0,,0,,0,,,,第一章：线性规划（,3,）,基变量,,基,X,1,,基,X,2,,非基,X,3,,基,X,4,,非基,X,5,,B,-1,b,,,,X,2,,,,,,,,,,,,＋,,,,X,1,,,,,,,,,,,,＋,,,,X,4,,,,,,,,,,,,＋,,,,检验数,,0,,0,,0,,0,,负,,,,,,利润,Z = 0(,非基,X,3,)+,负,(,非基,X,5,),,这时,非基,X,3,取任何值，,都不改变目标函数的值，,因此有无穷最优解,3,无穷最优解：,第一章：线性规划（,3,）,基变量,,基

62、,X,1,,基,X,2,,非基,X,3,基,X,4,,非基,X,5,,B,-1,b,,,,X,2,,,0,,,1,,,2,,,0,,5,,4,,,,X,1,,,1,,0,,,4,,,0,,,1,,5,,,,X,4,,,0,,,0,,,-3,,1,,,0,,1,,,,检验数,,0,,0,,D,,0,,- 8,,,-9,,,,D>0,,表示,,D=0,，表示,,D<0,，表示,第一章：线性规划（,3,）,基变量,,基,X,1,,基,X,2,,非基,X,3,基,X,4,,非基,X,5,,B,-1,b,,,,X,2,,,0,,,1,,,a,,,0,,5,,4,,,,X,1,,,1,,0,,,-4,,,

63、0,,,1,,5,,,,X,4,,,0,,,0,,,-3,,1,,,0,,1,,,,检验数,,0,,0,,D,,0,,- 8,,,-9,,,,当,a>0,时：,,D>0,,表示 转元是,a,,D=0,，表示 无穷个最优解,,D<0,，表示 最优解达到,当,a <0,时：,,D>0,,表示 无限大,最优解,,,思路：我们从几何图解法－知道关注顶点,,单纯形法求解过程本质是从可行域的一个顶点转到另一个顶点，,如何找到第一个顶点？,实际第一个顶点对应,A,中包括的一个单位矩阵,Max Z=2X,1,+X,2,+0X,3,+0X,4,,3X,1,+5X,2,+X,3,=15,,6X,1,+2X

64、,2,+X,4,=24,,X,1,,X,2,,X,3,,X,4,>=0,,,,3 5,,1 0,,,6 2,,0 1,,A=,,=,,,N,B,引入松弛变量后，,A,中包括的一个单位矩阵,问题： 如果,A,中不包括单位矩阵，怎么办,第一章：线性规划（,3,）,例,8 P32,,1   min Z=-3 X,1,+X,2,+X,3,,X,1,-2X,2,+ X,3,<=11,,-4X,1,+X,2,+ 2X,3,>=3,,-2X,1,+ X,3,=1,,X,1,,X,2,,X,3,>=0,第一章：线性规划（,3,）,问题： 下面例,A,中不包括单位矩阵，怎么办,Min Z=

65、 -3X,1,+X,2,+X,3,+0X,4,+0X,5,,X,1,-2X,2,+ X,3,+ X,4,=11,,-4X,1,+X,2,+ 2X,3,-X,5,=3,,-2X,1,+ X,3,=1,,X,1,,X,2,,X,3,>=0,,X,i,>=0,i =1,2,…,5,,1 -2,1 1 0,,,-4 1,2 0 -1,,,-2 0 1 0 0,,A=,,例,8 P32,,1   min Z=-3 X,1,+X,2,+X,3,,X,1,-2X,2,+ X,3,<=11,,-4X,1,+X,2,+ 2X,3,>=3,,-2X,1

66、,+ X,3,=1,,X,1,,X,2,,X,3,>=0,第一章：线性规划（,3,）,解决方法： 一定让,A,中包括单位矩阵！,,,X,1,-2X,2,+ X,3,+ X,4,=11,,-4X,1,+X,2,+ 2X,3,-X,5,+ X,6,=3,,-2X,1,+ X,3,+ X,7,=1,,X,1,,X,2,,X,3,>=0,,,X,i,>=0,i =1,2,…,7,,1 -2,1,1,0,0 0,,,-4 1,2,0,-1,1 0,,,-2 0 1,0,0,0 1,,A=,,等式中再加入的变量叫人工变量，它必须为,0,，否则原来约束条件不成立！,二,,,人工变量法求线性规划的初始可行基：,,目的：求初始可行基,,原理：人工变量的成本无穷大,,1,,大,M,法,,2,,二阶段法,,原理：,,要点：,,第一阶段：首先加入人工变量,,新的目标函数改变为：,,min,人工变量 （原来变量的成本为零）,,用单纯形表求解,,第二阶段：将第一阶段最终单纯形表除去人工变量,,新的目标函数＝原来的目标函数,第一章：线性规划（,3,）,第一章：线性规划（,3,）,二,,,人工变