单纯形表法(基本原理+例题解析) |
您所在的位置:网站首页 › bland法则是什么 › 单纯形表法(基本原理+例题解析) |
基本思想:从一个基本可行解出发,一步步的转到更优的基本可行解,直至最优解。 单纯形法总有两种形式,一是单纯形法,还有一种是单纯形表法。下面我们依次展开讨论。 单纯形法: 基本概念:单纯形法其实是对消去法的一个总结,归纳和公式化。 标准线性规划问题:
约束条件 两边左乘 目标函数 将 令 如果 目标函数 如果 定义:称 由此综合,可总结出定理: 1)对于标准线性规划问题,如果基矩阵为 B ,并且 2)如果线性规划的某个检验数 下面给出运用两个定理的例题,用于加深理解。 1,判断 解:
由
下面计算检验数向量: 2,对于下面的线性规划,讨论其有无最优解? 解:
下面主要判断 计算检验数向量: 步骤1:找到初始可行基矩阵 B ,解 步骤2:求单纯性乘子 w,解 步骤3:解 步骤4:确定下标 r , 例题:利用单纯形法求解下列问题: 解:将约束条件化为标准型:
第一次迭代:
计算检验数: 确定进基变量:又知道对应基变量的判别数均为零,因此最大判别数是 确定离基变量:
确定下标:
第二次迭代:
计算检验数: 确定进基变量:又知道对应基变量的判别数均为零,因此最大判别数是 确定离基变量:
确定下标:
第三次迭代:
计算检验数: 确定进基变量:又知道对应基变量的判别数均为零,且检验数小于零,故得到最优解。 单纯形表是通过表格的形式,按照行列式的变换规则,运算得到最优解,原理与单纯形法一致,但是书写起来更为便捷。并严格按照上文给出的定理1,判断是否为最优解。 下面依然以一道例题来解释单纯形表的运算过程: 例题分析:可以对比得到,单纯形表法简洁不少! Bland规则:针对退化情况(基循环的处理),我们可以采取两个规则: 规则一:进基变量的选择 由 规则二:离基变量的选择(和Dantzig离基规则相同) 由 从理论上看,在单纯形算法步骤中采用 Bland 规则,可以使算法在有限步结束。 从计算实践来看,Dantzig 规则效果更好,迭代次数少。 对于线性规则问题,先按照 Dantzig 规则进行单纯形迭代,万一遇到基的循环,在采用 Bland 规则。 (行文中若有纰漏,希望大家指正) |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |