运筹学线性规划图解法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.1 图解法,图解法不是解线性规划的主要方法,只是用于说明线性规划解的性质和特点。只能解两个变量问题。,（用图解法求解,线性规划不需要化成标准型）,图解法的步骤：,1、约束区域的确定,2、目标函数等值线,3、平移目标函数等值线求最优值,2 线性规划图解法,线性规划解的几种可能情况,1、唯一最优解,2、无穷多最优解,3,、,无可行解,4、,无有限最优解(无界解),1,例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、平移目标函数等值线求最优值,2,有无穷多解,线段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,约束条件围不成区域,(又称矛盾方程),无可行解,例3：,x,1,x,2,4,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,5,线性规划的几何特性,：,线性规划问题若有最优解,一定在其可行域的顶点达到；,唯一最优解,必在一个顶点达到,或无穷多最优解,至少在两个顶点达到,；,无解(可行域为空集或目标函数无有限极值)。,6,图解法得出线性规划问题解的几种情况,解的几种情况,约束条件图形特点,方程特点,唯一解,一般围成有限区域,最优值,只在一个顶点达到,无穷多解,在围成的区域边界上,至少,有两个顶点处达到最优值,目标和某一约束,方程成比例,无可行解,(,无,解,),围不成区域,有矛盾方程,无界解,(,无解,),围成无界区域,且无有限,最优值,缺少一必要条件,的方程,7,列向量,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,17,引理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,不是基可行解.,18,定理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),达到。,19,注： 1、有时目标函数可能在多个顶点处达到最大值，此时在这些顶点的凸组合处也达到最大值，称这种线性规划问题有无限多个最优解。,2、若可行域无界，则可能无最优解，也可能有最优解，但若有，必在顶点处取得。,20,