管理运筹学讲义：05.pptVIP

管理运筹学 第五章 单纯形法 第一节 基本思路和原理 第二节 表格形式 第三节 大M法和两阶段法 第四节 解的几种特殊情况 第五章 单纯形法 单纯形法(Simplex Method)是美国人丹捷格 (G.Dantzig)1947年创建的 这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。 单纯形法的表现形式： 代数法 表格法 矩阵法 1、凸集：集合C∈En，从C中任取两点X、Y，当0λ1时，仍有λX+（1-λ）Y∈C，则称C为凸集。 2、基：技术系数矩阵A中，m个线性无关的列向量，称为m维实空间中的一个基。其中，每个列向量称为基向量，剩下的n-m个列向量称为非基向量，所有的非基向量构成非基矩阵。 3、基变量：与基向量对应的变量称为基变量。同理，与非基向量对应的变量称为非基变量。 4、基解 对 进行分块处理，则有： 从而有： 令非基变量的取值等于零，得： 。 称： 为基B下的基解。 5、基可行解：符合非负性要求的基本解，称为基可行解。 6、可行基：基本可行解对应的基，称为可行基。 7、基最优解：满足目标函数要求的基本解，称为基最优解。 8、最优基：基最优解对应的基，称为最优基。 9、退化基可行解：基可行解中存在取零值的基变量，则称该基可行解为退化的基可行解。 10、退化基：退化的基可行解对应的基，称为退化基。 线性规划的基本性质 1、线性规划问题的可行域是凸集。 2、如果一个线性规划问题存在可行解，则一定有基解。 3、线性规划问题的基可行解对应于其可行域的顶点。 4、若线性规划问题存在最优解，则最优解可在其可行域的某个顶点上得到。 单纯形法的理论依据 基本过程 一、求初始可行基： 若A中含有单位矩阵，该矩阵为初始可行基。 若A中不含有单位矩阵，应用大M法或两阶段法求解。 基本过程 三、换基运算： 选择换出变量，按最大σ原则 选择换入变量，按最小θ原则 通过矩阵的初等变换换基 线性规划的解题思路 线性规划问题可以有无数个可行解，最优解只可能在顶点上达到，而有限个顶点对应的是基可行解，故只要在有限个基可行解中寻求最优解即可。 从一个顶点出发找到一个可行基，得到一组基可行解，检验是否最优。 如若不是，则向邻近的顶点转移，换一个可行基再求解、检验，如此迭代，目标值逐步得到改善，最终求得最优解。 单纯形法的表格形式 用单纯形法求解下列线性规划先要标准化 单纯形法的表格形式 用单纯形法求解下列线性规划 单纯形法的表格形式 标准化； 初始单纯形表； 检验数的计算； 最优的判别：检验数全非正； 迭代：进出基。 单纯形法的表格形式 标准化； 单纯形法的表格形式 初始单纯形表 单纯形法的表格形式 初始单纯形表 单纯形法的表格形式 单纯形表 单纯形法的表格形式 检验数最大的正数对应的非基变量进基； 该列系数中正的求相应行的比值：常数项比系数； 比值最小的行对应的基变量出基； 初等变换找新基可行解。 单纯形法的表格形式 迭代 单纯形法的表格形式 第一次迭代 单纯形法的表格形式 第二次迭代 作业和预习 作业： P.97第五章习题 5（1）、（2） 预习：第五章3、4节 1 3 1 0 7 4 2 0 1 9 基? 填目标函数系数, 填基变量列, 填CB列, 计算Zj, 计算检验数σj, 4 1 0 0 x3 x4 0 0 0 0 0 0 0 4 1 0 0 单纯形法的表格形式 1 3 1 0 7 4 2 0 1 9 4 1 0 0 x3 x4 0 0 0 0 0 0 0 4 1 0 0 最优吗？ 查什么？ 不是！ 谁进基？ 检验数最大的x1进基, 谁出基？ x1的系数有正的吗？ 求比值？ 7 9/4 9/4 4 单纯形法的表格形式 1 3 1 0 7 4 2 0 1 9 4 1 0 0 x3 x4 0 0 0 0 0 0 0 4 1 0 0 9/4 7 基变量列中___换为___, x4 x1 改CB列,___换为___. 0 4 单纯形法的表格形式 x3 x4 4 1 0 0 0 0 1 3 1 0 7 4 2 0 1