Chapter2.3-2.4线性规划问题的解的概念.ppt

2.3 线性规划问题 解的概念,一、LP问题的各种解,可行解：满足约束条件和非负条件的决策变量的一组取值。全部可行解的集合称为可行域。 最优解：使目标函数达到最优值的可行解。对应的目标函数值称为最优值。,3. 基: 设Amn(nm)为约束方程组的系数矩阵，其秩为m。Bmm是矩阵A中的一个mm阶的满秩子矩阵， 则称B是线性规划问题的一个基（基矩阵）。,设B=（aij）mm中的每一个列向量Pj(j=1,2,m)为基向量。与基向量Pj对应的变量xj称为基变量，其他的变量称为非基变量。,基：若B是矩阵A中mm阶非奇异子矩阵（B0），则B是线性规划问题的一个基。不妨设：, j=1,2,m 基向量。 , j=1,2,m 基变量。 , j=m+1,n 非基变量。,线性规划问题解的概念,4.基解：设AX=b是含n个决策变量、 m个约束条件的LP的约束方程组，B是LP问题的一个基，若令不与B的列相应的n-m个分量（非基变量）都等于零，所得的方程组的解称为方程组AX=b关于基B的基本解，简称为LP的基本解。,5.基可行解：满足非负条件的基解。 6.可行基：对应基可行解的基称为可行基. 7.退化解：若基解XB中至少有一个分量为零，称为退化解。 由此可知，退化基可行解中的非零分量一定小于m个, 非退化解中非零分量一定等于m个。,线性规划解的关系图,非可行解,可行解,基可行解,基解,线性规划问题解的概念,例2.6 求出下列线性规划问题的一个基、 基变量、基解、基可行解和可行基。,解：化为标准形式为,由此，约束方程的系数矩阵为,;,;,;,矩阵秩不超过3，而,是一个的满秩阵，故,是一个基，,x4,x5,x6是基变量，x1,x2,x3是非基变量。,令非基变量x1,x2,x3为零,则 X,是一个基解。,是一个可行基。,因该基解中所有变量取值为非负，故又是基可行解，对应的基,2.4 线性规划的图解法,解的几何表示,1什么是图解法？ 线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。 求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。,例2.7 的数学模型,目标函数 Max Z = 2x1 + 3x2 约束条件 3 x1 + 6x2 24 2x1 + x2 10 x1、 x2 0,x1,x2,10 9 8 7 6 5 4 3 2 1 0,| | | | | | | | | 1 2 3 4 5 6 7 8 9,x1,x2,3x1 + 6x2 24,目标函数 Max Z = 2x1 + 3x2 约束条件 3x1 + 6x2 24 2x1 + x2 10 x1、 x2 0,2x1 + x2 10,x2,图解法,2x1 + x2 10,10 9 8 7 6 5 4 3 2 1 0,可行域,D,目标函数 Max Z = 2x1 + 3x2 约束条件 3x1 + 6x2 24 2x1 + x2 10 x1、 x2 0,x2,图解法,2x1 + x2 10,10 9 8 7 6 5 4 3 2 1 0,可行域,D,目标函数 Max Z = 2x1 + 3x2 约束条件 3x1 + 6x2 24 2x1 + x2 10 x1、 x2 0,2x1 + 3x2 = 6,x2,图解法,2x1 + x2 10,10 9 8 7 6 5 4 3 2 1 0,D,目标函数 Max Z = 2x1 + 3x2 约束条件 3x1 + 6x2 24 2x1 + x2 10 x1、 x2 0,3x1 + 6x2 = 24 2x1 + x2 = 10,图解法求解步骤,由全部约束条件作图求出可行域； 作目标函数等值线，确定使目标函数最优的移动方向； 平移目标函数的等值线，找出最优点，算出最优值。,线性规划问题求解的 几种可能结果,(a) 唯一最优解,(b)无穷多最优解,该线性规划的可行域为上图中四边形OAED（即阴影区），虚线为目标函数等值线，箭头为目标函数值递增的方向。沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的一条边界线段AE重合，这个结果表明，该线性规划有无穷多个最优解线段AE上的所有点都是最优点，它们都使目标函数取得相同的最大值Zmax=3。,(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问题,18 16 14 12 10 8 6 4 2 0,| | | | | | | | | 2 4 6 8 10 12 14 16 18,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,图解法 （练习）,18 16 14 12 10 8 6 4 2 0,| | | | | | | | | 2 4 6 8 10 12 14 16 18,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,可行域,A,B,C,D,E,图解法 （练习）,18 16 14 12 10 8 6 4 2 0,| | | | | | | | | 2 4 6 8 10 12 14 16 18,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),34x1 + 40x2 = 272,图解法 （练习）,18 16 14 12 10 8 6 4 2 0,| | | | | | | | | 2 4 6 8 10 12 14 16 18,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),图解法 （练习）,x2,18 16 14 12 10 8 6 4 2 0,| | | | | | | | | 2 4 6 8 10 12 14 16 18,x1,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),最优解 (3,6),4x1+ 6x2=48 2x1+ 2x2 =18,用图解法解线性规划,结 论,从上面用图解法求解案例的过程中明显感觉到对具有三个决策变量的线性规划进行图解就麻烦得多了。因此，尽管图解法具有简单、直观的优点，但它的使用是有局限性的，对仅含有两个至多不超过三个决策变量的线性规划才适于使用图解法，大多数情况下仅对含有两个决策变量的线性规划才使用图解法求解，而对含有三个及三个以上决策变量的线性规划则应考虑使用更加有效的通用算法单纯形法来进行求解，这将在2.5节加以介绍。,课堂练习： 对下列线性规划问题，并用图解法求最优解 。,讨论：如何求得基解？,第一步 模型标准化；,第二步 按照基本解的定义, 找基（非退化3阶方阵）,多少个？不超过 ，为什麽？怎麽找？, 确定基变量和非基变量；, 令非基变量为0，解出基变量,求解结果：,H(6,4,-6,0,0)T, C(3,1,0,3,0)T,B(2,2,0,0,2)T, D(2,0,2,4,0)T,F(-2,0,6,0,4)T,