教案4_单纯形法(改).ppt

本节重点 单纯形表 特别是检验数行 单纯形法的计算步骤大M法两阶段法解的存在情况判别 4 1单纯形表用表格法求解LP 规范的表格 单纯形表如下 23000 121004001004001 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 0 4 T z3 14 单纯形法的计算步骤 第一步 将线性规划模型标准化 第二步 选择单位矩阵的基为初始可行基 必要时要加人工变量 对应的变量为初始基变量 建立初始单纯形表 第三步 进行最优解的判别 即计算非基变量的检验数 若所有的检验数均 0 则目前的解为最优解 计算结束 否则转步骤四 第四步 在单纯形表中选检验数最大的列为主元列 主元列对应的变量为入基变量用主元列 用主元列中的正元素去除对应的常数项 选最小者所对应的行为主元行 主元行对应的基变量为出基变量 主元行与主元列相交的元素为主元素 第五步 通过方程的初等变换将主元列中的主元素变为1 其它元素变为零 在基变量栏中 在原来出基变量的位置 改写成入基变量 得到新的单纯形表 转步骤三 练习 5单纯形法的进一步讨论 一 目标函数为Min的情形 三种处理方法 1令Z Z MaxZ CX 2求MinZ 当所有检验数cj zj 0时为最优 否则要迭代 换入检验数最小的那个变量 确定换出变量的方法和前面Max的情形一样 3规定检验数为zj cj 其余过程和前面Max的情形一样 5 1几种情况 其中第2 3个约束方程中无明显基变量 分别加上人工变x6 x7 二 约束方程为 或 的情形 加人工变量 这时 初始基和初始基可行解很明显 X 0 0 0 0 11 0 3 1 T不满足原来的约束条件 如何使得可从X 0 开始 经迭代逐步得到x6 0 x7 0的基可行解 从而求得问题的最优解 有两种方法 反之 若加了人工变量的问题解后最优解中仍含人工变量为基变量 便说明原问题无可行解 例8的单纯形表格为 只要原问题有可行解 随着目标函数向最大化方向的改善 人工变量一定会逐步换出基 从而得到原问题的基可行解 进而得到基最优解 5 2大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 113 21 5 3两阶段法 第一阶段 以人工变量之和最小化为目标函数 min x6 x7 第二阶段 以第一阶段的最优解 不含人工变量 为初始解 以原目标函数为目标函数 约束方程为 或 的情形 加人工变量 人工变量法 确定初始可行基 原约束方程 AX b 加入人工变量 xn 1 xn m 人工变量是虚拟变量 加入原方程中是作为临时基变量 经过基的旋转变换 将人工变量均能换成非基变量 所得解是最优解 若在最终表中检验数小于零 而且基变量中还有某个非零的人工变量 原问题无可行解 MaxZ 2x1 x2 x3s t 4x1 2x2 2x3 42x1 4x2 204x1 8x2 2x3 16x1 x2 x3 0 用两阶段法求下面线性规划问题的解 5 4线性规划问题解的讨论 一 无可行解maxz 2x1 4x2x1 x2 102x1 x2 40 x1 x2 0 人工变量不能从基底换出 此时原线性规划问题无可行解 两阶段法 例 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 而对应系数列中元素全部小于或等于零 无换出变量 则原问题有无界解 练习 写出单纯形表 分析检验数与系数关系并画图验证 线性规划解除有唯一最优解的情况外 还有如下几种情况 无可行解退化无穷多解无