最优化问题数学模型课件.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《最优化问题数学模型课件.ppt》由会员分享,可在线阅读,更多相关《最优化问题数学模型课件.ppt(117页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、关于最优化问题数学模型第1页,此课件共117页哦 数学家对最优化问题的研究已经有很多年的历史。以前解决最优化问题的数学方法只限于古典求导方法和变分法,拉格朗日(Lagrange)乘数法解决等式约束下的条件极值问题。计算机技术的出现,使得数学家研究出了许多最优化方法和算法用以解决以前难以解决的问题。一、最优化模型的概述 解决最优生产计划、最优设计、最优策略.第2页,此课件共117页哦 运用最优化方法解决最优化问题的一般方法步骤如下:前期分析:分析问题,找出要解决的目标,约束条件,并确立最优化的目标。定义变量,建立最优化问题的数学模型,列出目标函数和约束条件。针对建立的模型,选择合适的求解方法或数
2、学软件。编写程序,利用计算机求解。对结果进行分析,讨论诸如:结果的合理性、正确性,算法的收敛性,模型的适用性和通用性,算法效率与误差等。第3页,此课件共117页哦 最优化模型分类方法有很多,可按变量、约束条件、目标函数个数、目标函数和约束条件的是否线性是否依赖时间等分类。根据目标函数,约束条件的特点将最优化模型包含的主要内容大致如下划分:线性规划 整数规划 非线性规划 多目标规划 动态规划 对策论二、最优化模型的分类第4页,此课件共117页哦最优化模型的求解方法分类图克定理库恩极值原理有约束变分法微分法无约束解析法-.1.5.4网络优化方法多目标优化法随机搜索法单纯形法方向加速法步长加速法坐标
3、轮换法多维搜索法插值法黄金分割法裴波那契法一维搜索法数值算法.2复形法法法化有为无梯度法梯度投影法可行方向法有约束梯度法变尺度法共轭梯度法拟牛顿法最速下降法无约束梯度法梯度算法SWIFTSUMT.3第5页,此课件共117页哦最优化数学模型形式 min()xf x.()0,1,2,.,()0,1,2,.,iistg ximh xin 其中,极大值问题可以转化为极小值问题来进行求解。如求:max()xf x 可以转化为:min()xf x三、最优化模型的建立目标:求函数极值或最值,求取得极值时变量的取值。第6页,此课件共117页哦问题:某工厂在计划期内要安排生产I、II两种产品,已知生产单位产品所
4、需的设备台时及A、B两种原材料的消耗,如下表所示 12kg40原材料原材料B16kg04原材料原材料A8台时21设备III该工厂每生产一件产品I可获利2元,每生产一件产品II可获利3元。问应如何安排计划使该工厂获利最多?第7页,此课件共117页哦解:该工厂生产产品I x1件,生产产品II x2件,我们可建立如下数学模型:2132maxxxz0,12416482212121xxxxxxs.t.2,41421xxz第8页,此课件共117页哦 最优化问题中的所有变量均为整数时,这类问题称为整数规划问题。整数规划可分为线性整数规划和非线性整数规划,以及混合整数规划等。如果决策变量的取值要么为0,要么为
5、1,则这样的规划问题称为01规划。第9页,此课件共117页哦问题:问题:某班级准备从某班级准备从5名名游泳队员中选择游泳队员中选择4人人组成接力队,参加学校组成接力队,参加学校的的4*100m混合泳接力比赛。混合泳接力比赛。5名队员名队员4种泳姿种泳姿的百米平均成绩如表的百米平均成绩如表2-1,问应如何选拔队员组成接力队?,问应如何选拔队员组成接力队?队员甲已丙丁戊蝶泳仰泳蛙泳自由泳66.8秒57.2787067.475.6668758.666.45367.874.27184.659.469.657.283.862.4表2-1第10页,此课件共117页哦问题分析:问题分析:记甲、乙、丙、丁、戊
6、分别为记甲、乙、丙、丁、戊分别为i i=1,2,3,4,5;=1,2,3,4,5;记泳姿记泳姿j j=1,2,3,4.=1,2,3,4.记队员记队员 i i 的第的第 j j 种泳姿的百米最好成绩为种泳姿的百米最好成绩为c_c_ijij(s),(s),则表则表2-12-1可以表示成表可以表示成表2-2.2-2.c_iji=1i=2i=3i=4i=5j=1j=2j=3j=466.857.2787067.475.6668758.666.45367.874.27184.659.469.657.283.862.4表2-2第11页,此课件共117页哦 决策变量:引入0-1变量 ,若选择队员i参加泳姿j的
7、比赛,记,否则记 。目标函数:当队员i入选泳姿j时,表示该队员的成绩,否则 。于是接力队的成绩可表示为 约束条件:根据接力队要求,满足约束条件a.每人最多只能入选4种泳姿之一,即b.每种泳姿必须有1人而且只能有一人入选,即ijx0ijx1ijx.151iijx.141jijxijx.4151jiijijxcf0ijijxcijijxc第12页,此课件共117页哦 综上所述,这个问题的优化模型可写作:.1,0ijx.4,3,2,1,151jxiij.5,4,3,2,1,1.41ixtsjij4151minjiijijxcf第13页,此课件共117页哦非线性规划问题的一般数学模型:其中,为目标函数
8、,为约束函数,这些函数中至少有一个是非线性函数。min().()0,1,2,()0,1,2,.ijf xstg ximh xjlnEx)(xf)(),(xhxgji第14页,此课件共117页哦应用实例:供应与选址 某公司有6个建筑工地要开工,每个工地的位置(用平面坐标系a,b表示,距离单位:km)及水泥日用量d(t)由下表给出目前有两个临时料场位于A(5,1),B(2,7),日储量各有20t假设从料场到工地之间均有直线道路相连 (1)试制定每天的供应计划,即从A,B两料场分别向各工地运送多少水泥,可使总的吨千米数最小(2)为了进一步减少吨千米数,打算舍弃两个临时料场,改建两个新的,日储量各为2
9、0t,问应建在何处,节省的吨千米数有多大?第15页,此课件共117页哦建立模型 记工地的位置为(ai,bi),水泥日用量为di,i=1,6;料场位置为(xj,yj),日储量为ej,j=1,2;料场j向工地i的运送量为Xij当用临时料场时决策变量为:Xij,当不用临时料场时决策变量为:Xij,xj,yj第16页,此课件共117页哦 事实上,客观世界中的大多问题都是非线性的,给予线性化处理是近似的,是在作了科学的假设和简化后得到的.另一方面,有一些是不能进行线性化处理的,否则将严重影响模型对实际问题近似的可依赖型.由于非线性规划问题在理论分析和计算上通常是很困难的,也不能像线性规划那样给出简洁的结
10、果形式和全面透彻的结论.所以,在数学建模时,要进行认真的分析,对实际问题进行合理的假设、简化,首先考虑用线性规划模型,若线性近似误差较大时,则考虑用非线性规划.第17页,此课件共117页哦 在约1万米的高空的某边长为160km的正方形区域内,经常有若干架飞机作水平飞行,区域内每架飞机的位置和速度向量均由计算机记录其数据,以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘时,计算机记录其数据后,要立即计算并判断是否会发生碰撞。若会发生碰撞,则应计算如何调整各架飞机(包括新进入的飞机)飞行的方向角,以避免碰撞,且使飞机的调整的幅度尽量小,例1 1995年全国数学建模A题:飞行管理问题例题讲解例
11、题讲解第18页,此课件共117页哦该题比较有意思的一句话是:“使调整弧度最小”开放性的一句话,没有限制得很死,较灵活,给参赛者的创新空间比较大一些,使得构建模型的目标函数表现形式很多,再加上模型求解方法(算法)的多样性,从而可以呈现出五花八门的论文。第19页,此课件共117页哦 不碰撞的标准为任意两架飞机的距离大于不碰撞的标准为任意两架飞机的距离大于8km;假设条件:30 飞机飞行的方向角调整幅度不应超过 ;(因飞机飞行的速度变化不大)所有飞机的飞行 速度 v 均为800km/h;有时需要通过查阅文献、资料给出合理假设注:第20页,此课件共117页哦 进入该区域的飞机在到达区域边缘时,与区域内
12、 飞机的距离应在60km以上;最多需考虑六架飞机;不必考虑飞机离开此区域后的状况。根据当年竞赛题目给出的数据,可以验证新进入的飞机与区域内的飞机的距离超过60公里。根据当年竞赛题目给出的数据,可以验证区域内的飞机不超过架(包括新进入的)。第21页,此课件共117页哦 个人的想法不同,队友之间争执不下的情况下,若时间允许,都可一一写到论文中去,建立的模型一、模型二;或者经讨论后,选择一个认为更合理的。现在看来,无论是构建模型,还是计算,都不太难。本例题未给出数据,将重点放在如何构建模型上第22页,此课件共117页哦解:(1)不考虑飞机的尺寸,用点代表飞机;(2)已在区域内的5架飞机按给定的方向角
13、作 直线飞行,则必不会碰撞,也不会发生 意外;(应该根据题目中所给出的数据简 单的 验证一下)(3)飞机调整方向角的过程可在瞬间完成,(不 计调整方向所花费的时间)。为解决该问题,补充假设:第23页,此课件共117页哦变量、参数的符号假设(为了建模)00,1 26)iixyii 第第 架架机机的的初初始始位位置置,(,01 26)iii 第第 架架机机的的整整前前的的方方向向角角,(,1 26)iii 第第 架架机机的的整整后后的的方方向向角角,(,在区域内飞行iiTi 第第 架架 机机按按方方向向角角飞时间(可以根据数据算出来)第24页,此课件共117页哦四种情况:四个象限,易用4个表达式表
14、示说明:用初等数学的知识即可完成,思考:在哪个时间段某两架飞机可能相撞??ijTTor otherelseIn fact,我们只需考虑两架飞机同时在区域内飞行时的情况,也就是说,min,ijT T才是同在区域内的状况。记为ijT第25页,此课件共117页哦 00002202,mincoscossinsinijijijijijt Tijijdxxvtyyvt 根据题目条件,需计算第 架飞机之间的最短距离,i j第26页,此课件共117页哦为此,我们可以给出原问题的模型如下:00612min,60,1,2,6,.,1,2,6.6iiiijijiidi jijs ti 思考:是否还有其他的表达形式?
15、非线性规划模型分别从目标函数和约束条件角度思考第27页,此课件共117页哦首先思考一下目标函数是否有其它的表达?061miniii 同学们首先想到的可能是Oh,Sorry!有正有负抵消第28页,此课件共117页哦061miniii 0621miniii 最小一乘 法最小二乘 法 因最小一乘法带绝对值,不好计算,以上两式,比较而言,后者较好。为了避免抵消or第29页,此课件共117页哦有的队员这样考虑:016min maxiii 令为 ,转化为二次规划用到经验模型中确定参数的近似准则:就所有飞机而言,让调整弧度最大的即尽可能小,Chebshavf 准则第30页,此课件共117页哦其次讨论一下约束
16、条件是否有其它表达?若考虑区域内不发生碰撞(若时间允许,也可以考虑出了区域的情况,另外建模)、错层飞行(飞高或者飞低避免碰撞),进行模型的进一步改进,重点应放在解决问题的方法上。如 02,1,2,6,6,60,1,2,6,iiijijidi jij 第31页,此课件共117页哦 无论选择哪一种表达,怎样考虑约束条件,目标函数都不可能是线性的。现在看来,那年的题目建模只是在条件的考虑上和建模中目标函数的表达方面较难一点。是一个带不等式约束的非线性规划问题。而且不可能转化成线性的形式。第32页,此课件共117页哦非线性规划模型按约束条件可分为以下三类:无约束非线性规划模型:等式约束非线性规划模型:
17、min()nf xxRmin().()0,1,2,jf xst h xjr 不等式约束非线性规划模型:min().()0,1,2,if xst g xim第33页,此课件共117页哦如数据拟合的最小二乘问题就是一个无约束极值问题。其思想是:观察点(实验数据点)到曲线的距离的平方之和最小 无约束非线性规划模型:第34页,此课件共117页哦理论上无约束极值问题可化成求解 0grad fx 即解一个 n 元方程组,且往往是非线性方程组。而一般说来,非线性方程组的求解并不比求无约束极值容易。第35页,此课件共117页哦求解无约束极值问题的基本方法:迭代法 从一个给定的初始可行点 出发,依次0 x产生一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优化 问题 数学模型 课件
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内