2第一章线性规划(教案)2010[1].3.21 修改--模板修改

1、运筹学,重庆大学 经济与工商管理学院,熊中楷 教授/博士生导师,联系方式13452378728 个人介绍：,顶级斯坦福大学,顶级伯克利大学,著名约克大学,著名俄亥俄大学,著名俄亥俄大学,下乡种地,山区犁田,改变命运靠运筹,一 本章内容： 1线性规划的引例，标准形式 2线性规划图解法 3线性规划单纯形方法（代数方法和表格方法） 4线性规划的应用（建立模型） 二 教学目的： 掌握线性规划的引例，标准形式和几种解法的原理 三 本章重点： 几种解法和线性规划的应用（建立模型） 四 本章难点：单纯形方法（代数方法和表格方法） 五 计划学时：12学时,第一章：线性规划,问题：如

2、何计划使得工厂利润最大？ 分析：决策中的关键变量是什么？变量中的相互因果关系是什么？ 怎样用数学公式来建立有用的模型？,第一章：线性规划（1）,第一章 线性规划及单纯形法 1.1 一般线性规划问题的数学模型 典型引例： 某工厂在计划期内安排甲，乙两种产品，已知生产单位产品所消耗资源以及产生的利润如下表：,思路：收益最大 资源有约束 Max 2X1 +3X2 X1 + 2X2 =0 X2=0,第一章：线性规划（1）,一般形式Max CXAX=0,1 2 4 0 0 4,A=,X1 X2,8 16 12,b=,c=,2 3,A是技术矩阵，b 是资源向量，C 是利润向量 A=A1A2 Ai表示生产I

3、种产品消耗的资源,1线性规划定义 求一组变量x1，x2，xn的值，使之满足关于这组变量的若干个线性等式或不等式的约束条件，而且使这组变量的一个线性函数取到极大值（或极小值）。这些变量称为决策变量，所要优化的函数称为目标函数，决策变量是取实数值的连续变量。这样的问题称为线性规划。 2线性规划的一般形式与标准形式 3线性规划的解的相关定义 可行解 满足线性规划所有约束条件的各变量的一组值X=（x1，x2，xn）T，称为线性规划问题的可行解。全部可行解的集合称为可行域。 最优解 使线性规划的目标函数达到以最优值（依照具体问题，或者是极大值，或者是极小值）的可行解称为线性规划问题的最优解。 上述两个概

4、念，对于一般形式、标准形式都适用，而下述五个概念，仅适用于标准形式。,第一章：线性规划（1）,图解法 引例： 目标函数：MAX Z= X1+ 3X 2 满足的 约束条件： 5 X1+10 X2 =1 X2=0,X1+3X 2 = 常数 ： 目标函数的等值线 由右图知，在D点得最优解。D点坐标（2，4），此时max Z=14 画出各种情况对应的图形：,第一章：线性规划（1）,5 10 1 1 0 1,A=,X1+X2 = 1,X2 = 4,X1+3X2 = 常数,5X1+10X2 = 50,目标函数等值线,可行域和它的顶点,第一章：线性规划（1）,D,第一章：线性规划（1）,从图解法猜想: LP

5、最优解是可行域的顶点之一 因此，我们更关注可行域的顶点（有限个）,图解法基本要求 能正确地按图解法的步骤画出图来解答题目，并会判定解的类型。 知识要点 （1）图解法仅适用于两个变量的线性规划问题，求解时按原来题目对目标函数的优化要求去求解即可，不必将求极小值化为求极大值。 三个变量的线性规划问题用图解法求解时，可行域是三维空间的多面体，很难用平面上的图形画得清晰准确，目标函数对应的是三维空间中的平面，难以通过平面上画出的立体图形求出最优解。所以，从理论上讲，三个变量的线性规划也有图解法，但实际上不可行。多于三个变量的线性规划涉及到在高于三维的向量空间中求解优化问题，而三维以上的空间已无直观的几

6、何意义，故不存在相应的图解法。 （2）线性规划问题的解的情况共有四种： （3）线性规划问题如果有最优解，则可行域的某个顶点必定是最优解。为求最优解，可以先计算可行域某个顶点处的目标函数值，再考察它周围相邻顶点的目标函数值是否比这个值更优，如果为否，则该顶点就是最优解（或最优解之一），否则转到比这个点的目标函数值更优的另一顶点，重复上述过程，直到找出对应最优解的顶点。,第一章：线性规划（1）,已知几何图形上判断线性规划解各种类型。,从图解法猜想 LP最优解是可行域的顶点之一,运筹学,线性规划（2）,.线性规划问题的解的基本概念,对于标准型LP问题,可行解：满足约束条件的解称为可行解。 基：A中任

