6运筹学(精品·公开课件).ppt

第 3 章 线性规划模型的单纯形法 3.1 线性规划数学模型的结构及特征 3.2 线性规划模型的标准形式 3.3 基、基本解、基本可行解 3.4 单纯形表的数学原理 3.5 从一个基本可行解转化为相邻的基本可行解 3.6 最优性检验和解的判别 3.7 单纯形表法 3.8 人工变量法和两阶段法 3.9 计算机软件QM求解 上周内容回顾 单纯形表法求解线性规划模型的步骤 （1）转换一般的线性规划模型为标准型，并 写出A，C，b （2）找初始基本可行解 （3）计算单纯形表中的各矩阵，并构造单纯 形表 （4）判断基最优解 （5）换基迭代，返回（4） 观察法:直接观察得到初始可行基 “≤”类型的约束条件: 加入松弛变量即形成可行基 “≥”或“=”类型的约束条件: 加入非负人工变量 最优性检验与解的判别 （1）最优解判别定理：若： 为基可行解，且全部 则 为最优解。 （3）无穷多最优解判定定理：若： 又存在某一个非基变量 ，且对应的列向量有正数，则存在无穷多最优解。 换基迭代 （1）找入基变量：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善（较快增大）； 进基变量对应的系数列称为主元列。 （2）找出基变量：按最小比值原则确定出基变量，为的是保持解的可行性； 出基变量所在的行称为主元行。 （3）定轴心项：主元行和主元列的交叉元素称为主元素。 （4）作行变换：按照主元素进行矩阵的初等行变换——把主元素变成1，主元列的其他元素变成0（即主元列变为单位向量） （5）替换变量，用入基变量代替出基变量 写出新的基本可行解，返回最优性检验。 3.7.6 关于单纯形法的总结 初始单纯形表和最优单纯形表的比较 3.8 人工变量法和两阶段法 大M法求解线性规划模型中的几种特殊情况 （1）无可行解。检验数全部小于等于零且有人工变量为基变量，则此线性规划模型无可行解。 （2）无界解。如果存在一个检验数大于零，但对应列中的系数向量的每一个元素都小于或等于零，则此线性规划模型是无界的。 （3）无穷多最优解。基变量中无人工变量，且无2的情况，非基变量中的检验数有零，则此线性规划模型有无穷多最优解。 事实上由图解法知该问题无可行解 4.1 对偶模型的提出 4.2 原模型与对偶模型的线性规划模型之 间的关系 4.3 对偶模型的基本性质 4.4 对偶模型的经济意义——影子价格 4.5 对偶模型最优解和影子价格 4.6 对偶单纯形法 设生产A、B产品数分别为x1、x2，则数学模型为 第二阶段：将第一阶段计算得到的最终表，去掉 人工变量，将目标函数换为原问题的目标函数，作为 第二阶段计算的初始表，继续单纯形法 ，直至求得最 优解。 仍以【例3-8】来说明两阶段法。其运算过程如下： 第一阶段： 0 0 0 0 0 -1 -1 cj ? b x7 x6 x5 x4 x3 x2 x1 XB CB 10 0 0 -1 0 0 4 -2 cj-zj 9 1 0 0 0 1 3 0 x7 -1 1 0 1 -1 0 -1 1 -2 x6 -1 4 0 0 0 1 1 1 1 x4 0 4 1 3 6 0 -4 3 0 4 0 6 cj-zj 6 1 -3 3 0 4 0 6 x7 -1 1 0 1 -1 0 -1 1 -2 x2 0 3 0 -1 1 1 2 0 3 x4 0 表3-14 第一阶段单纯形法求解过程 0 0 0 0 0 -1 -1 cj ? b x7 x6 x5 x4 x3 x2 x1 XB CB 6 0 -4 3 0 4 0 6 cj-zj 6 1 -3 3 0 4 0 6 x7 -1 1 0 1 -1 0 -1 1 -2 x2 0 3 0 -1 1 1 2 0 3 x4 0 1 - 1 0 -1 -1 0 0 0 0 0 cj-zj 1 1/6 -1/2 1/2 0 2/3 0 1 x1 0 3 1/3 0 0 0 1/3 1 0 x2 0 0 -1/2 1/2 -1/2 0 0 0 0 x4 0 第一阶段有最优解，原问题有基可行解。 -1 -1 0 0 0 0 0 cj ? b x7 x6 x5 x4 x3 x2 x1 XB CB -1 -1 0 0 0 0 0 cj-zj 1 1/6 -1/2 1/2 0 2/3