4 4 3求解线性规划问题的单纯形法 由前述可知 线性规划问题的目标函数的最小值一定是在基本可行解中获得 所以在寻找最优解时 只需要考虑基本可行解就够了 单纯形法求解线性规划问题就是应用的这一思想 1将线性规划问题化为标准型2将线性规划问题化为典范型 从而可立即得到一组初始基本可行解 称为初始点x 0 该点的目标函数值为Z x 0 3寻找另一个基本可行解x 1 由一个典范型化为另一个典范型 使Z x 1 Z x 0 4继续寻找好的基本可行解x 2 x 3 x 4 使目标函数值不断下降 直到目标函数值不可能再被改进 二由一个典范型化为另一个典范型的过程 迭代的目的是要寻找一个使目标函数更小的基本可行解 为了达到这个目的 单线形法分两步进行 第一步 从原来的非基本变量中选出一个使其进入基本变量中 这个被选中的变量叫进基变量 第二步 从原来的基本变量中选出一个使其进入非基本变量中 即令这个选中的为零称这个为离基变量 进基变量是由原来令其为零而变为正数 离基变量是由原来非零 而变为等于零 选进基与离基变量的原则 使目标函数值得到最快的减小 非基本变量 基本可行解中 令其取值为零的变量为非基本变量基本变量 基本可行解中 非基本变量以外的变量 又称基变量 三单纯形表格法求解线性规划问题的步骤 例 求解下面线性规划问题MinZ 3u1 2u2s t u1 2u2 43u1 2u2 14 u1 u2 3 u1 0 u2 0 例 求解线性规划问题MinZ 3u1 2u2s t u1 2u2 43u1 2u2 14 u1 u2 3解 1 引入松弛变量或剩余变量将线性规划问题化为标准型MinZ 3u1 2u2s t u1 2u2 u3 43u1 2u2 u4 14 u1 u2 u5 3 2 将线性规划问题化为典范型 得到初始基本可行解 令 u1 0 u2 0 则 u3 4 u4 14 u5 3 写出初始单纯形表 MinZ 3u1 2u2s t u1 2u2 u3 43u1 2u2 u4 14 u1 u2 u5 3 非基变量u1 0 u2 0基本变量u3 u4 u5 3求解线性规划问题的算法 4 用单纯形表进行迭代计算 3求解线性规划问题的算法 例4 5 求解线性规划问题MinJ x1 2x2 x3 3x4s t x1 x2 3x3 x4 6 2x2 x3 x4 0 x2 0 x3 0 x4 0解 1 引入松弛变量或剩余变量将线性规划问题化为标准型MinJ x1 2x2 x3 3x4s t x1 x2 3x3 x4 6 2x2 x3 x4 x5 3 x2 6x3 x4 x6 4 2 将线性规划问题化为典范型 得到初始基本可行解 最明显的可行解就是把系数为1的变量留下作为基变量 并设其他变量为零 作非基变量 本问题留下x1 6 x5 3 x6 4其值为约束等式右边的常系数 其他变量为零 作非基变量x2 0 x3 0 x4 0初始基本可行解 非基变量 x2 0 x3 0 x4 0 基变量 x1 6 x5 3 x6 4 写出初始单纯形表 MinJ x1 2x2 x3 3x4s t x1 x2 3x3 x4 6 2x2 x3 x4 x5 3 x2 6x3 x4 x6 4 非基变量x2 x3 x4基本变量x1 x5 x6 x4 4 用单纯形表进行迭代计算 四求初始基本可行解的方法由标准形化为典范形的方法 前面介绍的单纯形法 是从一个初始的典范形式开始的 当最初的标准形式不是典范形式时 要想办法由标准形式化为典范形 方法 在原问题中引入人工变量 又称人为变量 构造一个新的已是典范形的问题 用单纯形法对此新问题进行迭代求解 迭代的结果 只要原问题有解 则新问题的最优解与原问题的最优解等价 化典范形的方法有两种 大M法和两阶段法 A 大M法 设原问题如下 Minc1u1 c2u2 cnuns t a11u1 a12u2 a1nun b1a21u1 a22u2 a2nun b2a31u1 a32u2 a3nun b3 am1u1 am2u2 amnun bmu1 0 u2 0 un 0b1 0 b2 0 bm 0 3求解线性规划问题的算法 在原问题中引入人工变量 并将一个很大的正数M作为目标函数中人工变量的系数 从而构成具有典范型的新问题Minc1u1 c2u2 cnun Mun 1 Mun 2 Mun ms t a11u1 a12u2 a1nun un 1 b1a21u1 a22u2 a2nun un 2 b2a31u1 a32u2 a3nun un 3 b3 am1u1 am2u2 amnun un m bmu1 0 u2 0 un m 0b1 0 b2 0 bm 0新问题的解就是原问题的解 例 用大M法求解线性规划问题MinJ 4x1 x2 x3s t 2x1 x2 2x3 43x1 3x2 x3 3x1 0 x2 0 x3 0解 此问题已经是标准形 但不是典范型 引入两个人工变量x4 0 x5 0将问题化为典范型 构成新问题 MinJ 4x1 x2 x3 Mx4 Mx5s t 2x1 x2 2x3 x4 43x1 3x2 x3 x5 4x1 0 x2 0 x3 0 x4 0 x5 0其中M是一个充分大的数 给新问题列单纯形表 解出 此问题的解基本变量 x2 2 5 x3 9 5非基本变量x1 0 x4 0 x5 0即 新问题的解x 0 2 5 9 5 0 0 T原问题的解x 0 2 5 9 5 T且 目标函数值相同 新问题的极值J 原问题的极值J 11 5 MinJ 4x1 x2 x3 Mx4 Mx5 二 修正单纯形法 早期单纯形法的计算机程序是计算整个单纯形表格 为了节省计算时间 需要将整个表格存于内存中 由于计算机内存的有限性 使原始的单纯形法不适用于大型问题 为提高计算机效率节省内存 单纯形法不断被改进 发展为实用的单纯形法 修正的单纯形法 原理与原始单纯形法相同 改进在于 原始单纯形法中仅有一小部分列向量与进基和离基变量的变换有关 大部分的列向量 尤其当n m时 其与基本变量的变换无关 但也要跟着做换基运算 这非常浪费时间 修正单纯形法消除了这些不必要的计算 节省了存储量