线性规划问题的图解法-四维空间展开.ppt

线性规划问题的图解法 满足约束条件的变量的值 称为可行解 所有可行解构成的集合称为可行域 使目标函数取得最优值的可行解 称为最优解 不存在可行解的LP问题称该LP问题无解 其可域行为空集 1 线性规划问题解的概念 例1解下面的LP问题maxS 50 x1 30 x2s t 4x1 3x2 1202x1 x2 50 x1 x2 0 2 图解法求解线性规划问题 x2 50 40 30 20 10 10 20 30 40 x1 4x1 3x2 120 由4x1 3x2 120 x1 0 x2 0围成的区域 x2 50 40 30 20 10 10 20 30 40 x1 2x1 x2 50 由2x1 x2 50 x1 0 x2 0围成的区域 x2 50 40 30 20 10 10 20 30 40 x1 2x1 x2 50 4x1 3x2 120 可行域 同时满足 2x1 x2 504x1 3x2 120 x1 0 x2 0的区域 可行域 x2 50 40 30 20 10 10 20 30 40 x1 可行域 O 0 0 Q1 25 0 Q2 15 20 Q3 0 40 可行域是由约束条件围成的区域 该区域内的每一点都是可行解 的全体组成问题的解集合 该问题的可行域是由O Q1 Q2 Q3作为顶点的凸多边形 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目标函数是以s作为参数的一组平行线x2 s 30 5 3 x1 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当S值不断增加时 该直线x2 S 30 5 3 x1沿着其法线方向向右上方移动 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当该直线移到Q2点时 s 目标函数 值达到最大 maxs 50 15 30 20 1350此时最优解 15 20 Q2 15 20 可行域 目标函数等值线 最优解 6 4 8 6 0 x1 x2 例2解下面的LP问题 maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 满足约束条件的可行域一般都构成凸多边形 这一事实可以推广到更多变量的场合 最优解必定能在凸多边形的某一个顶点上取得 这一事实也可以推广到更多变量的场合 二个重要结论 1 最优解是唯一解 解的讨论 例1maxS 50 x1 30 x2s t 4x1 3x2 1202x1 x2 50 x1 x2 0 15 20 例1的目标函数由maxs 50 x1 30 x2变成 maxs 40 x1 30 x2s t 4x1 3x2 1202x1 x2 50 x1 x2 0 2 无穷多组最优解 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目标函数是同约束条件 4x1 3x2 120平行的直线x2 S 30 4 3 x1 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当S的值增加时 目标函数同约束条件 4x1 3x2 120重合 Q1与Q2之间都是最优解 Q1 25 0 Q2 15 20 例 maxs x1 x2s t 2x1 x2 40 x1 x2 20 x1 x2 0 3 无界解 x2 50 40 30 20 10 10 20 30 40 x1 该可行域无界 目标函数值可增加到无穷大 称这种情况为无界解或无最优解 例 maxs 2x1 3x2s t x1 2x2 8x1 4x2 3 2x1 x2 4x1 x2 0 该问题可行域为空集 即无可行解 也不存在最优解 4 无可行解 解的情况 有可行解有唯一最优解有无穷最优解无最优解无可行解