7、何一组m个线性无关的列向量构成的子矩阵,称为该问题的一个基（basis）,与中的这些列向量对应的变量称为基变量（basic variable）,研究思路： 几何图形的点-对应代数式子,可行域的点有什么特点？,可行域的点就是满足约束条件的点，因此从约束条件出发,最优解：若基本可行解又是最优解（也称基本最优解），这个基就称为最优基（optimal basis）,基本解：对于基,令非基变量为零,求得满足约束条件(1)的解，称为基对应的基本解（basic solution）。,基本可行解：满足非负条件的基本解称为基本可行解（basic feasible solution）；基本可行解所对应的基称为可行

8、基（feasible basis）。,线性规划问题的解的基本概念,AX=b A=BN B存在逆， B XB + N XN = b XB = B-1b - B-1 N XN 如果 XN = 0， XB = B-1b，这个叫基解。 这个解不一定满足非负。 如果 XB = B-1b = 0, 那么XB = B-1b ， XN = 0 是基可行解，也就是可行域的点 重要结论：如果 XB = B-1b = 0, 那么XB = B-1b ， XN = 0 不仅是可行域的点,而且是可行域的顶点。,线性规划的基本理论,由图解法的步骤，可以从几何的角度得出以下两个猜想： （1）线性规划问题的可行域是一个有界或无

9、界的凸多边 形，其顶点个数是有限个。 （2）若线性规划问题有最优解，那么最优解一定可在可 行域的某个顶点上找到。,第一章：线性规划（2）,与猜想相关的几个基本概念,（1）凸集：设k是n维欧式空间的一个点集，若任意两点 X(1)k, X(2)k的连线上的一切点X(1)+ (1-)X(2)k ( 01),则称k为凸集。 连接几何形体中任意两点的线段仍完全在该几何形体之中。 有限个凸集的交集仍然是凸集。有限个凸集的交集仍然是凸集吗？,第一章：线性规划（2）,（2）凸组合：设X(1)，X(2)，X(k)是n维欧式空间中的k个点， 若存在1, 2, k满足0i1,( i=1,2,k), 使X=1X(1)

10、+2 X(2)+k X(k)， 则称X为X(1)，X(2)，X(k)的凸组合。 凸集k中任意两点X(1)，X(2)连线上的任一点X都是X(1)与X(2)的一个凸组合。 (3) 顶点：设k为凸集，Xk,若X不能用X(1)k,X(2)k两点的 一个凸组合表示为X=X(1)+ (1-)X(2),其中01 ， 则称X为k的一个顶点。,与猜想相关的几个基本概念,第一章：线性规划（2）,定理1：若线性规划问题存在可行域，则其可行域 是一个凸集。,证明：为了证明满足=，0的所有点（可行解）组成的几何体是凸集，只要证明中任意两点任意两点连线上的一切点均满足线性约束条件既可。 任取，满足 则对任意的有,线性规划

11、的基本定理,又因为均0，所以 由此可知，即是凸集。,第一章：线性规划（2）,证明：必要性：因为是基本解，由基本解的定义，的非零分量所对应的系数列向量线性无关，又因为是可行解，由基本可行解的定义，非零分量均是正的，所以的正分量所对应的系数列向量线性无关。 充分性：设是线性规划问题的可行解，且正分量所对应的列向量也线性无关，则必有km,若k=m，则 刚好构成一个基，为相应的基本可行解。若km，则由线性代数知识，一定可以从其余的n-k个系数列向量中取出m-k个与构成最大线性无关向量组，其对应的基本可行解恰好为，不过此时的是一个退化的基本可行解。,引理1：线性规划问题的可行解 是基本可行解的充要条件是

12、的正分量所对应的系数列向量线性无关。,第一章：线性规划（2）,定理2：设线性规划问题的可行域 ，则是的一个 顶点的充分必要条件是为线性规划问题的基本可行解。,第一章：线性规划（2）,证明：必要性 不失一般性，假设基可行解X的前m个分量为正。,现在证明如果x不是基可行解，则它一定不是顶点。只要证明它在2个可行解的连线上 由引理1， x不是基可行解，它的正分量对应的系数列向量线性相关，,即x(1),x(2)是可行解，因此x不是顶点,第一章：线性规划（2）,充分性：若是线性规划的一个基本可行解，要证明是可行域的一个顶点， 仍用反证法，倘若不是可行域的顶点 ，,的基变量所对应的系数列向量线性相关，与X

13、是基本可行解矛盾。,第一章：线性规划（2）,例 已知线性规划问题的约束条件为,试讨论可行域顶点和基本可行解之间的对应关系。 解:可行域 为四维凸多面体，可以推得在四维空间中有3个顶点， =(0,0,10,10)，=(0,10,0,10)，=(10,0,0,0)。 这3个顶点与线性规划的5个基本可行解的对应关系如下： 顶点对应以x3,x4为基变量的基本可行解； 顶点对应以x2,x4为基变量的基本可行解； 顶点对应x1,x2;x1,x3和x1,x4为基变量的退化基本可行解（退化即存在基变量为0),第一章：线性规划（2）,一个线性规划问题，如果它的所有基本可行解都是非退化的，那么 称这个线性规划是非

