1、线性规划问题的图解法四维空间展开线性规划问题的图解法四维空间展开例例1 解下面的解下面的LP问题问题 max S=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1,x2 0第1页/共21页x2504030201010203040 x1第2页/共21页x2504030201010203040 x12x1+x2 50由由2x1+x2 50 x1 0 x2 0围成的区域围成的区域第3页/共21页x2504030201010203040 x14x1+3x2 120同时满足同时满足:2x1+x2 504x1+3x2 120 x1 0 x2 0的区域的区域可行域可行域第4页
2、/共21页x2504030201010203040 x1O(0,0)Q1(25,0)Q2(15,20)Q3(0,40)可行域是由约束条件围成的区域可行域是由约束条件围成的区域,该区该区域内的每一点都是可行解域内的每一点都是可行解,的全体组成的全体组成问题的解集合问题的解集合.该问题的可行域是由该问题的可行域是由O,Q1,Q2,Q3作为作为顶点的顶点的凸多边形凸多边形第5页/共21页x2504030201010203040 x1目标函数是以目标函数是以s作作为参数的一组平行为参数的一组平行线线x2=s/30-(5/3)x1第6页/共21页x2504030201010203040 x1当当S值不断
3、增加时值不断增加时,该直线该直线x2=S/30-(5/3)x1沿着其法线方向向右上方沿着其法线方向向右上方移动移动.第7页/共21页x2504030201010203040 x1当该直线移到当该直线移到Q2点时点时,s(目目标函数标函数)值达到最大值达到最大:max s=50*15+30*20=1350此时最优解此时最优解=(15,20)Q2(15,20)第8页/共21页可行域可行域目标函数等值目标函数等值线线最优最优解解64-860 x1x2例例2 解下面的解下面的LP问题问题第9页/共21页满足约束条件的可行域一般都构成凸多边形满足约束条件的可行域一般都构成凸多边形.这一事实这一事实可以推
4、广到更多变量的场合可以推广到更多变量的场合.最优解必定能在凸多边形的某一个顶点上取得最优解必定能在凸多边形的某一个顶点上取得,这一事这一事实也可以推广到更多变量的场合实也可以推广到更多变量的场合.第10页/共21页例例1 max S=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1,x2 0第11页/共21页例例1的目标函数由的目标函数由 max s=50 x1+30 x2变成变成:max s=40 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1,x2 0第12页/共21页x2504030201010203040 x1第13页/共21
5、页x2504030201010203040 x1Q1(25,0)Q2(15,20)第14页/共21页例例:max s=x1+x2 s.t.-2x1+x2 40 x1-x2 20 x1,x2 0第15页/共21页x2504030201010203040 x1该可行域无界该可行域无界,目标函数值可增加目标函数值可增加到无穷大到无穷大,称这种情况为无界解或称这种情况为无界解或无最优解无最优解.第16页/共21页例例:max s=2x1+3x2 s.t.x1+2x2 8 x1 4 x2 3 -2x1+x2 4 x1,x2 0该问题可行域为空集该问题可行域为空集,即无即无可行解可行解,也不存在最优解也不存在最优解.第17页/共21页解的情况解的情况:有可行解有可行解有唯一最优解有唯一最优解有无穷最优解有无穷最优解无最优解无最优解无可行解无可行解第18页/共21页第19页/共21页第20页/共21页
