《数学规划》第二章-线性规划.ppt

1、数学规划第二章-线性规划本章主要内容n线性规划问题的标准型n基本解和基本可行解n线性规划的基本定理n基本可行解与极点的关系（图解法）线性规划问题的雏形考虑问题：n求 max x0=x1+3x2满足条件：-x1+x21 x1+x2 2 （p）X1，x20 x1x2CBADX0=5X0=0线性规划问题最基本的性质：线性规划问题最基本的性质：在顶点达到极值，通过代数方法，在顶点达到极值，通过代数方法，描述高维空间中多面体的顶点，然描述高维空间中多面体的顶点，然后，进一步求出达到极值的顶点。后，进一步求出达到极值的顶点。n其中，f（x）、hi（x）和gp（x）为En内的实函数。目标函数约束函数当目标函

2、数与约束函数均为线性函数时，则称为线性规划。线性规划通常解决下列两类问题：线性规划通常解决下列两类问题：（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源最少的资源 （如资金、设备、原标材料、人工、时间等）（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标去完成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多好的经济效益（如产品量最多 、利润最大）、利润最大）解：设甲、乙、丙、丁四种产品的产量分别为x1,x2,x3和x4，

3、则上述问题可表示为线性规划问题：产品产品台时台时材料材料1材料材料2材料材料3每千克产品预测利润每千克产品预测利润甲甲a11a21a31a41c1乙乙a12a22a32a42c2丙丙a13a23a33a43c3丁丁a14a24a34a44c4资源限制资源限制b1b2b3b41.1求：使预测利润最大的方案。求：使预测利润最大的方案。例例1.2 某企业计划生产甲、乙两种产品。这些产品分某企业计划生产甲、乙两种产品。这些产品分别要在别要在A、B、C、D、四种不同的设备上加工。按工、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台艺资料规定，单件产品在不同设备上加工所需要的台时

4、如下表所示，企业决策者应如何安排生产计划，使时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？企业总的利润最大？设 备产 品 A B C D利润（元）甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 台 时 12 8 16 12n解：设x1、x2分别为甲、乙两种产品的产量，则 数学模型为：水资源系统中的线性规划问题水资源系统中的线性规划问题n例1.3 某冲积平原有四个供水井，拟取砂石承压含水层地下水作供水某冲积平原有四个供水井，拟取砂石承压含水层地下水作供水之用，设四个井的允许降深分别为之用，设四个井的允许降深分别为15，18，17，20米，问各井抽水量米，问各井抽水量为多

5、少，才能使总开采量最大？为多少，才能使总开采量最大？解：设各抽水井的抽水量分别为x1，x2，x3，x4，四个井同时工作，相互间产生水位干扰，根据线性叠加原理，流场内任一点，水位降深等于各井抽水对该点降深之和。n设aij代表第j井单位抽水量在i井处产生的降深，则四个井的降深分别为：，411jjjxa412jjjxa413jjjxa414jjjxan依题意有：该问题的目标是使开采量最大化，即：maxZ=x1+x2+x3+x4n同时，各井的降深不能超过允许降深，即 约束条件为：n显然还应有：x1，x2，x3，x402017181544434324214143433323213142432322212

6、1414313212111xaxaxaxaxaxaxaxaxaxaxaxaxaxaxaxa2.1 线性规划问题的标准型线性规划问题的标准型1.线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成1 1）问题的目标函数是多个决策变量的）问题的目标函数是多个决策变量的线性函数线性函数，通常是求最，通常是求最大值或最小值；大值或最小值；（2 2）问题的约束条件是一组多个决策变量的）问题的约束条件是一组多个决策变量的线性线性不等式或等式。不等式或等式。00 )()(min)max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz目标函数：

7、目标函数：约束条件：约束条件：2.线性规划数学模型的一般形式线性规划数学模型的一般形式)21(j 0 )21(i )(Z(min)max 11nxmbxaxcjnjijijnjjj简写为：简写为：)(21TncccC nxxX1 mjjjaaP1 mbbB1 0)(min)maxTXBxpXCzjj其中：其中：mnmnaaaaA1111 0)(min)maxTXBAXXCZ其中：其中：nxxX1 mbbB1)(21TncccCn3.线性规划问题的标准形式m,1,2,in,1,2,j0,xbxas.txc max Zjn1jijijn1jjj特点：特点：(1)目标函数求最大值（有时求最小值）目标

8、函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3)决策变量决策变量xj为非负。为非负。如何化标准形式？如何化标准形式？目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函数乘以，则可将目标函数乘以(-1)，可化为求极大值问题。可化为求极大值问题。jjxczmin也就是：令也就是：令 ，可得到上式。，可得到上式。zz jjxczzmax即即若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：jxjjjxxx 0,jjxx 变量的变换变量的变换 约束方程的转换：由

9、不等式转换为等式。约束方程的转换：由不等式转换为等式。ijijbxa0iniinjijxbxxa称为松弛变量称为松弛变量 ijijbxa0iniinjijxbxxa称为剩余变量称为剩余变量 变量变量 的变换的变换 可令可令 ，显然，显然0jxjjxx0 jx例例1.4 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式 ,0,52324 7 532min321321321321321无约束xxxxxxxxxxxxxxxZ(2)第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变量左端加入松驰变量x4，x40,化为等式；化为等式；(3)第二个约束条件是第二个约束条件是“”

