2-1-1单纯形法的矩阵描述及改进单纯形法.pptVIP

返回 上页 下页 对偶问题 返回 上页 下页 对偶问题 返回 继续 第一节 单纯形法的进一步讨论 ----单纯形法的矩阵描述 及改进单纯形法介绍 单纯形法的矩阵描述 不妨设基为 基变量 非基变量 设线性规划问题 则 单纯形法的矩阵描述 其中 令 得当前的基解为： 当前基解 约束方程组 当前目标值 目标函数 令 得当前的目标函数值为： 单纯形法的矩阵描述 当前检验数 单纯形法的矩阵描述 检验数 其中 当前 对应的系数列 矩阵单纯形法计算的描述 线性规划问题 化为标准型，引入松弛变量 初始单纯形表 非基变量 基变量 初始基变量 矩阵单纯形法计算的描述 基变量 非基变量 当基变量为 时，新的单纯形表 矩阵单纯形法计算的描述 当前检验数 当前基解 修正单纯形法简介 原因： 单纯形法的目的是要求问题的最优解， 而在迭代过程中，单纯形表中的某些列与 求最优解关系不大。因此，对单纯形法进 行修正。 需要换入的变量对应的列 思路： 每次迭代关键求出 修正单纯形法的优点： 能够从问题的原来参数（A，b，C）， 计算出单纯形表中所有的数据，只要导出 即可。 单纯形表中的任一数字，只要作部分的矩阵乘法即可获得。 修正单纯形法简介 有关公式： 当换入变量 ，换出变量 时， 新的 为： 修正单纯形法简介 单纯形乘子（行向量） 其中 确定新的换入变量 确定新的换出变量 有关公式： 修正单纯形法简介 修正单纯形法要点： 寻求初始可行解，方法与单纯形法相同。 其迭代过程如下： 确定换入变量，方法与单纯形法相同。 确定换出变量，方法与单纯形法相同。 确定新的基可行解： 首先导出B-1 然后计算XB= B-1 b 迭代终止原则与单纯形法相同。 修正单纯形法简介 单纯形法的矩阵描述 及改进单纯形法介绍 返回 返回 上页 下页 对偶问题 返回 上页 下页 对偶问题