数学建模优化模型

数学建模-------优化模型第二讲线性规划建模方法第三讲整数规划建模方法第四讲指派问题第六讲图论简介第五讲动态规划建模第一讲数学建模概论第一章数学建模概论1.1数学建模由来1.2从现实对象到数学模型1.3数学建模的重要意义1.4数学建模的方法和步骤1.5数学模型的特点和分类1.6近几年国内竞赛题1.7怎样学习数学建模与竞赛组队1.8撰写数学建模论文•1985年由美国工业与应用数学学会和美国运筹学会联合主办大学生数学建模竞赛（MCM)1.1数学建模由来•在上世纪70年代末和80年代初，英国著名的剑桥大学专门为研究生开设了数学建模课程•数学建模作为一门崭新的课程在20世纪80年代进入我国高校，萧树铁先生1983年在清华大学首次为本科生讲授数学模型课程，他是我国高校开设数学模型课程的创始人•1992年由中国工业与应用数学学会举办全国大学生数学建模竞赛（94年起由国家教委高教司和中国工业与应用数学学会共同举办）•1987年由姜启源教授编写了我国第一本数学建模教材•2005年全国数学建模竞赛，共有来自全国30个省、市、自治区的795所高校8492支队（其中甲组6556队、乙组1936队）、25476名来自各个专业的大学生参加本次竞赛•95年我校参加全国大学生数学建模竞赛，最初开设选修课是因为参加数学建模竞赛的需要，选修的学生数较少，而且必须是往年成绩较优的学生才允许选修•97年学校决定在原有基础上，在部分专业开设数学建模必修课，并同时对其他专业开设数学建模选修课•2000年起结合课程教学与竞赛安排，在每年五月底或六月初举办全校大学生数学建模竞赛•近两年数学建模课程每年选课人数2000余人•1995-2009年学生参加全国大学生数学建模竟赛及获奖情况：年份参赛全国全国省一等奖省二等奖省三等奖队数一等奖二等奖19953111119964111119977222111998742611999712312000101332200110213220021512351200315233362004161324420052241383200628192007302520083237200933182006年获一等奖1队，二等奖3队2007年获一等奖1队，二等奖5队2008年获一等奖4队，二等奖4队2009年获一等奖2队，二等奖2队•2006-2009年学生参加美国大学生数学建模竟赛及获奖情况：玩具、照片、飞机、火箭模型……~实物模型地图、电路图、分子结构图……~符号模型模型是为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物模型集中反映了原型中人们需要的那一部分特征1.2从现实对象到数学模型我们常见的模型你碰到过的数学模型——“航行问题”用x表示船速，y表示水速，列出方程：75050)(75030)(yxyx答：船速每小时20千米/小时.甲乙两地相距750千米，船从甲到乙顺水航行需30小时，从乙到甲逆水航行需50小时，问船的速度是多少?x=20y=5求解航行问题建立数学模型的基本步骤•作出简化假设（船速、水速为常数）；•用符号表示有关量（x,y表示船速和水速）；•用物理定律（匀速运动的距离等于速度乘以时间）列出数学式子（二元一次方程）；•求解得到数学解答（x=20,y=5）；•回答原问题（船速每小时20千米/小时）。数学模型(MathematicalModel)和数学建模（MathematicalModeling)对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。建立数学模型的全过程（包括表述、求解、解释、检验等）数学模型数学建模1.3数学建模的重要意义•电子计算机的出现及飞速发展；•数学以空前的广度和深度向一切领域渗透。数学建模作为用数学方法解决实际问题的第一步，越来越受到人们的重视。•在一般工程技术领域数学建模仍然大有用武之地；•在高新技术领域数学建模几乎是必不可少的工具；•数学进入一些新领域，为数学建模开辟了许多处女地。数学建模的具体应用•分析与设计•预报与决策•控制与优化•规划与管理数学建模计算机技术知识经济如虎添翼数学建模的基本方法•机理分析•测试分析根据对客观事物特性的认识，找出反映内部机理的数量规律将对象看作“黑箱”,通过对量测数据的统计分析，找出与数据拟合最好的模型机理分析没有统一的方法，主要通过实例研究(CaseStudies)来学习。以下建模主要指机理分析。•二者结合用机理分析建立模型结构,用测试分析确定模型参数1.4数学建模的方法和步骤数学建模的一般步骤模型准备模型假设模型构成模型求解模型分析模型检验模型应用模型准备了解实际背景明确建模目的搜集有关信息掌握对象特征形成一个比较清晰的‘问题’模型假设针对问题特点和建模目的作出合理的、简化的假设在合理与简化之间作出折中模型构成用数学的语言、符号描述问题发挥想像力使用类比法尽量采用简单的数学工具数学建模的一般步骤模型求解各种数学方法、软件和计算机技术如结果的误差分析、统计分析、模型对数据的稳定性分析模型分析模型检验与实际现象、数据比较，检验模型的合理性、适用性模型应用数学建模的一般步骤数学建模的全过程现实对象的信息数学模型现实对象的解答数学模型的解答表述求解解释验证(归纳)(演绎)表述求解解释验证根据建模目的和信息将实际问题“翻译”成数学问题选择适当的数学方法求得数学模型的解答将数学语言表述的解答“翻译”回实际对象用现实对象的信息检验得到的解答实践现实世界数学世界理论实践1.5数学模型的特点和分类模型的逼真性和可行性模型的渐进性模型的稳定性模型的可转移性模型的非预制性模型的条理性模型的技艺性模型的局限性数学模型的特点数学模型的分类应用领域人口、交通、经济、生态……数学方法初等数学、微分方程、规划、统计……表现特性描述、优化、预报、决策……建模目的了解程度白箱灰箱黑箱确定和随机静态和动态线性和非线性离散和连续1.6近几年全国大学生数学建模竞赛题A农作物施肥效果分析1992B实验数据分解A交调频率设计1993B足球比赛的排名问题A逢山开路1994B锁具装箱A一个飞行管理问题1995B天车与冶炼炉的作业调度A节水洗衣机问题1996B最优捕鱼问题A零件的参数设计1997B最优截断切割问题A投资的收益和风险1998B灾情巡视路线A自动化车床管理1999B钻井布局ADNA序列分类2000B钢管订购和运输A血管的三维重建2001B公交车调度A车灯线光源的优化设计2002B彩票中的数学ASARS的传播2003B露天矿生产的车辆安排A奥运会临时超市网点设计2004B电力市场的输电阻塞管理A长江水质的评价和预测2005BDVD在线租赁A出版社的资源配置2006B艾滋病疗法的评价及疗效的预测A中国人口增长预测2007B乘公交，看奥运A数码相机定位2008B高等教育学费标准探讨A制动器试验台的控制方法分析2009B眼科病床的合理安排1.7怎样学习数学建模与竞赛组队数学建模与其说是一门技术，不如说是一门艺术技术大致有章可循艺术无法归纳成普遍适用的准则想像力洞察力判断力•学习、分析、评价、改进别人作过的模型•亲自动手，认真作几个实际题目根据数学建模竞赛章程，三人组成一队。这三人中必须一人数学基础较好，一人应用数学软件（如Matlab,lindo,maple等）和编程（如c,Matlab,vc++等）的能力较强，一人科技论文写作的水平较好。•科技论文的写作要求整篇论文的结构严谨，语言要有逻辑性，用词要准确。•三人之间要能够配合得起来。若三人之间配合不好，会降低效率，导致整个建模的失败。•如果可能的话，最好是数学好的懂得编程的一些知识，编程好的了解建模，搞论文写作也要了解建模，这样会合作得更好。因为数学好的在建立模型方案时会考虑到编程的便利性，以利于编程；编程好的能够很好地理解模型，论文写作的能够更好、更完全地阐述模型。否则会出现建立的模型不利于编程，程序不能完全概括模型，论文写作时会漏掉一些不经意的东西。•在合作的过程中，最好是能够在三人中找出一个所谓的组长，即要能够总揽全局，包括任务的分配，相互间的合作和进度的安排。•在建模过程中出现意见不统一——如何处理？仅我个人的经验而言，除了一般的理解与尊重外，我觉得最重要的一点就是“给我一个相信你的理由”和“相信我，我的理由是……”，不要作无谓的争论。1.8撰写数学建模论文1、摘要:问题、模型、方法、结果2、问题重述3、模型假设与记号4、分析与建立模型5、模型求解6、模型检验7、模型推广8、参考文献9、附录第二讲线性规划建模方法一、从现实问题到线性规划模型二、线性规划模型的求解三、线性规划建模实例四、线性规划的对偶问题例1加工奶制品的生产计划1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1制订生产计划，使每天获利最大•35元可买到1桶牛奶，买吗？若买，每天最多买多少?•可聘用临时工人，付出的工资最多是每小时几元?•A1的获利增加到30元/公斤，应否改变生产计划？每天:一、从现实问题到线性规划模型1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤x1桶牛奶生产A1x2桶牛奶生产A2获利24×3x1获利16×4x2原料供应5021xx劳动时间48081221xx加工能力10031x决策变量目标函数216472xxzMax每天获利约束条件非负约束0,21xx线性规划模型(LP)时间480小时至多加工100公斤A150桶牛奶每天模型分析与假设比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型A1A2现有资源设备128台时甲4016公斤乙0412公斤利润2030（元）制订生产计划,使每天获利最大例2工厂生产两种产品A1,A2,已知生产单位产品情况如表：设生产A1、A2分别x1、x2公斤maxz=20x1+30x2(1)1212121228,(2)4016,(3)..0412,(4)0,0.(5)xxxxstxxxx目标函数约束条件决策变量一、从现实问题到线性规划模型线性规划模型标准型:maxz=c1x1+c2x2+…+cnxn11112211211222221122,,..,0,1,,.nnnnmmmnnmiaxaxaxbaxaxaxbstaxaxaxbxin(LP)线性规划模型标准型矩阵表示：maxz=cx..,0stAXbX12[,,,],ncccc12[,,,],Tmbbbb12[,,,],TnXxxx[].ijmnAa0,bmax(min)z=c1x1+c2x2+…+cnxn1111221121122222112211(,),(,),..(,),0,0,,,,,,.nnnnmmmnnmijklaxaxaxbaxaxaxbstaxaxaxbxxiiijjj线性规划模型一般形式：1.线性规划的一般形化为标准型一般步骤(1)Minz=cx转化为maxz’=-cx(2)1122iiinnaxaxaxib加松弛变量yi1122iiinniiaxaxaxyb1122iiinnaxaxax(3)ib加剩余变量yi1122iiinniiaxaxaxyb(4)若存在可正可负变量xi令12,iiixxx12,0.iixxmaxz=20x1+30x2(1)1212121228,(2)4016,(3)..