第一章1、线性规划问题的基本概念-(1).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,最优化方法,孔翔宇,北方民族大学数学与信息科学学院,序,研究内容：在有限种或无限种可行方案中挑选最优方案，,构造寻求最优解的计算方法,研究目的：主要解决最优计划、最优分配、最,优决策、最佳设计、最佳管理等最优化问题。,应用领域：科学工程、国防、交通、管理、经济、金融、,计算机等。,1.,最优化方法概述,2,最优化方法,(Optimization Techniques),隶属于运筹学,.,运筹学（,Operations Research,）是用数学方法研究各种系统的最优化问题，应用数学模型求得合理利用各种资源的最佳方案，为决策者提供科学决策的依据。,数学规划又包括线性规划，整数规划，非线性规划，目标规划和动态规划等，是运筹学的主要内容,.,一些背景知识,3,运筹学这一名词最早出现于,1938,年。当时英，美等国盟军在与德国的战争中遇到了许多错综复杂的战略和战术问题难以解决，比如,(,),防空雷达的布置问题,：,(,),护航舰队的编队问题,：,为了应付上述各种复杂问题，英美等国逐批召集不同专业背景的科学家，在三军组织了各种研究小组，研究的问题都是军事性质的，在英国称为“,Operational Research”,，其他英语国家称为“,Operations Research”,，意思是军事行动研究。这些研究小组运用系统优化的思想，应用数学技术分析军事问题，取得了非常理想的效果。,4,二次大战以后，在军事运筹小组中工作过的一部分科学家开始转入民用部门，他们把对军事系统最优化的研究成果拓展到各种民用系统的研究上。,1947,年美国数学家,G.B.Dantzig,在研究,美国空军资源配置,时,提出了求解线性规划的有效方法,单纯形法,。二十世纪五十年代初，应用计算机求解线性规划获得成功。,至五十年代末，一些工业先进国家的大型企业已经较普遍地使用运筹学方法解决在生产经营管理中遇到的实际问题，并取得了良好的效果，至六十年代中期，运筹学开始应用于一些服务性行业和公用事业。,5,我国运筹学的研究始于五十年代中期,，当时由,钱学森,教授将运筹学从西方国家引入我国，以,华罗庚,教授为首的一大批科学家在有关企事业单位积极推广和普及运筹学方法，在建筑，纺织，交通运输，水利建设和邮电等行业都有不少应用。关于邮递员投递的最佳路线问题就是由我国年轻的数学家,管梅谷,于,1962,年首先提出的，在国际上统称为中国邮递员问题。我国运筹学的理论和应用研究在较短时间内赶上了世界水平。,6,2.,学习本课程所需的数学知识,向量、向量的模（范数）、向量的运算、,线性相关与无关、基,.,矩阵的运算及性质、矩阵的秩、特征值、正定性。,向量函数、连续性、可微性、,梯度,、,Hessen,矩阵,、向量函数（多元函数,）,Taylor,定理,7,3.,课程基本内容：,线性规划,无约束最优化方法,约束最优化方法,多目标最优化方法（选学）,动态优化方法（选学）,8,4.,学习要求,掌握,主要的优化模型的数学计算方法,.,了解,现代优化方法及其数学原理,.,熟练掌握,应用数学软件计算优化问题,.,9,5.,参考书目,主要参考书目：,理论方面：,(1),解可新、韩健，,最优化方法,，天津大学出版社,2004,(2),何坚勇，,最优化方法,清华大学出版社，,2007,计算方面：,(3),马昌凤，,最优化方法及其,MATLAB,程序设计,，科学出版社，,2010,(4),朱德通，,最优化模型与实验,同济大学出版社，,2003,其它参考书：,(5),卢名高、刘庆吉编著，,最优化应用技术,，石油工业出版社,2002,(6),唐焕文，秦学志,实用最优化方法,，大连理工大学出版社，,2004,(7),钱颂迪，,运筹学,，清华大学出版社，,1990,(8),袁亚湘、孙文瑜著，,最优化理论与方法,，科学出版社，,2005,10,第一讲 线性规划的基本概念,线性规划问题及其数学模型,线性规划的图解法,线性规划问题的标准型,标准型线性规划的解,线性规划的基本原理,1.,问题的提出：,在生产管理的经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方式。,有限资源：劳动力、原材料、设备或资金等,最佳：有一个标准或目标，使利润达到最大或成本达到最小。,有限资源的合理配置有,两类,问题,如何合理的使用有限的资源，使生产经营的,效益达到最大,；,在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所,消耗的资源数最少,。,1.1,线性规划问题及其数学模型,例,:,某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：,每吨产品的消耗,每周资源总量,甲,乙,维生素,（公斤）,30,20,160,设备,（台）,5,1,15,已知该厂生产每吨甲、乙药品的利润分别为,5,万元和,2,万元。但根据市场需求调查的结果，甲药品每周的产量不应超过,4,吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？,定义,:,x,1,为生产甲种药品的计划产量数，,x,2,为生产乙种药品的计划产量数。,目标：,要使总利润最大化,max,z,=5,x,1,+2,x,2,约束：,每周资源总量的限制，,30,x,1,+20,x,2,160,5,x,1,+,x,2,15,甲种药品每周产量不应超过,4,吨的限制,x,1,4,计划生产数不可能是负数，,x,1,0,x,2,0,每吨产品的消耗,每周资源总量,甲,乙,维生素,（公斤）,30,20,160,设备,（台）,5,1,15,单位利润,(,万元,),5,数学模型为,每吨产品的消耗,每周资源总量,甲,乙,维生素（公斤）,30,20,160,设备（台）,5,1,15,单位利润,(,万元,),5,这是一个如何合理的使用有限的资源，使生产经营的效益达到最大的数学规划问题。,在满足一组约束条件的限制下，寻求,决策变量,x,1,，,x,2,的决策值，使目标函数达到最大值。,例：,某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品。已知甲、乙两种原料都含有,A,、,B,、,C,三种化学成分，两种原料分别所含三种化学成分的百分比含量，以及按合同规定的产品中三种化学成分的最低含量如下表所示：,已知甲、乙两种原料的成本分别是每公斤,3,元和,2,元，厂方希望总成本达到最小，问如何配置该产品？,原料,化学成分含量（,%,）,产品中化学成分的最低含量,（,%,）,甲,乙,A,12,3,4,B,2,3,2,C,3,15,5,化学成分,定义,x,1,，,x,2,分别为每公斤产品中甲，乙两种原料的数量，,目标：,使总成本最小化,min,z,=3,x,1,+2,x,2,约束：,配料平衡条件，,x,1,+,x,2,=1,产品中,A,、,B,、,C,三种化学成分的最低含量,12,x,1,+3,x,2,4,2,x,1,+3,x,2,2,3,x,1,+15,x,2,5,非负性条件,x,1,0,x,2,0,原料,化学成分含量（,%,）,产品中化学成分的最低含量（,%,）,甲,乙,A,12,3,4,B,2,3,2,C,3,15,5,单位成本（元）,化学成分,数学模型：,原料,化学成分含量（,%,）,产品中化学成分的最低含量（,%,）,甲,乙,A,12,3,4,B,2,3,2,C,3,15,5,单位成本（元）,化学成分,这是一个原料配制问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。,满足一组约束条件的同时，寻求变量,x,1,和,x,2,的值使目标函数取得最小值。,例,:,某铁器加工厂要制作,100,套钢架，每套要用长为,2.9,米，,2.1,米和,1.5,米的圆钢各一根。已知原料长为,7.4,米，问应如何下料，可使材料最省？,分析,：在长度确定的原料上截取三种不同规格的圆钢，可以归纳出,8,种不同的下料方案：,圆钢（米）,2,9,1,2,0,1,0,1,0,0,2,1,0,0,2,2,1,1,3,0,1,5,3,1,2,0,3,1,0,4,料头（米）,0,0.1,0.2,0.3,0.8,0.9,1.,1.4,问题归纳为,如何混合使用这,8,种不同的下料方案，来制造,100,套钢架，且要使剩余的余料总长为最短。,设 表示用第,j,种下料方案下料的原料根数，,j,=1,2,8,目标：,使余料总长度最小化,min,z,=0,x,1,+0.1,x,2,+0.2,x,3,+0.3,x,4,+0.8,x,5,+0.9,x,6,+1.1,x,7,+1.4,x,8,约束：,三种规格圆钢根数,x,1,+2,x,2,+,x,4,+,x,6,=100,2,x,3,+2,x,4,+,x,5,+,x,6,+3,x,7,=100,3,x,1,+,x,2,+2,x,3,+3,x,5,+,x,6,+4,x,8,=100,非负取整条件,x,j,0(,j,=1,28),且取整数,圆钢（米）,2,9,1,2,0,1,0,1,0,0,2,1,0,0,2,2,1,1,3,0,1,5,3,1,2,0,3,1,0,4,余料（米）,0,0.1,0.2,0.3,0.8,0.9,1.,1.4,数学模型,s.t.,这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，,使所消耗的资源数最少的数学规划问题。,满足一组约束条件的同时，寻求变量,x,1,至,x,8,的值,使目标函数取得最,小值。,圆钢（米）,2,9,1,2,0,1,0,1,0,0,2,1,0,0,2,2,1,1,3,0,1,5,3,1,2,0,3,1,0,4,料头（米）,0,0.1,0.2,0.3,0.8,0.9,1.1,1.4,且为整数,与规划问题有关的数学模型总有两部分组成：,约束条件：,反映了有限资源对生产经营活动的种种约束，或者生产经营必须完成的任务；,目标函数,：反映生产经营者在有限资源条件下希望达到的生产或经营的目标。,2.,线性规划的一般数学模型,线性规划模型的特征：,（,1,）用一组,决策变量,x,1,，,x,2,，,x,n,表示某一方案，且在一般情况下，,变量的取值是非负的。,（,2,）有一个,目标函数,，这个目标函数可表示为这组变量的,线性,函数。,（,3,）存在若干个,约束条件,，约束条件用决策变量的线性等式或线,性不等式来表达。,（,4,）要求目标函数,实现最大化,（,max,）,或,最小化,（,min,）。,满足上述,4,个特征的规划问题称为,线性规划问题。,通常称 为,决策变量,，为,价值系数,，,为,消耗系数,为,资源限制系数,。,线性规划的模型的一般形式,:,目标函数,满足约束条件,min(max),1.2,线性规划的图解法,适用于,求解两个变量,的线性规划问题,1.,图解法的基本步骤,例,4,:,利用例,1,说明图解法的主要步骤，,例,1,的数学模型为,O,5,10,15,x,1,x,1,=4,x,2,10,1,A,B(2,5),C,z,5,x,1,+,x,2,=15,30,x,1,+20,x,2,=160,5,x,1,+2,x,2,=5,线性规划图解法的基本步骤,（,1,）建立以,x,1,x,2,为坐标轴的直角坐标系，画出线性规划问题,的,可行域,（,2,）求目标函数,z,=,C,1,x,1,+,C,2,x,2,的,梯度,z,=,（,c,1,c,2,）,（,3,）,任取,等值线,C,1,x,1,+,C,2,x,2,=,z,0,沿梯度,z,正方向平移,（若是极小化问题，则沿,负梯度方向,z,平移），,求等直线将离未离可行域时与可行域的交点。,（,4,）若交点存在，则该点坐标就是最优解,X,*,。,例如,：,max,z,=,x,1,+3,x,2,s.t.,x,1,+,x,2,6,-,x,1,+2,x,2,8,x,1,0,x,2,0,可行域,目标函数等值线,最优解,6,4,-8,6,0,x,1,x,2,28,2.,图解法的几种可能结果,(1,）有,唯一最优解,，如例,1,则目标函数等值线,10,x,1,+2,x,2,=,z,与第二约束,5,x,1,+,x,2,15,的边界线平行。将等值线沿梯度,z,=,（,10,，,2,）正方向平移至,B,点时与可行域,OABC,的整条边界线,AB,重合。,这表明线段,AB,上的每一点都使目标函数取得同样的最大值，因而都是最优解。,（,2,）有,无穷多最优解,如例,1,中的目标函数设为,:,max,z,=10,x,1,+2,x,2,例,5,:,试用图解法求解下列线性规划问题,（,3,）,无界解,（或称无最优解）,无界解是指线性规划问题的最优解无界。,若是极大化问题，则可使目标函数值,z+,极小化问题 则可使目标函数值,z-,，,有无界解的线性规划问题的可行域通常是,无界区域，但反之则不必然。,-1 O,2,4,x,1,x,2,2,4,z,=(3,2),-2,x,1,+,x,2,=2,x,1,-3,x,2,=3,-1 O,3,3,（,4,）,无可行解,某些线性规划问题的可行域是空集，既不存在满足所有约束条件的点，这时问题无可行解，当然更谈不上最优解了。,在实际中出现这种情况可以认为资源条件无法满足人们的要求，既不存在可行方案。,1.,标准线性规划模型,(1),线性规划问题的,标准形式,：,其中,(1.1),为,目标函数,，,(1.2),为,约束条件,，,(1.3),为,非负条件,，为称呼方便，有时将,(1.3),也称为约束条件。,（,1.2,）,（,1.3,）,1.3,线性规划的标准形式,（,1.1,）,其中,C,=(,c,1,c,2,c,n,),称为,价值向量,，,X,=(,x,1,x,2,x,n,),T,为决策变量向量，,P,j,=(,a,1,j,x,2j,x,mj,),T,为,决策变量,x,j,所对应的消耗系数向量,，,b,=(,b,1,b,2,b,m,),T,为,资源向量,。,(2),紧凑格式：,(3),向量格式：,其中 为,m,n,阶矩阵,(4),矩阵格式：,C,=(,c,1,c,2,c,n,),，,X,=(,x,1,x,2,x,n,),T,，,b,=(,b,1,b,2,b,m,),T,。,35,2.,非标准形式线性规划问题的标准化,（,1,）极大化与极小化：,原目标函数,(2),线性不等式与线性等式：,其中,x,n,+,i,为非负,松弛变量,，,其中,x,n,+,k,为非负,剩余变量,。,(3),非负变量与符号不受限制的变量,若,x,i,的符号不受限制，则可,引进非负变量,x,i,1,x,i,2,，令,x,i,=,x,i,1,-,x,i,2,，使线性规划里所有的变量都转化为有非负限制的变量。,(4),右端项有负值的问题：,在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如,b,i,0,，,则把该等式约束两端同时乘以,1,，得到：,a,i1,x,1,a,i2,x,2,a,in,x,n,=,b,i,。,37,例,6,:,将下述线性规划问题化为标准型,符号不受限制,解,:,令,可将目标函数化为,min,型，,令,其中,38,考虑一个标准的线性规划问题：,1.4,标准型线性规划的解,其中,为,n,维行向量，,是,n,维列向量，,是,m,维列向量，,是,m,n,阶矩阵，假定满足,m,n,，且,(,)=,m.,39,(2),最优解,:,使目标函数（,1.4),达到最优值的的可行解称为最优解，,最优解常用,X,*,表示。,(3),基,:,若,是,中,m,m,阶非奇异矩阵，即,|,|0,，,则称是线性规,划问题的一个基。,可行解集 称为线性规划问题的,可行域,。,线性规划问题解的概念：,(1),可行解,:,满足约束条件,(1.5),，,(1.6),的解,称为线性规划问题的可行解。,40,一个线性规划的基通常不是唯一的，,但是基的个数也不会超过,C,n,m,个。,一旦确定了线性规划的基，则相应的基向量、基变量和非基变量也就确定。,若是线性规划问题的一个基，那么,一定是由,m,个线性无关的列向量组成,，不失一般性，可设,称 为,基向量,，,与基向量,P,j,相对应的变量,x,j,(,j,=1,2,，,，,m,),称为,基变量,。,41,(,4),基本解,。设,B,是线性规划的一个基，若,令,n-m,个非基变量等于,0,，则,所得的方程组,=b,的解称为线性规划问题的一个基本解（简称,基解,）。,有一个基就可以求得一个基本解。,由基的有限性可知，基本解的个数也不会超过,C,n,m,个。,由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。,(5),基本可行解,。,满足非负条件,的基本解称为基本可行解,(,简称,基可行解,),。与基本可行解对应的基成为,可行基,。,基本可行解的非零向量的个数小于等于,m,，,并且都是非负的。,由于基本可行解的数目一般少于基本解的数目，因此可行基的数目也要少于基的数目。,当基本可行解中有一个或多个基变量是取零值时，称此解为,退化的基本可行解,。,42,线性规划问题各种解的关系可用文氏图表示，,可行解,基本解,基本,可行,解,43,例,7,：求下列约束方程所对应的线性规划的所有基本解，基本可行解。,解：,化为标准形式后,为,2,4,阶矩阵。,且,R(A)=2,所以该线性规划基的个数,=6,个,若令非基变量 ，约束方程组为,可得对应的基本解 是一个基本可行解。,x,1,x,2,为基变量，,44,对应基本基本解,对应基本基本解,对应基本基本解,按相同步骤，可求得线性规划其他,4,个基,：,对应基本基本解,45,若利用图解法画出线性规划的可行域，如图，,C,O,B,A,4,4,8,46,1.5,线性规划的基本原理,由图解法的步骤，可以从几何的角度得出以下两个结论：,（,1,）线性规划问题的可行域是一个有界或无界的,凸多边,形,，其,顶点个数是有限,个。,（,2,）若线性规划问题有最优解，那么,最优解一定可在可,行域的某个顶点,上找到。,47,（,1,）凸集,：设,K,是,n,维欧式空间的一个点集，若任意两点,X,(1),K,X,(2),K,的连线上的一切点,X,(1),+(1-),X,(2),K,(01),则称,K,为凸集。,1.,几个基本概念,线性约束条件,凸集例,顶点个数,有限,有限,无限,有限,无限,非凸集例,48,连接几何形体中任意两点的线段仍完全在该几何形体之中。,有限个凸集的交集仍然是凸集。,凸集定义的几何解释,49,（,2,）凸组合,：设,X,(1),，,X,(2),，,，,X,(k),是,n,维欧式空间,E,n,中的,k,个点，若存在,1,2,k,满足,0,i,1,(,i,=1,2,k,),且,1,+,2,+,k,=1,，,使,X=,1,X,(1),+,2,X,(2),+,k,X,(,k,),，,则称,X,为,X,(1),，,X,(2),，,，,X,(k),的,凸组合,。,凸组合的几何意义,凸集,K,中任意两点,X,(1),，,X,(2),连线上的任一点,X,都是,X,(1),与,X,(2),的一个凸组合。,50,X,(1),X,(3),X,(2),X,X=,X,+(1-,)X,(2),，,(0,1),x,1,x,2,O,X=,X,(1),+(1-,)X,(3),，,(0,1),51,X,(1),X,(3),X,(2),X,X=u,1,X,(1),+u,2,X,(2),+u,3,X,(3),x,1,x,2,O,X=,X,(1),+(1-,)X,(3),，,(0,1),52,(3),顶点,：设,K,为凸集，,XK,若,X,不能用,X,(1),K,X,(2),K,两点,(,X,(1),X,(2),),的一个凸组合表示为,X=X,(1),+(1-)X,(2),其中,01,，则称,X,为,K,的一,个,顶点,。,或若凸集,K,中的点,X,不能成为,K,中任何线段的内点，则称,X,为,K,的一个顶点。,53,定理,1,：,若线性规划问题存在可行域，则其可行域,D,=,X,/,AX=b,x,0,是一个凸集。,证明：,为了证明满足,=,，,0,的所有点（可行解）组成的几何体是凸集，只要证明中任意两点任意两点,X,(1),，,X,(2),连线上的一切点均满足,线性约束条件,既可。,2.,线性规划的基本定理,任取，满足,则对任意的有,又因为均,0,，所以,由此可知，即是凸集。,54,证明：必要性：,因为是基本解，由基本解的定义，的非零分量所对应的系数列向量线性无关，又因为是可行解，由基本可行解的定义，非零分量均是正的，所以的正分量所对应的系数列向量线性无关。,充分性：,设是线性规划问题的可行解，且正分量所对应的列向量也线性无关，则必有,km,若,k=m,，则,刚好构成一个基，为相应的基本可行解。若,km,，则由线性代数知识，一定可以从其余的,n-k,个系数列向量中取出,m-k,个与构成最大线性无关向量组，其对应的基本可行解恰好为，不过此时的是一个退化的基本可行解。,引理,1,：,线性规划问题的可行解,是基本可行解的,充要条件,是的正分量所对应的系数列向量线性无关。,55,定理,2,：,设线性规划问题的可行域,，则是的一个顶点的,充分必要条件,是为线性规划问题的基本可行解。,证明思路：必要性：,由引理,1,，若,X,是,D,的一个顶点，要证明,X,是线性规划的一个基本可行解，只要证明的正分量所对应的系数列向量线性无关。,用反证法,，倘若的正分量所对应的系数列向量线性相关，则可以在中找到两点，使，与是的顶点矛盾,.,充分性：,若是线性规划的一个基本可行解，要证明是可行域的一个顶点，,仍用反证法,，倘若不是可行域的顶点,，可以证明的基变量所对应的系数列向量线性相关，与,X,是基本可行解矛盾。,56,例,8:,已知线性规划问题的约束条件为,试讨论可行域顶点和基本可行解之间的对应关系。,解,:,可行域,为四维凸多面体，可以推得在四维空间中有,3,个顶点，,=(0,0,10,10),，,=(0,10,0,10),，,=(10,0,0,0),。,这,3,个顶点与线性规划的,5,个基本可行解的对应关系如下：,顶点对应以,x,3,x,4,为基变量的基本可行解；,顶点对应以,x,2,x,4,为基变量的基本可行解；,顶点对应,x,1,x,2,;,x,1,x,3,和,x,1,x,4,为基变量的退化基本可行解,.,57,一个线性规划问题，如果它的所有基本可行解都是非退化的，那么称这个,线性规划是非退化,的，只有在这种情况下，顶点和基本可行解 之间才是一一对应的。,定理,3,(,线性规划的基本定理,):,若可行域,D,非空有界，那么线性规划问题的目标函数一定可以 在可行域,D,的顶点上达到最优值。,证明思路,：,因为可行域非空有界，所以线性规划一定有最优解，倘若,X,(0),不是顶点，且目标函数在该点处取到最优值,z,*,，则必能找到可行域的一个顶点,X,(,m,),，使目标函数,在,X,(,m,),的,值也等于,z,*,。,58,说明,:,定理,3,并不排除在一个非顶点上有一个最优解的可能性。但是在一个 给定的线性规划问题的所有最优解中，至少有一个是顶点。,如果可行域无界，则线性规划问题可能无最优解。,如果目标函数同时在两个顶点上达到最优解，那么不难证明在这两个 点的凸组合上也达到最优解，这时线性规划问题有无穷多最优解。,59,定理,1,：,若线性规划问题存在可行域，则其可行域,是一个凸集。,定理,2,：,设线性规划问题的可行域,，则是的一个,顶点的,充分必要条件,是为线性规划问题的基本可行解。,定理,3,：,若可行域,D,非空有界，那么线性规划问题的目标函数一定可以 在可行域,D,的顶点上达到最优值。,60,Linear Programming in MATLAB,61,