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

上页上页 下页下页 返回返回v 图解法图解法v 线性规划问题求解的线性规划问题求解的几种可能结果几种可能结果v由图解法得到的启示由图解法得到的启示2.2 线性规划解的概念、性质线性规划解的概念、性质及图解法及图解法继续继续 返回返回上页上页 下页下页 返回返回上页上页 下页下页 返回返回例例 1的数学模型的数学模型目标函数目标函数 Max Z = 2x1 + 3x2约束条件约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0x1 x2上页上页 下页下页 返回返回9 8 7 6 5 4 3 2 1 0 | | | | | | | | |1 2 3 4 5 6 7 8 9 x1x2x1 + 2x2 8(0, 4)(8, 0)目标函数目标函数 Max Z = 2x1 + 3x2约束条件约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 04x1 164 x2 12v图解法图解法可行域步骤步骤一：一：由全由全部约部约束条束条件作件作图求图求出出 可可行域行域；上页上页 下页下页 返回返回9 8 7 6 5 4 3 2 1 0 | | | | | | | | |1 2 3 4 5 6 7 8 9 x1x2目标函数目标函数 Max Z = 2x1 + 3x2约束条件约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0x1 + 2x2 84x1 164 x2 12可行域B CDEAv图解法图解法B上页上页 下页下页 返回返回9 8 7 6 5 4 3 2 1 0 x2目标函数目标函数 Max Z = 2x1 + 3x2约束条件约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0| | | | | | | | |1 2 3 4 5 6 7 8 9 x1x1 + 2x2 84x1 164 x2 12B CDEA2x1 + 3x2 = 6v图解法图解法步骤步骤二：二：作目作目标函标函数等数等值线值线，确，确定使定使目标目标函数函数最优最优的移的移动方动方向；向；上页上页 下页下页 返回返回9 8 7 6 5 4 3 2 1 0 x2目标函数目标函数 Max Z = 2x1 + 3x2约束条件约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0| | | | | | | | |1 2 3 4 5 6 7 8 9 x1x1 + 2x2 84x1 164 x2 12B CDEAv图解法图解法x1+ 2x2=84x1 =16Max Z=14最优解最优解 (4, 2)步骤步骤三：三：平移平移目标目标函数函数的等的等值线值线，找，找出最出最优点优点，算，算出最出最优值优值。上页上页 下页下页 返回返回图解法求解步骤图解法求解步骤 由全部约束条件作图求出可行域；由全部约束条件作图求出可行域； 作目标函数等值线，确定使目标函数最作目标函数等值线，确定使目标函数最优的移动方向；优的移动方向； 平移目标函数的等值线，找出最优点，平移目标函数的等值线，找出最优点，算出最优值。算出最优值。上页上页 下页下页 返回返回9 8 7 6 5 4 3 2 1 0 x2| | | | | | | | |1 2 3 4 5 6 7 8 9 x1B CDEA最优解最优解 (4, 2)改变约束条件或目标函数，解的结果如何？线性规划问题求解的线性规划问题求解的几种可能结果几种可能结果(a) 唯一最优解唯一最优解 上页上页 下页下页 返回返回9 8 7 6 5 4 3 2 1 0 x2| | | | | | | | |1 2 3 4 5 6 7 8 9 x1B CDEA线性规划问题求解的线性规划问题求解的几种可能结果几种可能结果x1 + 2x2 = 8目标函数目标函数 Max Z = x1 + 2x2约束条件约束条件 x1 + 2x2 8 4x1 16 4x2 12x1、 x2 0(b)无穷多最优解无穷多最优解上页上页 下页下页 返回返回(c)无界解无界解Max Z = x1 + x2-2x1 + x2 4 x1 - x2 2 x1、 x2 0x2x1线性规划问题求解的线性规划问题求解的几种可能结果几种可能结果上页上页 下页下页 返回返回(d)无可行解无可行解Max Z = 2x1 + 3x2x1 +2 x2 8 4 x1 16 4x2 12 -2x1 + x2 4 x1、 x2 0 可行域为空集可行域为空集线性规划问题求解的线性规划问题求解的几种可能结果几种可能结果上页上页 下页下页 返回返回图解法的几点结论图解法的几点结论 :（由图解法得到的启示）（由图解法得到的启示）可行域是有界或无界的可行域是有界或无界的 凸多边形凸多边形 。若线性规划问题存在最优解，它一定若线性规划问题存在最优解，它一定可以在可以在 可行域的顶点可行域的顶点 得到。得到。若两个顶点同时得到最优解，则其连若两个顶点同时得到最优解，则其连线上的所有点都是最优解。线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其解题思路：找出凸集的顶点，计算其目标函数值，比较即得。目标函数值，比较即得。上页上页 下页下页 返回返回练习：练习：用图解法求解用图解法求解 LP问题问题Max Z = 15 x1 + 25 x2x1 + 3x2 60 x1 + x2 40x1、 x2 0上页上页 下页下页 返回返回max z = 15x1 +25x2s.t. x1 + 3x2 60x1 + x2 40x1， x2 0 L1Z=250目标函数变形：x2=-3/5 x1+z/25x2x1最优解 ： x1=30 x2 =10最优值 ： zmax=700B点是使 z达到最大的唯一可行点(30,10)A（ 0,20）C（ 40, 0）0B上页上页 下页下页 返回返回习题：用图解法求下列线性规划 :习题 2max z = 2x1 + 2x2s.t. 2x1 x2 2-x1 + 4x2 4x1， x2 0习题 3max z = 2x1 + 2x2s.t. x1 + x2 1x1 3x2 3 x1 3x1， x2 0习题 4max z = 5x1 + 3x2s.t. x1 + x2 1x1 + 2x2 4x1， x2 0上页上页 下页下页 返回返回O x1x2Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。A(1,0)可行域为无界区域一定无最优解吗？max z = 2x1 + 2x2s.t. 2x1 x2 2-x1 + 4x2 4x1， x2 0习题：用图解法求下列线性规划 :上页上页 下页下页 返回返回0x1x2A (1,0) minZ(多解 )线段 AD上的任一点都是最优解minZ = 2习题 3max z = 2x1 + 2x2s.t. x1 + x2 1x1 3x2 3 x1 3x1， x2 0(30,10)B(3,0)C(3,2)D(0,1)若 min Z 换为 max Z则最优解为?点上页上页 下页下页 返回返回0x1x2A (1,0)(30,10)B(4,0)D(0,1)习题 4max z = 5x1 + 3x2s.t. x1 + x2 1x1 + 2x2 4x1， x2 0C(0,2)无可行解上页上页 下页下页 返回返回根据以上例题，进一步分析讨论可知线性规 划的可行域和最优解有以下几种可能的情况1.可行域为封闭的有界区域(a)有唯一的最优解；(b)有无穷多个最优解；2.可行域为非封闭的无界区域(c)有唯一的最优解；(d)有无穷多个最优解；(e)目标函数无界 (即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少 )，因而没有有限最优解。3.可行域为空集(f)没有可行解，原问题无最优解上页上页 下页下页 返回返回1.图解法求解步骤图解法求解步骤 由全部约束条件作图求出可行域；由全部约束条件作图求出可行域； 作目标函数等值线，确定使目标函数最优的作目标函数等值线，确定使目标函数最优的移动方向；移动方向； 平移目标函数的等值线，找出最优点，算出平移目标函数的等值线，找出最优点，算出最优值。最优值。小结：小结：上页上页 下页下页 返回返回1.可行域为封闭的有界区域(a)有唯一的最优解；(b)有无穷多个最优解；2.可行域为非封闭的无界区域(c)有唯一的最优解；(d)有无穷多个最优解；(e)目标函数无界 (即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少 )，因而没有有限最优解。3.可行域为空集(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） 可行解： 满足 约束条件 （ 1-2）（ 1-3）的解为可行解。所有可行解的集合为可行域。（ 4） 最优解： 满足式（ 1-1）的可行解，使得目标函数达到最大值的可行解就是最优解。（ 5）基本解： 对某一确定的基 B，令非基变量等于零，由式（ 1-2）解出基变量，称这组解为基本解。（ 6）基本可行解： 基本解是可行解则