线性规划及单纯形法.pptVIP

第一章 线性规划与单纯形方法,复习： 线性规划问题的提出 线性规划模型的特点 线性规划模型的一般形式与标准形式 如何将一般形式化为标准形式,例1.3 将下列问题化成标准型: Min S = -x1+2x2-3x3 s.t. x1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3 = 5 x1,x2 0 x3 无非负限制,Max S = x1-2x2+3x3 -3x3 s.t. x1+x2+x3 -x3 +x4 =7 x1-x2+ x3 -x3 -x5=2 -3x1+x2+2x3 -2x3 =5 x1, x2 , x3 ，x3 , x4，x5 0,1-2 线性规划的图解法,例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E) 得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500,2 图 解 法,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。 下面通过例1详细讲解其方法：,(1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。,（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。,（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。,（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,线性规划问题的有关概念 （1）可行解：满足约束条件与非负限制的变量的值，称为可行解。 （2）可行域：全部可行解的集合称为可行域。 （3）最优解：使目标函数取得最优值的可行解，称为最优解。,线性规划的图解,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,例1.4,例1.5 max S=50x1+30x2 s.t. 4x1+3x2 120 2x1+x2 50 x1, x2 0,x2,50,40,30,20,10,10,20,30,40,x1,4x1+3x2 120,x2,50,40,30,20,10,10,20,30,40,x1,2x1+x2 50,x2,50,40,30,20,10,10,20,30,40,x1,2x1+x2 50,4x1+3x2 120,可行域,同时满足： 2x1+x2 50 4x1+3x2 120 x1 0 x2 0 的区域可行域,x2,50,40,30,20,10,10,20,30,40,x1,可行域,O（0，0）,Q1（25，0）,Q2（15，20）,Q3（0，40）,该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形 可行域内的每一点都是可行解。,x2,50,40,30,20,10,10,20,30,40,x1,可行域,目标函数等值线,x2,50,40,30,20,10,10,20,30,40,x1,可行域,当该直线移到Q2点时，目标函数值达到最大： Max S=5015+30 20=1350 此时最优解=（15，20）,Q2（15，20）,图解法求解步骤,由全部约束条件作图求出可行域； 作目标函数等值线； 平移目标函数的等值线，找出最优点，算出最优值。,练习： 目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,9 8 7 6 5 4 3 2 1 0,| | | | | | | | | 1 2 3 4 5 6 7 8 9,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,x2,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,可行域,图解法,9 8 7 6 5 4 3 2 1 0,| | | | | | | | | 1 2 3 4 5 6 7 8 9,x1,x2,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,可行域,图解法,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,图解法,例 某公司由于生产需要，共需要A，B两种原料至少350 吨（A，B两种材料有一定替代性），其中A原料至少购进125 吨。但由于A，B两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？,解：目标函数： Min f = 2x1 + 3 x2 约束条件： s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。,线性规划问题求解的 几种可能结果,(a) 唯一最优解,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,(b)无穷多最优解,线性规划问题求解的 几种可能结果,目标函数 Max Z = 2X1 + 3X2 约束条件 2X1 + 3X2 8 4X1 16 4X2 12 X1、 X 20,(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 可行域为空集,线性规划问题求解的 几种可能结果,该问题可行域为空集，即无可行解，也不存在最优解。,重要结论： 如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解； 无穷多个最优解。线段BC上的所有点都代表了最优解； 无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件； 无可行解。可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。,图解法的几点结论: （由图解法得到的启示）,可行域是有界或无界的凸多边形。 若线性规划问题存在最优解，它一定可以在可行域的顶点得到。 若两个顶点同时得到最优解，则其连线上的所有点都是最优解。 解题思路：找出凸集的顶点，计算其目标函数值，比较即得。,1-3 线性规划问题解的概念,对于线性规划标准型,也即： Max Z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+.+a1nxn=b1 a21x1+a22x2+.+a2nxn=b2 . am1x1+am2x2+.+amnxn=bm x1,x2.xn 0 其中：bi 0(i=1,2,.m),可行解:满足AX=b, X=0的解X称为线性规划问题的可行解。 最优解：使Z=CX达到最大值的可行解称为最优解。 基：设r(A)=m,并且B是A的m 阶非奇异的子矩阵（|B|0),则称矩阵B为线性规划问题的一个基。,基向量：矩阵B=（P1，P2.Pm) ，其列向量Pj称为对应基B的基向量。 基变量和非基变量：与基向量 Pj 相对应的变量xj就称为基变量，其余的就称为非基变量。,不妨设：,基础解：对于某一特定的基B，非基变量取0值的解，称为基础解。 令非基变量等于零，则可由约束方程组 AXb求得一个解，这样的解称为基础解。 基础可行解：基础解不一定都是可行的。满足非负限制的基础解，称为基础可行解。 可行基：与基础可行解对应的基，称为可行基。,为了理解基、基变量、基础解和基础可行解的概念，用下列例子说明,例1.7：max S = 2x1 + 3x2 s.t. -2x1 + 3x2 6 3x1 - 2x2 6 x1 + x2 4 x1, x2 0,化为标准型：,max S = 2X1 + 3X2+0X3+0X4+0X5 s.t. -2X1 + 3X2 +X3=6 3X1 - 2X2 +X4=6 X1 + X2 +X5=4 X1, X2 , X3, X4, X5 0,写出约束方程组的系数矩阵：,矩阵A的秩为3，而 是一个33的满秩矩阵， 故 是上述线性规划问题的一个基。因而与P3, P4, P5,对应的变量X3，X4，X5是基变量，X1，X2是非基变量。,在约束方程组中，如果令X1=X2=0，即可解得X3=6，X4=6，X5=4，由此,是线性规划问题的一个基础解。因为该基础解中所有变量取值为非负，所以它又是基础可行解。与这个基础可行解对应的基（P3，P4，P5）是一个可行基。,解的集合：,非可行解,可行解,解的集合：,基础解,解的集合：,可行解,基础解,基础可行解,解的集合：,可行解,基础解,最优解,基础可行解,练习：找出下列线性规划问题的基础解、基础可行解和可行基 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0 注意，线性规划的基础解、基础可行解和可行基只与线性规划问题标准形式的约束条件有关。,3 2 1 0 0 A = （P1 ,P2 ,P3 ,P4 ,P5）= 2 1 0 1 0 0 3 0 0 1 A矩阵包含以下10个33的子矩阵： B1=（p1 ，p2 ，p3 ） B2=（p1 ，p2 ，p4） B3=（p1 ，p2 ，p5） B4=（p1 ，p3 ，p4） B5=（p1 ，p3 ，p5） B6=（p1 ，p4 ，p5） B7=（p2 ，p3 ，p4） B8=（p2 ，p3 ，p5） B9=（p2 ，p4 ，p5） B10=（p3 ，p4 ，p5）,其中B4= 0，因而B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。 对于基B3=（p1 ，p2 ，p5），令非基变量x3 = 0， x4 = 0，即在等式约束中令x3 = 0，x4 = 0，解线性方程组： 3 x1 + 2 x2 + 0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x2 + x5 = 75 得到x1 =15，x2 = 10，x5 = 45，对应的基础可行解： x=(x1 ，x2 ，x3 ，x4 ，x5)T=(15，10，0，0，45)T。于是对应的基B3是一个可行基。,类似可得到 x(2) = (5,25,0,5,0)T （对应B2） x(7) = (20,