《1线性规划问题的图解法-四维空间展开.ppt》由会员分享,可在线阅读,更多相关《1线性规划问题的图解法-四维空间展开.ppt(21页珍藏版)》请在三一文库上搜索。
1、线性规划问题的图解法,满足约束条件的变量的值, 称为可行解. 所有可行解构成的集合称为可行域. 使目标函数取得最优值的可行解, 称为最优解. 不存在可行解的LP问题称该LP问题无解, 其可域行为空集.,1、线性规划问题解的概念,例1 解下面的LP问题 max S=50x1+30x2 s.t. 4x1+3x2 120 2x1+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,
2、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 50 4x1+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,2
3、0,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(目标函数)值达到最大: max s=50*15+30*20=1350 此时最优解=(15,20),Q2(15,20),可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,例2 解下面的LP问题,ma
4、x z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,满足约束条件的可行域一般都构成凸多边形.这一事实可以推广到更多变量的场合. 最优解必定能在凸多边形的某一个顶点上取得,这一事实也可以推广到更多变量的场合.,二个重要结论:,1. 最优解是唯一解,解的讨论:,例1 max S=50x1+30x2 s.t. 4x1+3x2 120 2x1+x2 50 x1, x2 0,(15, 20),例1的目标函数由 max s=50x1+30x2 变成: max s=40x1+30x2 s.t. 4x1+3x2 120 2x1+x2 50 x1, x2 0,2. 无穷多组最优
5、解,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),例: max s=x1+x2 s.t. -2x1+x2 40 x1-x2 20 x1, x2 0,3. 无界解,x2,50,40,30,20,10,10,20,30,40,x1,该可行域无界,目标函数值可增加到无穷大,称这种情况为无界解或无最优解.,例: max s=2x1+3x2 s.t. x1+2x2 8 x1 4 x2 3 -2x1+x2 4 x1, x2 0,该问题可行域为空集,即无可行解,也不存在最优解.,4. 无可行解,解的情况: 有可行解 有唯一最优解 有无穷最优解 无最优解 无可行解,
链接地址:https://www.31doc.com/p-3405146.html