《(精品)运筹学线性规划图解法.ppt》由会员分享，可在线阅读，更多相关《(精品)运筹学线性规划图解法.ppt（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2.1 图解法图解法 图解法不是解线性规划的主要方法,只是用于说明线性规划解的性质和特点。只能解两个变量问题。（用图解法求解,线性规划不需要化成标准型）图解法的步骤：1、约束区域的确定 2、目标函数等值线 3、平移目标函数等值线求最优值2 线性规划图解法线性规划图解法线性规划解的几种可能情况 1、唯一最优解 2、无穷多最优解 3、无可行解 4、无有限最优解(无界解)例1：max z=2x1+3x2 s.t.x1+2x28 4x116 x1,x20有唯一解x1x2可行域(4,2)z=14目标函数等值线画图步骤画图步骤：1、约束区域的确定 2、目标函数等值线3、平移目标函数等值线求最优值有无穷多解
2、线段Q1Q2上的任意点都是最优解x2x1x1+2x2=84x2=123x1=12例2 max z=2x1+4x2 s.t.x1+2x28 4x2 12 3x1 12 x1,x2 0Q1Q2约束条件围不成区域(又称矛盾方程)无可行解例3：x1x2max z=4x1+3x2 -3x1+2x26 s.t.-x1+3x218 x1,x2 0无有限最优解(无界解)x1 x2例4：-3x1+2x2=6线性规划的几何特性线性规划的几何特性线性规划的几何特性线性规划的几何特性：线性规划问题若有最优解,一定在其可行域的顶点达到；唯一最优解必在一个顶点达到 或无穷多最优解至少在两个顶点达到；无解(可行域为空集或目
3、标函数无有限极值)。图解法得出线性规划问题解的几种情况解的几种情况约束条件图形特点方程特点唯一解一般围成有限区域,最优值只在一个顶点达到无穷多解在围成的区域边界上,至少有两个顶点处达到最优值目标和某一约束方程成比例无可行解(无解)围不成区域有矛盾方程无界解(无解)围成无界区域,且无有限最优值缺少一必要条件的方程列向量列向量 x=(x1，x2，xm）T为m维列向量。xRm线性相关线性相关 一组向量v1,vn,如果有一组不全为零的系数 1,n,使得:1 v1+nvn=0 则称v1,vn 是线性相关的.线性无关线性无关 一组向量v1,vn,如果对于任何数1,n,若要满足:1 v1+nvn=0,则必有
4、系数 1=n=0,(全为零)则称v1,vn线性无关(线 性独立).矩阵矩阵A A的秩的秩 设A为一个mn阶矩阵(m0的数乘（2）式在分别与（1）相加和相减，这样得到(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)Pm=b引理引理2 2 若若K K是有界凸集是有界凸集,则任何一点则任何一点XKXK可表示为可表示为K K的顶点的凸组合的顶点的凸组合.证明略。必要性（基可行解顶点，用反证法）：X不是可行域的顶点,故可在可行域内找到两个不同的点x(1),x(2)，使得X=x(1)+(1-)x(2),0m时,有X j=xj(1)=xj(2)=0,由
5、于x(1),x(2)是可行域的两点.应满足Pjxj(1)=b 与 Pjxj(2)=b将这两式相减,即得 Pj(xj(1)-xj(2)=0因x(1)x(2),所以上式系数(xj(1)-xj(2)不全为零,故向量P1,P2,Pm组线性相关与假设矛盾.即X不是基可行解.定理定理定理定理3 3 3 3 若可行域有界若可行域有界,线性规划问题的目标函数一定可以线性规划问题的目标函数一定可以在其可行域的顶点上达到最优在其可行域的顶点上达到最优.证证：设X(1),X(2),X(k)是可行域的顶点,若X(0)不是顶点且目标函数在X(0)处达到最优 z*=CX(0)(设标准型是z*=max z),则X(0)可以用顶点表示为 X(0)=iX(i)i0,i=1记X(1),X(2),X(k)中满足max CX(i)的顶点为X(m)。于是，由假设CX(0)为最优解，所以CX(0)=CX(m)，即最优解可在顶点X(m)达到。注：1、有时目标函数可能在多个顶点处达到最大值，此时在这些顶点的凸组合处也达到最大值，称这种线性规划问题有无限多个最优解。2、若可行域无界，则可能无最优解，也可能有最优解，但若有，必在顶点处取得。