《数学建模之运筹学.ppt》由会员分享，可在线阅读，更多相关《数学建模之运筹学.ppt（68页珍藏版）》请在三一办公上搜索。
1、第一讲 数学建模简介及数学规划模型 Introduction of MM and Mathematical Programming Model,Network Programming,数学建模 Mathematical Modeling,数学建模简介,一般地，数学模型可以描述为，对于现实世界的一个特定对象，为了一个特定目的，根据特有的内在规律，作出一些必要的简化假设，运用适当的数学工具，得到的一个数学结构。把现实世界中的实际问题加以提炼，抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用过程称为数学建模。数学模型或者能解释特定现象
2、的现实状态，或者能预测到对象的未来状况，或者能提供处理对象的最优决策或控制。,数学模型的分类,1、按模型的应用领域分类：生物数学模型 医学数学模型 地质数学模型 数量经济学模型 数学社会学模型2、按是否考虑随机因素分类：确定性模型 随机性模型3、按是否考虑模型的变化分类：静态模型 动态模型,4、按应用离散方法或连续方法分类：离散模型 连续模型5、按建立模型的数学方法分类：几何模型 微分方程模型 图论模型 规划论模型 马氏链模型,6、按人们对是物发展过程的了解程度分类：（1）白箱模型：指那些内部规律比较清楚的模 型。如力学、热学、电学以及相关的工程技 术问题。（2）灰箱模型：指那些内部规律尚不十
3、分清楚，在建立和改 善模型方面都还不同程度地有许多 工作要做的问题。如 气象学、生态学经济学等领域的模型。（3）黑箱模型：指一些其内部规律还很少为人们 所知的现象。如生命科学、社会科学等方面的问题。但由于因素众多、关系复杂，也可简化为灰箱模型来研究。,数学建模的几个过程,1、模型准备 2、模型假设 3、模型建立 4、模型构成 5、模型求解 6、模型分析 7、模型检验 8、模型应用,模型准备,了解实际背景,明确建模目的,搜集有关信息,掌握对象特征,形成一个比较清晰的问题,模型假设 针对问题特点和建模目的 作出合理的、简化的假设 在合理与简化之间作出折中,模型建立,用数学的语言、符号描述问题 发挥
4、想像力使用类比法 尽量采用简单的数学工具,各种数学方法、软件和计算机技术,如结果的误差分析、统计分析、模型对数据的稳定性分析,模型求解,模型分析,模型检验 与实际现象、数据比较，检验模型的合理性、适用性,模型应用,数学建模有助于培养以下几个方面的素质和能力：,数学素质和能力计算机应用能力论文写作能力团队合作精神和进行协调的组织能力培养想象能力发展观察力，形成洞察力勇于参与的竞争意识和不怕困难、奋力攻关的顽强意志,为培养和选拔优秀的数学人才，世界各国有各种不同形式不同层次的数学竞赛.传统的数学竞赛只局限于演绎、推理等纯数学形式，它不能培养和发展学生运用数学知识解决实际问题的能力，不能满足科学技术
5、飞速发展的时代需要.从1983年起，在美国就有一些有识之士开始探讨组织一项应用数学方面的竞赛的可能性.,1985年美国第一届大学生数学建模竞赛（mathematical competition in modeling）1988年改为mathematical contest in modeling简称MCM.由美国工业与应用数学会和美国运筹学会联合举办.1985年起每年举行一届，一般在每年的二月下旬或三月初的某个星期五或星期日举行.美国竞赛评出Outstanding,Meritorious,Honorable Mention及Successful Participation等级别.,1989年北
6、京的三所大学组队参加美国的MCM竞赛,此后我国的参赛队伍越来越多.19921993年中国工业与应用数学学会（CSIAM）举办了两次中国大学生数学建模竞赛.1994年起，由国家教委（教育部）高教司和中国工业与应用数学学会共同于每年9月举办，1999年开始设立大专组的竞赛.,无论是美国还是我国大学本科组数学建模竞赛题每年都是两道，参赛队从中任选一道题目.一般来说其中一道是连续型，另一道是离散型；或者一道是开放型的，另一道是严谨型的.竞赛内容或题目是由工程技术、管理科学中的实际问题简化而成，留有充分余地供参赛者发挥其聪明才智和创造精神.竞赛形式为三名学生组成一队，可以自由地收集资料、调查研究，使用计
7、算机、因特网和任何软件，在三天时间内分工合作完成一篇论文.评奖标准为模型假设的合理性、建模的创造性、结果的准确性和文字表述的清晰程度.,初等模型,一辆汽车在拐弯时急刹车，结果冲到路边的沟里（见下图），交通警察立即赶到了事故现场。司机申辩说，当他进入弯道时刹车失灵，他还一口咬定，进入弯道其车速为每小时英里（这是该路的速度上限，约合每秒.米）。警察验车时证实该车的制动器在事故发生时确实失灵，然而，司机所说的车速是否真实可信呢？,现在，让我们帮警察计算一下司机所报速度的真实性。连接刹车痕迹的初始点和终点，用x表示沿连线汽车横向所走出的距离，用y表示竖直的距离，如下图,上面的表中，我们给出了外侧刹车痕
8、迹的有关值，而且，经过测量还发现，该车并没有偏离它所行驶的转弯路线，也就是说，它的车头一直指向切线方向。可以假设，该车的重心是沿一个半径为r的圆做圆周运动。假设磨擦力作用在该车速度的法线方向上，并设汽车的速度v是一个常数。显然，磨擦力提供了向心力，设磨擦系数为,则,其中m为汽车质量.由上式易得,如何计算圆周半径r？假设已知弦的长度为c，弓形的高度为h，其图如下所示，由勾股定理知,由前面的表中代入近似数据c=33.27,h=3.55后，得 r=40.75米 根据实际路面与汽车轮胎的情况，可以测量出磨擦系数，经过实际测试得到 g=8.175米秒 将此结果代入我们上面利用第二定律所得到的式子中，得
9、v18.25米秒 此结果比司机所报速度（17.92米秒）略大。但是，我们不得不考虑计算半径r及测试时的误差。如果误差允许在以内，无疑，此计算结果对司机是相当有利的。,椅子能在不平的地面上放稳吗？,把四只脚的椅子往不平的地面上一放，通常只有三只脚着地，放不稳，然而有人认为只要稍挪动几次，就可以四脚着地，放稳了，对吗？,问题分析 通常三只脚着地 放稳的标准:四只脚着地 四条腿一样长，椅脚与地面点接触，四脚连线呈正方形;地面高度连续变化，可视为数学上的连 续曲面;地面相对平坦，使椅子在任意位置至少三只脚 同时着地。,模型假设,建立模型,用数学语言把椅子位置和四只脚着地的关系表示出来.,椅子位置,利用
10、正方形(椅脚连线)的对称性,用(对角线与x轴的夹角)表示椅子位置,四只脚着地,椅脚与地面距离为零,距离是的函数,四个距离(四只脚),两个距离,正方形ABCD绕O点旋转,A,C 两脚与地面距离之和记为f(),B,D 两脚与地面距离之和记为g(),用数学语言把椅子位置和四只脚着地的关系表示出来.,f(),g()是连续函数,对任意,f(),g()至少一个为0,数学问题,已知：f(),g()是连续函数;对任意，f()g()=0;且 g(0)=0，f(0)0.证明：存在0，使f(0)=g(0)=0.,地面为连续曲面,椅子在任意位置至少三只脚着地,模型求解,将椅子旋转900，对角线AC和BD互换.由g(0
11、)=0，f(0)0，知f(/2)=0,g(/2)0.令h()=f()g(),则h(0)0和h(/2)0.由 f,g的连续性知 h为连续函数,据连续函数的基本性质,必存在0,使h(0)=0,即f(0)=g(0).因为f()g()=0,所以f(0)=g(0)=0.,评注和思考,建模的关键:,和 f(),g()的确定.,模型假设中四脚呈正方形不是本质的,读者可考虑长方形的情形.,数学规划模型,实际问题中的优化模型,x决策变量,f(x)目标函数,gi(x)0约束条件,多元函数条件极值,决策变量个数n和约束条件个数m较大,最优解在可行域的边界上取得,重点在模型的建立和结果的分析,无约束优化线性规划非线性
12、规划整数规划多目标规划动态规划等等,线性规划,设每月生产小、中、大型汽车的数量分别为x1,x2,x3,汽车厂生产计划,模型建立,线性规划模型(LP),模型求解,3）模型中增加条件：x1,x2,x3 均为整数，重新求解。,OBJECTIVE FUNCTION VALUE 1)632.2581VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.731183 3)0.0000
13、00 0.003226,1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。,2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。,但必须检验它们是否满足约束条件。为什么？,结果为小数，怎么办？,IP可用LINDO直接求解,整数规划(Integer Programming,简记IP),“gin 3”表示“前3个变量为整数”，等价于：gin x1gin x2gin x3,IP 的最优解x1=64，x2=168，x3=0，最优值z=632,max 2x1+3x2+4x3st1.5x1+3x
14、2+5x3600280 x1+250 x2+400 x360000endgin 3,OBJECTIVE FUNCTION VALUE 1)632.0000VARIABLE VALUE REDUCED COST X1 64.000000-2.000000 X2 168.000000-3.000000 X3 0.000000-4.000000,模型求解,IP 结果输出,其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：,方法1：分解为8个LP子模型,汽车厂生产计划,若生产某类汽车，则至少生产80辆，求生产计划。,x1,x2,x3=0 或 80,x1=80，x2=150，
15、x3=0，最优值z=610,LINDO中对0-1变量的限定：int y1int y2int y3,方法2：引入0-1变量，化为整数规划,M为大的正数，可取1000,OBJECTIVE FUNCTION VALUE 1)610.0000VARIABLE VALUE REDUCED COST X1 80.000000-2.000000 X2 150.000000-3.000000 X3 0.000000-4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000,若生产某类汽车，则至少生产80辆，求生产计划。,x1
16、=0 或 80,最优解同前,NLP虽然可用现成的数学软件求解(如LINGO,MATLAB)，但是其结果常依赖于初值的选择。,方法3：化为非线性规划,非线性规划（Non-Linear Programming，简记NLP）,实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。,若生产某类汽车，则至少生产80辆，求生产计划。,x1=0 或 80,非线性规划,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a,b表示，距离单位：千米）及水泥用量d（吨）如下：,为保障供应，需建两个料场，日储量各为20吨，问应建在何处，使总的吨千米数最小，并试制定每天的供应计划.,一个有约束
17、条件的非线性规划问题的解法大致分为：用线性规划、二次规划来逐步逼近非线性规划的方法；对约束非线性规划问题不预先作转换的直接求解方法，如随机试验法等；对约束非线性规划问题不预先作转换，直接进行处理的分析方法，如可行方向法、凸单纯形法等；把约束非线性规划问题转换为无约束非线性规划来求解的方法，如SUMT外点法、SUMT内点法、乘子法等。,整数规划,为了选修课程门数最少，应学习哪些课程？,选课策略,选修课程最少，且学分尽量多，应学习哪些课程？,0-1规划模型,决策变量,目标函数,xi=1 选修课号i 的课程（xi=0 不选）,选修课程总数最少,约束条件,最少2门数学课，3门运筹学课，2门计算机课。,
18、先修课程要求,最优解：x1=x2=x3=x6=x7=x9=1,其它为0；6门课程，总学分21,0-1规划模型,约束条件,x3=1必有x1=x2=1,模型求解（LINDO）,学分最多,多目标优化的处理方法：化成单目标优化。,两目标(多目标)规划,讨论：选修课程最少，学分尽量多，应学习哪些课程？,课程最少,以学分最多为目标，不管课程多少。,以课程最少为目标，不管学分多少。,多目标规划,在课程最少的前提下以学分最多为目标。,注意：最优解不唯一！,LINDO无法告诉优化问题的解是否唯一。,可将x9=1 易为x6=1,最优解：x1=x2=x3=x5=x7=x9=1,其它为0；总学分由21增至22。,多目
19、标规划,对学分数和课程数加权形成一个目标，如三七开。,最优解：x1=x2=x3=x4=x5=x6=x7=x9=1，其它为0；总学分28。,讨论与思考,最优解与1=0，2=1的结果相同学分最多,多目标规划,最优解与1=1，2=0的结果相同课程最少,多目标规划模型,在许多客观实际问题中，要达到的目标往往不止一个。例如，设计导弹时既要使其射程最远，有要燃料最省，还要精度最高。这类含有多个目标的优化问题称为多目标规划问题。,设市场上有香蕉、苹果、葡萄三种水果，其单价分别为4.2元/千克，2.4元/千克，2.2元/千克。现在某单位要筹办一次节日茶话会，要求用于买的水果不少于10千克，香蕉、苹果的总和不少于6千克，问如何确定最好的购买方案。,目标规划模型,目标规划是一个新的多目标决策工具，它能把决策者的意愿反映到数学模型中。目标规划不像线性（或非线性）规划那样去直接求目标函数的最大（小）值，而是寻求实际能够达到的值与目标之间的偏差变量的最小值，这些偏差变量表示目标的达成程度。,动态规划模型,
