《数学建模培训》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 Modeling n应用知识从实际课题中抽象、提炼出数 学模型的过程。 例1. 手机电话卡的选择 已知入网电话卡每分钟0.4元，每 月25元租金；神州行每分钟0.6元，不 用月租费。问：选择哪种卡比较省钱 ？ 例2. 银行问题 去银行取钱对每个人来说可能都不 是一次愉快的经历，因为每次去取钱都 要花很长时间排队。银行现在实行的排 队方法是否合理？你是否有办法在现有 窗口的情况下提高整个系统的效率？ 数学建模作为用数学方法解决实际问题的 第一步，越来越受到人们的重视。 数学建模的一般步骤 实体 信息 求 解 假设建模 验证应用分析 数学模型的分类 分类标准具体类别 对某个实际问题 了解的深入程度 白箱模型、灰箱模型、黑箱模型 模型中变量的特 征 连续模型、离散模型；确定性模型、随 机性模型；静态模型、动态模型等 建模中所用的数 学方法 初等模型、微分方程模型、差分方程模 型、统计回归模型、数学规划模型等 研究课题的实际 范畴 人口模型、生态系统模型、交通流模型 、经济模型、基因模型等 建模的目的 描述模型、预报模型、优化模型、决策 模型、控制模型等 能力的培养 n能力上的锻炼 Google n创新的能力 观察能力 分析能力 n在尽可能短的时间内查到并学会你想应 用的知识的本领 图书馆 归纳能力 数据处理能力 一些简单的实例 n例1. 某人第一天由A地去B地，第二天 由B地沿原路返回A地。问：在什么条 件下，可以保证途中至少存在一地，此 人在两天中的同一时间到达该地。 分析：假如我们换一种想法，把第二天的返回改变成另 一人在同一天由B去A，问题就化为：在什么条件下，两 人至少在途中相遇一次？易得：只要任何一人的到达时 间晚于另一人的出发时间，两人必会在途中相遇。 例2：椅子放稳问题 把椅子往不平的地面上一放，通常只 有 ，放不稳，然而只需稍微挪 动几次，就可以使 ，放稳 了。 四只脚同时着地 三只脚着地 模型假设： n椅子四条腿一样长，椅脚与地面接触 处可视为一个点，四脚的连线呈正方 形。 n地面可视为数学上的连续曲面。 n椅子在任何位置至少有三只脚同时着 地。 建模： n设椅子的四只脚位于点 其连线构 成一正方形，对角线的交点为坐标原点，对 角线 为坐标轴（坐标系如图所示） 。 D A C B O C B A D y x 设 为 两点椅子的脚离开地面的距离 之和； 为 两点的 椅子的脚离开地面的距 离之和，则由条件得： 注意到： 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图解法 0 123 1 2 3 y x 状态s=(x,y)：16个格点 允许状态： 10个 点 允许决策： 移动1或2格； k奇，左下移； k偶，右上移。 s1 sn+1 d1 d11 d1,d11给出安全渡河方案 评注和思考 n规格化方法，易于推广 n考虑4名商人各带一随从的情况 例4 n某人平时下班总是按预定时间到达某处 ，然后他妻子开车接他回家。有一天， 他比平时提早了三十分钟到达该处，于 是此人就沿着妻子来接他的方向步行回 去并在途中遇到了妻子。这一天，他比 平时提前了十分钟到家，问此人共步行 了多长时间？ 分析 n提前的十分钟时间从何而来？ 会合点相遇点家 5分钟 5:305:35 n由相遇点到会合点需开几分钟？ n相遇时他已步行了多少分钟？ n请思考：本题解答中隐含了哪些假设条 件？ 预备技能 n数学知识 分析、代数、几何、概率、统计、优化、 方程 n软件使用 Matlab, Mathematica, Maple, Lindo, Lingo n编程：C/C+ 第二部分 数学规划模型 数学规划的一般模型 n min f (x) s.t. hi(x)=0, i=1, , m gp(x)0, p=1, , t nf(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, , t n若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, , t n若f(x), hi(x)( i=1, , m), gp(x)( p=1, , t) 中至少有一个是非线性函数，问题(MP) 就被称为非线性规划问题。 (MP) 数学规划模型 n线性规划问题： min z=c x s.t. Ax=b x0 n若要求变量 x 取整数值时，则称之为整 数规划； n若变量只取0或1时，则称之为0-1规划； n若只要求部分变量取整数值，则称之为 混合整数规划。 例1 奶制品的生产和销售 n每天有50桶牛奶供应 试制订生产计划，使每天获利最大 1桶 牛奶 3公斤A1 甲：12小时 获利24元/公斤 4公斤A2 乙：8小时 获利16元/公斤 n每天正式工人总的劳动时间为480小时 n设备甲每天至多能加工100公斤A1 n设备乙的加工能力没有限制 x1,x2 =0 n决策变量 ： 1桶 牛奶 3公斤A1 甲：12小时 获利24元/公斤 4公斤A2 乙：8小时 获利16元/公斤 获利 243x1 获利 164 x2 x1桶牛奶生产A1, x2桶牛奶生产A2 n目标函数 ： Max z=72x1+64 x2 线性 规划 模型 (LP) n约束条件 ： 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 x1D 0 z=0 z=2400 z=3360 模型求解方法 n为此求解方程 n容易得到该方程的解为 x=(20, 30)T 在B(20,30)点得到最优解 模型求解方法 n基本思想：从可行域的一个顶点（基本 可行解）出发，转换到另一个顶点，并 且使目标函数值逐步减小，有限步后可 得到最优解。 n单纯形算法不是多项式时间算法 n单纯形算法 模型求解 n单纯形算法 n利用计算机软件 lingo, lindo n椭球算法、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千克 B1 2小时,3元 1千克 获利44元/千克 0.75千克 B2 2小时,3元 1千克 获利32元/千克 出售x1 千克 A1, x2 千克 A2， X3千克 B1, x4千克 B2 原料 供应 劳动 时间 加工能力 决策 变量 目标 函数 利润 约束 条件 非负约束 x5千克 A1加工B1， x6千克 A2加工B2 附加约束 例2 指派问题 n某生产车间有四位工人，现要安排他们分别完成 四项工作，每人做每项工作所消耗的时间如下： A B C D 15 18 21 24 甲 乙 丙 丁 19 23 22 18 26 17 16 19 19 21 23 17 n请问安排哪位工人完成哪项工作，可使总的消耗 工时最少？ 工人 工作 模型求解 n整数规划的算法 n匈牙利算法 例3 生猪的出售时机 n饲养场每天投入4元资金，用于饲料、人力 、设备，估计可使80千克重的生猪体重增 加2公斤。 n市场价格目前为每千克8元，但是预测每天 会降