数学建模培训.ppt

第一部分 建立数学模型,数学？,数学有什么用？怎么用？,数学？,电子计算机的出现及飞速发展；数学以空前的广度和深度向一切领域渗透。,数学有什么用？,数学？,工程技术领域：,数学有什么用？,大型水坝的应力问题、天气预报,数学？,工程技术领域：,数学有什么用？,高新技术领域：通讯、航天、微电子、自动化,数值风洞数值模拟飞行器流场波音777实现“无纸设计”，同时全部实验都在计算机上完成,数学？,工程技术领域：,数学有什么用？,高新技术领域：,计量经济学人口控制论,新的领域：,数学生态学数学地质学等,数学？,数学有什么用？,怎么用？,解决实际问题；数学模型。,模型,博览会上汽车、水果,电站、卫星、铁路,照片、图表、公式、程序,模型与原型,原型：是指人们在现实世界里关心、研究或从事生产、管理的实际对象。,模型：指为了某个特定的目的将原型的一部分信息简缩、提炼而构成的原型替代物。,模型不是原型原封不动的复制品。原型有各个方面和层次的特征，而模型只要求与某种目的有关的那些方面和层次。,模型的分类（用模型替代原型）,直观模型：玩具、照片,思维模型,符号模型：地图、电路图、化学结构式,数学模型：由数字、字母或其它数学符号组成的，描述现实对象数量规律的数学公式、图形或算法。,物理模型：风洞中的飞机模型,数学模型,对于一个现实对象，为了一个特定目的，根据其内在规律，做出必要的简化假设，运用适当的数学工具，得到的一个数学结构。,已知的数学模型,“航行问题”：甲乙两地相距750公里，船从甲地到乙地顺水航行需要30小时，从乙地到甲地逆水航行需要50小时，问船速、水速各若干？,数学模型无所不在,专业研究领域：物理、计算机研究,日常投资：投资、决策,各行各业：经济、金融,数学建模,Mathematical Modeling,应用知识从实际课题中抽象、提炼出数学模型的过程。,例1.手机电话卡的选择,已知入网电话卡每分钟0.4元，每月25元租金；神州行每分钟0.6元，不用月租费。问：选择哪种卡比较省钱？,例2.银行问题,去银行取钱对每个人来说可能都不是一次愉快的经历，因为每次去取钱都要花很长时间排队。银行现在实行的排队方法是否合理？你是否有办法在现有窗口的情况下提高整个系统的效率？,数学建模作为用数学方法解决实际问题的 第一步，越来越受到人们的重视。,数学建模的一般步骤,实体信息,求解,假设,建模,验证,应用,分析,数学模型的分类,能力的培养,能力上的锻炼,Google,创新的能力,观察能力分析能力,在尽可能短的时间内查到并学会你想应用的知识的本领,图书馆,归纳能力数据处理能力,一些简单的实例,例1.某人第一天由A地去B地，第二天由B地沿原路返回A地。问：在什么条件下，可以保证途中至少存在一地，此人在两天中的同一时间到达该地。,分析：假如我们换一种想法，把第二天的返回改变成另一人在同一天由B去A，问题就化为：在什么条件下，两人至少在途中相遇一次？易得：只要任何一人的到达时间晚于另一人的出发时间，两人必会在途中相遇。,例2：椅子放稳问题,把椅子往不平的地面上一放，通常只有，放不稳，然而只需稍微挪动几次，就可以使，放稳了。,四只脚同时着地,三只脚着地,模型假设：,椅子四条腿一样长，椅脚与地面接触处可视为一个点，四脚的连线呈正方形。,地面可视为数学上的连续曲面。,椅子在任何位置至少有三只脚同时着地。,建模：,设椅子的四只脚位于点 其连线构成一正方形，对角线的交点为坐标原点，对角线 为坐标轴（坐标系如图所示）。,D,A,C,B,O,C,B,A,D,y,x,设 为 两点椅子的脚离开地面的距离之和；为 两点的椅子的脚离开地面的距离之和，则由条件得：,注意到：,椅子的四脚落地意味着 故不妨假设 则问题归结为是否存在 使得,令 则 是定义在 上的连续函数，且,求解,由条件可知：有,且,由根的存在定理知：使得 即,问题：,在原问题中，若将一个四方形的椅子改为长方形的桌子，则该如何求解？,例3.商人们怎样安全过河,三名商人各带一个随从乘船渡河，一只小船只能容纳两人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多就杀人越货。但是如何乘船渡河的大权掌握在商人们的手中。,3名商人 3名随从,问题分析（多步决策过程）,决策：,要求：,每一步(此岸到彼岸或彼岸到此岸)船上的人员,在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.,：过程的状态,：允许状态的集合,建模：,：第 次渡河前此岸的商人数,：第 次渡河前此岸的随从数,：状态转移律,：第 次渡船上的随从数,：决策,：允许决策集合,建模：,：第 次渡船上的商人数,求，使，并按转移律由 到。,建模：,多步决策问题：,模型求解,穷举法：编程上机,图解法,0,1,2,3,1,2,3,y,x,状态s=(x,y)：16个格点,允许状态：,10个 点,允许决策：,移动1或2格；k奇，左下移；k偶，右上移。,s1,sn+1,d1,d11,d1,d11给出安全渡河方案,评注和思考,规格化方法，易于推广,考虑4名商人各带一随从的情况,例4,某人平时下班总是按预定时间到达某处，然后他妻子开车接他回家。有一天，他比平时提早了三十分钟到达该处，于是此人就沿着妻子来接他的方向步行回去并在途中遇到了妻子。这一天，他比平时提前了十分钟到家，问此人共步行了多长时间？,分析,提前的十分钟时间从何而来？,会合点,相遇点,家,5分钟,5:30,5:35,由相遇点到会合点需开几分钟？,相遇时他已步行了多少分钟？,请思考：本题解答中隐含了哪些假设条件？,预备技能,数学知识,分析、代数、几何、概率、统计、优化、方程,软件使用,Matlab,Mathematica,Maple,Lindo,Lingo,编程：C/C+,第二部分 数学规划模型,数学规划的一般模型,min f(x)s.t.hi(x)=0,i=1,m gp(x)0,p=1,t,f(x),hi(x)(i=1,m),gp(x)(p=1,t)均是定义在En上的实函数。,x=(x1,xn)T:决策变量,f(x):目标函数,hi(x),gp(x):约束函数,数学规划的一般模型,min f(x)s.t.hi(x)=0,i=1,m gp(x)0,p=1,t,若f(x),hi(x)(i=1,m),gp(x)(p=1,t)均为线性函数，则问题(MP)就被称为线性规划问题。,线性规划问题：求多变量线性函数在线性约束条件下的最优值。,(MP),数学规划的简单分类,线性规划(LP)目标和约束均为线性函数 非线性规划(NLP)目标或约束中存在非线性函数 二次规划(QP)目标为二次函数、约束为线性 整数规划(IP)决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划,连续优化,离散优化,优化模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问题求解的难度增加,线性规划问题的标准形式,min c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1,x2,xn0,其中cj,bi,aij 均为实常数。,任意线性规划问题可化为标准形式。,线性规划问题标准化,目标函数标准化 max z=min(-z),约束条件标准化,假设约束条件中有不等式约束 ai1x1+ai2x2+ainxnbi,引入新变量 xn+1(称为松弛变量),则上式等价于 ai1x1+ai2x2+ainxn+xn+1=bi,xn+1 0,线性规划问题标准化,自由变量标准化,若变量 xj 无约束,可引入两个新变量xj,xj”,故以下只考虑标准形式，也可用矩阵形式表示为 min z=c x s.t.Ax=b x0,令 xj=xj-xj”，xj,xj”0,数学规划的一般模型,min f(x)s.t.hi(x)=0,i=1,m gp(x)0,p=1,t,若f(x),hi(x)(i=1,m),gp(x)(p=1,t)中至少有一个是非线性函数，问题(MP)就被称为非线性规划问题。,(MP),数学规划模型,线性规划问题：min z=c x s.t.Ax=b x0,若要求变量 x 取整数值时，则称之为整数规划；,若变量只取0或1时，则称之为0-1规划；,若只要求部分变量取整数值，则称之为混合整数规划。,例1 奶制品的生产和销售,每天有50桶牛奶供应,试制订生产计划，使每天获利最大,1桶牛奶,3公斤A1,甲：12小时,获利24元/公斤,4公斤A2,乙：8小时,获利16元/公斤,每天正式工人总的劳动时间为480小时,设备甲每天至多能加工100公斤A1,设备乙的加工能力没有限制,x1,x2=0,决策变量：,1桶牛奶,3公斤A1,甲：12小时,获利24元/公斤,4公斤A2,乙：8小时,获利16元/公斤,获利 243x1,获利 164 x2,x1桶牛奶生产A1,x2桶牛奶生产A2,目标函数：,Max z=72x1+64 x2,线性规划模型(LP),约束条件：,x1+x2=50,12x1+8x2=480,3x1=100,线性规划问题求解,满足约束条件的解称为可行解所有可行解构成的集合称为可行域满足目标式的可行解称为最优解,线性规划问题的可行域是一个凸多边形；,线性规划问题如果存在最优解，则最优解必在可行域的顶点处达到。,可行域的几何特征：,可行域的顶点称为基本可行解。,模型求解方法,图解法,约束条件,x1+x2=50,12x1+8x2=480,3x1=100,x1,x2=0,目标函数,max z=72x1+64x2,z=c(常数)等值线,l1:x1+x2=50,l2:12x1+8x2=480,l3:3x1=100,l4:x1=0,l5:x2=0,l2,l1,l3,l4,l5,A,B,C,x2,x1,D,0,z=0,z=2400,z=3360,模型求解方法,为此求解方程,容易得到该方程的解为 x=(20,30)T,在B(20,30)点得到最优解,模型求解方法,基本思想：从可行域的一个顶点（基本可行解）出发，转换到另一个顶点，并且使目标函数值逐步减小，有限步后可得到最优解。,单纯形算法不是多项式时间算法,单纯形算法,模型求解,单纯形算法,利用计算机软件 lingo,lindo,椭球算法、Karmarkar算法,奶制品的生产销售计划,在例1基础上深加工,试制订生产计划，使每天获利最大,每天：50桶牛奶,480小时,设备甲至多生产100公斤A1,1桶牛奶,3公斤A1,甲：12小时,获利24元/公斤,4公斤A2,乙：8小时,获利16元/公斤,0.8公斤B1,获利44元/公斤,1公斤,2小时,3元,0.75公斤B1,获利32元/公斤,1公斤,2小时,3元,出售x1 千克 A1,x2 千克 A2，,X3千克 B1,x4千克 B2,原料供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x5千克 A1加工B1，x6千克 A2加工B2,附加约束,例2 指派问题,某生产车间有四位工人，现要安排他们分别完成四项工作，每人做每项工作所消耗的时间如下：,A B C D,15 18 21 24,甲 乙 丙 丁,19 23 22 18,26 17 16 19,19 21 23 17,请问安排哪位工人完成哪项工作，可使总的消耗工时最少？,工人,工作,模型求解,整数规划的算法,匈牙利算法,例3 生猪的出售时机,饲养场每天投入4元资金，用于饲料、人力、设备，估计可使80千克重的生猪体重增加2公斤。市场价格目前为每千克8元，但是预测每天会降低0.1元，问生猪应何时出售。如果估计和预测有误差，对结果有何影响。,模型建立,若当天出售，利润为808640元,t天出售：,生猪体重 w=80+rt 出售价格 p=8-gt,资金投入 C=4t 销售收入 R=pw,利润：Q(t)=R-C=pw-C=(8-gt)(80+rt)-4t,目标：求t使得Q(t)最大,其中r是生猪的每天的体重增加量，g是生猪每天的价格降低量。,模型求解,10天后出售，可多得利润20元。,用微分法：,解得：,本例中，估计r=2,g=0.1。,故t=10，且Q(10)=660 640。,常见的数学规划模型:,