14、退化的，只有在这种情况下，顶点和基本可行解 之间才是一一对应的。 定理3 若可行域D非空有界，那么线性规划问题的目标函数一定可以在可行域D的顶点上达到最优值。 证明的思路是：因为可行域非空有界，所以线性规划一定有最优解， 倘若 不是顶点，且目标函数在该点处取到最优值 ，则这个点可以表示成为顶点的凸组合，,线性规划的基本定理,定理3并不排除在一个非顶点上有一个最优解的可能性。但是在一个 给定的线性规划问题的所有最优解中，至少有一个是顶点。 如果可行域无界，则线性规划问题可能无最优解。 如果目标函数同时在两个顶点上达到最优解，那么不难证明在这两个 点的凸组合上也达到最优解，这时线性规划问题有无穷多

15、最优解。,第一章：线性规划（2）,为什么要学习线性规划基本定理-研究求解 可行域顶点的代数表达,基本可行解就是可行域的顶点-基本可行解代入目标函数值,AX=b B XB + N XN = b XB = B-1b - B-1 N XN 相应的目标函数值： Z= CX = CB XB + CN XN = CB (B-1b - B-1 N XN) + CN XN = CB B-1b +( CN - CB B-1 N) XN 0 XB,目标函数值中非基变量XN的系数 CN - CB B-1 N) XN有几种情况 Z=54-3X1-5X4 Z=39+X3-4X5+8X6,目标函数值中非基变量XN的系数

16、CN - CB B-1 N) XN有检验作用，叫检验数,( CN - CB B-1 N)是非基变量检验数 如果 非基变量 XN 0 则Z = CB B-1b,技术矩阵A中基变量系数B,技术矩阵A中 非基变量系数N,技术矩阵A中基变量系数B,技术矩阵A中 非基变量系数N,如果B=I单位矩阵，那么直接可以看出一个基本可行解= 顶点,检验数可以判别是否最优解,例 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 注意，线性规划

17、的基本解、基本可行 解（极点）和可行基只与线性规划问 题标准形式的约束条件有关。,理解线性规划基本定理,第一章：线性规划（2）,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,第一章：线性规划（2）,其中B4= 0，因而

18、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是一个可行基。,第一章：线性规划（2）,类似可得到 x(2) = (5,25,0,5,0)T

19、（对应B2） x(7) = (20,0,5,0,75)T （对应B5） x(8) = (0,25,15,15,0)T （对应B7） x(9) = (0,0,65,40,75)T （对应B10） 是基本可行解； 而x(3)= (0,32.5,0,7.5,-22.5)T（对应B9） x(4)= (65/3,0,0,-10/3,75)T （对应B6） x(5)= (7.5,25,-7.5,0,0)T （对应B1） x(6) = (0,40,-15,0,-45)T （对应B8） 是基本解。,第一章：线性规划（2）,因此，对应基本可行解（极点） 的B2 B3 B5 B7 B10都是可行基。 这里指出了一

20、种求解线性规划问题的可能途径，就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的（最多个），因此必定可以从有限个基本可行解中找到最优解。,第一章：线性规划（2）,利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。,求解线性规划的单纯形法,第一章：线性规划（2）,求解线性规划的单纯形法,从几何图解法猜想：LP最优解是可行域的顶点之一,现在从代数上看可行域的点的特点

21、可行域的点就是满足约束条件的点，因此从约束条件出发 AX=b B XB + N XN = b XB = B-1b - B-1 N XN 相应的目标函数值： Z= CX = CB XB + CN XN = CB (B-1b - B-1 N XN) + CN XN = CB B-1b +( CN - CB B-1 N) XN 0 XB 如果 XN = 0， XB = B-1b， 相应的目标函数值：Z= CB B-1b ，这个解不一定满足非负。 如果 XB = B-1b = 0, 那么XB = B-1b ， XN = 0 是可行解，也就是可行域的点 重要结论：如果 XB = B-1b = 0, 那么

22、XB = B-1b ， XN = 0 不仅是可行域的点， 而且是可行域的顶点。,第一章：线性规划（2）,例：用单纯形法的基本思路解线性规划问题 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,第一章：线性规划（2）,第一次迭代： （1）取初始可行基B10= (p3 , p4 , p5)，那么x3 ，x4 ，x5为基变量，x1 ，x2为非基变量。将基变量和目标函数用非基变量表示： z=1500 x1+2500 x2 x3

23、 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2 当非基变量x1，x2=0时，相应的基变量和目标函数值为x3=65，x4=40，x5= 75，z = 0，得到当前的基本可行解： x=(0,0,65,40,75)T，z = 0 。,第一章：线性规划（2）,（2）选择进基变量。在目标函数 z = 1500 x1 + 2500 x2中，非基变量x1，x2的系数都是正数，因此 x1 ，x2进基都可以使目标函数z增大，但x2的系数为2500，绝对值比x1的系数1500大，因此把x2作为进基变量可以使目标函数z增加更快。选择x2为进基变量，使x2

