金融学院-管理运筹学-02-线性规划与单纯型法ppt课件

1、管理运筹学.线性规划与单纯型法第二讲.由实践问题引出数学模形。产品A产品B资源限量劳动力设备原材料9434510360200300利润元/KG701201. 确定决策变量: 设消费A, B分别为x1, x22. 确定目的函数: 3. 确定约束条件: 一、LP问题的根本概念典型的LP问题:一、LP问题的根本概念用向量符号表示为:用向量和矩阵表示为:一、LP问题的根本概念1. 基、基向量、基变量、非基变量设A为约束方程组的mn阶系数矩阵，其秩为m，B是A中的一个m阶满秩子矩阵，称B为LP问题的一个基。B中每一个列向量称为基向量，对于的变量xj为基变量，其他的变量称为非基变量。一、LP问题的根本概念

2、1. 基、基向量、基变量、非基变量一、LP问题的根本概念满足约束方程(包括非负约束)的一切解，称为可行解。对于某组选定的基，令非基变量为0，与约束方程求得的独一解，称为基解。2. 可行解、基解、基可行解、可行基一、LP问题的根本概念基解中满足一切变量非负约束的解，称为基可行解。2. 可行解、基解、基可行解、可行基与基可行解对应的基称为可行基。一、LP问题的根本概念概念练习: 找出以下LP问题的全部基解。 1234512345一、LP问题的根本概念组合x1x2x3x4x5z基可行解？1-2001-3001-4001-5002-3002-4002-5003-4003-5004-50051045/5

3、5-120452175541010-5415/52.51.517.554-32224319一、LP问题的根本概念1. 连线:二、重要定理与引理在n维Euclid空间中，点X与Y连线上的点，是指如下方式的点T:当跑遍区间0,1时,相应的点T的集合就构成点X与Y之间的连线。 2. 凸集:一个由n 维点所构成的集合K，假设对于K中恣意两点X,Y K，恒有: 那么n维点集K称为凸集，即K中恣意两点的连线上的点也在K中。 3. 凸组合:假定有k个n 维Euclid 空间的点它们的凸组合是指如下方式的点X :特别，两个点X与Y的凸组合，叫做它们连线上的点。二、重要定理与引理4. 顶点:设K是凸集，点X K

4、；假设对K中任何两个不同的点X ,Y ，以下等式恒不成立:就称X为凸集K的顶点。换句话说，凸集的顶点，就是不在凸集中恣意两点连线上的点。 二、重要定理与引理定理1. 假设 LP问题的可行域非空, 那么可行域为凸集定理2. LP问题的基可行解X对应LP问题可行域的顶点定理3. 假设LP问题有最优解，那么一定存在至少一个基可行解为最优解二、重要定理与引理LP问题的规范型，见P20(1) 列初始单纯形表三、单纯形法的计算步骤cjc1cmcjcnCB基bx1xmxjxnc1x1b110aija1nc2x2b200a2ja2n.cmxmbm01amjamn=cj-zj000(2) 从一个基可行解转换为相

5、邻的另一个基可行解不失普通性，设初始基可行解中的前m个为基变量，设单位矩阵的列向量为Pi，增广矩阵中单位矩阵以外的某个列向量为Pj，那么Pj可以成为Pi的线性表达：111a1j.amj三、单纯形法的计算步骤两式相加：三、单纯形法的计算步骤对于一个正数：除了X(0)，还有其他解吗？111a1j.amj只需：问题：X(1)是基可行解吗？三、单纯形法的计算步骤要使X(1)成为基可行解，必需满足：且，至少一个等式成立！显然，对于小于等于0的 aij，上述不等式无条件成立；对于大于0的aij，那么令：三、单纯形法的计算步骤111a1j.amj111以上的系数矩阵的初等行变换，成为换基变换；假设仅且变换一

6、个基变量，称对应的两个基可行解为相邻的基可行解。对应的顶点称为相邻的顶点，简称邻点。三、单纯形法的计算步骤将X(0), X(1)分别代入目的函数：(3) 最优性判别三、单纯形法的计算步骤其中：称为检验数，也可表达为：或：三、单纯形法的计算步骤【例】用单纯型法解以下LP问题：用矩阵方式表示为：四、运用举例首先构造初始单纯型表如下：cj21000CB基bx1x2x3x4x50 x315051000 x424620100 x5511001cj-zj20001四、运用举例cj21000CB基bx1x2x3x4x50 x315051000 x424620100 x5511001cj-zj20001x1四

