线性规划数学模型省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级二级二级二级二级二级二级二级二级二级二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级二级二级二级二级二级二级二级二级二级二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,第二章 线 性 规 划,（,L,inear,P,rogramming,）,线性规划问题是目标函数和约束条件均为线性最优化问题。自从,1947,年丹捷格,(Dantzig),提出求解线性规划单纯形方法以来，线性规划在理论上趋向成熟。尤其是在计算机能处理成千上万个约束条件和决议变量线性规划问题之后，线性规划适用领域更为广泛，已成为当代管理中经常采取基本方法之一。线性规划是最优化问题中主要领域之一，很多运筹学中实际问题都能够用线性规划来表述。很多其它种类最优化问题算法也都能够分拆成线性规划子问题，然后求解。,经过学习本章，应该了解线性规划相关概念，掌握线性规划模型建立及优化方法，会用计算机对大型线性规划模型问题进行求解和分析。本章难点为单纯形计算方法。,第1页,1,第一节 线性规划问题提出,线性规划是运筹学一个主要分支，主要用于研究处理有限资源最正确分配问题，即怎样对有限资源做出最正确方式调配和最有利使用，方便最充分地发挥资源效能，以获取最正确经济效益。,它适用领域非常广泛，从工业、农业、商业、交通运输业、军事计划和管理及决议到整个国民经济计划最优方案提出，都有它用武之地，是当代管理科学主要基础和伎俩之一。,第2页,2,第一节 线性规划问题提出,线性规划研究问题主要有以下两类。,(1),给出一定量人力、物力、财力等资源，怎样统筹规划这些有限资源完成最大任务。,（如资金、设备、原标材料、人工、时间等）,(2),给定一项任务，怎样运筹规划，合理安排，以最少资源来完成它。,（如产品量最多、利润最大,.,）,线性规划要研究两类问题中都有一个限制条件：第一类问题是给出一定量人力、物力和财力等资源；第二类问题是给定一项任务。,第3页,3,第二节 线性规划问题数学模型,当用线性规划方法对实际问题进行优化时，必须把这个实际问题用恰当数学形式表示出来，这个表示过程，就是建立数学模型过程。数学模型建立需要经验和技巧以及相关专业知识，只有经过大量实践，在建立模型时才能得心应手。初课时可从题目中所给出限制条件和目标入手，由限制条件建立起线性方程组，由目标得到目标函数。,下面，结合若干个实际问题讨论数学模型建立。,第4页,4,一、投资问题数学模型,解（参见教材,P15,）,第5页,5,二、配料问题数学模型,解（参见教材,P16,）,第6页,6,二、配料问题数学模型,某化工厂要用三种原料,A,，,B,，,C,混合配制三种不一样规格,产品,X,，,Y,，,Z,。,相关数据以下,：,产品,规 格,单价,(,元,/kg),X,原料D不少于50%,原料P不超出25%,50,Y,原料D不少于25%,原料P不超出50%,35,Z,不 限,25,原料,最大供量,(kg/,天,),单价,(,元,/kg),A,100,65,B,100,25,C,60,35,应如合配制,，,才能使利润到达最大,？,表,2-3,表,2-4,第7页,二、配料问题数学模型,一、,决议变量,设以,x,ij,表示天天生产,第,i,种产品中所含第,j,种原料,数量,(kg,，,右表,),。,j,i,A,B,C,X,Y,Zx,11,x,12,x,13,x,21,x,22,x,23,x,31,x,32,x,33,二、约束条件,规格约束,(,据,表,2-3,),x,11,+,x,12,+,x,13,x,11,0.50,x,11,+,x,12,+,x,13,x,12,0.25,x,11,+,x,12,+,x,13,x,21,0.25,x,11,+,x,12,+,x,13,x,22,0.50,第8页,二、配料问题数学模型,改写成,-,x,11,+,x,12,+,x,13,0,-,x,11,+,3,x,12,-,x,13,0,-,3,x,21,+,x,22,+,x,23,0,x,21,+,x,22,-,x,23,0,资源约束,(,据,表,2-4,),x,11,+,x,21,+,x,31,100,x,12,+,x,22,+,x,32,100,x,13,+,x,23,+,x,33,60,第9页,二、配料问题数学模型,三、目标函数,总产值,(,据,表,2-3,),产品,X,产值,:,50,(,x,11,+,x,12,+,x,13,),产品,Y,产值,:,35,(,x,21,+,x,22,+,x,23,),产品,Z,产值,:,25,(,x,31,+,x,32,+,x,33,),以上三项之和即,总产值,。,总成本,(,据,表,2-4,),原料,A,成本,:,65,(,x,11,+,x,21,+,x,31,),原料,B成本,:,25,(,x,12,+,x,22,+,x,32,),原料,C,成本,:,35,(,x,13,+,x,23,+,x,33,),以上三项之和即,总成本,。,第10页,二、配料问题数学模型,目标函数,为：,总利润,=,总产值,-,总成本,max,z,=,-,15,x,11,+,25,x,12,+,15,x,13,-,30,x,21,+,10,x,22,-,40,x,31,-,10,x,33,该问题数学模型为,:,s.t.,-,x,11,+,x,12,+,x,13,0,-,x,11,+,3,x,12,-,x,13,0,-,3,x,21,+,x,22,+,x,23,0,x,21,+,x,22x,23,0,x,11,+,x,21,+,x,31,100,x,12,+,x,22,+,x,32,100,x,13,+,x,23,+,x,33,60,x,ij,0,，,i=1,2,3,；,j=1,2,3,第11页,配料问题,练习：,某化工厂依据一项协议要为用户生产一个用甲、乙两种原料混合配制而成特殊产品。甲、乙两种原料都含有,A,，,B,，,C,三种化学成份,，,其含量,(,%,),是,:,甲为,12,，,2,，,3,；,乙为,3,，,3,，,15,。,按协议要求,，,产品中三种化学成份含量,(,%,),不得低于,4,，,2,，,5,。,甲、乙原料成本为每千克,3,，,2,元。,厂方希望总成本到达最小,，,则应怎样配制该产品,？,第12页,配料问题,成份含量,(%),原,料,化学成份,甲,乙,产品成份,最低含量,(%),A,B,C,12,3,2,3,3,15,4,2,5,成本（元,/,千克）,3,2,x,1,x,2,min,z,=,3,x,1,+,2,x,2,12,x,1,+,3,x,2,4,2,x,1,+,3,x,2,2,s.t.,3,x,1,+,15,x,2,5,x,1,+,x,2,=,1,x,1,x,2,0,配料平衡条件,z,第13页,三、人力资源问题数学模型,解（参见教材,P17,）,第14页,14,三、人力资源问题数学模型,练习：,某昼夜服务公交线路天天各时间段内所需司机和乘务人员人数以下表所表示：,班次,时间,所需人员,1,6:00,10:00,60,2,10:00,14:00,70,3,14:00,18:00,60,4,18:00,22:00,50,5,22:00,2:00,20,6,2:00,6:00,30,设司机和乘务人员分别在各时间段开始时上班，并连续工作,8,小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配置司机和乘务人员人数降低,?,第15页,三、人力资源问题数学模型,解：设,x,i,表示第,i,班次时开始上班司机和乘务人员人数。,此问题最优解：,x,1,50,，,x,2,20,，,x,3,50,，,x,4,0,，,x,5,20,，,x,6,10,，一共需要司机和乘务员,150,人。,第16页,四、合理下料问题数学模型,合理下料问题是机械工业常碰到问题。毛坯车间经常要在长度一定条形材料或面积一定板材上切割若干个含有一定形状、尺寸毛坯。在普通情况下，材料不可能被完全利用，会有边角余料，造成浪费。所以，怎样最大程度地降低边角余料，提升材料利用率，使得切割要求数量毛坯所用材料最少就是合理下料问题所要研究。,例,2-5,某车间有一批长度为,180cm,钢管,(,数量充分多,),，为了制造零件需要，要将其截成三种不一样长度管料：,70cm,、,52cm,、,35cm,。要求这三种管料需要量分别不少于,100,根、,150,根和,100,根。问：应怎样下料能使消耗钢管数量最少？,解（参见教材,P18,）,第17页,17,四、合理下料问题数学模型,练习：,制造某种机床,，,需要,A,B,C,三种轴件,，,其规格与数量如表所表示,，,各类轴件都用,5.5,米长同一个圆钢下料,。,若计划生产,100,台机床,，,最少需要用多少根圆钢,？,第18页,四、合理下料问题数学模型,轴类,规格：长度（米）,每台机床所需轴件数,A,3.1,1,B,2.1,2,C,1.2,4,余料,j,1.2,找出全部,省料截法,一根圆钢所截各类轴件数,截法,轴类,轴,件,需要量,A(,3.1,),100,B(2.1,),200,C(1.2,)400,余料,(,米,),2,3,4,5,1,1,1,0,0.3,1,0,2,0,0,2,1,0.1,0,0,1,0,2,4,1,0.7,第19页,四、合理下料问题数学模型,min,z,=,x,1,+,x,2,+,x,3,+,x,4,+,x,5,s.t.,x,1,+,x,2,100,x,1,+,2,x,3,+,x,4,200,2,x,2,+,x,3,+,2,x,4,+,4,x,5,400,x,1,，,x,2,，,x,3,，,x,4,，,x,5,0,则该问题数学模型为,:,设第,j,种截法下料,x,j,根。,第20页,四、合理下料问题数学模型,例：现有一批某种型号圆钢长,8,米，需要截取,2.5,米长毛坯,100,根，长,1.3,米毛坯,200,根。问怎样才能既满足需要，又能使总用料最少？,解：为了找到一个省料套裁方案，必须先设计出很好几个下料方案。其次要求这些方案总体能裁下全部各种规格圆钢，以满足对各种不一样规格圆钢需要并到达省料目标，为此能够设计出,4,种下料方案以供套裁用。,2.5m,3,2,1,0,1.3m,0,2,4,6,料头,0,0.4,0.3,0.2,第21页,四、合理下料问题数学模型,设按方案,、,、,、,下料原材料根数分别为,x,j,(j=1,，,2,3,4),，可列出下面数学模型：,第22页,五、运输问题数学模型,问题提出：某类产品有若干个产地，已知每个生产地产量；这类产品有若干个消费地，已知每个消费地需要量。假设总产量等于总需要量。问题是怎样编制一个最优运输计划，使从产地到消费地运输费用最小。,解（参见教材,P20,）,第23页,23,六、产品配比问题数学模型,例,某厂拟生产甲、乙两种产品，每件利润分别为,3,、,5,百元。,甲、乙产品部件各自在,A,、,B,两个车间分别生产，每件甲、,乙产品部件分别需要,A,、,B,车间生产能力,1,、,2,工时。两件,产品部件最终都要在,C,车间装配，装配每件甲、乙产品分别,需要,3,、,4,工时，三车间天天可用于生产这两种产品工时分别,为,8,、,12,、,36,，问应怎样安排生产这两种产品才能赢利最多？,第24页,产品配比问题,z,x,1,x,2,决议变量,z,=,3,x,1,+,5,x,2,max,0,目标函数,x,1,8 ,2,x,2,12,3,x,1,+,4,x,2,36 ,函数约束,x,1,，,x,2,0 ,非负性约束,s.t.,甲 乙,1,0,3,0,2,4,8,12,36,A,B,C,车间,产品,单耗（工时,/,件）,最大生产能力,（工时,/,天）,单位利润,（百元,/,件）,3,5,第25页,线性规划问题数学模型,练习：,某企业计划生产甲、乙两种产品。这些产品分别要在,A,、,B,、,C,、,D,、四种不一样设备上加工。按工艺资料要求，单件产品在不一样设备上加工所需要台时以下表所表示，企业决议者应怎样安排生产计划，使企业总利润最大？,设 备,产 品,A,B,C,D,利润（元）,甲,2,1,4,0,2,乙,2,2,0,4,3,有 效 台 时,12,8,16,12,第26页,线性规划问题数学模型,解：设,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,第27页,七、生产计划问题数学模型,某企业拟用,m,种资源生产,n,种产品,，,已知第,i,种,资源数量为,b,i,其单价为,p,i,每生产一个单位第,j,种,产品所提供产值为,v,j,所消耗第,i,种资源数量,为,a,ij,。,第,j,种产品协议与指令性计划产量指标为,e,j,最高需求量为,d,j,。,该企业应怎样确定生产计划,？,第28页,一、,决议变量,设,x,j,为第,j,种产品计划产量,二、,约束条件,指标约束,x,j,e,j,j,=,1,2,n,需求约束,x,j,d,j,j,=,1,2,n,资源约束,三、,目标函数,总产值,七、生产计划问题数学模型,j=1,n,a,ij,x,j,b,i,i=1,2,m,j=1,n,m,i=1,z,2,=,p,i,(a,ij,x,j,),总成本,z,1,=,v,j,x,j,n,j=1,第29页,七、生产计划问题数学模型,i=1,=,v,j,x,j,-,p,i,(a,ij,x,j,),j=1,n,m,j=1,n,=,(v,j,-,p,i,a,ij,),x,j,j=1,n,i=1,m,令,c,j,=,v,j,-,p,i,a,ij,i=1,m,x,j,e,j,j,=,1,2,n,x,j,d,j,a,ij,x,j,b,i,i,=,1,2,m,j=1,n,max z,=,c,j,x,j,j=1,n,s.t.,则,总利润,z,=,z,1,-,z,2,第30页,七、生产计划问题数学模型,某厂生产,、,、,三种产品，都分别经,A,、,B,两道工序加工。设,A,工序可分别在设备,A1,和,A2,上完成，有,B1,、B2,、,B3,三种设备可用于完成,B,工序。已知产品,可在,A,、,B,任何一个设备上加工；产品,可在任何规格,A,设备上加工，但完成,B,工序时，只能在,B1,设备上加工；产品,只能在,A2,与,B2,设备上加工。加工单位产品所需工序时间及其它各项数据以下表，试安排最优生产计划，使该厂赢利最大。,第31页,七、生产计划问题数学模型,设备,产品,设备有效台时,设备加工费,（单位小时）,A1,5,10,6000,300,A2,7,9,10 000,321,B1,6,8,12,4000,250,B2,4,7000,783,B3,7,11,4000,200,原料费（每件）,0.25,0.35,05,售价（每件）,1.25,2.00,2.8,第32页,七、生产计划问题数学模型,解：设,x,ijk,表示产品,i,在工序,j,设备,k,上加工数量。约束条件有：,第33页,七、生产计划问题数学模型,目标是利润最大化，即利润计算公式以下：,带入数据整理得到：,第34页,七、生产计划问题数学模型,所以该规划问题模型为：,第35页,有,n,种食品,每种食品中含有,m,种营养成份,。,食品用,j,=,1,2,n,表示,，,养分用,i,=,1,2,m,表示,。,已知第,j,种,食品单价为,c,j,天天最大供量为,d,j,;,而每单位第,j,种食品所含,第,i,种养分数量为,a,ij,。,假定某种生物天天对第,i,种养分,需求量最少为,b,i,而天天进食数量限定在,h,1,h,2,范围内,。,试求该生物食谱,，,使总成本为最小,。,八、食谱问题数学模型,第36页,八、食谱问题数学模型,设,x,j,为天天提供给该生物食用第,j,种食品数量，,则该问题数学模型为,:,s.t.,0,x,j,d,j,j,=,1,2,n,min z,=,c,j,x,j,j=1,n,j=1,h,1,x,j,h,2,n,j=1,a,ij,x,j,b,i,i,=,1,2,m,n,第37页,八、食谱问题数学模型,配料问题,例：某人天天食用甲、乙两种食物（如猪肉、鸡蛋），其资料以下：问两种食物各食用多少，才能既满足需要、又使总费用最省？,2 1.5,原料单价,1.00,7.50,10.00,0.1 0.15,1.7 0.75,1.10 1.30,A,1,A,2,A,3,最 低,需要量,甲 乙,含量 食物,成份,第38页,八、食谱问题数学模型,解：设,X,j,表示,B,j,种食物用量,第39页,九、产品配套问题数学模型,某厂制造某种部件，由,2,个,B,1,零件,3,个,B,2,零件配套组装而成,。,该厂有,A,1,A,2,A,3,三种机床可加工这两种零件,，,每种机床台数,，,以及每台机床生产率以下表所表示,。,求产量最大生产方案,。,第40页,九、产品配套问题数学模型,一、决议变量,设以,x,ij,表示每台,Ai,(,i,=,1,2,3,),机床每个工作日加工,B,j,(,j,=,1,2,),零件时间,(,单位,:,工作日,),；,z,为,B,1,B,2,零件按,2:3,百分比配套数量,(,套,/,日,),。,机床,种类,机床,台数,每台,机床生产率,(,件,/,日,),零件,B,1,零件,B,2,A,1,3,20,30,A,2,2,35,45,A,3,4,10,18,x,11,x,12,x,21,x,22,x,31,x,32,第41页,九、产品配套问题数学模型,二、约束条件,工时约束,配套约束,机床,种类,总,生产率,(,件,/,日,),零件,B,1,零件,B,2,A,1,60,90,A,2,70,90,A,3,40,72,x,11,x,12,x,21,x,22,x,31,x,32,z,=min (60,x,11,+70,x,21,+40,x,31,),(90,x,12,+90,x,22,+72,x,32,),1,2,1,3,z,(60,x,11,+70,x,21,+40,x,31,),1,2,z,(90,x,12,+90,x,22,+72,x,32,),1,3,非线性，等价改写成：,或,x,11,+,x,12,=,1,x,21,+,x,22,=,1,x,31,+,x,32,=,1,z,-,35,x,11,-,35,x,21,-,20,x,31,0,z,-,30,x,12,-,30,x,22,-,24,x,32,0,第42页,九、产品配套问题数学模型,则该问题数学模型为,:,max,z,s.t.,x,11,+,x,12,=1,x,21,+,x,22,=1,x,31,+,x,32,=1,z,35,x,11,35,x,21,20,x,31,0,z,30,x,12,30,x,22,24,x,32,0,z,x,11,x,12,x,21,x,22,x,31,x,32,0,第43页,线性规划问题数学模型,线性规划数学模型由三个要素组成,决议变量,Decision variables,目标函数,Objective function,约束条件,Constraints,其特征是：,（,1,）问题目标函数是多个决议变量,线性,函数，通常是求最大值或最小值；,（,2,）问题约束条件是一组多个决议变量,线性,不等式或等式。,怎样区分一个模型是线性规划模型？,第44页,线性规划问题数学模型,目标函数：,约束条件：,线性规划数学模型普通形式,简写为：,普通,LP,模型,三类参数,：,价值系数,c,j,，,消耗系数,a,ij,，,右端常数,b,i,.,LP,模型,三要素,：,决议变量,，,目标函数,，,约束条件,.,第45页,线性规划问题数学模型,向量形式：,其中：,第46页,线性规划问题数学模型,矩阵形式：,其中：,第47页,谢谢观看！,第48页,48,