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

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

2、数均为线性函数时，则称为线性规划。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）其中，f（x）、hi（x）和gp（x）为En内的实函数。目标解：设甲、乙、丙、丁四种产品的产量分别为x1,x2,x3和x4，则上述问题可表示为线性规划问题：产品台时材料1材料2材料3每千克产品预测利润甲a11a21a31a41c1乙a12a22a32a42c2丙a13a23a33a43c3丁a14a24a34a44c

3、4资源限制b1b2b3b41.1求：使预测利润最大的方案。解：设甲、乙、丙、丁四种产品的产量分别为x1,x2,x3和x例1.2 某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？ 设 备产 品 A B C D利润（元） 甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 台 时 12 8 16 12例1.2 某企业计划生产甲、乙两种产品。这些产品分别要在解：设x1、x2分别为甲、乙两种产品的产量，则 数学模型为：max Z = 2x1 + 3x

4、2 x1 0 , x2 0s.t. 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12解：设x1、x2分别为甲、乙两种产品的产量，则max Z 水资源系统中的线性规划问题例1.3 某冲积平原有四个供水井，拟取砂石承压含水层地下水作供水之用，设四个井的允许降深分别为15，18，17，20米，问各井抽水量为多少，才能使总开采量最大？ 解：设各抽水井的抽水量分别为x1，x2，x3，x4，四个井同时工作，相互间产生水位干扰，根据线性叠加原理，流场内任一点，水位降深等于各井抽水对该点降深之和。设aij代表第j井单位抽水量在i井处产生的降深，则四个井的降深分别为： ， ， ，依题意

5、有：该问题的目标是使开采量最大化，即：maxZ=x1+x2+x3+x4同时，各井的降深不能超过允许降深，即 约束条件为：显然还应有：x1，x2，x3，x40水资源系统中的线性规划问题例1.3 某冲积平原有四个供水井，2.1 线性规划问题的标准型1. 线性规划的数学模型由三个要素构成决策变量 Decision variables 目标函数 Objective function约束条件 Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。 怎样辨别一个模型是线性规划模型？ 2.1 线性规划问

6、题的标准型1. 线性规划的数学模型由三个要目标函数：约束条件：2. 线性规划数学模型的一般形式简写为：目标函数：约束条件：2. 线性规划数学模型的一般形式简写为：向量形式：其中：向量形式：其中：矩阵形式：其中：矩阵形式：其中：3. 线性规划问题的标准形式特点：(1) 目标函数求最大值（有时求最小值）(2) 约束条件都为等式方程，且右端常数项bi都大于或等于零(3) 决策变量xj为非负。3. 线性规划问题的标准形式特点：如何化标准形式？ 目标函数的转换 如果是求极小值即 ，则可将目标函数乘以(-1)，可化为求极大值问题。也就是：令 ，可得到上式。即若存在取值无约束的变量 ，可令 其中： 变量的变

7、换如何化标准形式？ 目标函数的转换 如果是求极小值即 约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量 变量 的变换 可令 ，显然 约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变例1.4 将下列线性规划问题化为标准形式例1.4 将下列线性规划问题化为标准形式(2) 第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3) 第二个约束条件是“”号，在“”左端减去剩余变量x5，x50；(4) 第3个约束方程右端常数项为-5，方程两边同乘以(-1)，将右端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令z=-z,得到max z=-z，即当z

8、达到最小值时z达到最大值，反之亦然;解:（）因为x3无符号要求 ，即x3取正值也可取负值，标准型中要求变量非负，所以用 替换 ，且 (2) 第一个约束条件是“”号，在“”左端加入松驰变量x标准形式如下：标准形式如下：线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。2.2 基本解和基本可行解线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3 可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。 最优解：使目标函数达到最大值的可行解。 基：设A为约束条件的mn阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵

9、（B0），称B是规划问题的一个基。设：称 B中每个列向量Pj ( j = 1 2 m) 为基向量。与基向量Pj 对应的变量xj 为基变量。除基变量以外的变量为非基变量。 可行解：满足约束条件、的解为可行解。所有可行解的集合 基解：某一确定的基B，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过 基可行解：满足变量非负约束条件的基本解，简称基可行解。 可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解 基解：某一确定的基B，令非基变量等于零，由约束条件方程对于有n个变量、m个等式约束的线性规划问题，基本解的个数最

10、多为：基本可行解的个数最多为：2.3 线性规划的基本定理对于有n个变量、m个等式约束的线性规划问题，基本解的个数最多例2. 2-1 求线性规划问题的所有基矩阵解: 约束方程的系数矩阵为25矩阵 r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即例2. 2-1 求线性规划问题的所有基矩阵解: 约束方程的系图解法线性规划问题的求解方法一 般 有两种方法图 解 法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但必需将一般形式变成标准形式下面我们分析一下简单的情况 只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几

11、何意义等优点。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 用图解法求解线性规划问题max Z = 2X1 + X2 例2.2-2 用图解法图解法x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2

12、17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此点是唯一最优解，且最优目标函数值 max Z=17.2可行域max Z = 2X1 + X2图解法x1x2oX1 - 1.9X2 = 3.8()X1 图解法max 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 蓝色线段上的所

13、有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值max Z=34.2是唯一的。可行域图解法max Z=3X1+5.7X2x1x2oX1 - 1.图解法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图解法x1x2oX1 - 1.9X2 = 3.8 ()X1246x1x2246无界解(无最优解)max Z=x1+2x2例2.2-3x1+x2=4()x1+3x2

14、=6()3x1+x2=6() max Z min Z246x1x2246无界解(无最优解)max Z=x1+2xx1x2O10203040102030405050无可行解(即无最优解)max Z=3x1+4x2例2.2-4x1x2O10203040102030405050无可行解(图解法学习要点：1. 通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）2. 作图的关键有三点： (1) 可行解区域要画正确 (2) 目标函数增加的方向不能画错 (3) 目标函数的直线怎样平行移动图解法学习要点：相关定理与推论相关定理与推论本章小结1、线性规划的标准型2、线性规划的基本解和基本可行解3、线性规划的常用求解方法图解法本章小结1、线性规划的标准型作业靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为每天200万m3的支流。第一化工厂每天排放含有某种有害物质的工业污水2万m3，第二天化工厂每天