《数学建模优化080420》由会员分享，可在线阅读，更多相关《数学建模优化080420（226页珍藏版）》请在金锄头文库上搜索。
1、数学建模,-优化模型,第二讲 线性规划建模方法,第三讲 整数规划建模方法,第四讲 指派问题,第六讲 图论简介,第五讲 动态规划建模,第一讲 数学建模概论,第一章 数学建模概论,1.1 数学建模由来 1.2 从现实对象到数学模型 1.3 数学建模的重要意义 1.4 数学建模的方法和步骤 1.5 数学模型的特点和分类 1.6 近几年国内竞赛题 1.7 怎样学习数学建模与竞赛组队 1.8 撰写数学建模论文,1985年由美国工业与应用数学学会和美国运筹 学会联合主办大学生数学建模竞赛（ MCM ),1.1 数学建模由来, 在上世纪70年代末和80年代初，英国著名的剑 桥大学专门为研究生开设了数学建模课
2、程, 数学建模作为一门崭新的课程在20世纪80年代 进入我国高校，萧树铁先生1983年在清华大学首次为本科生讲授数学模型课程，他是我国高校开设数学模型课程的创始人,玩具、照片、飞机、火箭模型 , 实物模型,地图、电路图、分子结构图 , 符号模型,模型是为了一定目的，对客观事物的一部分 进行简缩、抽象、提炼出来的原型的替代物,模型集中反映了原型中人们需要的那一部分特征,1.2 从现实对象到数学模型,我们常见的模型,你碰到过的数学模型“航行问题”,用 x 表示船速，y 表示水速，列出方程：,答：船速每小时20千米/小时.,甲乙两地相距750千米，船从甲到乙顺水航行需30小时， 从乙到甲逆水航行需5
3、0小时，问船的速度是多少?,x =20 y =5,航行问题建立数学模型的基本步骤,作出简化假设（船速、水速为常数）；,用符号表示有关量（x, y表示船速和水速）；,用物理定律（匀速运动的距离等于速度乘以 时间）列出数学式子（二元一次方程）；,求解得到数学解答（x=20, y=5）；,回答原问题（船速每小时20千米/小时）。,数学模型 (Mathematical Model) 和 数学建模（Mathematical Modeling),对于一个现实对象，为了一个特定目的， 根据其内在规律，作出必要的简化假设， 运用适当的数学工具，得到的一个数学结构。,建立数学模型的全过程 （包括表述、求解、解释
4、、检验等）,数学模型,数学建模,1.3 数学建模的重要意义,电子计算机的出现及飞速发展；,数学以空前的广度和深度向一切领域渗透。,数学建模作为用数学方法解决实际问题的第一步， 越来越受到人们的重视。,在一般工程技术领域数学建模仍然大有用武之地；,在高新技术领域数学建模几乎是必不可少的工具；,数学进入一些新领域，为数学建模开辟了许多处女地。,数学建模的具体应用,分析与设计,预报与决策,控制与优化,规划与管理,数学建模,计算机技术,知识经济,数学建模的基本方法,机理分析,测试分析,根据对客观事物特性的认识， 找出反映内部机理的数量规律,将对象看作“黑箱”,通过对量测数据的 统计分析，找出与数据拟合
5、最好的模型,机理分析没有统一的方法，主要通过实例研究 (Case Studies)来学习。以下建模主要指机理分析。,二者结合,用机理分析建立模型结构, 用测试分析确定模型参数,1.4 数学建模的方法和步骤,数学建模的一般步骤,模 型 准 备,了解实际背景,明确建模目的,搜集有关信息,掌握对象特征,形成一个 比较清晰 的问题,模 型 假 设,针对问题特点和建模目的,作出合理的、简化的假设,在合理与简化之间作出折中,模 型 构 成,用数学的语言、符号描述问题,发挥想像力,使用类比法,尽量采用简单的数学工具,数学建模的一般步骤,模型 求解,各种数学方法、软件和计算机技术,如结果的误差分析、统计分析、
6、 模型对数据的稳定性分析,模型 分析,模型 检验,与实际现象、数据比较， 检验模型的合理性、适用性,模型应用,数学建模的一般步骤,数学建模的全过程,现实对象的信息,数学模型,现实对象的解答,数学模型的解答,(归纳),(演绎),表述,求解,解释,验证,根据建模目的和信息将实际问题“翻译”成数学问题,选择适当的数学方法求得数学模型的解答,将数学语言表述的解答“翻译”回实际对象,用现实对象的信息检验得到的解答,实践,现实世界,数学世界,1.6 近几年全国大学生数学建模竞赛题,1.7 怎样学习数学建模与竞赛组队,数学建模与其说是一门技术，不如说是一门艺术,技术大致有章可循,艺术无法归纳成普遍适用的准则
7、,想像力,洞察力,判断力,学习、分析、评价、改进别人作过的模型,亲自动手，认真作几个实际题目,根据数学建模竞赛章程，三人组成一队。,这三人中必须一人数学基础较好，,一人应用数学软件（如Matlab,lindo,maple等） 和编程（如c,Matlab,vc+等）的能力较强，,一人科技论文写作的水平较好。,科技论文的写作要求整篇论文的结构严谨，语言要有逻辑性，用词要准确。, 三人之间要能够配合得起来。若三人之间配合不好， 会降低效率，导致整个建模的失败。, 如果可能的话，最好是数学好的懂得编程的一些知识，编程好的了解建模，搞论文写作也要了解建模，这样会合作得更好。因为数学好的在建立模型方案时会
8、考虑到编程的便利性，以利于编程；编程好的能够很好地理解模型，论文写作的能够更好、更完全地阐述模型。否则会出现建立的模型不利于编程，程序不能完全概括模型，论文写作时会漏掉一些不经意的东西。,在合作的过程中，最好是能够在三人中找出一个所谓的组长，即要能够总揽全局，包括任务的分配，相互间的合作和进度的安排。,在建模过程中出现意见不统一如何处理？仅我个人的经验而言，除了一般的理解与尊重外，我觉得最重要的一点就是“给我一个相信你的理由”和“相信我，我的理由是”，不要作无谓的争论。,1.8 撰写数学建模论文,1、摘要:问题、模型、方法、结果,2、问题重述,3、模型假设与记号,4、分析与建立模型,5、模型求
9、解,6、模型检验,7、模型推广,8、参考文献,9、附录,第二讲 线性规划建模方法,一、从现实问题到线性规划模型,二、线性规划模型的求解,三、线性规划建模实例,四、线性规划的对偶问题,例1 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天:,一、从现实问题到线性规划模型,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目
10、标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,模型分析与假设,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,A1,A2每公斤的获利是与各自产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数,加工A1,A2的牛奶桶数是实数,线性规划模型,制订生产计划,使每天获利
11、最大,例2工厂生产两种产品A1,A2,已知生产单位产品情况如表：,设生产A1、A2分别x1、x2公斤,max z= 20x1+30x2 (1),目标函数,约 束 条 件,决策变量,一、从现实问题到线性规划模型,线性规划模型标准型:,maxz= c1 x1 +c2x2 +cnxn,(LP),线性规划模型标准型矩阵表示：,max z= c x,max(min) z= c1 x1 +c2x2 +cnxn,线性规划模型一般形式：,1.线性规划的一般形化为标准型 一般步骤,(1) Min z= cx 转化为max z =-cx,(2),加松弛变量yi,(3),加剩余变量yi,(4) 若存在可正可负变量x
12、i 令,max z= 20x1+30x2 (1),标准型,(1), x1 +2x2 +x3 =8,(2), 4 x1 +0 x2 +x4 =16,(3), 0x1 +4x2 +x5 =12,max z= 20x1+30x2,x1 +2x2 +x3 =8 4 x1 +0 x2 +x4 =16 0x1 +4x2 +x5 =12 x1 ,x2 ,x3 ,x4 ,x5,s.t,例 将下述线性规划问题化为标准型,Min z= - x1 +2x2 -3x3,无约束,标准型,max z = x1 -2x2 +3(x4 x5 )+0 x6 +0x7,(1), x3 = x4 -x5 , x4 ,x5,(2),
13、 x1 +x2 +x3 +x6 =7,(3), x1 -x2 +x3 -x7 =2,合理下料问题,有长度为8米的某型号圆钢，现需要长度为2.5米的毛坯100根，长度为1.3米的毛坯200根，如何选者下料方式，所需总用料最省？,解：可能的下料方式：,设按第i种下料方式的圆钢xi根，i=1,2,3,4,min z= x1+x2 +x3 +x4,有一组决策变量,约束条件是决策变量的线性等式或不等式,目标函数是决策变量的线性函数,这样的规划问题称为线性规划.记为（LP）,例.某小区一个24小时营业便利店,一天各时段所需服务员最少人数如下表.根据实际情况,要求每个服务员必须连续工作八小时,试建立需服务员
14、总人数最少的排班方案数学模型.,解：设各班次新增服务员数分别为x1,x2, x3, x4, x5, x6,则,min z= x1+x2+ x3+x4+x5+x6,且xi为整数,连续投资问题,某部门计划5年内用一百万投资下列项目： A：从第一年到第四年初需投资，此年末回收本利115% B: 第三年初需投资，第五年末回收本利125%，投资额40万 C:第二年初需投资，第五年末回收本利140%，投资额30万 D：每年初可购买公债，当年末归还，利息6% 如何投资，五年后获利最大？,解：设第i年初投资项目A,B,C,D分别为xiA , xiB , xiC , xiD 万元,i=1,2,3,4,5,x1A
15、+x1D=100,x2A+x2C+x2D=1.06 x1D ,x3A+x3B+x3D=1.06 x2D+1.15 x1A,x4A+x4D=1.06 x3D+1.15 x2A,x5D=1.06 x4D+1.15 x3A,x2C 40, x3B 30,xiA , xiB , xiC , xiD0 i=1,2,3,4,5.,Max Z= 1.15x4A +1.40x2C +1.25x3B +1.06 x5D,s.t.,二、线性规划模型的求解,（一）图解法（n=3时）,（二）单纯形法,（三）数学软件：如LINDO软件,max z= c x,(LP),可行解：满足约束条件AX=b,X,最优解:可行解中使
16、目标最优的。即X*D,且任意XD, CX* CX,可行集：所有可行解的集合,的X的值,制订生产计划,使每天获利最大,工厂生产两种产品A1,A2,已知生产单位产品情况如下：,设生产A1、A2分别x1、x2公斤,max z= 20x1+30x2 (1),（一）图解法（n=3时）,(1)在平面上作出可行集,A,B,C,D,3,4,由图解法直观得:n=2时,(LP)的可行集是凸多边形,最优解可以在其某个顶点处达到.,线性规划基本性质:(LP)的可行集是凸多面体,最优解可以在凸多面体的某个顶点处达到.,线性规划求解思路:通过代数的方法描述高维空间凸多面体的顶点,再使用经济的方法来求出达到极值的顶点.,x1,x2,0,(2)在可行集中找最优解,max z= 20x1+30x2 (1),（二）单纯形法,1.基、基本可行解的概念(顶点的代数描述),2.单纯
