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

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 线性规划的基本性质,第二章 线性规划的基本性质,1,本章主要内容,线性规划问题的标准型,基本解和基本可行解,线性规划的基本定理,基本可行解与极点的关系（图解法）,本章主要内容线性规划问题的标准型,2,线性规划问题的雏形,考虑问题：,求 max x,0,=x,1,+3x,2,满足条件：-x,1,+x,2,1,x,1,+x,2,2 （,p,）,X,1,，x,2,0,x,1,x,2,C,B,A,D,X,0,=5,X,0,=0,线性规划问题最基本的性质：,在顶点达到极值，通过代数方法，描述高维空间中多面体的顶点，然后，进一步求出达到极值的顶点。,线性规划问题的雏形考虑问题：x1x2CBADX0=5X0=0,3,其中，,f,（,x,）、,h,i,（,x,）和,g,p,（,x,）为,E,n,内的实函数。,目标函数,约束函数,当目标函数与约束函数均为线性函数时，则称为线性规划。,线性规划通常解决下列两类问题：,（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标,（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大）,其中，f（x）、hi（x）和gp（x）为En内的实函数。目标,4,解：设甲、乙、丙、丁四种产品的产量分别为x,1,x,2,x,3,和x,4,，则上述问题可表示为线性规划问题：,产品,台时,材料1,材料2,材料3,每千克产品预测利润,甲,a,11,a,21,a,31,a,41,c,1,乙,a,12,a,22,a,32,a,42,c,2,丙,a,13,a,23,a,33,a,43,c,3,丁,a,14,a,24,a,34,a,44,c,4,资源限制,b,1,b,2,b,3,b,4,1.1,求：使预测利润最大的方案。,解：设甲、乙、丙、丁四种产品的产量分别为x1,x2,x3和x,5,例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 某企业计划生产甲、乙两种产品。这些产品分别要在,6,解：,设,x,1,、,x,2,分别为甲、乙两种产品的产量，则,数学模型为：,max Z=2x,1,+3x,2,x,1,0,x,2,0,s.t.,2x,1,+2x,2,12,x,1,+2x,2,8,4x,1,16,4x,2,12,解：设x1、x2分别为甲、乙两种产品的产量，则max Z,7,水资源系统中的线性规划问题,例1.3,某冲积平原有四个供水井，拟取砂石承压含水层地下水作供水之用，设四个井的允许降深分别为15，18，17，20米，问各井抽水量为多少，才能使总开采量最大？,解：设各抽水井的抽水量分别为x,1,，x,2,，x,3,，x,4,，四个井同时工作，相互间产生水位干扰，根据线性叠加原理，流场内任一点，水位降深等于各井抽水对该点降深之和。,设a,ij,代表第j井单位抽水量在i井处产生的降深，则四个井的降深分别为：,，,依题意有：该问题的目标是使开采量最大化，即：,maxZ=x,1,+x,2,+x,3,+x,4,同时，各井的降深不能超过允许降深，即,约束条件为：,显然还应有：x,1,，x,2,，x,3,，x,4,0,水资源系统中的线性规划问题例1.3 某冲积平原有四个供水井，,8,2.1 线性规划问题的标准型,1.线性规划的数学模型由三个要素构成,决策变量,Decision variables,目标函数 Objective function,约束条件 Constraints,其特征是：,（,1）问题的目标函数是多个决策变量的,线性函数,，通常是求最大值或最小值；,（2）问题的约束条件是一组多个决策变量的,线性,不等式或等式。,怎样辨别一个模型是线性规划模型？,2.1 线性规划问题的标准型1.线性规划的数学模型由三个要,9,目标函数：,约束条件：,2.线性规划数学模型的一般形式,简写为：,目标函数：约束条件：2.线性规划数学模型的一般形式简写为：,10,向量形式：,其中：,向量形式：其中：,11,矩阵形式：,其中：,矩阵形式：其中：,12,3.线性规划问题的标准形式,特点：,(1)目标函数求最大值（有时求最小值）,(2)约束条件都为等式方程，且右端常数项,b,i,都大于或等于零,(3)决策变量,x,j,为非负。,3.线性规划问题的标准形式特点：,13,如何化标准形式？,目标函数的转换,如果是求极小值即 ，则可将目标函数乘以(-1)，可化为求极大值问题。,也就是：令 ，可得到上式。,即,若存在取值无约束的变量 ，可令,其中：,变量的变换,如何化标准形式？目标函数的转换 如果是求极小值即,14,约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,变量 的变换,可令 ，显然,约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变,15,例1.4 将下列线性规划问题化为标准形式,例1.4 将下列线性规划问题化为标准形式,16,(2)第一个约束条件是“”号，在“”左端加入松驰变量,x,4,，,x,4,0,化为等式；,(3)第二个约束条件是“”号，在“”左端减去剩余变量,x,5,，,x,5,0；,(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1)，将右端常数项化为正数；,(5)目标函数是最小值，为了化为求最大值，令z=-z,得到max z=-z，即当z达到最小值时z达到最大值，反之亦然;,解:（）因为,x,3,无符号要求，即,x,3,取正值也可取负值，标准型中要求变量非负，所以,用 替换 ，且,(2)第一个约束条件是“”号，在“”左端加入松驰变量x,17,标准形式如下：,标准形式如下：,18,线性规划问题,求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。,2.2 基本解和基本可行解,线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3,19,可行解,：满足约束条件、的解为可行解。所有可行解的集合为可行域。,最优解,：使目标函数达到最大值的可行解。,基：,设A为约束条件的mn阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（B0），称B是规划问题的一个基。设：,称 B中每个列向量,P,j,(j=1 2,m),为基向量。与基向量,P,j,对应的变量,x,j,为,基变量,。除基变量以外的变量为,非基变量,。,可行解：满足约束条件、的解为可行解。所有可行解的集合,20,基解：,某一确定的基B，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过,基可行解：,满足变量非负约束条件的基本解，简称基可行解。,可行基：,对应于基可行解的基称为可行基。,非可行解,可,行,解,基解,基可行解,基解：某一确定的基B，令非基变量等于零，由约束条件方程,21,对于有n个变量、m个等式约束的线性规划问题，基本解的个数最多为：,基本可行解的个数最多为：,2.3 线性规划的基本定理,对于有n个变量、m个等式约束的线性规划问题，基本解的个数最多,22,例2.2-1 求线性规划问题的所有基矩阵,解:约束方程的系数矩阵为25矩阵,r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即,例2.2-1 求线性规划问题的所有基矩阵解:约束方程的系,23,图解法,线性规划问题的求解方法,一 般 有,两种方法,图 解 法,单纯形法,两个变量、直角坐标,三个变量、立体坐标,适用于任意变量、但必需将,一般形式变成标准形式,下面我们分析一下简单的情况,只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。,2.4 基本可行解与极点的关系,图解法线性规划问题的求解方法一 般 有图 解 法两个变量、直,24,max Z=2X,1,+X,2,X,1,+1.9X,2,3.8,X,1,-1.9X,2,3.8,s.t.X,1,+1.9X,2,10.2,X,1,-1.9X,2,-3.8,X,1,，X,2,0,例2.2-2 用图解法求解线性规划问题,max Z=2X1+X2 例2.2-2 用图解法,25,图解法,x,1,x,2,o,X,1,-1.9X,2,=3.8,(),X,1,+1.9X,2,=3.8(,),X,1,-1.9X,2,=-3.8(,),X,1,+1.9X,2,=10.2,(),4=2X,1,+X,2,20=2X,1,+X,2,17.2=2X,1,+X,2,11=2X,1,+X,2,Lo：0=2X,1,+X,2,（7.6，2）,D,max Z,min Z,此点是唯一最优解，,且最优目标函数值,max Z=17.2,可行域,max Z=2X,1,+X,2,图解法x1x2oX1-1.9X2=3.8()X1,26,图解法,max Z=3X,1,+5.7X,2,x,1,x,2,o,X,1,-1.9X,2,=3.8,(),X,1,+1.9X,2,=3.8(,),X,1,-1.9X,2,=-3.8(,),X,1,+1.9X,2,=10.2,(),（7.6，2）,D,L,0,：0=3X,1,+5.7X,2,max Z,（3.8，4）,34.2,=3X,1,+5.7X,2,蓝色线段上的所有点都是最,优解这种情形为有无穷多最,优解，但是最优目标函数值,max Z=34.2是唯一的。,可行域,图解法max Z=3X1+5.7X2x1x2oX1-1.,27,图解法,x,1,x,2,o,X,1,-1.9X,2,=3.8,(),X,1,+1.9X,2,=3.8(,),X,1,+1.9X,2,=10.2,(),D,L,0,：0=5X,1,+4X,2,max Z,min Z,8=5X,1,+4X,2,43=5X,1,+4X,2,（0，2）,可行域,此点是唯一最优解,min Z=5X,1,+4X,2,图解法x1x2oX1-1.9X2=3.8()X1,28,2,4,6,x,1,x,2,2,4,6,无界解(无最优解),max,Z,=,x,1,+2,x,2,例2.2-3,x1+x2=4(),x1+3x2=6(),3x1+x2=6(),max Z,min Z,246x1x2246无界解(无最优解)max Z=x1+2x,29,x,1,x,2,O,10,20,30,40,10,20,30,40,50,50,无可行解(即无最优解),max Z=3,x,1,+4,x,2,例2.2-4,x1x2O10203040102030405050无可行解(,30,图解法,学习要点：,1.通过图解法了解线性规划有几种解的形式,（唯一最优解；无穷多最优解；无界解；无可行解）,2.,作图的关键有三点：,(1)可行解区域要画正确,(2)目标函数增加的方向不能画错,(3)目标函数的直线怎样平行移动,图解法学习要点：,31,相关定理与推论,相关定理与推论,32,本章小结,1、线性规划的标准型,2、线性规划的基本解和基本可行解,3、线性规划的常用求解方法图解法,本章小结1、线性规划的标准型,33,作业,靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m,3,，在两个工厂之间有一条流量为每天200万m,3,的支流。第一化工厂每天排放含有某种有害物质的工业污水2万m,3,，第二天化工厂每天排放这种工业污水1.4万m,3,。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个化工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是100元/万m,3,，