24、的值从0开始增加，另一个非基变量x1保持零值不变。,第一章：线性规划（2）,（3）确定出基变量。在约束条件 x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2 中，由于进基变量x2在3个约束条件中的系数都是负数，当x2的值从0开始增加时，基变量x3 、x4 、x5的值分别从当前的值65、40和75开始减少，当x2增加到25时，x5首先下降为0成为非基变量。这时，新的基变量为x3 、x4 、x2 ，新的非基变量为x1 、x5 ，当前的基本可行解和目标函数值为： x = (0，25，15，15，0)T，z = 62500。,第一章：线性

25、规划（2）,第二次迭代： （1）当前的可行基为B7 = (p2 , p3 , p4)，那么x2 ，x3 ，x4为基变量，x1 ，x5为非基变量。将基变量和目标函数用非基变量表示： z = 62500 + 1500 x1 (2500/3) x5 x2 = 25 (1/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5,第一章：线性规划（2）,（2）选择进基变量。在目标函数 z = 62500 + 1500 x1 (2500/3) x5 中，非基变量x1的系数是正数，因此 x1进基可以使目标函数z增大，于是选择x1进基，使x1的值从0

26、开始增加, 另一个非基变量x5保持零值不变。 (3)确定出基变量。 x2 = 25 (1/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5,第一章：线性规划（2）,在约束条件中，由于进基变量x1在两个约束条件中的系数都是负数，当x1的值从0开始增加时，基变量x3 、x4的值分别从当前的值15、15开始减少，当x1增加到5时，x3首先下降为0成为非基变量。这时，新的基变量为x1 、x2 、x4 ，新的非基变量为x3 、x5 ，当前的基本可行解和目标函数值为： x = (5，25，0，5，0)T，z = 70000。,第三次迭代：

27、（1）当前的可行基为B2 = (p1 , p2 , p4 )，那么x1 ，x2 ，x4为基变量，x3 ，x5为非基变量。将基变量和目标函数用非基变量表示： z = 70000 500 x3 500 x5 x1 = 5 (1/3) x3 + (2/9) x5 x2 = 25 (1/3) x5 x4 = 5 + (2/3) x3 (1/9) x5,第一章：线性规划（2）,（2）选择进基变量。在目标函数 z = 70000 500 x3 500 x5 中，非基变量x3 、x5的系数均不是正数，因此进基都不可能使目标函数z增大，于是得到最优解，x* = (5，25，0，5，0)T，最优目标值为z* =

28、 70000。我们也称相应的基B2 = (p1 , p2 , p4)为最优基。计算结束。,以下定义结合上面讲的图解法理解（对应可行域的顶点） 基 设标准形式线性规划的约束方程组为AX=b。若B是系数矩阵A的m阶满秩子矩阵，则称B是线性规划问题的一个基。B中的每一个列向量称为基向量，共m个，与基向量对应的变量称为基变量。B以外的列向量称为非基向量，共（nm）个,对应的变量称为非基变量。 基解 在标准形式线性规划的约束方程组中，对应基B，令所有非基变量都等于零，求解约束方程组AX=b，可惟一得出基变量的一组值，这些值和取零的非基变量的值合起来，称为线性规划问题的基解或基本解。 基的个数不超过从n中

29、取m的组合数 ，一个基对应一个基解，故基解的个数也不超过从n中取m的组合数 。基解中非零分量的个数不会大于约束方程的个数m。若一个基解的基变量中有取零值的，则此基解称为退化的，否则称为非退化的。 基可行解 对于标准形式的线性规划，如果一个基解X还满足变量取值非负性的约束条件X0，则称此基解为基可行解或基本可行解。 最优基 如果一个基可先行解是最优解，则它所对应的可行基叫做最优基。,第一章：线性规划（1）,根据下图，具体给出 可行域，ABFHE（阴影部分） 基可行解：点A，B，F，H，E（可行=非负） 基解：全部基可行解 + 点D，C，I，J，G,A,B,C,D,E,F,G,H,I,J,思路：几

30、何顶点（计算机不可识别） 如何用计算机可以识别的代数方法找到顶点,下面讲的单纯形法求解过程本质是从可行域的一个顶点转到另一个顶点 单纯形法与 George Dantzig 加州大学大二学生创新 （90岁）,AX=b B XB + N XN = b XB = B-1b - B-1 N XN Z= CX = CB XB + CN XN = CB (B-1b - B-1 N XN) + CN XN = CB B-1b +( CN - CB B-1 N) XN 0 XB 如果 XN = 0， XB = B-1b Z= CB B-1b 如果 XB = B-1b = 0, 那么XB = B-1b ， XN

31、 = 0 是可行解,代数方法,基B,非基N,我们想知道满足约束条件的点有什么特点 ，因此从约束方程出发,第一章：线性规划（2）,Max 2X1 +3X2 X1 + 2X2 =0 X2=0 加入松驰变量 X3 ，X4 ，X5 变成等式约束 Max 2X1 +3X2 +0X3 +0X4 +0X5 X1 + 2X2 + X3 = 8 4X1 + X4 =16 4X2 +X5 =12 X1=0 X2=0 X3=0 X4=0 X5=0,1 2 1 0 0 4 0 0 1 0 0 4 0 0 1,A=,XB =,X3 X4 X5,1 2 4 0 0 4,N=,XN =,X1 X2,第一章：线性规划（2）,

32、Max 2X1 +3X2 X1 + 2X2 =0 X2=0 加入松驰变量 X3 ，X4 ，X5 变成等式约束 Max 2X1 +3X2 +0X3 +0X4 +0X5 X1 + 2X2 + X3 = 8 4X1 + X4 =16 4X2 +X5 =12 X1=0 X2=0 X3=0 X4=0 X5=0 基变量 X3 ， X4 ，X5 令非基变量取零值，得：,X3 = 8 2X2 X1 + X4 =164X1 +X5 =124X2 如果令非基变量取零值，得： X3 = 8 + X4 =16 +X5 =12 第一个可行解， 对应利润为零， 显然不是最优解，在X1 ，X2 平面上对应的可行域的顶点是

33、（0，0）,第一章：线性规划（2）,代数求解 1经济上分析 2几何图形上分析 3表上分析,如何寻找下一个可行域的顶点？显然我们希望把利润比较高的第2种产品尽可能多地生产 我们看， X3 = 8 2X2 X1 =0 得： 如果 X1 = 0，则X2 =0 得 X1 =0 得 X2 = 3 就是说：产品1最大产量为4；这时原材料A用完，（X1 = 8，并且X1 = 4 ）；产品2最大产量为3；这时原材料B用完 （X2 = 4，并且X2 = 3）；由于产品2的单位利润大于产品1的单位利润，因此我们首先考虑尽可能多地生产产品2， X2 = 3 变成基变量， 这时 X5 = 0，变成非基变量。,第一章：

34、线性规划（2）,第1张单纯形 表：,检验数 ( CN - CB B-1 N) = （2 3）-（0 0 0） = （2 3）,N是A中去掉单位矩阵,第一章：线性规划（2）,5分钟练习：如何得到第1张单纯形 表： Max 5X1 - 2X2 s.t. 4X1 + 7X2 =0 X2=0,检验数 ( CN - CB B-1 N) =,我们希望把上面分析放在表中： 表的结构,第一章：线性规划（2）,生产各种产品产生的利润，选择利润最大者,生产第2种产品，受第3种资源约束的最大生产量,总资源约束,单位产品的资源数量,上面分析放在表内：,检验数: 经济含义 正中取大（相应产品产生的利润最大）,基：,第一

35、章：线性规划（2）,X5,X5,X5,X5,X5,X5,转轴元： 确定先订列 检验数正中取大（相应产品利润最大） 再定行相除后正中取小（相应资源约束最厉害 总资源/单位产品消耗资源）,第一章：线性规划（2）,转轴的代数意义： 把转轴元变成1：表示解出基变量X2 把这一列的检验数变成0：表示把基变量X2代入目标函数（加减消元方法） 把这一列的其他系数变成0：表示基变量X2代入其他方程（加减消元方法） 把转轴元所在方程的多少倍加到另外一个方程实现加减消元,第一章：线性规划（2）,再看完整的一个例 A.图解法: max Z=2X1+X2 3X1+5X2=0 由右图知,在G2点能得到最优解, 其中G2

36、点坐标(15/4,3/4) max Z=33/4,第一章：线性规划（2）,3X1+5X2 = 15,6X1+2X2 = 24,G2,B.单纯形法: Max Z=2X1+X2+0X3+0X4 3X1+5X2+X3 =15 6X1+2X2 +X4=24 X1,X2,X3,X4=0 其初始单纯形表为,第一章：线性规划（2）,转轴元：,3 5 1 0 6 2 0 1,A=,( CN - CB B-1 N) =（2 1）-（0 0）,=,N B,3 5 6 2,于是得到新的基可行解X(1)=(4,0,3,0)-T,此时Z=8,相当于图形上G3;将上表X2替换X3得 ：,第一章：线性规划（2）,下一步：

37、把转轴元相应列变为单位向量,所有检验数=0, 得到最优解下X(2)=(15/4,3/4,0,0)T,此时 max Z=33/4,相当于图形上的G2点.,第一章：线性规划（2）,单纯形法求解过程及其经济含意 单纯形法求解过程本质是从可行域的一个顶点转到另一个顶点 确定转轴元 先订列 检验数正中取大（相应产品利润最大） 再定行 相除后正中取小（相应资源约束最厉害） 思路：几何顶点（计算机不可识别）代数基解（计算机可识别） 基- -基解-基可行解 A=(B, N) X 非负,AX=b B XB + N XN = b XB = B-1b - B-1 N XN Z= CX = CB XB + CN XN

38、 = CB (B-1b - B-1 N XN) + CN XN = CB B-1b +( CN - CB B-1 N) XN 0 XB,第一章：线性规划（2）,( CN - CB B-1 N)是非基变量检验数 如果 非基变量 XN 0 则Z = CB B-1b,第一章：线性规划（2）,3单纯形法计算的实质就是用矩阵的初等行变换求解约束方组AX=b，但求出的是基本解，这与线性代数中解方程组不同。另外，用单纯形法求出的这个基本解还是可行解，这由初始单纯形表对应的问题的标准形式以及最小比值原则加以保证，而且单纯形法的迭代计算还能保证后面得到的基可行解比前面的好（即使目标函数值越来越大），这缘于选换入

39、变量时是选其检验数为正数的变量。这些技巧，是通常线性代数中线性方程组的理论方法中所未涉及的，也正是单纯形法的独特贡献。 【例】线性规划问题是否可算作条件极值问题，它与微积分中讲的条件极值问题有何不同？解：线性规划问题也可以看成是条件极值问题，即要在满足所有约束的条件下，求目标函数的极值。它与微积分中讲到的条件极值是不同的： （1）它的约束条件中可以有不等式约束，而后者的限制条件都是等式；（2） 它的约束条件的个数一般地都多于变量的个数，而后者恰恰相反；（3） 它的目标函数与约束条件都是线性的，而后者不必如此。,第一章：线性规划（2）,运筹学,线性规划（3）,第一章：线性规划（3） 一 如何从单

40、纯形表判断线性规划解各种类型 二 人工变量法求线性规划的初始可行基：,第一章：线性规划（3）,一 已知几何图形上判断线性规划解各种类型。 如何从单纯形表判断线性规划解各种类型?,第一章：线性规划（3）,第一章：线性规划（3）,1唯一最优解,第一章：线性规划（3）,2 无界最优解：,注意：这时找不到“转轴元” 因为无法进行“再定行相除后正中取小”， 非基X3 产生利润而不消耗资源， 越多越好,X5,X5,X5,X5,X5,X5,第一章：线性规划（3）,利润Z = 0(非基X3)+ 负(非基X5) 这时非基X3 取任何值，都不改变目标函数的值，因此有无穷最优解,3 无穷最优解：,第一章：线性规划（

41、3）,D0, 表示 D=0，表示 D0，表示,第一章：线性规划（3）,当a0 时： D0, 表示 转元是a D=0，表示 无穷个最优解 D0，表示 最优解达到,当a 0, 表示 无限大最优解,思路：我们从几何图解法知道关注顶点 单纯形法求解过程本质是从可行域的一个顶点转到另一个顶点，如何找到第一个顶点？实际第一个顶点对应A 中包括的一个单位矩阵,Max Z=2X1+X2+0X3+0X4 3X1+5X2+X3 =15 6X1+2X2 +X4=24 X1,X2,X3,X4=0,3 5 1 0 6 2 0 1,A=,=,N B,引入松弛变量后，A 中包括的一个单位矩阵,问题： 如果A 中不包括单位矩

42、阵，怎么办,第一章：线性规划（3）,例8 P32 1 min Z=-3 X1+X2+X3 X1 -2X2+ X3 =3 -2X1 + X3 =1 X1,X2,X3=0,第一章：线性规划（3）,问题： 下面例A 中不包括单位矩阵，怎么办,Min Z= -3X1+X2+X3+0X4+0X5 X1 -2X2+ X3 + X4 =11 -4X1+X2+ 2X3 -X5=3 -2X1 + X3 =1 X1,X2,X3=0 Xi=0,i =1,2,5,1 -2 1 1 0 -4 1 2 0 -1 -2 0 1 0 0,A=,例8 P32 1 min Z=-3 X1+X2+X3 X1 -2X2+ X3 =3

43、 -2X1 + X3 =1 X1,X2,X3=0,第一章：线性规划（3）,解决方法： 一定让A 中包括单位矩阵！,X1 -2X2+ X3 + X4 =11 -4X1+X2+ 2X3 -X5+ X6 =3 -2X1 + X3 + X7 =1 X1,X2,X3=0 Xi=0,i =1,2,7,1 -2 1 1 0 0 0 -4 1 2 0 -1 1 0 -2 0 1 0 0 0 1,A=,等式中再加入的变量叫人工变量，它必须为0，否则原来约束条件不成立！,二 ,人工变量法求线性规划的初始可行基： 目的：求初始可行基 原理：人工变量的成本无穷大 1,大M法 2,二阶段法 原理： 要点： 第一阶段：首

44、先加入人工变量 新的目标函数改变为： min 人工变量 （原来变量的成本为零） 用单纯形表求解 第二阶段：将第一阶段最终单纯形表除去人工变量 新的目标函数原来的目标函数,第一章：线性规划（3）,第一章：线性规划（3）,二 ,人工变量法 求线性规划初始可行基 人工变量必须为0，才能保证原来等式成立。 Ax=b，原问题有解 若从检验数判断最优解得到，但人工变量不全为零 则无解 1 大M法 例8 P32 1 min Z=-3 X1+X2+X3 X1 -2X2+ X3 =3 -2X1 + X3 =1 X1,X2,X3=0 要点：引入松弛变量X4 ，利润为零，引入剩余变量X5，利润为零，引入人工变量X6

45、 X7 利润为负无穷大（或者成本为无穷大）,第一章：线性规划（3）,Min Z= -3X1+X2+X3+0X4+0X5 + MX6 +MX7 X1 -2X2+ X3 + X4 =11 -4X1+X2+ 2X3 -X5+ X6 =3 -2X1 + X3 + X7 =1 Xi=0,i =1,2,7 请同学写出 第1张单纯形表,复习： AX=b B XB + N XN = b XB = B-1b - B-1 N XN Z= CX = CB XB + CN XN = CB (B-1b - B-1 N XN) + CN XN = CB B-1b +( CN - CB B-1 N) XN 0 XB 检验数

46、,Min Z= -3X1+X2+X3+0X4+0X5 + MX6 +MX7 X1 -2X2+ X3 + X4 =11 -4X1+X2+ 2X3 -X5+ X6 =3 -2X1 + X3 + X7 =1 X1,X2,X3=0 Xi=0,i =1,2,7 注意如何得 第1张单纯形表,目标值 CB B-1 b = （0，M，M） (11，3，1）T = 4M,初始表非基变量检验数 ( CN - CB B-1 N)=（-3，1，1，0）-（0, M，M） 1，-2，1， 0 -4，1， 2，-1 -2, 0, 1, 0 = （-3，1， 1，0） -（-6M，M， 3M，M ） =（-3+6M， 1-

47、M， 1-3M， M ）,第一章：线性规划（3）,非基变量检验数 ( CN - CB B-1 N)=（-3，1，1，0）-（0, M，M） 1，-2，1， 0 -4，1， 2，-1 -2, 0, 1, 0 = （-3，1， 1，0） -（-6M，M， 3M，+M ） =（-3+6M， 1-M， 1-3M， M ）,下一步： 把转轴元相应列变为单位向量: 这一行乘以 -（1-3M）加到最下一行,第一章：线性规划（3）,先确定转轴元：定行检验数 负中取小，定列相除后正中取小 下一步： 把转轴元相应列变为单位向量: 这一行乘以 -（1-M）加到最下一行 得到新检验数,第一章：线性规划（3）,第一章：

48、线性规划（3）,P32 例8 最后一表,X=（4，1，9，0，0，0，0） 人工变量全部为0,目标值-2,第一章：线性规划（3）,2 两阶段法 要点：第一阶段：加入人工变量，第一阶段的目标函数改变为：min 人工变量的和 （原来变量的成本为零） 用单纯形表求解 第二阶段：将第一阶段最终单纯形表除去人工变量， 第二阶段的目标函数原来的目标函数 引例： min Z=- 3X1 + X2 + X3 X1- 2X2 + X3 =3 -2X1 + X3 =1 X1,X2,X3=0,第一章：线性规划（3）,min W =人工X6 + 人工X7 X1- 2X2 + X3 X4 =11 -4X1 +X2+2X

49、3 X5 X6 =3 -2X1 + X3 X7 =1 X1, X2, X3 ，X4，X5 ，X6 ，X7=0,第一张单纯型表？,第一章：线性规划（3）,min W =人工X6 + 人工X7 X1- 2X2 + X3 X4 =11 -4X1 +X2+2X3 X5 X6 =3 -2X1 + X3 X7 =1 X1, X2, X3 ，X4，X5 ，X6 ，X7=0,第一张单纯型表 :,非基变量检验数计算CN - CB B-1N(0000)（0，1，1） 1 -2 1 0 4 1 2 -1 2 0 1 0,第一章：线性规划（3）,6,第一章：线性规划（3）,非基变量检验数计算CN - CB B-1N

50、0（0，1，1）（1，4，2 ）T 6 ( CN - CB B-1 N)是非基变量检验数 人工变量是非基变量零 因此有解,第一章：线性规划（3）,非基变量检验数计算CN - CB B-1N(3 0)（0，1，1） 3 -2 0 -1 -2 0,第一章：线性规划（3）,单纯形法的进一步讨论-大M法及两阶段法-解的类型 基本要求 1熟练掌握人工变量法（大M法及两阶段法）。 2能准确地根据单纯形表中的检验数判别所解问题的解的类型。 知识要点 1人工变量法 大M法： 用单纯形法求解线性规划问题时，先要将问题化为标准形式，若这时约束方程组的系数矩阵中还没有包括一个单位矩阵（阶数要等于约束方程的个数），则

51、可在一些约束方程上添加非负的人工变量，使系数矩阵中凑出个单位矩阵来。人工变量在目标函数中的系数为“-M”，M是充分大的正数。通过用单纯形法解这个新的线性规划（不妨称为大M问题）来求解原来的线性规划，这种方法叫大M法。 两阶段法 这种方法用与大M法相同。解决约束方程组系数矩阵中必须出现单位矩阵的问题，但以后将分成两个阶段计算：第一阶段目标函数是改为所有人工变量的和，求极小值，约束条件是原来问题的约束条件添加了松弛变量（剩余变量）以及人工变量后的约束条件。第二个阶段则是利用第一个阶段的结果单纯形表，或者说明原来题目无可行解，如果有解则去掉第一个阶段的结果单纯形表中人工变量对应的列，第二阶段目标函数

52、为原题目 的目标函数，继续根据单纯形方法计算,第一章：线性规划（3）,2检验准则（适用于有人工变量的问题，仅就大M法叙述，两阶段法有同样结论） （1）如果所有检验数均小于或等于零而且单纯形表的基变量没有取值非零的人工变量，那么已得到原来问题的最优解。 （2）如果所有检验数均小于或等于零，但基变量中还有不为零的人工变量，那么原 来问题无可行解。 （3）如果所解的大M问题有无界解（即有可行解但无最优解），则当人工变量全为零时，那么原来问题也有无界解，而当人工变量不全为零时，那么原来问题无可行解。 3关于线性规划问题最优解是唯一，有如下定理 非退化的基可行解X0是唯一最优解的充分必要条件是，这个基可

53、行解X0所有非基变量的检验数均小于零。 这也就是说，非退化的基可行解X0不是唯一最优解（从而问题有无穷多最优解）的充分必要条件是这个基可行解X0的某个非基变量的检验数等于零。,1。线性规划的引例与模型 矩阵A, 向量C,b,AX, a1,a1x,的经济含意 标准型式（max, 等式约束，非负限制） 松弛变量，剩余变量经济含意 可行解 2 线性规划的几何意义 图解法 可行域, 可行解 图示线性规划的解的各种情况 (1) 唯一最优解 (2) 无穷最优解 (3) 无界最优解 从图解法猜想 1 LP最优解是可行域的顶点之一 2 如可行域有界, 则LP最优解就是可行域的一个顶点 3 基可行解对应可行域的

54、顶点,运筹学,线性规划（4）,第一章：线性规划（4） 应用四例,线性规划模型特点 1 一个目标函数：线性 2 几个约束条件：线性 3 多个决策变量：非负,世界500强企业中广泛的应用是因为现实中的确存在各种约束： 关键设备生产能力约束 各类能源约束（电力，煤） 工艺流程约束 产品类结构关系约束（例如产品的合金比，钢坯的连铸比） 物流过程上，中，下游产品供需约束 某些产品下限约束（例如必要库存，稳定的用户需求）,第一章：线性规划（4） 应用四例,下料问题 案例 国际会议上本人听到日本教授的下料的论文。 本人家装修跃层木地板，废料多。 本人裁剪衣服，先用纸剪好。,第一章：线性规划（4） 应用四例,

55、企业 下料问题： 按需下料 废料最少,原材料7.4米,产品2.9米,产品2.1米,产品1.5米,第一章：线性规划（4） 应用四例,第一章：线性规划（4） 应用四例,例1 下料问题 用长度为.m的圆钢截断成制造某种机床所许的三个轴坯，长度分别为2.9m,2.1m,1.5m。现需要台机床。建立线性规划模型以寻求最佳的截断方案所需圆钢最少。 我们设j为第j种方案截断的圆钢根数，截断圆钢的方案有种：,第一章：线性规划（4）应用四例,在成品规格较多，原料长度较长，截断方案多时，表中的轴坯长度最好按长短从上到下排列，对第一行数字从左到右逐渐减少；在第一行数字相等时，第二行数字从左到右逐渐减少，这样可以避免遗漏。 目标函数是下料最少即： in0.1X1+0.3X2+0.9X3+1.1X5+0.2X6+0.8X7+1.4X8 约束条件方程是每种长度的轴坯至少是100根以及非负约束： 2X1+X2+X3+X4100 2X2+X3+3X5+2X6+X7100 X1+X3+3X4+2X6+3X7+4X8100 Xj0且为整数，j=1，2，38 由此可以解出最少需求。,第一章：线性规划（4） 应用四例,配料问题 案例 本人MBA学生: 工厂厂长 面临的问题：钢轨的配料,企业 配料问题 比例混 合,C,P,H,A,B,D,第一章：线性规划（4） 应用四例,例2 配料