线性规划(图解法).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,Page,*,图解法,线性规划问题的求解方法,一 般 有,两种方法,图 解 法,单纯形法,两个变量、直角坐标,三个变量、立体坐标,适用于任意变量、但必需将,一般形式变成标准形式,下面我们分析一下简单的情况,只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。,图解法,一、线性规划的图解法（解的几何表示）,对于只有两个变量的线性规划问题，可以在二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。,图解法求解线性规划问题的步骤如下：,（,1,）分别取决策变量,x,1,，,x,2,为坐标向量建立直角坐标系；,图解法,（,2,）对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过判断确定不等式所决定的半平面。各约束半平面交出来的区域,（存在或不存在）,，若存在，其中的,点表示的解,称为此线性规划的,可行解,。这些,符合约束限制的点集合,，称为,可行集或可行域。,进行（,3,）；否则该线性规划问题无可行解。,图解法,（,3,）任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置（有时,交于无穷远处，此时称无有限最优解,）。若有交点时，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。,图解法,图解法简单、直观,，,便于初学者了解线性规划基本原理和几何意义,；,例,2,.,10,用图解法求解线性规划问题,max,:,z,=50,x,1,+30,x,2,s.t.,4,x,1,+3,x,2,120,2,x,1,+,x,2,50,x,1,0，,x,2,0,图解法,x,2,x,1,40,50,30,2,x,1,+,x,2,50,20,10,10,20,30,4,x,1,+3,x,2,120,z,=50 x,1,+30,x,2,=600,z,=50 x,1,+30,x,2,=900,z,=50 x,1,+30,x,2,=1350,(15,20),图解法,图解法的观察（一）,有效与无效,(,紧与松,),约束：与最优解相关的约束为有效,(,紧,),约束,。,最优解：总是在可行域的边界上，一般由可行域的顶点表示。,可行域：由约束平面围起来的凸多边形区域，可行域内的每一个点代表一 个可行解。,图解法,例,2,.,11,用,图解法求解,max,z,=,x,1,+,x,2,s.t.,x,1,+2,x,2,4,x,1,-2,x,2,5,x,1,x,2,0,无可行解的线性规划问题,图解法,1,4,2,3,5,1,2,3,x,1,x,2,x,1,+2,x,2,4,x,1,-2,x,2,5,图解法,例,2.12,用图解法求解：,max,z=2x,1,+x,2,s.t.x,1,+x,2,2,x,1,-2x,2,0,x,1,x,2,0,无界的线性规划问题,图解法,1,4,2,3,5,1,2,3,x,1,x,2,x,1,+,x,2,2,z,=2,x,1,+,x,2,x,1,-2,x,2,0,图解法,如果目标函数线平行与一个约束线，线性规划问题有无穷多最优解。,例,2,.,13,用图解法求解：,max,z,=40,x,1,+30,x,2,s.t.,4,x,1,+3,x,2,120,2,x,1,+,x,2,50,x,1,0，,x,2,0,存在无穷多最优解,图解法,x,2,x,1,40,50,30,2,x,1,+,x,2,50,20,10,10,20,30,4,x,1,+3,x,2,120,z,=40 x,1,+30,x,2,图解法,图解法的观察（二）,如果可行域为空集，线性规划 问题无可行解；,如果目标函数等值线可以无限制地在可行域内向改善 的方向移动，线性规划问题无界,;,线性规划问题也可能存在无穷多个最优解。,图解法,max Z=2X,1,+X,2,X,1,+1.9X,2,3.8,X,1,-1.9X,2,3.8,s.t,.X,1,+1.9X,2,10.2,X,1,-1.9X,2,-3.8,X,1,，,X,2,0,例,1.5,用图解法求解线性规划问题,图解法,x,1,x,2,o,X,1,-1.9X,2,=3.8,(),X,1,+1.9X,2,=3.8(,),X,1,-1.9X,2,=-3.8(,),X,1,+1.9X,2,=10.2,(),4=2,X,1,+X,2,20=2,X,1,+X,2,17.2=2,X,1,+X,2,11=2,X,1,+X,2,Lo,：,0=2X,1,+X,2,（,7.6,，,2,）,D,max Z,min Z,此点是唯一最优解，,且最优目标函数值,max Z=17.2,可行域,max Z=2X,1,+X,2,图解法,max Z=3X,1,+5.7X,2,x,1,x,2,o,X,1,-1.9X,2,=3.8,(),X,1,+1.9X,2,=3.8(,),X,1,-1.9X,2,=-3.8(,),X,1,+1.9X,2,=10.2,(),（,7.6,，,2,）,D,L,0,：0=3X,1,+5.7X,2,max Z,（,3.8,，,4,）,34.2,=3,X,1,+5.7X,2,蓝色线段上的所有点都是最,优解这种情形为有无穷多最,优解，但是最优目标函数值,max Z=34.2,是唯一的。,可行域,图解法,min Z=5X,1,+4X,2,x,1,x,2,o,X,1,-1.9X,2,=3.8,(),X,1,+1.9X,2,=3.8(,),X,1,+1.9X,2,=10.2,(),D,L,0,：0=5X,1,+4X,2,max Z,min Z,8=5X,1,+4X,2,43=5X,1,+4X,2,（,0,，,2,）,可行域,此点是唯一最优解,图解法,2,4,6,x,1,x,2,2,4,6,无界解,(,无最优解,),max,Z,=,x,1,+2,x,2,例,1.6,x,1,+x,2,=4(),x,1,+3x,2,=6(),3x,1,+x,2,=6(),max Z,min Z,x,1,x,2,O,10,20,30,40,10,20,30,40,50,50,无可行解,(,即无最优解,),max Z=3,x,1,+4,x,2,例,1.7,图解法,学习要点：,1.,通过图解法了解线性规划有几种解的形式,（唯一最优解；无穷多最优解；无界解；无可行解）,2.,作图的关键有三点：,(1),可行解区域要画正确,(2),目标函数增加的方向不能画错,(3),目标函数的直线怎样平行移动,单纯形法基本原理,凸集：如果集合,C,中任意两个点,X,1,、,X,2,，其连线上的所有点也都是集合,C,中的点，称,C,为凸集。,凸集,凸集,不是凸集,顶 点,图解法,在凸集中，不能表示为不同点的凸组合的点,称为凸集的极点，用严格的定义描述如下。,定义,3,设,C,为一凸集，如果,C,中不存在任何两个不同的点,X,1,、,X,2,，使得,X,成为这两个点连线上的一个点，即,X,S,，,X,1,S,，,X,2,S,。如果对于,0,1,，若,X=,X,1,+(1-,)X,2,则必定有,X=X,1,=X,2,，,则称,X,为,S,的一个,顶点,。,图解法,可以证明，线性规划的可行域以及最优解有以下性质：,（,1,）、若线性规划的,可行域非空,，则可行域,必定为一凸集,；,（,2,）、线性规划问题的基本可行解对应于可行域的,顶点,；,（,3,）、若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优，或在可行域的,某个顶点,（唯一最优解）或在,某两个顶点及其连线上,（无穷多最优解）得到。,