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

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