数学建模之运筹学

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