金融学院管理运筹学线性规划与单纯型法

管理运筹学线性规划与单纯型法第二讲由实践问题引出数学模形。产品A产品B资源限量劳动力设备原材料9434510360200300利润元/KG701201.确定决策变量:设消费A,B分别为x1,x22.确定目的函数:3.确定约束条件:一、LP问题的根本概念12/31/20233典型的LP问题:一、LP问题的根本概念12/31/20234用向量符号表示为:用向量和矩阵表示为:一、LP问题的根本概念12/31/202351.基、基向量、基变量、非基变量设A为约束方程组的m×n阶系数矩阵，其秩为m，B是A中的一个m阶满秩子矩阵，称B为LP问题的一个基。B中每一个列向量称为基向量，对于的变量xj为基变量，其他的变量称为非基变量。一、LP问题的根本概念12/31/202361.基、基向量、基变量、非基变量一、LP问题的根本概念12/31/20237满足约束方程(包括非负约束)的一切解，称为可行解。对于某组选定的基，令非基变量为0，与约束方程求得的独一解，称为基解。2.可行解、基解、基可行解、可行基一、LP问题的根本概念12/31/20238基解中满足一切变量非负约束的解，称为基可行解。2.可行解、基解、基可行解、可行基与基可行解对应的基称为可行基。一、LP问题的根本概念12/31/20239概念练习:找出以下LP问题的全部基解。1234512345一、LP问题的根本概念12/31/202310组合x1x2x3x4x5z基可行解？1-2001-3001-4001-5002-3002-4002-5003-4003-5004-50051045////55-120452175541010-5415////52.51.517.554-32224319

×

××××

一、LP问题的根本概念12/31/2023111.连线:二、重要定理与引理在n维Euclid空间中，点X与Y连线上的点，是指如下方式的点T:当α跑遍区间[0,1]时,相应的点T的集合就构成点X与Y之间的连线。12/31/2023122.凸集:一个由n维点所构成的集合K，假设对于K中恣意两点X,Y∈K，恒有:那么n维点集K称为凸集，即K中恣意两点的连线上的点也在K中。3.凸组合:假定有k个n维Euclid空间的点它们的凸组合是指如下方式的点X:特别，两个点X与Y的凸组合，叫做它们连线上的点。二、重要定理与引理12/31/2023134.顶点:设K是凸集，点X∈K；假设对K中任何两个不同的点X,Y，以下等式恒不成立:就称X为凸集K的顶点。换句话说，凸集的顶点，就是不在凸集中恣意两点连线上的点。二、重要定理与引理12/31/202314定理1.假设LP问题的可行域非空,那么可行域为凸集定理2.LP问题的基可行解X对应LP问题可行域的顶点定理3.假设LP问题有最优解，那么一定存在至少一个基可行解为最优解二、重要定理与引理LP问题的规范型，见P2012/31/202315(1)列初始单纯形表三、单纯形法的计算步骤cjc1…cm…cj…cnCB基bx1…xm…xj…xnc1x1b110…aij…a1nc2x2b200…a2j…a2n...............cmxmbm01…amj…amnб=cj-zj00012/31/202316(2)从一个基可行解转换为相邻的另一个基可行解不失普通性，设初始基可行解中的前m个为基变量，设单位矩阵的列向量为Pi，增广矩阵中单位矩阵以外的某个列向量为Pj，那么Pj可以成为Pi的线性表达：111a1j.amj三、单纯形法的计算步骤12/31/202317两式相加：三、单纯形法的计算步骤对于一个正数：θ12/31/202318除了X(0)，还有其他解吗？111a1j.amj只需：问题：X(1)是基可行解吗？三、单纯形法的计算步骤12/31/202319要使X(1)成为基可行解，必需满足：且，至少一个等式成立！显然，对于小于等于0的aij，上述不等式无条件成立；对于大于0的aij，那么令：三、单纯形法的计算步骤12/31/202320111a1j.amj111以上的系数矩阵的初等行变换，成为换基变换；假设仅且变换一个基变量，称对应的两个基可行解为相邻的基可行解。对应的顶点称为相邻的顶点，简称邻点。三、单纯形法的计算步骤12/31/202321将X(0),X(1)分别代入目的函数：(3)最优性判别三、单纯形法的计算步骤12/31/202322其中：称为检验数，也可表达为：或：三、单纯形法的计算步骤12/31/202323【例】用单纯型法解以下LP问题：用矩阵方式表示为：四、运用举例12/31/202324首先构造初始单纯型表如下：cj21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj-zj20001四、运用举例12/31/202325cj21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj-zj20001x1四、运用举例12/31/202326cj21000CB基bx1x2x3x4x50x315051002x124620100x5511001cj-zj20001x1四、运用举例12/31/202327cj21000CB基bx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61cj-zj000-1/31/3第一次迭代终了四、运用举例12/31/202328cj21000CB基bx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61cj-zj000-1/31/3x2四、运用举例12/31/202329cj21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj-1/2-1/4000四、运用举例12/31/202330化为规范方式：五、单纯型法的进一步讨论—人工变量法(大M法)【例】用单纯型法求解以下LP问题：12/31/202331构造初始单纯型表：cj-30100-M-MCB基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj-zj-3-2M0004M-M1五、单纯型法的进一步讨论—人工变量法(大M法)12/31/202332第1次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-Mx7660403-31cj-zj-3+6M-4M0003M1+4M五、单纯型法的进一步讨论—人工变量法(大M法)12/31/202333第2次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj-zj-M-3/2-M+1/20003/23五、单纯型法的进一步讨论—人工变量法(大M法)12/31/202334第3次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj-zj-M+3/4-M+1/4-9/2-3/4000五、单纯型法的进一步讨论—人工变量法(大M法)12/31/202335同样标题六、单纯型法的进一步讨论—两阶段法为了保证人工变量为0，可讲目的函数设为：12/31/202336构造初始单纯型表：cj00000-1-1CB基bx1x2x3x4x5x6x70x441111000-1x61-21-10-110-1x790310001cj-zj-20004-11六、单纯型法的进一步讨论—两阶段法12/31/202337第1次迭代：cj00000-1-1CB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-1x7660403-31cj-zj6-400034六、单纯型法的进一步讨论—两阶段法12/31/202338第2次迭代：cj00000-1-1CB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj-zj-1-100000即，当X(1)=(1,3,0,0,0,0,0)时，可使目的函数x6+x7获得最小，当x6=x7=0时六、单纯型法的进一步讨论—两阶段法12/31/202339上述获得最优的单纯型迭代中止的表，等价于一个约束方程组I：而约束方程组I又等价于约束方程组II：故，构造新的初始单纯型表如下：六、单纯型法的进一步讨论—两阶段法12/31/202340cj-30100CB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj-zj六、单纯型法的进一步讨论—两阶段法12/31/202341cj-30100CB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj-zj第1次迭代：0003/23六、单纯型法的进一步讨论—两阶段法12/31/202342cj-30100CB基bx1x2x3x4x50x400001-1/20x25/2-1/2100-1/41x33/23/20103/4cj-zj第1次迭代：-9/2-3/4000六、单纯型法的进一步讨论—两阶段法12/31/202343七、单纯型法解的讨论补充定理1.假设LP问题有最优解，那么基可行解中必有最优解。补充定理2.假设X(1),X(2),...,X(K)皆为某LP问题的最优解，那么它们的凸组合也是该LP问题的最优解。补充定理3.假设LP问题的可行域有界，而它的基可行解中的一切最优解为:X(1),X(2),...,X(K),那么它们的一切凸组合包括了该LP问题的所有