10、号，在号，在“”左端减去剩余变量左端减去剩余变量x5，x50；(4)第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以，方程两边同乘以(-1)，将右端常数项化为正数；将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到max z=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然;解解:（）因为（）因为x3无符号要求无符号要求，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以33xx 3x0,33 xx用用 替换替换 ，且

11、，且 0,5 )(252 )(7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ标准形式如下：标准形式如下：)3(,2,1,0)2(),2,1(.)1(max11njxmibxatsxcZjnjijijnjjj线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)(2)、(3)(3)的方程的方程组中找出一个解，使目标函数组中找出一个解，使目标函数(1)(1)达到最大值。达到最大值。2.2 基本解和基本可行解基本解和基本可行解 可行解可行解：满足约束条件、的解为可行

12、解。所有可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。的集合为可行域。最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。基：基：设设A为约束条件的为约束条件的mn阶系数矩阵阶系数矩阵(mn)，其秩为，其秩为m，B是矩阵是矩阵A中中m阶满秩子矩阵（阶满秩子矩阵（B 0），称），称B是规划问题的是规划问题的一个基。设：一个基。设：)(11111mmmmmppaaaaB 称称 B中每个列向量中每个列向量Pj(j=1 2 m)为基向量。与基向量为基向量。与基向量Pj 对应的变量对应的变量xj 为为基变量基变量。除基变量以外的变量为。除基变量以外的变量为非基变量

13、非基变量。基解：某一确定的基B，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过 基可行解：满足变量非负约束条件的基本解，简称基可行解。可行基：对应于基可行解的基称为可行基。mnC非可行解非可行解可可行行解解基解基解基可行解基可行解n对于有n个变量、m个等式约束的线性规划问题，基本解的个数最多为：基本可行解的个数最多为：2.3 线性规划的基本定理线性规划的基本定理n例2.2-1 求线性规划问题的所有基矩阵 5,1,0226103524max53214321321jxxxxxxxxxxxxZj解解:约束方程的系数矩阵为约束方程

14、的系数矩阵为25矩阵矩阵 10261001115Ar(A)=2，2阶子矩阵有阶子矩阵有10个，其中基矩阵只有个，其中基矩阵只有9个，即个，即 100116010211120101015061111005261161015987654321BBBBBBBBB图解法图解法n线性规划问题的求解方法线性规划问题的求解方法一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但必需将适用于任意变量、但必需将一般形式变成标准形式一般形式变成标准形式下面我们分析一下简单的情况下面我们分析一下简单的情况 只有两个

15、决策只有两个决策变量的线性规划问题，这时可以通过图解的方法变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。探线性规划基本原理和几何意义等优点。2.4 基本可行解与极点的关系max Z=2X1+X2 X1+1.9X2 3.8 X1 -1.9X2 3.8s.t.X1+1.9X2 10.2 X1 -1.9X2 -3.8 X1 ，X2 0例例2.2-2 用图解法求解线性规划问题用图解法求解线性规划问题x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.

16、8()X1+1.9X2=10.2()4=2X1+X2 20=2X1+X2 17.2=2X1+X2 11=2X1+X2 Lo：0=2X1+X2（7.6，2）Dmax Zmin Z此点是唯一最优解，此点是唯一最优解，且最优目标函数值且最优目标函数值 max Z=17.2可行域可行域max Z=2X1+X2max Z=3X1+5.7X2x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1-1.9X2=-3.8()X1+1.9X2=10.2()（7.6，2）DL0：0=3X1+5.7X2 max Z（3.8，4）34.2=3X1+5.7X2 蓝色线段上的所有点都是最蓝色线段上的所有点

17、都是最优解这种情形为有无穷多最优解这种情形为有无穷多最优解，但是最优目标函数值优解，但是最优目标函数值max Z=34.2是唯一的。是唯一的。可行域可行域x1x2oX1-1.9X2=3.8()X1+1.9X2=3.8()X1+1.9X2=10.2()DL0：0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2（0，2）可行域可行域此点是唯一最优解此点是唯一最优解min Z=5X1+4X2 006346321212121xxxxxxxx、246x1x2246无界解无界解(无最优解无最优解)max Z=x1+2x2例例2.2-3x1+x2=4()x1+3x2=6()

18、3x1+x2=6()max Z min Zx1x2O10203040102030405050无可行解无可行解(即无最优解即无最优解)0,050305.140221212121 xxxxxxxxmax Z=3x1+4x2例例2.2-4学习要点：学习要点：1.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）（唯一最优解；无穷多最优解；无界解；无可行解）2.作图的关键有三点：作图的关键有三点：(1)可行解区域要画正确可行解区域要画正确(2)目标函数增加的方向不能画错目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动目标函数

19、的直线怎样平行移动相关定理与推论相关定理与推论本章小结1、线性规划的标准型2、线性规划的基本解和基本可行解3、线性规划的常用求解方法图解法作业n靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为每天200万m3的支流。第一化工厂每天排放含有某种有害物质的工业污水2万m3，第二天化工厂每天排放这种工业污水1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个化工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是100元/万m3，第二化工厂处理工业污水的成本是800元/万m3。n问：在满足环保要求的条件下，每个工厂各应处理多少工业污水，使这两个工厂每天处理工业污水费用最小。