线性规划的单纯形法5.pptVIP

第二章 线性规划的单纯形法 本 章 重 点 单纯形法的基本概念和思想 单纯形法的计算步骤 两阶段法和大M法 单纯形法的基本概念 单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出 尽管在其后的几十年中，又有一些算法问世，但是单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率 单纯形法的基本概念 预备知识 线性规划问题的标准型 单纯形法的基本概念 预备知识 最小化函数转为最大化函数：乘（-1） 单纯形法的基本概念 化标准型的一些方法 “ ”约束条件转化为“ ”约束条件 “ ” 约束条件转化为“ ”约束条件 单纯形法的基本概念 例：将下面的线性规划模型转化为标准型 线性规划的建模 化标准型的一些方法 “ ”约束条件转化为“ ”约束条件 “ 无约束 ” 约束条件转化为“ ”约束条件 单纯形法的基本概念 例：将下面的线性规划模型转化为标准型 线性规划的建模 化标准型的一些方法 如果 将约束条件 化为等式约束 单纯形法的基本概念 将下面的线性规划模型转化为标准型 单纯形法的基本概念 定义： 可行解：满足全体约束条件的解 最优解：可行解中最优的，记作 对于所有可行解有 直观上，可行解是可行域中的点，是一个可行方案 最优解是可行域的顶点，是一个最优的可行方案 单纯形法的基本概念 定义：在标准形式的线性规划的约束方程组中，若令其中任意个变量为零，则得到的新方程组可能有唯一解，则这个唯一解与令其为零的个变量一起组成的一个解，称为的一个基本解。 新方程组中不为零的变量称为基本变量（基变量）。其它变量称为非基本变量（非基变量）。 单纯形法的基本概念 例： 单纯形法的基本概念 单纯形法的基本概念 定义：如果基本解又是可行的，则称其为基本可行解。——是非负的基本解 单纯形法的基本概念 定义：如果基本解又是可行的，则称其为基本可行解。——是非负的基本解 定义：如果基本解中存在一个基本变量为0，则称其为退化的基本解，如果退化的基本解又是可行的，则称为退化的基本可行解。 单纯形法的基本概念 例 令 得到方程组 有唯一解 解 是退化解 单纯形法的基本概念 定理：如果点A是线性规划问题可行域中的一个顶点，则它一定是线性规划问题的基可行解 例：第一章中的家具生产问题 单纯形法的基本概念 单纯形法的基本概念 定义：对于具有m个约束条件的线性规划问题，两个基可行解被认为是相邻的，是指他们的基变量中有m-1个变量相同。 例：上面图中顶点B,C是相邻的，B的基本变量为：xC，s1，C的基本变量是xT，xc 单纯形法的基本思想 单纯形方法的基本思想是：从标准形式出发，找一个基本可行解为出发点，以此去找一个相邻的、更优的基本可行解。这样一次比一次好的找下去，直到找到最优解。 单纯形法的基本思想 例 第一步:化为标准形式 单纯形法的基本思想 第二步：寻找初始基本可行解,用非基本变量表示基本变量并计算目标函数值 单纯形法的基本思想 第三步:将使得目标函数增长最快的变量换入基本变量中，并将依然保持 的变量换出基变量中 第四步：将基变量用非基变量表示，并带入目标函数 单纯形法的基本思想 第五步:将 换入基本变量中，并保持 单纯形法的基本思想 第六步:用非基本变量表示基本变量 单纯形法的基本思想 求解的一般步骤： 将线性规划模型化为标准形式 寻找一组初始基本可行解 将基变量表示为非基变量的函数，并将其带入目标函数中 将目标函数中价格系数非负的、最大的变量设为换入变量，计算换入变量的取值范围，计算换出变量 得到另一个基本可行解，并回到3，直到目标函数中所有的非基变量的价格系数小于等于0 单纯形法的基本思想 例2：求解下列单纯形法 单纯形法的基本思想 第一步：化为标准形式 单纯形法的基本思想 第二步：通过设置r个变量为非基本变量，寻找初始基本可行解,用非基本变量表示基本变量并带入到目标函数中，计算目标函数值 单纯形法的基本思想 第三步:将使得目标函数增长最快的变量 换入基本变量中，并依然保持 ，求换出变量 单纯形法的基本思想 第四步:确定换入变量为 ，计算换出变量，并将基本变量表示为非基变量的函数 本 章 重 点 单纯形法的基本概念和思想 单纯形法的