线性规划单纯形(Simplex)算法总结与个人理解 | 您所在的位置:网站首页 › 线性规划实训总结 › 线性规划单纯形(Simplex)算法总结与个人理解 |
关于线性单纯形算法的总结,具体包括单纯形算法,大M法,两阶段法以及单纯形法的一些特殊情况。 关于单纯形法的理解,主要参考了线性规划-单纯形算法详解。单纯形法的特殊情况参考了单纯形法的几种特殊情况。 这里不对单纯形算法的原理进行证明,但是给出自己对计算单纯形表的每一个步骤的理解。 1 线性规划的形式说明 一般线性规划可化为如下形式: 其中,b 可为正也可为负。当 b 中元素全为正时,显然 x = 0 是满足线性规划约束的一个基本可行解,可直接运用单纯形算法;当 b 中存在元素为负数时,需要运用大M法,或两阶段法先找到一个基本可行解。 2 单纯形算法 以下述线性规划为例,说明单纯形算法: 步骤1:转化为最小化问题并添加松弛变量 步骤2:构造初始单纯形表: 上表中,位于第一列的变量 步骤3:用非基本变量替出基本变量 如上表,因为 选定 1)选择 2)替出变量 如果所有的比值结果都为非正数,则说明 第一次替换后的结果如下: 这里 步骤4:重复步骤3,直到 z 行所有系数为非负。这里用 因为原问题求的是最大值,所以这里的 21 就是原问题的最大值,对应最优解为 如果非基本变量 z 行的系数也为 0 ,例如这里如果 3 大M法 当 b 中存在元素为负数时, b 中存在元素为负数,相当于约束中存在大于等于约束,现以下述例子说明大M法(事实上当存在大于等于或者等于约束时,运用大M法,对等式约束而言松弛变量相当于人工变量)。 添加人工变量 Ri ,原规划问题可写成: 大M法,顾名思义,M在这里为取值很大的正数,因此若原问题最小值存在,最优解必然使 同样,列单纯形表(或称之为单纯形矩阵): 利用 可以看到,引入人工变量 第一次用 第二次用 第三次用 所以我们得到 - z = - 17/5,即 z 的最小值为 17/5,对应最优解为: 如果最后我们得到的结果中,仍存在人工变量 Ri 为基本变量且取值不为 0 ,则说明原问题无可行解。(可以认为必须要引入额外人工变量以后才能求解,但此时人工变量不为零,所求解的问题已经跟原问题不同了) 4 两阶段法两阶段法相当于引入人工变量后,将原问题分成以下两个问题分阶段求解: 第一阶段:单独优化人工变量之和 最终结果为: 如果最后第一阶段的最优值不为零,则说明原问题无可行解(原问题改变了)。 根据本文之前的说明,单纯形矩阵的演变过程是初等行变换的过程,最后得到的方程组与原方程组等价。在第一阶段优化结束时, 第二阶段:在新的约束方程组下优化原问题。 初始单纯形表为: 相当于: 第一阶段相当于找到了一个基本可行解: 观察大M法与上述结果可以发现,两阶段法与大M法十分相似。 5 退化问题最后补充一个关于退化的说明。在求解过程中,可能会出现 z 行出现两个或两个以上的变量系数相等且都小于零,或者确定要替入的非基变量后,求比值确定替出的基本变量时可能出现两个或者两个以上的基本变量的比值相同或都为0,此时如果随便选择变量进行操作,可能会造成循环,无法求得最优解。出现的原因是模型中存在多余的约束,使多个基本可行解对应同一顶点。 当出现退化问题时,按照先决策变量,后松弛变量,再人工变量的顺序选择替入或替出变量。 |
CopyRight 2018-2019 实验室设备网 版权所有 |