资源描述
,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,运筹学 熊中楷 教授,/,博士生导师,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,运筹学,重庆大学 经济与工商管理学院,熊中楷 教授,/,博士生导师,联系方式：,023-65111708 bearelm,1,个人介绍：,顶级斯坦福大学,顶级伯克利大学,著名约克大学,著名俄亥俄大学,著名俄亥俄大学,下乡种地,山区犁田,改变命运靠运筹,一 本章内容：,1,线性规划的引例，标准形式,2,线性规划图解法,3,线性规划单纯形方法（代数方法和表格方法）,4,线性规划的应用（建立模型）,二 教学目的：,掌握线性规划的引例，标准形式和几种解法的原理,三 本章重点：,几种解法和线性规划的应用（建立模型）,四 本章难点：,单纯形方法（代数方法和表格方法）,五 计划学时：,12,学时,第一章：线性规划,甲产品,乙产品,资源量,设备,1,2,8,台时,原材料,A,4,0,16,公斤,原材料,B,0,4,12,公斤,产生的收益,2,元,3,元,问题：如何计划使得工厂利润最大？,分析：决策中的关键变量是什么？变量中的相互因果关系是什么？,怎样用数学公式来建立有用的模型？,第一章：线性规划（,1,）,第一章 线性规划及单纯形法,1.1,一般线性规划问题的数学模型,典,型引例： 某工厂在计划期内安排甲，乙两种产品，已知生产单位产品所消耗资源以及产生的利润如下表：,思路：收益最大,资源有约束,Max 2X,1,+3X,2,X,1,+ 2X,2,= 8,4X,1,=16,4X,2,=0,X,2,=0,第一章：线性规划（,1,）,一般形式,Max CX,AX=0,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,线性规划的解的相关定义,可行解,满足线性规划所有约束条件的各变量的一组值,X=,（,x,1,，,x,2,，,，,x,n,）,T,，称为线性规划问题的可行解。全部可行解的集合称为可行域。,最优解,使线性规划的目标函数达到以最优值（依照具体问题，或者是极大值，或者是极小值）的可行解称为线性规划问题的最优解。,上述两个概念，对于一般形式、标准形式都适用，而下述五个概念，仅适用于标准形式。,第一章：线性规划（,1,）,图解法,引例：,目标函数：,MAX Z= X,1,+,3X,2,满足的 约束条件：,5 X,1,+10 X,2,=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,）,从图解法猜想,:,LP,最优解是可行域的顶点之一,因此，我们更关注可行域的顶点（有限个）,图解法,基本要求,能正确地按图解法的步骤画出图来解答题目，并会判定解的类型。,知识要点,（,1,）图解法仅适用于两个变量的线性规划问题，求解时按原来题目对目标函数的优化要求去求解即可，不必将求极小值化为求极大值。,三个变量的线性规划问题用图解法求解时，可行域是三维空间的多面体，很难用平面上的图形画得清晰准确，目标函数对应的是三维空间中的平面，难以通过平面上画出的立体图形求出最优解。所以，从理论上讲，三个变量的线性规划也有图解法，但实际上不可行。多于三个变量的线性规划涉及到在高于三维的向量空间中求解优化问题，而三维以上的空间已无直观的几何意义，故不存在相应的图解法。,（,2,）线性规划问题的解的情况共有四种：,（,3,）线性规划问题如果有最优解，则可行域的某个顶点必定是最优解。为求最优解，可以先计算可行域某个顶点处的目标函数值，再考察它周围相邻顶点的目标函数值是否比这个值更优，如果为否，则该顶点就是最优解（或最优解之一），否则转到比这个点的目标函数值更优的另一顶点，重复上述过程，直到找出对应最优解的顶点。,第一章：线性规划（,1,）,已知几何图形上判断线性规划解各种类型。,从图解法猜想,LP,最优解是可行域的顶点之一,运筹学,线性规划（,2,）,.,线性规划问题的解的基本概念,对于标准型,LP,问题,可行解：,满足约束条件的解称为可行解。,基：,A,中任何一组,m,个线性无关的列向量构成的子矩阵,称为该问题的一个基（,basis,）,与中的这些列向量对应的变量称为基变量（,basic variable,）,研究思路： 几何图形的点,-,对应代数式子,可行域的点有什么特点？,可行域的点就是满足约束条件的点，因此从约束条件出发,最优解：,若基本可行解又是最优解（也称基本最优解），这个基就称为最优基,（,optimal basis,）,基本解：,对于基,令非基变量为零,求得满足约束条件,(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,是基可行解，也就是可行域的点,重要结论：,如果,XB = B-1b = 0,那么,XB = B-1b,，,XN = 0,不仅是可行域的点,而且是可行域的顶点。,线性规划的基本理论,由图解法的步骤，可以从几何的角度得出以下两个猜想：,（,1,）线性规划问题的可行域是一个有界或无界的凸多边,形，其顶点个数是有限个。,（,2,）若线性规划问题有最优解，那么最优解一定可在可,行域的某个顶点上找到。,第一章：线性规划（,2,）,与猜想相关的几个基本概念,（,1,）凸集：设,k,是,n,维欧式空间的一个点集，若任意两点,X,(1),k, X,(2),k,的连线上的一切点,X,(1),+ (1-)X,(2),k,( 01),则称,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),，,X,(2),，,，,X,(k),的凸组合。,凸集,k,中任意两点,X,(1),，,X,(2),连线上的任一点,X,都是,X,(1),与,X,(2),的一个凸组合。,(3),顶点：设,k,为凸集，,Xk,若,X,不能用,X,(1),k,X,(2),k,两点的,一个凸组合表示为,X=X,(1),+ (1-)X,(2),其中,01,，,则称,X,为,k,的一个顶点。,与猜想相关的几个基本概念,第一章：线性规划（,2,）,定理,1,：若线性规划问题存在可行域，则其可行域,是一个凸集。,证明：为了证明满足,=,，,0,的所有点（可行解）组成的几何体是凸集，只要证明中任意两点任意两点连线上的一切点均满足线性约束条件既可。,任取，满足,则对任意的有,线性规划的基本定理,又因为均,0,，所以,由此可知，即是凸集。,第一章：线性规划（,2,）,证明：,必要性：,因为是基本解，由基本解的定义，的非零分量所对应的系数列向量线性无关，又因为是可行解，由基本可行解的定义，非零分量均是正的，所以的正分量所对应的系数列向量线性无关。,充分性,：设是线性规划问题的可行解，且正分量所对应的列向量也线性无关，则必有,km,若,k=m,，则,刚好构成一个基，为相应的基本可行解。若,k= 0,那么,X,B,= B,-1,b,，,X,N,= 0,是可行解，也就是可行域的点,重要结论：,如果,X,B,= B,-1,b = 0,那么,X,B,= B,-1,b,，,X,N,= 0,不仅是可行域的点， 而且是可行域的顶点。,第一章：线性规划（,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,为非基变量。将基变量和目标函数用非基变量表示：,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,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,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,，,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,开始增加,另一个非基变量,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,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,第一章：线性规划（,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,是线性规划问题的一个基。,B,中的每一个列向量称为基向量，共,m,个，与基向量对应的变量称为基变量。,B,以外的列向量称为非基向量，,共（,n,m,）个,对应的变量称为非基变量。,基解,在标准形式线性规划的约束方程组中，对应基,B,，令所有非基变量都等于零，求解约束方程组,AX=b,，可惟一得出基变量的一组值，这些值和取零的非基变量的值合起来，称为线性规划问题的基解或基本解。,基的个数不超过从,n,中取,m,的组合数 ，一个基对应一个基解，故基解的个数也不超过从,n,中取,m,的组合数 。基解中非零分量的个数不会大于约束方程的个数,m,。若一个基解的基变量中有取零值的，则此基解称为退化的，否则称为非退化的。,基可行解,对于标准形式的线性规划，如果一个基解,X,还满足变量取值非负性的约束条件,X0,，则称此基解为基可行解或基本可行解。,最优基,如果一个基可先行解是最优解，则它所对应的可行基叫做最优基。,第一章：线性规划（,1,）,根据下图，具体给出,可行域，,ABFHE,（阴影部分）,基可行解：点,A,，,B,，,F,，,H,，,E,（可行,=,非负）,基解：全部基可行解,+,点,D,，,C,，,I,，,J,，,G,A,B,C,D,E,F,G,H,I,J,思路：几何顶点（计算机不可识别）,如何用计算机可以识别的代数方法找到顶点,下面讲的单纯形法求解过程本质是从可行域的一个顶点转到另一个顶点,单纯形法与,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 = 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,=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,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,=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,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,）,第一章：线性规划（,2,）,代数求解,1,经济上分析,2,几何图形上分析,3,表上分析,如何寻找下一个可行域的顶点？显然我们希望把,利润比较高,的第,2,种产品尽可能多地生产,我们看，,X,3,= 8,2X,2,X,1,=0,得：,如果,X,1,= 0,，则,X,2,= 4,如果,X,2,= 0,，则,X,1,=0,得,X,1,=0,得,X,2,= 3,就是说：产品,1,最大产量为,4,；这时原材料,A,用完，（,X,1,= 8,，并且,X,1,= 4,）；产品,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,- 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,=0,X,2,=0,检验数,( C,N,- C,B,B,-1,N) =,我们希望把上面分析放在表中： 表的结构,第一章：线性规划（,2,）,生产各种产品产生的利润，选择利润最大者,基变量,X,1,X,2,X,3,X,4,X,5,B,-1,b,X,3,1,2,1,0,0,8,82,X,4,4,0,0,1,0,16,X,5,0,4,0,0,1,12,124,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,检验数,:,经济含义 正中取大（相应产品产生的利润最大）,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,82,X,4,4,0,0,1,0,16,X,5,0,4,0,0,1,12,124,检验数,2,3,0,0,0,0,转轴元：,确定先订列 检验数正中取大（相应产品利润最大）,再定行相除后正中取小（相应资源约束最厉害 总资源,/,单位产品消耗资源）,第一章：线性规划（,2,）,基变量,X,1,X,2,X,3,X,4,X,5,B,-1,b,X,3,1,2,1,0,0,8,82,X,4,4,0,0,1,0,16,X,5,0,4,0,0,1,12,124,检验数,2,3,0,0,0,0,转轴的代数意义：,把转轴元变成,1,：表示解出基变量,X,2,把这一列的检验数变成,0,：表示把基变量,X,2,代入目标函数（加减消元方法）,把这一列的其他系数变成,0,：表示基变量,X,2,代入其他方程（加减消元方法）,把转轴元所在方程的多少倍加到另外一个方程实现,加减消元,第一章：线性规划（,2,）,再看完整的一个例,A.,图解法,:,max Z=2X,1,+X,2,3X,1,+5X,2,=15,6X,1,+2X,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 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=,( 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,得,：,第一章：线性规划（,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,表示,D=0,，表示,D0,时：,D0,表示 转元是,a,D=0,，表示 无穷个最优解,D0,，表示 最优解达到,当,a 0,表示 无限大,最优解,思路：我们从几何图解法知道关注顶点,单纯形法求解过程本质是从可行域的一个顶点转到另一个顶点，,如何找到第一个顶点？,实际第一个顶点对应,A,中包括的一个单位矩阵,Max 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,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,=3,-2X,1,+ X,3,=1,X,1,X,2,X,3,=0,第一章：线性规划（,3,）,问题： 下面例,A,中不包括单位矩阵，怎么办,Min Z= -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,=3,-2X,1,+ 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,）,二,人工变
展开阅读全文