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

上页上页上页上页下页下页下页下页返回返回返回返回v 图解法图解法v 线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果v由图解法得到的启示由图解法得到的启示 2.2 线性规划解的概念、性质线性规划解的概念、性质及图解法及图解法继续继续继续继续返回返回返回返回上页上页上页上页下页下页下页下页返回返回返回返回上页上页上页上页下页下页下页下页返回返回返回返回例例1的数学模型的数学模型 目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0 x1 x2上页上页上页上页下页下页下页下页返回返回返回返回9 8 7 6 5 4 3 2 1 0|123456789x1x2x1+2x2 8(0,4)(8,0)目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 04x1 164 x2 12v图解法图解法可行域可行域步骤步骤步骤步骤一：一：一：一：由全由全由全由全部约部约部约部约束条束条束条束条件作件作件作件作图求图求图求图求出出出出可可可可行域行域行域行域；上页上页上页上页下页下页下页下页返回返回返回返回9 8 7 6 5 4 3 2 1 0|123456789x1x2 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0 x1+2x2 84x1 164 x2 12可行域可行域BCDEAv图解法图解法B上页上页上页上页下页下页下页下页返回返回返回返回9 8 7 6 5 4 3 2 1 0 x2 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0|123456789x1x1+2x2 84x1 164 x2 12BCDEA2x1+3x2=6v图解法图解法步骤步骤步骤步骤二：二：二：二：作目作目作目作目标函标函标函标函数等数等数等数等值线，值线，值线，值线，确定确定确定确定使目使目使目使目标函标函标函标函数最数最数最数最优的优的优的优的移动移动移动移动方向；方向；方向；方向；上页上页上页上页下页下页下页下页返回返回返回返回9 8 7 6 5 4 3 2 1 0 x2 目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0|123456789x1x1+2x2 84x1 164 x2 12BCDEAv图解法图解法x1+2x2=8 4x1=16Max Z=14最优解最优解(4,2)步骤步骤步骤步骤三：三：三：三：平移平移平移平移目标目标目标目标函数函数函数函数的等的等的等的等值线，值线，值线，值线，找出找出找出找出最优最优最优最优点，点，点，点，算出算出算出算出最优最优最优最优值。值。值。值。上页上页上页上页下页下页下页下页返回返回返回返回图解法求解步骤图解法求解步骤由全部约束条件作图求出可行域；由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最作目标函数等值线，确定使目标函数最优的移动方向；优的移动方向；平移目标函数的等值线，找出最优点，平移目标函数的等值线，找出最优点，算出最优值。算出最优值。上页上页上页上页下页下页下页下页返回返回返回返回9 8 7 6 5 4 3 2 1 0 x2|123456789x1BCDEA最优解最优解(4,2)改变约束条件改变约束条件或目标函数，或目标函数，解的结果如何解的结果如何？线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果(a)唯一最优解唯一最优解 上页上页上页上页下页下页下页下页返回返回返回返回9 8 7 6 5 4 3 2 1 0 x2|123456789x1BCDEA线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果x1+2x2=8 目标函数目标函数目标函数目标函数 Max Max Z Z=x x1 1+2 2x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0(b)无穷多最优解无穷多最优解上页上页上页上页下页下页下页下页返回返回返回返回 (c)无界解无界解 Max Max Z Z=x x1 1+x x2 2 -2-2x x1 1+x x2 2 4 4 x x1 1-x x2 2 2 2 x x1 1、x x2 2 0 0 0 0 x2x1线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果上页上页上页上页下页下页下页下页返回返回返回返回(d)无可行解无可行解 Max Max Z Z=2=2x x1 1+3+3x x2 2 x x1 1+2 +2 x x2 2 8 8 4 4 x x1 1 16 16 4 4x x2 2 12 12 -2-2x x1 1+x x2 2 4 4 x x1 1、x x2 2 0 0 0 0可行域为空集可行域为空集可行域为空集可行域为空集线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果上页上页上页上页下页下页下页下页返回返回返回返回可行域是有界或无界的可行域是有界或无界的凸多边形凸多边形。若线性规划问题存在最优解，它一定若线性规划问题存在最优解，它一定可以在可以在可行域的顶点可行域的顶点得到。得到。若两个顶点同时得到最优解，则其连若两个顶点同时得到最优解，则其连线上的所有点都是最优解。线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其解题思路：找出凸集的顶点，计算其目标函数值，比较即得。目标函数值，比较即得。上页上页上页上页下页下页下页下页返回返回返回返回练习：练习：用图解法求解用图解法求解LP问题问题 Max Z=15 x1+25 x2x1+3x2 60 x1+x2 40 x1、x2 0 0上页上页上页上页下页下页下页下页返回返回返回返回max z=15x1+25x2s.t.x1+3x2 60 x1+x2 40 x1，x2 0 L1Z=250目标函数变形：目标函数变形：x2=-3/5 x1+z/25x2x1最优解最优解：x1=30 x2=10最优值最优值：zmax=700B B点是使点是使z z达到最大达到最大的唯一可的唯一可行点行点(30,10)A A（0,200,20）C C（40,040,0）0B 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上页上页上页上页下页下页下页下页返回返回返回返回Ox1x2Note:可行域为无界区域，可行域为无界区域，目标函数值可无限目标函数值可无限增大，即解无界。增大，即解无界。称为无最优解。称为无最优解。A(1,0)A(1,0)可行域为无界可行域为无界区域一定无最区域一定无最优解吗？优解吗？max z=2x1+2x2 s.t.2x1 x2 2 -x1+4x2 4 x1，x2 0习题：用图解法求下列线性规划习题：用图解法求下列线性规划:上页上页上页上页下页下页下页下页返回返回返回返回0 0 x1x2A(1,0)(1,0)minZ(多解多解)线段线段ADAD上的任一点上的任一点都是最优解都是最优解minZminZ=2=2习题3max z=2x1+2x2 s.t.x1+x2 1 x1 3x2 3 x1 3 x1，x2 0(30,10)B(3,0)(3,0)C(3,2)(3,2)D(0,1)(0,1)若若min Z 换换为为max Z则最优解为则最优解为?点点上页上页上页上页下页下页下页下页返回返回返回返回0 0 x1x2A(1,0)(1,0)(30,10)B(4,0)(4,0)D(0,1)(0,1)习题4max z=5x1+3x2 s.t.x1+x2 1 x1+2x2 4 x1，x2 0C(0,2)(0,2)无可行解无可行解上页上页上页上页下页下页下页下页返回返回返回返回 根据以上例题，进一步分析讨论可知线性规根据以上例题，进一步分析讨论可知线性规划的可行域和最优解有以下几种可能的情况划的可行域和最优解有以下几种可能的情况 1.1.可行域为封闭的有界区域可行域为封闭的有界区域 (a)(a)有唯一的最优解；有唯一的最优解；(b)(b)有无穷多个最优解；有无穷多个最优解；2.2.可行域为非封闭的无界区域可行域为非封闭的无界区域 (c)(c)有唯一的最优解；有唯一的最优解；(d)(d)有无穷多个最优解；有无穷多个最优解；(e)(e)目标函数无界目标函数无界(即虽有可行解，但在可行即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少域中，目标函数可以无限增大或无限减少)，因而没有，因而没有有限最优解。有限最优解。3.3.可行域为空集可行域为空集 (f)(f)没有可行解，原问题无最优解没有可行解，原问题无最优解 上页上页上页上页下页下页下页下页返回返回返回返回1.图解法求解步骤图解法求解步骤由全部约束条件作图求出可行域；由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的作目标函数等值线，确定使目标函数最优的移动方向；移动方向；平移目标函数的等值线，找出最优点，算出平移目标函数的等值线，找出最优点，算出最优值。最优值。小结：小结：上页上页上页上页下页下页下页下页返回返回返回返回 1.1.可行域为封闭的有界区域可行域为封闭的有界区域 (a)(a)有唯一的最优解；有唯一的最优解；(b)(b)有无穷多个最优解；有无穷多个最优解；2.2.可行域为非封闭的无界区域可行域为非封闭的无界区域 (c)(c)有唯一的最优解；有唯一的最优解；(d)(d)有无穷多个最优解；有无穷多个最优解；(e)(e)目标函数无界目标函数无界(即虽有可行解，但在即虽有可行解，但在 可行域中，目标函数可以无限增大或无限可行域中，目标函数可以无限增大或无限 减少减少)，因而没有有限最优解。，因而没有有限最优解。3.3.可行域为空集可行域为空集 (f)(f)没有可行解，原问题无最优解没有可行解，原问题无最优解 2.线性规划的可行域和最优解线性规划的可行域和最优解上页上页上页上页下页下页下页下页返回返回返回返回二、线性规划解的有关概念二、线性规划解的有关概念v可行解、最优解可行解、最优解v基、基变量、非基变量基、基变量、非基变量v基本解、基本可行解基本解、基本可行解v可行基、最优基可行基、最优基继续继续继续继续返回返回返回返回定义定义 线性规划的线性规划的标准型：标准型：A 是是mn矩阵，矩阵，mn 并且并且r(A)=m。（1）线性规划的基线性规划的基基基 (basis)：B 是是A中的一个非奇异（可逆）的中的一个非奇异（可逆）的 mm子矩阵，即子矩阵，即|B|0，则称，则称B是线性规划的一个是线性规划的一个基基(或或基矩阵基矩阵)。行满秩行满秩的矩阵的矩阵当当m=n时时，基矩，基矩阵阵唯一；唯一；当当mn时时，最多不超，最多不超过过 Cnm。上页上页上页上页下页下页下页下页返回返回返回返回【解解】约束方程的系数矩阵为约束方程的系数矩阵为25矩阵矩阵【例例1-14】已知线性规划已知线性规划求所有基矩阵。求所有基矩阵。容易看出容易看出r(A)=2，2阶阶子矩子矩阵阵最多有最多有几几个？个？C52=10其中基矩阵有几个？其中基矩阵有几个？上页上页上页上页下页下页下页下页返回返回返回返回基向量：基向量：基基B中的列向量中的列向量 pj(j=1,2,m);基变量：基变量：与基向量对应的决策变量与基向量对应的决策变量 xj(j=1,2,m)；非基非基变量：变量：与非基向量对应的决策变量与非基向量对应的决策变量非非基向量：基向量：其余的列向量其余的列向量（2）基向量、非基向量、基变量、非基变量基向量、非基向量、基变量、非基变量基向量基向量：p1和和p4基变量：基变量：x1和和x4，基基变变量量、非非基基变变量量是是针针对对某某一一确确定定基基而而言言的的，不同的基对应的基变量和非基变量也不同。不同的基对应的基变量和非基变量也不同。非基向量非基向量：p2、p3和和p5非基变量：非基变量：x2、x3和和x5（3 3）可行解：可行解：满足满足约束条件约束条件（1-21-2）（）（1-31-3）的解为）的解为 可行解。所有可行解的集合为可行域。可行解。所有可行解的集合为可行域。（4 4）最优解：最优解：满足式（满足式（1-11-1）的可行解，使得目标函）的可行解，使得目标函数达到最大值的可行解就是最优解。数达到最大值的可行解就是最优解。（5 5）基本解：）基本解：对某一确定的基对某一确定的基B B，令非基变量等于零，令非基变量等于零，由式（由式（1-21-2）解出基变量，称这组解为基本解。）解出基变量，称这组解为基本解。（6 6）基本可行解：）基本可行解：基本解是可行解则称为是基本可行解基本解是可行解则称为是基本可行解（即非负的基本解）（即非负的基本解）。显然，只要基本解中的基变量的解满足式（显然，只要基本解中的基变量的解满足式（1.）的非负要求，）的非负要求，那么这个基本解就是基本可行解。那么这个基本解就是基本可行解。在在例例1-14中中，对对来来说说，x1,x2是是基基变变量量，x3,x4，x5是是非非基基变变量量，令令x3=x4=x5=0，则式（则式（1.）为）为因因|B1|，由克莱姆法由克莱姆法则则知，知，x1、x2有唯一解有唯一解x12/5,x2=1则基本解为则基本解为对对B2来说，来说，x1,x4为基变量，令非基变量为基变量，令非基变量x2,x3,x5为零，由式为零，由式（1.2）得到）得到 ，x4=4，由于由于 是基本解，从而它是基本可行解，在是基本解，从而它是基本可行解，在 中中x10,因此不是可行解，也就不是基本可行解。因此不是可行解，也就不是基本可行解。反之，可行解不一定是基本可行解反之，可行解不一定是基本可行解例如例如 满足式（满足式（1.2）（）（1.3），但不是），但不是任何基矩阵的基本解。任何基矩阵的基本解。（8）可行基）可行基 基可行解对应的基称为可行基；基可行解对应的基称为可行基；最优基最优基 基本最优解对应的基称为最优基；基本最优解对应的基称为最优基；（7）基本最优解）基本最优解 最优解是基本解称为基本最优解。最优解是基本解称为基本最优解。基基本本最最优优解解、最最优优解解、基基本本可可行行解解、基基本本解解、可可行行解解的关系如下所示：的关系如下所示：基本最优解基本最优解基本可行解基本可行解可行解可行解最最 优优 解解基本解基本解当最优解唯一时，最优解亦是基本最优解，当最优解唯一时，最优解亦是基本最优解，当最优解不唯一时，则最优解不一定是基本最优解。当最优解不唯一时，则最优解不一定是基本最优解。上页上页上页上页下页下页下页下页返回返回返回返回系数阵A中可找出多个基B返回返回返回返回非负的基本解就是基本可行解每个基B都对应于一个基本解注意：线性规划的基本解、基本可行解和可注意：线性规划的基本解、基本可行解和可行基只与线性规划问题标准形式的约束条件行基只与线性规划问题标准形式的约束条件有关。与目标函数无关。有关。与目标函数无关。上页上页上页上页下页下页下页下页返回返回返回返回（9 9）凸集）凸集定义定义1 1 设集合设集合 是是 n n 维欧氏空间中的一个点维欧氏空间中的一个点集，如果集，如果 及实数及实数 则则称称 K 是一个是一个凸集凸集。几何意义：如果集合中任意两点连线上的一切点都在几何意义：如果集合中任意两点连线上的一切点都在 该集合中，则称该集合为凸集。该集合中，则称该集合为凸集。凸集凸集上页上页上页上页下页下页下页下页返回返回返回返回定义定义 2 2 设设 则称则称为为点点 的一个的一个凸组凸组合合。定义定义3 3 设凸集设凸集 两点两点 表示为表示为 则称则称 x 为为 K 的一个的一个极点极点（或（或顶点顶点）。）。定理定理 LP 问题的可行解集问题的可行解集（1010）凸组合）凸组合（1111）极点）极点上页上页上页上页下页下页下页下页返回返回返回返回【定理定理1.1】若线性规划可行解若线性规划可行解K非空非空,则则K是凸集。是凸集。【定理定理1.2】线性规划的可行解集合线性规划的可行解集合K的点的点X是极点的是极点的 充要条件为充要条件为X是基本可行解。是基本可行解。定定理理1.3】若若线线性性规规划划有有最最优优解解,则则最最优优值值一一定定可可以以在在可可行行解解集集合合的的某某个个极极点点上上得得到到,最最优优解解就就是是极极点点的的坐坐标标向量。向量。定定理理1.2刻刻划划了了可可行行解解集集的的极极点点与与基基本本可可行行解解的的对对应应关关系系，极极点点是是基基本本可可行行解解，反反之之，基基本本可可行行解解一一定定是是极极点点，但但它它们们并并非非一一一一 对对应应，有有可可能能两两个个或或几几个个基本可行解对应于同一极点（退化基本可行解时）。基本可行解对应于同一极点（退化基本可行解时）。(12)线性规划的基本定理线性规划的基本定理上页上页上页上页下页下页下页下页返回返回返回返回 定定理理1.3描描述述了了最最优优解解在在可可行行解解集集中中的的位位置置，若若最最优优解解唯唯一一，则则最最优优解解只只能能在在某某一一极极点点上上达达到到，若若具具有有多多重重最最优优解解，则则最最优优解解是是某某些些极极点点的的凸凸组组合合，从从而而最最优优解解是是可可行行解解集集的的极极点点或或界界点点，不不可可能能是是可可行行解解集集的的内点内点。若若线线性性规规划划的的可可行行解解集集非非空空且且有有界界，则则一一定定有有最最优优解解；若若可可行行解解集集无无界界，则则线线性性规规划划可可能能有有最最优优解解，也可能没有最优解。也可能没有最优解。定定理理1.2及及1.3还还给给了了我我们们一一个个启启示示，寻寻求求最最优优解解不不是是在在无无限限个个可可行行解解中中去去找找，而而是是在在有有限限个个基基本本可可行行解解中中去去寻寻求求。下下一一节节将将介介绍绍一一种种有有效效地地寻寻找找最最优优解解的的方方法。法。上页上页上页上页下页下页下页下页返回返回返回返回的可行域以及最优解有以下性质的可行域以及最优解有以下性质:1.1.若线性规划的可行域非空，则可行域必定若线性规划的可行域非空，则可行域必定为一为一凸集凸集2.2.若线性规划的可行域非空，则至多有若线性规划的可行域非空，则至多有有限有限个极点个极点.3.3.若线性规划有最优解若线性规划有最优解,则至少有一个则至少有一个极点极点是是最优解最优解.可行域内可行域内无限个无限个可行解可行解可行域的可行域的有限个极有限个极点点搜索搜索