7、、运用举例cj21000CB基bx1x2x3x4x50 x315051002x124620100 x5511001cj-zj20001x1四、运用举例cj21000CB基bx1x2x3x4x50 x315051002x1412/601/600 x5104/60-1/61cj-zj000-1/31/3第一次迭代终了四、运用举例cj21000CB基bx1x2x3x4x50 x315051002x1412/601/600 x5104/60-1/61cj-zj000-1/31/3x2四、运用举例cj21000CB基bx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1

8、/21x23/2010-1/43/2cj-zj-1/2-1/4000四、运用举例化为规范方式：五、单纯型法的进一步讨论人工变量法(大M法)【例】用单纯型法求解以下LP问题：构造初始单纯型表：cj-30100-M-MCB基bx1x2x3x4x5x6x70 x441111000-Mx61-21-10-110-Mx790310001cj-zj-3-2M0004M-M1五、单纯型法的进一步讨论人工变量法(大M法)第1次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70 x4330211-100 x21-21-10-110-Mx7660403-31cj-zj-3+6M-4M0003M1

9、+4M五、单纯型法的进一步讨论人工变量法(大M法)第2次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70 x400001-1/21/2-1/20 x23011/30001/3-3x11102/301/2-1/21/6cj-zj-M-3/2-M+1/20003/23五、单纯型法的进一步讨论人工变量法(大M法)第3次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70 x400001-1/21/2-1/20 x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj-zj-M+3/4-M+1/4-9/2-3/4000五、单纯型法

10、的进一步讨论人工变量法(大M法)同样标题六、单纯型法的进一步讨论两阶段法为了保证人工变量为0，可讲目的函数设为：构造初始单纯型表：cj00000-1-1CB基bx1x2x3x4x5x6x70 x441111000-1x61-21-10-110-1x790310001cj-zj-20004-11六、单纯型法的进一步讨论两阶段法第1次迭代：cj00000-1-1CB基bx1x2x3x4x5x6x70 x4330211-100 x21-21-10-110-1x7660403-31cj-zj6-400034六、单纯型法的进一步讨论两阶段法第2次迭代：cj00000-1-1CB基bx1x2x3x4x5x

11、6x70 x400001-1/21/2-1/20 x23011/30001/30 x11102/301/2-1/21/6cj-zj-1-100000即，当X(1)=(1,3,0,0,0,0,0)时，可使目的函数x6+x7获得最小，当x6=x7=0时六、单纯型法的进一步讨论两阶段法上述获得最优的单纯型迭代中止的表，等价于一个约束方程组I：而约束方程组I又等价于约束方程组II：故，构造新的初始单纯型表如下：六、单纯型法的进一步讨论两阶段法cj-30100CB基bx1x2x3x4x50 x400001-1/20 x23011/300-3x11102/301/2cj-zj六、单纯型法的进一步讨论两阶段

12、法cj-30100CB基bx1x2x3x4x50 x400001-1/20 x23011/300-3x11102/301/2cj-zj第1次迭代：0003/23六、单纯型法的进一步讨论两阶段法cj-30100CB基bx1x2x3x4x50 x400001-1/20 x25/2-1/2100-1/41x33/23/20103/4cj-zj第1次迭代：-9/2-3/4000六、单纯型法的进一步讨论两阶段法七、单纯型法解的讨论补充定理1. 假设LP问题有最优解，那么基可行解中必有最优解。补充定理2. 假设X(1), X(2),., X(K)皆为某LP问题的最优解，那么它们的凸组合 也是该LP问题的最

13、优解。补充定理3. 假设LP问题的可行域有界，而它的基可行解中的一切最优解为: X(1), X(2),., X(K), 那么它们的一切凸组合包括了该LP问题的所 有最优解。(证明略)以下给出三个补充定理，可看作是求解线性规划问题的根本根据。情况1: 独一最优解只需非基变量的检验数全为负，且基变量中不含人工变量，该解即为独一最优解。情况2: 无解1. 当非基变量的检验数全为负，且基变量中含有人工变量，那么该LP问题无解。2. 可行域为空集。七、单纯型法解的讨论情况3: 解无界对于某个正检验数，其对应的Pj有非正的分量，该LP问题的解无界。七、单纯型法解的讨论看以下例子:cj1100CB基bx1x2x3x40 x34-21100 x421-101cj-zj1100请同窗们用图解加以验证，加深印