C3单纯形法.ppt

1、运 筹 学,李健 北京化工大学经济管理学院,讨论区 orppt123456,2020/8/5,北京化工大学经管学院,2,上节内容提要,线性规划与单纯形法 线性规划问题及其数学模型 问题的提出 图解法 线性规划问题的标准形式 线性规划问题解的概念 线性规划问题的几何意义 基本概念 几个定理,2020/8/5,北京化工大学经管学院,3,1.2 图解法,1 2 3 4 5 6 7 8,1 2 3 4 5 6,x2,x1,(4 2),0,唯一最优解,2020/8/5,北京化工大学经管学院,4,无穷多最优解,无界解,x1,x1,x2,x2,x1,x2,无可行解,2020/8/5,北京化工大学经管学院,6

2、,2.2 图解法,图解法直观、简便，适合变量数为三个以下的情形。变量数超过三个时怎么求解？,Linear Programming (LP)解的情况,唯 一 解（例1） 无 穷 解（例2） 无 界 解（例3） 无可行解（例4）,有最优解,无最优解,2020/8/5,北京化工大学经管学院,7,1.3 线性规划问题的标准形式,LP模型的一般形式为,LP模型的标准形式为,1. 目标函数为求极大值； 2. 所有约束（除非负约束）都 是等式，右端常数项为非负； 3. 变量为非负。, 可行解：满足约束条件(1-5)(1-6)的解为可行解。所有解的集合为可行解的集或可行域。, 最优解：使目标函数达到最大值的可

3、行解。, 基：B是矩阵A中mm阶非奇异子矩阵(B0），则B是一个基。,同时称 Pj ( j = 1 2 m) 为基向量。相应的 Xj 为基变量，否则为非基变量。,1.4 线性规划问题解的概念,2020/8/5,北京化工大学经管学院,9, 基解：有一个基，就可以求出一个基解。满足(1-5)，但不必满足(1-6)的所有基解，最多为 个。, 基本可行解：满足非负约束条件的基解，简称基可行解。, 可行基：对应于基可行解的基称为可行基。,非可行解,可 行 解,基解,基可行解,1.4 线性规划问题解的概念,2020/8/5,北京化工大学经管学院,10,2.2几个定理,定理1.设线性规划问题的可行域非空，则

4、可行域为凸集（凸多边形）。 引理1. 线性规划问题的可行解为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。,定理2.线性规划问题的基可行解对应于可行域的顶点。线性规划问题如有可行解，则必有基可行解。 引理2. 若K是有界凸集，则任何一点X属于K可表示为K的顶点的凸组合。,2020/8/5,北京化工大学经管学院,11,2.2几个定理,定理3. 设可行域有界，则线性规划问题必有最优解（唯一或无穷多），且必可在可行域的顶点达到最优值。（该顶点是最优解) 注：在多个点处达到最优值时，在这些点的凸组合处也达到最优值。此时，称这种线性规划问题有无限多个最优解。,定理4. 设可行域无界，则可

5、能无最优解（无界解），也可能有最优解（唯一或无穷多）。有最优解时，必可在可行域的顶点达到最优值。（该顶点是最优解),2020/8/5,北京化工大学经管学院,12,2.2几个定理,启示：我们可以仅仅在可行域的顶点处寻找LP的最优解，例如采用枚举法（顶点数目不超过 个）。但是对于n,m比较大时，这种方法是行不通的！单纯形法可以解决这一问题。,2020/8/5,北京化工大学经管学院,13,内容提要,线性规划与单纯形法 线性规划问题及其数学模型 线性规划问题的几何意义 单纯形法 单纯形法的计算步骤,2020/8/5,北京化工大学经管学院,14,1.3单纯形法,单纯形? 指零维中的点，一维中的线段，二维

6、中的三角形，三维中的四面体，n维空间中具有n+1个顶点的多面体。 单纯形法（Simplex method）的基本思想： 由LP解的性质：若有最优解，必在其可行域的顶点处达到。那么若对可行域的所有顶点进行比较，就可找出其最优解。但问题规模较大时，该做法计算量太大，不实用。单纯形法克服了这一缺点。它缩小了搜索顶点的范围：首先确定一个顶点，由此顶点出发转到下一顶点，并要求新顶点的目标函数值比前一顶点处的更优。大体步骤如下：首先将模型一般形式变成标准形式，再根据标准形式，从可行域中找一个初始顶点，并判断是否最优。如果是，得最优解；如果不是，转换到另一个顶点，并使得新顶点处目标函数值更优。 要解决的问题

7、；找初始顶点？判断最优？转换到另一顶点？,2020/8/5,北京化工大学经管学院,15,1.3.1举例,2020/8/5,北京化工大学经管学院,16,1.3.1举例,2020/8/5,北京化工大学经管学院,17,1.3.1举例,2020/8/5,北京化工大学经管学院,18,1.3.1举例,2020/8/5,北京化工大学经管学院,19,1.3.1举例,2020/8/5,北京化工大学经管学院,20,1.3.1举例,2020/8/5,北京化工大学经管学院,21,1.3.1举例,1 2 3 4 5 6 7 8,1 2 3 4 5 6,x2,x1,(4 2),0,找出一个初始可行解,是否最优,转移到另一

8、个目标函数 （找更大的基本可行解）,最优解,是,否,循 环,直到找出为止，核心是：变量迭代,结束,单纯形法步骤：,问题1,问题2,问题3,2020/8/5,北京化工大学经管学院,23,1.3.2初始基可行解的确定,问题1：找初始顶点？ 问题2：判断最优？ 问题3：转换到另一顶点？,找初始顶点分三种情况来进行：,2020/8/5,北京化工大学经管学院,24,1.3.2初始基可行解的确定,2020/8/5,北京化工大学经管学院,25,1.3.2初始基可行解的确定,2020/8/5,北京化工大学经管学院,26,1.3.3最优性检验与解的判别,问题1：找初始顶点？ 问题2：判断最优？ 问题3：转换到另

9、一顶点？,对于这四种情况都要根据相应准则判断出来。,LP解的情况,唯 一 解 无 穷 解 无 界 解 无可行解,有最优解,无最优解,2020/8/5,北京化工大学经管学院,27,1.3.3最优性检验与解的判别,2020/8/5,北京化工大学经管学院,28,1.3.3最优性检验与解的判别,2020/8/5,北京化工大学经管学院,29,1.3.45基变换（迭代、旋转运算）,问题1：找初始顶点？ 问题2：判断最优？ 问题3：转换到另一顶点？,2020/8/5,北京化工大学经管学院,30,1.3.45基变换（迭代、旋转运算）,2020/8/5,北京化工大学经管学院,31,1.3.45基变换（迭代、旋转运算）,202