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