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

满足约束条件的变量的值,称为可行解.所有可行解构成的集合称为可行域.使目标函数取得最优值的可行解,称为最优解.不存在可行解的LP问题称该LP问题无解,其可域行为空集.1、线性规划问题解的概念线性规划问题的图解法

例1解下面的LP问题maxS=50x1+30x2s.t.4x1+3x2?1202x1+x2?50x1,x2?02、图解法求解线性规划问题

x25040302010x14x1+3x2?120由4x1+3x2?120x1?0x2?0围成的区域

x25040302010x12x1+x2?50由2x1+x2?50x1?0x2?0围成的区域

x25040302010x12x1+x2?504x1+3x2?120可行域同时满足:2x1+x2?504x1+3x2?120x1?0x2?0的区域—可行域

x25040302010x1可行域O(0,0)Q1(25,0)Q2(15,20)Q3(0,40)可行域是由约束条件围成的区域,该区域内的每一点都是可行解,的全体组成问题的解集合.该问题的可行域是由O,Q1,Q2,Q3作为顶点的凸多边形

x25040302010x1可行域目标函数是以s作为参数的一组平行线x2=s/30-(5/3)x1

x25040302010x1可行域当S值不断增加时,该直线x2=S/30-(5/3)x1沿着其法线方向向右上方移动.

x25040302010x1可行域当该直线移到Q2点时,s(目标函数)值达到最大:maxs=50*15+30*20=1350此时最优解=(15,20)Q2(15,20)

例2解下面的LP问题可行域目标函数等值线最优解64-860x1x2max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0

满足约束条件的可行域一般都构成凸多边形.这一事实可以推广到更多变量的场合.最优解必定能在凸多边形的某一个顶点上取得,这一事实也可以推广到更多变量的场合.二个重要结论:优解是唯一解例1maxS=50x1+30x2s.t.4x1+3x2?1202x1+x2?50x1,x2?0(15,20)解的讨论:

maxs=50x1+30x2变成:maxs=40x1+30x2s.t.4x1+3x2?1202x1+x2?50x1,x2?0例1的目标函数由2.无穷多组最优解

x25040302010x1可行域目标函数是同约束条件:4x1+3x2?120平行的直线x2=S/30-(4/3)x1

x25040302010x1可行域当S的值增加时,目标函数同约束条件:4x1+3x2?120重合,Q1与Q2之间都是最优解.Q1(25,0)Q2(15,20)

例:maxs=x1+x2s.t.-2x1+x2?40x1-x2?20x1,x2?0无界解0102

x25040302010x1该可行域无界,目标函数值可增加到无穷大,称这种情况为无界解或无最优解.

4.无可行解该问题可行域为空集,即无可行解,也不存在最优解.s.t.x1+2x2?8x1?4x2?3例:maxs=2x1+3x201x1,x2?02x1+x2?402

01解的情况:有可行解02有唯一最优解03有无穷最优解04无最优解无可行解