《精编制作运筹学完整课件 单纯形法的计算步骤》由会员分享，可在线阅读，更多相关《精编制作运筹学完整课件 单纯形法的计算步骤（25页珍藏版）》请在金锄头文库上搜索。
1、本节重点 单纯形表 特别是检验数行 单纯形法的计算步骤大M法两阶段法解的存在情况判别 4 1单纯形表用表格法求解LP 规范的表格 单纯形表如下 计算步骤 1 找出初始可行基 确定初始基可行解 建立初始单纯形表 2 检验各非基变量xj的检验数 若 j 0 j m 1 n 则已得到最优解 可停止计算 否则转入下一步 3 在 j 0 j m 1 n中 若有某个 k对应xk的系数列向量Pk 0 则此问题是无界解 停止计算 否则 转入下一步 4 根据max j 0 k 确定xk为换入变量 按 规则计算 min bi aik aik 0 可确定第l行的基变量为换出变量 转入下一步 23000 121004
2、001004001 023000 000 81612 x3x4x5 4 3 23000 21010 1 2 92000 3 4 003 x3x4x2 24 301001 4 1640010 X 0 0 0 8 16 12 T z0 0 23000 21010 1 2 1300 201 4 203 x1x4x2 412 301001 4 800 412 X 1 0 3 2 16 0 T z1 9 23000 41001 40 1400 1 5 1 80 203 x1x5x2 2011 2 1 80 400 21 21 X 2 2 3 0 8 0 T z2 13 X 3 4 2 0 4 0 T z
3、3 14 5单纯形法的进一步讨论 5 1人工变量法 解决初始基可行解的问题 当某个约束方程中没有明显的基变量时 在该方程中加上人工变量 其中第2 3个约束方程中无明显基变量 分别加上人工变x6 x7 这时 初始基和初始基可行解很明显 X 0 0 0 0 11 0 3 1 T不满足原来的约束条件 如何使得可从X 0 开始 经迭代逐步得到x6 0 x7 0的基可行解 从而求得问题的最优解 有两种方法 反之 若加了人工变量的问题解后最优解中仍含人工变量为基变量 便说明原问题无可行解 例3的单纯形表格为 只要原问题有可行解 随着目标函数向最大化方向的改善 人工变量一定会逐步换出基 从而得到原问题的基可
4、行解 进而得到基最优解 3 大M法 在目标函数中加上惩罚项 max 3x1 x2 x3 Mx6 Mx7其中M为充分大的正数 3 6MM 13M 10 M00 0 x4103 20100 1 Mx610 1 00 11 21 1x31 2010001 1 1 M00 M0 3M 1 2 两阶段法 第一阶段 以人工变量之和最小化为目标函数min x6 x7 第二阶段 以第一阶段的最优解 不含人工变量 为初始解 以原目标函数为目标函数 5 2线性规划问题解的讨论 一 无可行解maxz 2x1 4x2x1 x2 102x1 x2 40 x1 x2 0 人工变量不能从基底换出 此时原线性规划无可行解 x
5、2 例 maxz 3x1 4x2x1 x2 402x1 x2 60 x1 x2 0 x1 x2 0 此题初始解是退化的 最优解也是退化解 退化解迭代中 当换入变量取零值时目标函数值没有改进 例maxz 3x1 5x23x1 5x2 152x1 x2 52x1 2x2 11x1 x2 0 如果将x1换入基底 得另一解 由可行域凸性易知 有两个最优解必有无穷多组最优解当非基底变量的检验数中有取零值 或检验数中零的个数大于基变量个数时 有无穷多解 四 无 有 界解maxz x1 x2 2x1 x2 4x1 x2 2 3x1 x2 3x1 x2 0 若检验数有大于0 而对应系数列中元素全部小于 等于零 无换出变量 则原问题有无界解 练习 写出单纯形表 分析检验数与系数关系并画图验证 线性规划解除有唯一最优解的情况外 还有如下几种情况 无可行解退化无穷多解无界解 人工变量不能从基底中换出 基可行解中非零元素个数小于基变量数 检验数中零的个数多于基变量的个数 检验数大于零 但对应列元素小于等于零 无换出变量 对目标函数求标准型线性规划问题 用单纯形法计算步骤的框图如下
