数学建模规划模型讲解.ppt
《数学建模规划模型讲解.ppt》由会员分享,可在线阅读,更多相关《数学建模规划模型讲解.ppt(71页珍藏版)》请在三一文库上搜索。
1、主讲人:穆学文,西安电子科技大学数学系 Email:,数学建模讲义,最优化模型 -线性规划,参考书目,1. 陈宝林。最优化理论与算法。清华大学出版社. 2. 谢金星,薛毅。优化建模与lindo/lingo优化软件. 清华大学出版社.,背景知识,运筹学理论的一部分 最早起源于中国古代 公元前6世纪孙武所著的孙子兵法 孙膑“斗马术”,田忌与齐王赛马,博弈论 运筹帷幄之中,决胜千里之外”。这千古名句也 可以说是对张良运筹思想的赞颂和褒奖。 国外起源与发展 1738年,D.Bernoulli首次提出了效用的概念,并以此作为决策的标准。,1896年,V.Pareto首次从数学角度提出多目标优化问题,引进
2、了Pareto最优的概念。 丹麦电话工程师A.K.Erlang开展了关于电话局中继线数目的话务理论的研究,1909年发表了他将概率论应用于电话话务理论的研究论文:“概率论与电话会话”,开排队论研究的先河。 1935-38年,英国为了正确地运用新研制的雷达系统来对付德国飞机的空袭,在皇家空军中组织了一批科学家,进行新战术试验和战术效率评价的研究,并取得了满意的效果。他们把自己从事的这种工作命名为“Operational Research”(运筹学,或直译为作战研究)。 1939年,苏联的. 总结了他对生产组织的研究,写了生产组织与计划中的数学方法一书,是线性规划应用于工业生产问题的经典著作,背景
3、知识(续),1947年,G.B.Dantzig提出了单纯形方法后,线性规划便迅速形成为一个独立的分支。 并逐级发展起来。 英国运筹学会1948年成立(1948-53年是运筹学俱乐部,1953年11月起改名为学会)。 。 二次大战胜利后,美英各国不但在军事部门继续保留了运筹学的研究核心,而且在研究人员、组织的配备及研究范围和水平上,都得到了进一步的扩大和发展,同时运筹学方法也向政府和工业等部门扩展。 1951年出版了新版(1946年的原版是保密的,1948年才撤销保密)的P.M.Morse和G.E.Kimball的运筹学方法(Methods of Operations Research),这是二
4、战结束后,对战时整个运筹学工作做系统的专业叙述的一本著作。 1951年,H.W.Kuhn与A.W.Tucker提出了Kuhn-Tucker条件,标志着非线性规划理论的初步形成。,背景知识(续),1952年5月美国运筹学会成立,并创刊Operations Research。 1953年,R.Bellman提出动态规划的名称,并阐述了最优化原理。 1954年,D.R.Dantzig等研究旅行推销员问题时提出了分解的思想,成为整数规划中两大方法割平面法与分枝定界法的萌芽。 1955年,G.Dantzig首先考虑出现随机变量的线性规划问题,这是最早提出的随机规划中的有补偿二阶段问题。 1956年, L
5、.R.Ford,Jr.与 D.R.Fulkerson提出并解决了网络最大流问题,加强了图论与线性规划的联系,促进了优化理论的研究。,背景知识(续),1959年1月1日,国际运筹学会联合会(1FORS)正式宣告成立,当时的联合会只包括英、美、法三个国家的运筹学会,首任(1959-61年)主席(当时称为秘书,到1968年第四届时才改称主席)为英国的Charles Goodeve。,背景知识(续),运筹学理论在中国的研究与发展 1957年,经中国科学院力学研究所所长钱学森的倡导,在该所成立了由许国志领导的国内第一个运筹学研究组(后成室)。刘源张、周华章、桂湘云等是该组最早的一批研究人员,从此在我国开
6、始了现代运筹学的研究。当年秋季,又有大学毕业生顾基发、董泽清、徐映波、陈锡康、郭绍僖、李秉全等分配进入该组。 1958年,中国科学院数学研究所所长华罗庚率领广大研究人员,包括吴文俊、越民义、万哲先、王元等在内,也开展了运筹学应用课题的研究,并影响和带动了全国范围内各部门、各高校的运筹学应用和推广工作。运输和农业等部门的“图上作业法”、“打麦场设计”、“中国邮递员问题”是典型的成果。,背景知识(续),1959年2月,山东大学在数学系中设置了国内最早的一个运筹学专门化,由谢力同与郑汉鼎执教。自当年暑假开始,每年都有运筹学方向的学生毕业,为我国运筹学事业的发展作出了重要贡献。 1959年,中国科学院
7、数学研究所成立了运筹学研究室,研究人员都由所内其它室组调入。孙克定任研究室主任,该室最早的一批研究人员有排队论组的越民义、吴方、徐光煇、韩继业;对策论组的吴文俊、江加禾、施闺芳;数学规划组的朱永津、应玫茜、马仲蕃、凌开诚等。与此同时,全国范围内很多高校也有大批教师转入运筹学领域。,背景知识(续),1965年起,华罗庚和他的小分队在全国工业部门开始普及推广统筹法的群众运动。在此后的二十年中,为普及推广双法(统筹法与从1970年开始普及推广的优选法),他们走访了全国23个省市中几百个城市的几千个工厂,并向数百万人开设讲座开展工作,取得了巨大的社会效益和经济效益。 1965年华罗庚统筹方法平话及其补
8、充一书由中国工业出版社出版。 1970年起,华罗庚和他的小分队开始在全国范围内普及推广优选法的群众运动。从此,统筹与优选双法变得家喻户晓,双法的普及推广也取得了极为可观的社会、经济效益。 1971年华罗庚优选法平话及其补充一书由国防工业出版社出版。,背景知识(续),1980年4月22-26日在山东济南,召开了中国数学会运筹学会成立暨第一届代表大会。中国运筹学倡导者之一,中国科学院副院长华罗庚主持了会议,有来自各地科研机构、高等院校、军事部门、工交企业等有关单位的82名代表出席。华罗庚在大会开幕式与闭幕式上均发表了讲话,回顾了他在全国范围普及推广“双法”的经验和成果,勉励大家以克敌攻坚的进取精神
9、积极开展运筹学研究。会议作了12个专题学术报告和个人成果的几十个分组报告。中国数学会理事长华罗庚被推选兼任运筹学会理事长,越民义、许国志、余潜修为副理事长,桂湘云为秘书长,推选常务理事11名,理事42名。会议决定学会挂靠在中科院应用数学所,背景知识(续),优化模型应用的广泛性,1. 系统分析,即生产计划和经营决策中的优化问题。例如: 合理计划生产:运输,分配,布局,选址,指派,下料、配料等优化问题(linear programming); 合理开发(或配置)资源:可再生资源的持续开发,不可再生资源的优化配置(linear programming) 合理运行设备:设备的最有运行(维修)方案. 合
10、理组合投资:追求最大受益、最小风险的投资组合方案(Multiobjective programming),2. 工程设计和控制中的非线性分析 (Non-linear programming and optimal control) 例如: 结构系统最优设计(人字架设计) 机械零件或部件的最优化设计(轮轴颈,凸轮设计) 化工设备最优设计(单件或连锁设备优化设计) 电力网络和水力网络的优化设计(平衡条件),历届数模竞赛所涉及的优化问题:,94年 A题 逢山开路(工程设计优化问题) 目标:工程造价最低 决策:在若干约束下选择一条最佳线路 95年 B题:天车调度问题(生产操作优化问题) 目标:年钢产量
11、最大 决策:天车调度的最优方案设计 96年 A题:最优捕鱼策略(开发资源优化问题) 目标:可持续捕捞的努力量及最大捕捞量 决策:在平衡条件下确定五年内最佳捕捞方案,97年 A题:零件参数设计(产品参数优化设计) 目标:产品总造价最低(产品质量损失费用 零件制造成本费用) 决策:零件参数的最佳水平组合方案 98年 A题:组合投资问题(风险决策优化问题) 目标(二目标):收益最大,风险最小 决策:组合投资方案 99年 A题:自动化车床管理(排队-更新问题) 目标:生产工序的效益(费用最低)最大 决策:最佳检验间隔河刀具更换策略,99年 B题:钻井布局问题(生产计划优化问题) 目标:最大限度利用初步
12、、勘探时的旧井数 决策:在规定精度的前提下确定系统勘探时的最 佳网络分布 2002年 A题:车灯线光源的优化设计 目标:线光源的功率最小 决策:在满足设计规范的条件下,计算线光源的长度 B题:彩票中的数学 目标:最大限度地吸引彩民积极购买彩票 决策:在保证彩民和彩票公司的利益上如何设置最佳彩票方案,04年 A题:奥运会场馆周围超市设计 目标:经济效益最大化,各个区域的平衡问题 05年 B题:DVD在线租赁 目标:满足顾客的需要,经济效益最大化 06年 A题:出版社书号分配问题 目标:经济效益最大化,不同学科书号的平衡问题 07年 B题:北京公交线路设计 目标:时间最小化,车票钱最小化,转站最小
13、化 08年 A题:中国学费的评价系统 目标:经济效益最大化,考虑到老百姓的支付能力 09年 医院眼科病人的等待系统 目标:提高病床的周转率,降低病人的抱怨程度,优化模型的一般形式,x:决策变量,f(x):目标函数,gi(x)0:约束条件,可行解:满足约束条件的解 最优解:取得最值的可行解 次优解:一个较满意的可行解 可行集(域):所有可行解组成的集合,,最优化问题至少有两要素:一是可能的方案;二是要追求的目标。后者是前者的函数。如果第一要素与时间无关就称为静态最优化问题,否则称为动态最优化问题。,建立最优化问题数学模型的三要素: (1)决策变量和参数。决策变量是由数学模型的解确定的未知数。参数
14、表示系统的控制变量,有确定性的也有随机性的。 (2)约束或限制条件。 由于现实系统的客观物质条件限制,模型必须包括把决策变量限制在它们可行值之内的约束条件,而这通常是用约束的数学函数形式来表示的。,一般的模型简化工作包括以下几类: (1)将离散变量转化为连续变量。 (2)将非线性函数线性化。 (3)删除一些非主要约束条件。,(3)目标函数。这是作为系统决策变量的一个数学函数来衡量系统的效率,即系统追求的目标。,线性规划(LP) 非线性规划(NLP) 整数规划(IP),主要内容,线性规划,1、概念和实例。 2、线性规划模型 3、线性规划的性质。 4、线性规划的主要算法。 5、用数学软件包求解线性
15、规划问题 6、建模案例选讲:投资的收益与风险,线性规划:就是一个线性函数在线性等式或不等式约束条件下的极值问题。 线性规划研究的问题主要有两类: 1、任务确定后,如何统筹安排,尽量做到用尽量少的人力和物力资源来完成任务; 2、有一定量的人力、物力资源,如何安排使用他们,使完成的任务(创造的利润)最多。 在生产管理和经济活动中经常提出这样一类问题, 即如何合理地利用有限的人力、物力、财力等资源,以便得到最好的经济效果。,线性规划的数学模型有三要素,从实际问题提炼成数学模型时,首先寻找需求解的未知量xj (j=1,n),然后列举三要素: 列写与自变量(未知量)有关的若干个线性约束条件(等式或不等式
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 规划 模型 讲解
链接地址:https://www.31doc.com/p-2156554.html