最优化问题数学模型省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,最优化模型,一、最优化模型概述,二、最优化模型分类,三、最优化模型建立及求解,四、最优化模型评价分析,第1页,数学家对最优化问题研究已经有很多年历史。,以前处理最优化问题数学方法只限于古典求导方法和变分法，拉格朗日（,Lagrange,）乘数法处理等式约束下条件极值问题。,计算机技术出现，使得数学家研究出了许多最优化方法和算法用以处理以前难以处理问题。,一、最优化模型概述,处理最优生产计划、最优设计、最优策略,.,第2页,利用最优化方法处理最优化问题普通方法步骤以下：,前期分析：分析问题，找出要处理目标，约束条件，并确立最优化目标。,定义变量，建立最优化问题数学模型，列出目标函数和约束条件。,针对建立模型，选择适当求解方法或数学软件。,编写程序，利用计算机求解。,对结果进行分析，讨论诸如：结果合理性、正确性，算法收敛性，模型适用性和通用性，算法效率与误差等。,第3页,最优化模型分类方法有很多，可按变量、约束条件、目标函数个数、目标函数和约束条件是否线性是否依赖时间等分类。,依据目标函数，约束条件特点将最优化模型包含主要内容大致以下划分：,线性规划 整数规划,非线性规划 多目标规划,动态,规划,对策论,二、最优化模型分类,第4页,最优化模型求解方法分类,第5页,最优化数学模型形式,其中，极大值问题能够转化为极小值问题来进行求解。如求：,能够转化为：,三、最优化模型建立,目标：求函数极值或最值，求取得极值时变量取值。,第6页,1.,线性规划,问题,：某工厂在计划期内要安排生产,I,、,II,两种产品，已知生产单位产品所需设备台时及,A,、,B,两种原材料消耗，以下表所表示,12kg,4,0,原材料,B,16kg,0,4,原材料,A,8,台时,2,1,设备,II,I,该工厂每生产一件产品,I,可赢利,2,元，每生产一件产品,II,可赢利,3,元。问应怎样安排计划使该工厂赢利最多？,第7页,解,：该工厂生产产品,I x1,件，生产产品,II x2,件，我们可建立以下数学模型：,s.t.,第8页,最优化问题中全部变量均为整数时，这类问题称为整数规划问题。,整数规划可分为线性整数规划和非线性整数规划，以及混合整数规划等。,假如决议变量取值要么为,0,，要么为,1,，则这么规划问题称为,0,1,规划。,2.,整数规划,第9页,问题：,某班级准备从,5,名,游泳队员中选择,4,人,组成接力队，参加学校,4*100m,混合泳接力比赛。,5,名队员,4,种泳姿,百米平均成绩如表,2-1,，问应怎样选拔队员组成接力队？,队员,甲,已,丙,丁,戊,蝶泳,仰泳,蛙泳,自由泳,66.8,秒,57.2,78,70,67.4,75.6,66,87,58.6,66.4,53,67.874.2,71,84.6,59.4,69.6,57.2,83.8,62.4,表,2-1,第10页,问题分析：,记甲、乙、丙、丁、戊分别为,i,=1,2,3,4,5;,记泳姿,j,=1,2,3,4.,记队员,i,第,j,种泳姿百米最好成绩为,c_,ij,(s),则表,2-1,能够表示成表,2-2.,c_ij,i=1,i=2,i=3,i=4,i=5,j=1,j=2,j=3,j=4,66.8,57.2,78,70,67.4,75.6,66,87,58.6,66.4,53,67.8,74.2,71,84.6,59.4,69.6,57.2,83.8,62.4,表,2-2,第11页,决议变量：,引入,01,变量 ，若选择队员,i,参加泳姿,j,比赛,记，不然记 。,目标函数：,当队员,i,入选泳姿,j,时，表示该队员成绩，不然 。于是接力队成绩可表示为,约束条件：,依据接力队要求，满足约束条件,a.,每人最多只能入选,4,种泳姿之一，即,b.,每种泳姿必须有,1,人而且只能有一人入选，即,第12页,总而言之，这个问题优化模型可写作：,第13页,非线性规划问题普通数学模型：,其中，为目标函数，,为约束函数，这些函数中最少有一个是非线性函数。,3.,非线性规划,第14页,应用实例：供给与选址,某企业有,6,个建筑工地要开工，每个工地位置（用平面坐标系,a,，,b,表示，距离单位：,km,）及水泥日用量,d(t),由下表给出当前有两个暂时料场位于,A(5,1),，,B(2,7),，日储量,各有,20t,假设从料场到工地之间都有直线道路相连,（,1,）试制订天天供给计划，即从,A,，,B,两料场,分别向各工地运输多少水泥，可使总,吨千米数最小,（,2,）为了深入降低吨千米数，打算舍弃两个暂时料场，改建两个新，日储量各为,20t,，问应建在何处，节约吨千米数有多大？,第15页,建立模型,记工地位置为,(a,i,，,b,i,),，水泥日用量为,d,i,，,i=1,6;,料场位置为,(x,j,，,y,j,),，日储量为,e,j,，,j=1,2,；料场,j,向工地,i,运输量为,X,ij,当用暂时料场时决议变量为：,X,ij,，,当不用暂时料场时决议变量为：,X,ij,，,x,j,，,y,j,第16页,实际上，客观世界中大多问题都是非线性，给予线性化处理是近似，是在作了科学假设和简化后得到.另首先，有一些是不能进行线性化处理，不然将严重影响模型对实际问题近似可依赖型.,因为非线性规划问题在理论分析和计算上通常是很困难，也不能像线性规划那样给出简练结果形式和全方面透彻结论.所以，在数学建模时，要进行认真分析，对实际问题进行合理假设、简化，首先考虑用线性规划模型，,若线性近似误差较大时,，则考虑用非线性规划.,第17页,在约,1,万米高空某边长为,160km,正方形区域内，经常有若干架飞机作水平飞行，区域内每架飞机位置和速度向量均由计算机统计其数据，方便进行飞行管理。当一架欲进入该区域飞机抵达区域边缘时，计算机统计其数据后，要马上计算并判断是否会发生碰撞。若会发生碰撞，则应计算,怎样调整,各架飞机（包含新进入飞机）飞行方向角，以防止碰撞，且使飞机调整幅度尽可能小，,例,1 1995,年全国数学建模,A,题：飞行管理问题,例题讲解,第18页,该题比较有意思一句话是：,“,使调整弧度最小”,开放性一句话，没有限制得很死，较灵活，,给参赛者创新空间比较大一些，使得构建模型,目标函数表现形式很多，再加上模型求解方法（算法）多样性，从而能够展现出五花八门论文。,第19页,不碰撞标准为任意两架飞机距离大于,8,km,;,假设条件：,飞机飞行方向角调整幅度不应超出 ；,（因飞机飞行速度改变不大）全部飞机飞行,速度,v,均为,800,km/h,;,有时需要经过查阅文件、资料给出合理假设,注：,第20页,进入该区域飞机在抵达区域边缘时，与区域内,飞机距离应在,60,km,以上；,最多需考虑六架飞机；,无须考虑飞机离开此区域后情况。,依据当年竞赛题目给出数据，能够验证新进入飞机与区域内飞机距离超出,60,公里。,依据当年竞赛题目给出数据，能够验证区域内飞机不超出架,(,包含新进入,),。,第21页,个人想法不一样，队友之间争吵不下情况下，若时间允许，都可一一写到论文中去，建立模型一模型二,；,或者经讨论后，选择一个认为更合理。,现在看来，不论是构建模型，还是计算，都不太难。,本例题未给出数据，将重点放在怎样构建模型上,第22页,解：,(1),不考虑飞机尺寸，用点代表飞机；,(2),已在区域内,5,架飞机按给定方向角作,直线飞行，则必不会碰撞，也不会发生,意外；,(,应该依据题目中所给出数据简,单 验证一下,),(3),飞机调整方向角过程可在瞬间完成,(,不,计调整方向所花费时间,),。,为处理该问题，补充假设：,第23页,变量、参数符号假设,（为了建模）,在区域内飞行,飞,时间（能够依据数据算出来）,第24页,四种情况：,四个象限，易用,4,个表示式表示,说明：,用初等数学知识即可完成，,思索：,在哪个时间段某两架飞机可能相撞？,In fact,我们只需考虑两架飞机,同时,在区域内,飞行时情况，也就是说，,才是同在区域内情况。,记为,第25页,依据题目条件，需计算第 架飞机之间,最短距离,第26页,为此，我们能够给出原问题模型以下：,思索：,是否还有其它表示形式？,非线性规划模型,分别从目标函数和约束条件角度思索,第27页,首先思索一下目标函数是否有其它表示？,同学们首先想到可能是,Oh,Sorry!,有正有负,抵消,第28页,最小一乘 法,最小二乘 法,因最小一乘法带绝对值，不好计算，以上两式，,比较而言，后者很好。,为了防止抵消,or,第29页,有队员这么考虑：,令为,转化为二次规划,用到经验模型中确定参数近似准则,:,就全部飞机而言，,让调整弧度最大,即,尽可能小，,Chebshavf,准则,第30页,其次讨论一下约束条件是否有其它表示？,若考虑区域内不发生碰撞（若时间允许，也能够考虑出了区域情况，另外建模）、错层飞行（飞高或者飞低防止碰撞），进行模型深入改进，重点应放在处理问题方法上。,如,第31页,不论选择哪一个表示，怎样考虑约束条件，目标函数都不可能是线性。,现在看来，那年题目建模只是在条件考虑上和建模中目标函数表示方面较难一点。,是一个带不等式约束非线性规划问题。,而且不可能转化成线性形式。,第32页,非线性规划模型按约束条件可分为以下三类：,无约束非线性规划模型：,等式约束非线性规划模型：,不等式约束非线性规划模型：,第33页,如,数据拟合最小二乘问题就是一个无约束极值问题。,其思想是：观察点（试验数据点）到曲线距离平方之和最小,无约束非线性规划模型：,第34页,理论上无约束极值问题可化成求解,即解一个,n,元方程组，且往往是非线性方程组。,而普通说来，非线性方程组求解并不比求无约束极值轻易。,第35页,求解无约束极值问题基本方法：,迭代法,从一个给定初始可行点 出发，依次,产生一个可行点列,一个极小值点,恰好是,使得某个,基本思绪：,或,收敛于,称含有这种性质算法,是,收敛,.,第36页,由,迭代到,时,记,即,其中向量,为,搜索方向,实数,称为,步长,确定以后,由,可唯一地确定,从,出发就可确定点列,第37页,迭代方法很多,各种迭代法区分在于选取,方式不一样,而,尤为关键,.,普通要求,递减,含有这种性质算法叫做,下降,算法,.,第38页,若已得,下降得最多,并确定了,可行下降方向,上选取步长,则在射线,使,且使,即求,求,过程称为,一维搜索,.,1.,下降算法,第39页,于是一维搜索归结为求解一维无约束极值问题,:,其算法有,Newton,法、平分法、黄金分割法,（,0.618,法）、分数法（,Fibonacci,法）、抛物线法（二次插值法）等，,前两种算法需计算,导数，,后三种算法只需计算,函数值下面仅介绍,Newton,法，对其它方法了解可参考相关书籍。,第40页,按,给定初始可行点 和控制误差 ，,迭代格式,迭代，,当,时，,即求得,最优解近似解,停顿计算。,Newton,法介绍,第41页,一个好算法必须以较快速度收敛到,最优解。,设算法产生点列,收敛于最优解,若存在,及,使,则称,为,p,阶收敛。,该算法也是,p,阶收敛。,第42页,称为,线性收敛；,当,且,时，,称为,超线性收敛；,当,时，,称为,平方收敛；,当,时，,第43页,一个算法是否收敛，,往往与,选取相关,若当,充分靠近,时，,由算法产生点列,才收敛于,则称该算法为含有局部收敛,性算法；,若对,则称该算法为含有全局收敛性算法。,由算法产生 点列,均收敛,于,第44页,Newton,法是平方收敛，含有局部收敛性；抛物线法是超线性收敛，含有全局收敛性；平分法、黄金分割法、分数法是线性收敛，含有全局收敛性。,常见一维搜索算法收敛性,第45页,当,含有多个极小值点时，,则算法求得,往往是,一个局部极小值点。,此时可,改变,取值，重新迭代求解。,若求得多个极小值点，则从中选择一个,较满意结果。,说明：,第46页,1847,年,Cauchy,提出了第一个无约束极值问题算法,梯度法或最速下降法：,2.,梯度法,第47页,例题：应用梯度法求解,解：,第48页,该算法含有全局收敛性，是线性收敛，但有时是很慢线性收敛，这似乎与“最速下降”矛盾。其实不然，最速下降方向函数在某点处局部性质，对局部来说是最速下降方向，对全局来说却不一定是最速下降方向，故梯度法不是有效实用算法。,经过对它改进或利用它与其它收敛快算法相结合可得,Newton,法、,Fletcher-Reeves,共轭梯度法、变尺度法和,Powell,法,等有效算法。,第49页,下面仅介绍前二者，对后二者了解可参阅相关书籍。,当,时，,则 。,其中,称为,在 处,Hesse,矩阵。,Newton,法,第50页,该算法是平方收敛，含有局部收敛性。,对,Newton,法进行改进，可得含有超线性收敛且含有全局收敛性,阻尼,Newton,法,或,修正,Newton,法,：,当,时，,有 。,第51页,Fletcher-Reeves,共轭梯度法,当,时，,有 。,该算法收敛速度介于梯度法和,Newton,法,其中,之间，既克服了前者慢收敛性，又防止了,后者计算量大和仅含有局部收敛性缺点。,第52页,（,2,）,只有等式约束非线性规划问题通常可用消元法、拉格朗日乘子法，将其化为无约束问题求解,.,（,3,）,含有不等式约束非线性规划问题解起来很复杂，求解这一类问题，通常将不等式化为等式约束，再将约束问题化为无约束问题，用线性迫近方法将非线性规划问题化为线性规划问题,.,下面先介绍一个简单非线性规划问题例子，其中一些约束条件是等式，这类非线性规划问题可用拉格朗日方法求解,.,第53页,第54页,第55页,第56页,第57页,Kuhn-Tucker,定理：对于不等式约束非线性最优化 极值问题,若 ，均可微，则其极值点存在必要条件是：,注：更详细结论参阅相关书籍,.,不等式约束非线性规划模型,第58页,注：,1,、库,-,图条件是判别有约束极值点必要条件，并非充分条件。不过对于凸函数、凸集问题也是判别其极值点充分条件。固此时局部最优解也必为全局最优解。,2,、库,-,图乘子与拉格朗日乘子类似。但拉格朗日乘子符号不是确定，可正可负；而库,-,恩乘子符号是确定，其规律为：,a,、求 ，时，则,b,、求 ，时，则,c,、求 ，时，则,d,、求 ，时，则第59页,罚函数法,:,约束最优化问题化为无约束最优化问题一个求解方法,第60页,第61页,罚函数法步骤：（等式约束最优化问题罚函数法）,第62页,第63页,第64页,第65页,罚函数法步骤：（不等式约束最优化问题罚函数法）,第66页,第67页,第68页,注：罚函数法更多详细改进工作，需参阅相关书籍,第69页,在许多实际问题中，衡量一个方案好坏标准往往不止一个，比如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高,.,这一类问题统称为多目标最优化问题或多目标规划问题,.,我们先来看一个投资计划例子,.,4.,多目标规划,第70页,例：投资问题,某企业在一段时间内有,a,(,亿元,),资金可用于建厂投资。若可供选择项目记为,1,2,m,。而且一旦对第,i,个项目投资就用去,a,i,亿元；而这段时间内可得收益,c,i,亿元。问怎样确定最正确投资方案？,最正确投资方案：投资最少，收益最大！,第71页,投资最少：,约束条件为：,收益最大：,第72页,第73页,第74页,第75页,第76页,第77页,第78页,第79页,第80页,第81页,第82页,5.,动态规划,动态规划模型问题普通要归结为求最优控制函数使某个泛函到达极值,.,求解泛函极值问题方法主要有,变分法,和,最优控制理论方法,.,第83页,第84页,第85页,第86页,第87页,一元函数泰勒公式：,第88页,二元函数泰勒公式,:,第89页,其中记号,表示,表示,第90页,第91页,第92页,第93页,第94页,第95页,第96页,第97页,例题：,(,最速降线问题,),最速降线问题是历史上变分法,开始发展第一个问题,.,它是贝努里（,J.Bernoulli,）,于,1696,年提出。问题提法是这么：,设,A,和,B,是铅直平面上不在同一铅直线上两点，在全部,连结,A,和,B,平面曲线中，,求一曲线,，当质点仅受重力作用，且初速为零，沿此曲线从,A,滑行至,B,时，使所需时间最短,.,第98页,第99页,第100页,第101页,第102页,第103页,第104页,第105页,第106页,第107页,例题：生产设备最大经济效益,某工厂购置了一台新设备投入到生产中。首先该设备伴随运行时间推移其磨损程度愈来愈大，所以其转卖价将伴随使用设备时间增加而减小；另首先生产设备总是要进行日常保养，花费一定保养费，保养能够减缓设备磨损程度，提升设备转卖价。那么，怎样确定,最优保养费,和,设备转卖时间,，才能使这台设备经济效益最大。,第108页,第109页,第110页,第111页,第112页,第113页,第114页,第115页,第116页,第117页,