单纯形法-人工变量法.ppt

人工变量的引入及其解法当约束条件为 型 引入剩余变量和人工变量 由于所添加的剩余变量的技术系数为 1 不能作为初始可行基变量 为此引入一个人为的变量 注意 此时约束条件已为 型 以便取得初始基变量 故称为人工变量由于人工变量在原问题的解中是不能存在的 应尽快被迭代出去 因此人工变量在目标函数中对应的价值系数应具有惩罚性 称为罚系数 罚系数的取值视解法而定两种方法大M法二阶段法 其中第2 3个约束方程中无明显基变量 分别加上人工变量x6 x7 约束方程为 或 的情形 加人工变量 这时 初始基和初始基可行解很明显 X 0 0 0 0 11 0 3 1 T不满足原来的约束条件 如何使得可从X 0 开始 经迭代逐步得到x6 0 x7 0的基可行解 从而求得问题的最优解 有两种方法 反之 若加了人工变量的问题解后最优解中仍含人工变量为基变量 便说明原问题无可行解 例的单纯形表格为 只要原问题有可行解 随着目标函数向最大化方向的改善 人工变量一定会逐步换出基 从而得到原问题的基可行解 进而得到基最优解 大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 两阶段法 第一阶段 以人工变量之和最小化为目标函数 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 用两阶段法求下面线性规划问题的解 线性规划问题解的讨论 一 无可行解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 而对应系数列中元素全部小于或等于零 无换出变量 则原问题有无界解 练习 写出单纯形表 分析检验数与系数关系并画图验证 线性规划解除有唯一最优解的情况外 还有如下几种情况 无可行解退化无穷多解无界解 人工变量不能从基底中换出 基可行解中非零元素个数小于基变量数