运筹学第一章 1.4 大M法和两阶段法课件.ppt

四、单纯形法的一般描述： ? 1、 初始可行解的确定 (1)初始可行基的确定 观察法—系数矩阵中是否含有现成的单位阵？ LP限制条件中全部是“≤”类型的约束 将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；; 先将约束条件标准化，再引入非负的人工变量， 以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”； 然后用大M法或两阶段法求解；;等式约束左端引入人工变量的目的;①如果限制条件中既有“≤”类型的约束，又有“≥”或“=”类型的约束，怎麽办？ 构造“不完全的人造基”！ ;（2）写出初始基本可行解—— 根据“用非基变量表示基变量的表达式”，非基变量取0，算出基变量，搭配在一起构成初始基本可行解。;此时LP的标准型为 ;初始可行基 ：; 一般（经过若干次迭代），对于基B， 用非基变量表出基变量的表达式 为：; 若 是对应于基B的基本可行解， 是非基变量 的检验数，若对于一切非基变量的角指标j，均有 ≤0，则X(0)为最优解。;举例：用非基变量表示基变量的表达式 ;要求： ; 3、进行基变换 （1）选择进基变量——原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善（较快增大）； 进基变量对应的系数列称为主元列。 （2）出基变量的确定——按最小比值原则确定出基变量，为的是保持解的可行性； 出基变量所在的行称为主元行。 主元行和主元列的交叉元素称为主元素。; 4、主元变换（旋转运算或枢运算） 按照主元素进行矩阵的初等行变换——把主元素变成1，主元列的其他元素变成0（即主元列变为单位向量） 写出新的基本可行解，返回最优性检验。;表格单纯形法求解步骤;第二步：最优性检验;; 利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。;该迭代过程直至下列情况之一发生时停止 ? 检验数行全部变为非正值； （得到最优解）或 ?主元列≤ 0 （最优解无界）;五、各种类型线性规划的处理 1、分类及处理原则： （1）类型一：目标要求是“Max”，约束条件是“≤”类型——左边加上非负松弛变量变成等式约束（约束条件标准化），将引入的松弛变量作为初始基变量，则初始可行基是一个单位阵，用原始单纯形法求解。;（2）类型二：目标要求是“Max”，约束条件是“=”类型——左边引入非负的人工变量，并将引入的人工变量作为初始基变量，则初始可行基是一个单位阵，然后用大M法或两阶段法求解。 （3）类型三：目标要求是“Max”，约束条件是“≥”类型——约束条件标准化，左边减去非负的剩余变量，变成等式约束，化为类型二。 ;2、处理人工变量的方法： （1）大M法——在约束条件中人为地加入非负的人工变量，以便使它们对应的系数列向量构成单位阵。 问题：加入的人工变量是否合理？如何处理？ 在目标函数中，给人工变量前面添上一个绝对值很大的负系数-M（M0），迭代过程中，只要基变量中还存在人工变量，目标函数就不可能实现极大化——惩罚！;① 最优表中，基变量不包含人工变量，则最优解就是原线性规划的最优解，不影响目标函数的取值； ② 最优表中，基变量中仍含有人工变量，表明原线性规划的约束条件被破坏，线性规划没有可行解，也就没有最优解！;大M法举例;六、迭代过程中可能出现的问题及处理方法;2、出现若干个相同的最小比值怎麽办？ （说明出现了退化的基本可行解，即非0分量的个数小于约束方程的个数。按照“摄动原理”所得的规则，从相同比值对应的基变量中选下标最大的基变量作为换出变量可以避免出现“死循环”现象）;（2） 两阶段法 第一阶段：建立辅助线性规划并求解，以判断原线性规划是否存在基本可行解。 辅助线性规划的结构：目标函数W为所有人工变量之和，目标要求是使目标函数极小化，约束条件与原线性规划相同。 ; 求解结果 ①W最优值=0——即所有人工变量取值全为0（为什麽？），均为非基变量，最优解是原线性规划的一个基本可行解，转入第二阶段； ②W最优值=0——但人工变量中有等于0的基变量，构成退化的基本可行解，可以转化为情况①；如何转化？ 选一个不是人工变量的非基变量进基， 把在基中的人工变量替换出来 ;③W最优值0——至少有一个人工变量取值0,说明基变量中至少有1个人工变量,表明原问题没有可行解,讨论结束。; ②（1）式目标要