资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.1,图解法,图解法不是解线性规划的主要方法,只是用于说明线性规划解的性质和特点。只能解两个变量问题。,（用图解法求解,线性规划不需要化成标准型）,图解法的步骤：,1,、约束区域的确定,2,、目标函数等值线,3,、平移目标函数等值线求最优值,2,线性规划图解法,线性规划解的几种可能情况,1,、唯一最优解,2,、无穷多最优解,3,、,无可行解,4,、,无有限最优解,(,无界解,),例,1,：,max z=2,x,1,+3x,2,s.t,.,x,1,+2x,2,8,4x,1,16,x,1,x,2,0,有唯一解,x,1,x,2,可行域,(4,2),z=14,目标函数等值线,画图步骤,：,1,、约束区域的确定,2,、目标函数等值线,3,、平移目标函数等值线求最优值,有无穷多解,线段,Q,1,Q,2,上的任意点都是最优解,x,2,x,1,x,1,+2x,2,=8,4x,2,=12,3x,1,=12,例,2 max z=2x,1,+4x,2,s.t,.x,1,+2x,2,8,4x,2,12,3x,1,12,x,1,x,2,0,Q,1,Q,2,约束条件围不成区域,(,又称矛盾方程,),无可行解,例,3,：,x,1,x,2,max z=4x,1,+3x,2,-3x,1,+2x,2,6,s.t,.-x,1,+3x,2,18,x,1,x,2,0,无有限最优解,(,无界解,),x,1,x,2,例,4,：,-3x,1,+2x,2,=6,线性规划的几何特性,：,线性规划问题若有最优解,一定在其可行域的顶点达到；,唯一最优解,必在一个顶点达到,或无穷多最优解,至少在两个顶点达到,；,无解,(,可行域为空集或目标函数无有限极值,),。,图解法得出线性规划问题解的几种情况,解的几种情况,约束条件图形特点,方程特点,唯一解,一般围成有限区域,最优值,只在一个顶点达到,无穷多解,在围成的区域边界上,至少,有两个顶点处达到最优值,目标和某一约束,方程成比例,无可行解,(,无,解,),围不成区域,有矛盾方程,无界解,(,无解,),围成无界区域,且无有限,最优值,缺少一必要条件,的方程,列向量,x=(x,1,，,x,2,，,，,x,m,）,T,为,m,维列向量。,x,R,m,线性相关,一组向量,v,1,v,n,如果有一组不全为零的系数,1,n,使得,:,1,v,1,+,n,v,n,=0,则称,v,1,v,n,是线性相关的,.,线性无关,一组向量,v,1,v,n,如果对于任何数,1,n,若要满足,:,1,v,1,+,n,v,n,=0,则必有系数,1,=,n,=0,(,全为零,),则称,v,1,v,n,线性无关,(,线,性独立,).,矩阵,A,的秩,设,A,为一个,mn,阶矩阵,(m0,的数乘（,2,）式在分别与（,1,）相加和相减，这样得到,(x,1,-,1,)P,1,+(x,2,-,2,)P,2,+(,x,m,-,m,)P,m,=b,(x,1,+,1,)P,1,+(x,2,+,2,)P,2,+(,x,m,+,m,)P,m,=b,引理,2,若,K,是有界凸集,则任何一点,XK,可表示为,K,的顶点的凸组合,.,证明略。,必要性（基可行解,顶点，用反证法）：,X,不是可行域的顶点,故可在可行域内找到两个不同的点,x,(1),x,(2),，,使得,X,=,x,(1),+(1-,)x,(2),0,m,时,有,X,j,=x,j,(1),=x,j,(2),=0,由于,x,(1),x,(2),是可行域的两点,.,应满足,P,j,x,j,(1),=b,与,P,j,x,j,(2),=b,将这两式相减,即得,P,j,(x,j,(1),-x,j,(2),)=0,因,x,(1),x,(2),所以上式系数,(x,j,(1),-x,j,(2),),不全为零,故向量,P,1,P,2,P,m,组线性相关与假设矛盾,.,即,X,不是基可行解,.,定理,3,若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优,.,证：,设,X,(1),X,(2),X,(k),是可行域的顶点,若,X,(0),不是顶点且目标函数在,X,(0),处达到最优,z,*,=CX,(0),(,设标准型是,z,*,=max z),则,X,(0),可以用顶点表示为,X,(0),=,i,X,(i,),i,0,i,=1,记,X,(1),X,(2),X,(k),中满足,max CX,(i),的顶点为,X,(m),。,于是，,由假设,CX,(0),为最优解，所以,CX,(0),=CX,(m),，,即最优解可在顶点,X,(m),达到。,注：,1,、有时目标函数可能在多个顶点处达到最大值，此时在这些顶点的凸组合处也达到最大值，称这种线性规划问题有无限多个最优解。,2,、若可行域无界，则可能无最优解，也可能有最优解，但若有，必在顶点处取得。,
展开阅读全文