第二章 线性规划解的概念、性质及图解法ppt课件.ppt

图解法 线性规划问题求解的 几种可能结果由图解法得到的启示,2.2 线性规划解的概念、性质及图解法,例1的数学模型,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,x1,x2,9 8 7 6 5 4 3 2 1 0,|123456789,x1,x2,x1 + 2x2 8,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,4x1 16,4 x2 12,图解法,可行域,步骤一：由全部约束条件作图求出可行域；,9 8 7 6 5 4 3 2 1 0,|123456789,x1,x2,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,可行域,图解法,B,9 8 7 6 5 4 3 2 1 0,x2,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,2x1 + 3x2 = 6,图解法,步骤二：作目标函数等值线，确定使目标函数最优的移动方向；,9 8 7 6 5 4 3 2 1 0,x2,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,图解法,x1+ 2x2=8 4x1 =16,Max Z=14,步骤三：平移目标函数的等值线，找出最优点，算出最优值。,图解法求解步骤,由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。,9 8 7 6 5 4 3 2 1 0,x2,改变约束条件或目标函数，解的结果如何？,线性规划问题求解的 几种可能结果,(a) 唯一最优解,9 8 7 6 5 4 3 2 1 0,x2,线性规划问题求解的 几种可能结果,x1 + 2x2 = 8,目标函数 Max Z = x1 + 2x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,(b)无穷多最优解,(c)无界解 Max Z = x1 + x2 -2x1 + x2 4 x1 - x2 2 x1、 x2 0,x1,线性规划问题求解的 几种可能结果,(d)无可行解 Max Z = 2x1 + 3x2 x1 +2 x2 8 4 x1 16 4x2 12 -2x1 + x2 4 x1、 x2 0可行域为空集,线性规划问题求解的 几种可能结果,图解法的几点结论:（由图解法得到的启示）,可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。,练习：用图解法求解LP问题,max z = 15x1 +25x2s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0,L1,Z=250,目标函数变形：,x2=-3/5 x1+z/25,x2,x1,最优解： x1=30 x2 =10最优值：zmax=700,B点是使z达到最大的唯一可行点,(30,10),A（0,20）,C（40, 0）,0,B,习题：用图解法求下列线性规划:,习题2max z = 2x1 + 2x2 s.t. 2x1 x2 2 -x1 + 4x2 4 x1，x2 0,习题3max z = 2x1 + 2x2 s.t. x1 + x2 1 x1 3x2 3 x1 3 x1，x2 0,习题4max z = 5x1 + 3x2 s.t. x1 + x2 1 x1 + 2x2 4 x1，x2 0,O,x1,x2,Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。,A(1,0),可行域为无界区域一定无最优解吗？,max z = 2x1 + 2x2 s.t. 2x1 x2 2 -x1 + 4x2 4 x1，x2 0,习题：用图解法求下列线性规划:,0,x1,x2,A (1,0),minZ,(多解)线段AD上的任一点都是最优解minZ = 2,习题3max z = 2x1 + 2x2 s.t. x1 + x2 1 x1 3x2 3 x1 3 x1，x2 0,(30,10),B(3,0),C(3,2),D(0,1),若min Z 换为max Z则最优解为?点,0,x1,x2,A (1,0),(30,10),B(4,0),D(0,1),习题4max z = 5x1 + 3x2 s.t. x1 + x2 1 x1 + 2x2 4 x1，x2 0,C(0,2),无可行解,根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况 1.可行域为封闭的有界区域 (a)有唯一的最优解； (b)有无穷多个最优解； 2.可行域为非封闭的无界区域 (c)有唯一的最优解；(d)有无穷多个最优解； (e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。 3.可行域为空集 (f)没有可行解，原问题无最优解,二、线性规划解的有关概念,可行解、最优解基、基变量、非基变量基本解、基本可行解可行基、最优基,Ax=b，x0；,1.可行解与最优解,极点,定义1 设集合 是 n 维欧氏空间中的一个点集，如果 及实数,则称 S 是一个凸集。,几何意义：如果集合中任意两点连线上的一切点都在 该集合中，则称该集合为凸集。,凸集,定义 2 设 则称,为点 的一个凸组合。,的可行域以及最优解有以下性质:,1.若线性规划的可行域非空，则可行域必定为一凸集2.若线性规划的可行域非空，则至多有有限个极点.3.若线性规划有最优解,则至少有一个极点是最优解.,1.图解法求解步骤,由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。,小结：,1.可行域为封闭的有界区域 (a)有唯一的最优解； (b)有无穷多个最优解； 2.可行域为非封闭的无界区域 (c)有唯一的最优解；(d)有无穷多个最优解； (e)目标函数无界(即虽有可行解，但在 可行域中，目标函数可以无限增大或无限 减少)，因而没有有限最优解。 3.可行域为空集 (f)没有可行解，原问题无最优解,2.线性规划的可行域和最优解,Ax=b，x0；,3.可行解与最优解,1.若线性规划的可行域非空，则可行域必定为一凸集2.若线性规划的可行域非空，则至多有有限个极点.3.若线性规划有最优解,则至少有一个极点是最优解.,4.线性规划的可行域和最优解的性质,2.线性规划的基、基本解 与基本可行解,在一般情况下，由于图解法无法解决三个变量以上的线性规划问题，对于n个变量的线性规划问题，我们必须用解方程的办法来求得可行域的极点。再来进一步考察前例。,2.线性规划的基、基本解 与基本可行解,例2.8 把例2.1的线性规划模型标准化，引入松驰变量 x3 ，x4 ，x5 0，得到Max z = 1500 x1 + 2500 x2s.t. 3x1+2x2+x3= 65 (A) 2x1+x2+x4= 40 (B) 3x2+x5= 75 (C) x1 ,x2 ,x3 ,x4 ,x5 0 用（D）（E）（F）（G）（H）分别表示x1 = 0、x2 = 0、x3 = 0、x4 = 0、x5 = 0 。这里一共有8个约束条件，其中3个等式约束（一般情况下，等式约束的个数少于决策变量的个数），5个变量非负约束（与决策变量个数相同）。每5个方程若线性无关可解得一个点，我们可以看到前例图解法得到的区域中每两条直线的交点与此例的各个方程有如下关系：见下图。,由上图可以看出： 直线A、B的交点对应于约束条件(A)、（B）、（C）、（F）、（G）的解，即：x(1) = (15,10,0,0,45)T 直线A、C的交点对应于约束条件(A)、（B）、（C）、（F）、（H）的解，即：x(2) = (5,25,0,5,0)T 直线A、D的交点对应于约束条件(A)、（B）、（C）、（D）、（F）的解，即：x(3) = (0,32.5,0,7.5,-22.5)T,Max z = 1500 x1 + 2500 x2s.t. 3x1+2x2+x3= 65 (A) 2x1+x2+x4= 40 (B) 3x2+x5= 75 (C) x1 ,x2 ,x3 ,x4 ,x5 0 用（D）（E）（F）（G）（H）分别表示x1 = 0、x2 = 0、x3 = 0、x4 = 0、x5 = 0 。,X(1),X(2),X(3),D,E,直线A、E的交点对应于约束条件(A)、（B）、（C）、（E）、（F）的解，即：x(4) = (65/3,0,0,-10/3,75)T 直线B、C的交点对应于约束条件(A)、（B）、（C）、（G）、（H）的解，即：x(5) = (7.5,25,-7.5,0,0)T 直线B、D的交点对应于约束条件(A)、（B）、（C）、（D）、（G）的解，即：x(6) = (0,40,-15,0,-45)T,E,D,X(5),X(6),直线B、E的交点对应于约束条件(A)、（B）、（C）、（E）、（G）的解，即：x(7) = (20,0,5,0,75)T 直线C、D的交点对应于约束条件(A)、（B）、（C）、（D）、（H）的解，即：x(8) = (0,25,15,15,0)T 直线C、E无交点（C、E相互平行） 直线D、E的交点对应于约束条件(A)、（B）、（C）、（D）、（E）的解，即：x(9) = (0,0,65,40,75)T,E,X(8),X(9),如果某一交点的坐标 (x1 , x2 , x3 , x4 , x5 )T全为非负，则该交点就对应于线性规划可行域的一个极点（如A、B，A、C，B、E，C、D和D、E的交点，共5个）如果某一交点的坐标中至少有一个分量为负值（如A、D，A、E，B、C和B、D的交点），则该交点不是可行域的极点。,E,定义 线性规划的约束条件： Ax=b，x0； A 是mn矩阵，mn 并且r(A)=m。,（1）线性规划的基,基 (basis)： B 是A中的一个非奇异（可逆）的 mm子矩阵，即|B|0 ，则称B是线性规划的一个基(或基矩阵)。,行满秩的矩阵,基向量：基B中的列 pj (j=1,2,m);,基变量：与基向量对应的决策变量 xj (j=1,2,m) ；,非基变量：与非基向量对应的决策变量 xj (j= m+1,n),非基向量：A中除基向量外，其余的列pj (j= m+1,n);,（1）线性规划的基,任取A中的m个线性无关列向量构成矩阵B，则B是A的一个基；,【解】约束方程的系数矩阵为24矩阵,容易看出r(A)=2，2阶可逆子矩阵最多有几个？,C42=6,基向量： p1和p2,基变量：x1和x2 ，,基向量： p3和p4,基变量： x3 和x4,基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。,非基向量： p3和p4,非基向量： p1和p2,非基变量：x1和x2,非基变量：x3和x4,若B是线性规划的一个基，设是A的前m列，则A可以表示为 A =B , N ，x也可相应地分成 xB x= xN其中:xB为m维列向量，它的各分量称为基变量， 与基B 的列向量对应； xN为n-m维列向量，它的各分量称为非基变量， 与非基矩阵N的列向量对应。,（2）基本解、基本可行解和可行基,基矩阵,这时约束等式Ax=b可表示为,求解,基变量,令非基变量,基本解： 称由约束 求出的X解为基本解。,矩阵描述为，对于线性规划的解 xB B-1b x= = xN 0,称为线性规划与基B 对应的基本解。 若其中B-1b 0，则称以上的基本解为一基本可行解（即非负的基本解），相应的基B称为可行基。,系数阵A中可找出多个基B,非负的基本解就是基本可行解,每个基B都对应于一个基本解,注意：线性规划的基本解、基本可行解和可行基只与线性规划问题标准形式的约束条件有关。与目标函数无关。,线性规划解的关系图,非可行解,可行解,基本可行解,基本解,结论：线性规划的基本可行解就是可行域的极点。,最优解？,求相应于B1和B6的基本解，是否基本可行解？,相应于基B6的基本解为X=(0,0,1,3)，是基本可行解.,相应于基B1的基本解为X=(7/5,-1/5,0,0)，不是基本可行解.,线性规划的基本定理“线性规划的基本可行解就是可行域的极点”线性规划的基本定理这一基本定理把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。这里指出了一种求解线性规划问题的可能途径，就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的,因此必定可以从有限个基本可行解中找到最优解。,1、线性规划的基,基 (basis)： B 是A中的一个非奇异（可逆）的 mm子矩阵，即|B|0 ，则称B是线性规划的一个基(或基矩阵)。,小结：,基向量：基B中的列 pj (j=1,2,m);,基变量：与基向量对应的决策变量 xj (j=1,2,m) ；,非基变量：与非基向量对应的决策变量 xj (j= m+1,n),非基向量：A中除基向量外，其余的列pj (j= m+1,n);,基本可行解：若其中B-1b 0，则称以上的基本解为一基本可行解（即非负的基本解），相应的基B称为可行基。,2.线性规划的基本解与基本可行解,非负的基本解就是基本可行解,系数阵A中可找出多个基B,每个基B都对应于一个基本解,线性规划解的关系图,非可行解,可行解,基本可行解,基本解,最优解？,可行解&最优解 ?,最优解一定是可行解，但可行解不一定是最优解。,线性规划解的关系图,非可行解,可行解,基本可行解,基本解,最优解？,基本解不一定是可行解，可行解也不一定是基本解。,可行解&基本解?,线性规划解的关系图,非可行解,可行解,基本可行解,基本解,最优解？,可行解&基本可行解?,基本可行解一定是可行解，但可行解不一定是基本可行解。,线性规划解的关系图,非可行解,可行解,基本可行解,基本解,最优解？,基本解&基本可行解?,基本可行解一定是基本解，但基本解不一定是基本可行解。,线性规划解的关系图,非可行解,可行解,基本可行解,基本解,最优解？,最优解&基本解?,最优解一定是基本解，基本解不一定是最优解。,线性规划解的关系图,非可行解,可行解,基本可行解,基本解,最优解？,最优解&基本可行解?,最优解一定是基本可行解，但基本可行解不一定是最优解。,线性规划的基本定理“线性规划的基本可行解就是可行域的极点”线性规划的基本定理,1 可行解与最优解：,最优解一定是可行解，但可行解不一定是最优解。,基本解不一定是可行解，可行解也不一定是基本解。,2 可行解与基本解：,3 可行解与基本可行解：,基本可行解一定是可行解，但可行解不一定是基本解。,基本可行解一定是基本解，但基本解不一定是基本可行解。,4 基本解与基本可行解：,5 最优解与基本解：,最优解一定是基本解，基本解不一定是最优解。,