离散优化数学建模精选文档.ppt
《离散优化数学建模精选文档.ppt》由会员分享,可在线阅读,更多相关《离散优化数学建模精选文档.ppt(102页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、离散优化数学建模离散优化数学建模本讲稿第一页,共一百零二页2008年年B B题题 高等教育学费标准探讨高等教育学费标准探讨请你们根据中国国情,收集诸如国家生均拨款、培养费用、请你们根据中国国情,收集诸如国家生均拨款、培养费用、家庭收入等相关数据,并据此通过数学建模的方法,就几类家庭收入等相关数据,并据此通过数学建模的方法,就几类学校或专业的学费标准进行定量分析,得出明确、有说服力学校或专业的学费标准进行定量分析,得出明确、有说服力的结论。数据的收集和分析是你们建模分析的基础和重要组的结论。数据的收集和分析是你们建模分析的基础和重要组成部分。你们的论文必须观点鲜明、分析有据、结论明确。成部分。你
2、们的论文必须观点鲜明、分析有据、结论明确。最后,根据你们建模分析的结果,给有关部门写一份报告,最后,根据你们建模分析的结果,给有关部门写一份报告,提出具体建议。提出具体建议。本讲稿第二页,共一百零二页 3.试题向大规模数据处理方向发展试题向大规模数据处理方向发展:从从05年开始,基本上每年都有一大数据量的赛题;数据结构年开始,基本上每年都有一大数据量的赛题;数据结构的复杂性:数据的真实性,数据的海量性,数据的不完备性,的复杂性:数据的真实性,数据的海量性,数据的不完备性,数据的冗余性数据的冗余性 4.求解算法和各类现代算法的融合求解算法和各类现代算法的融合;如:;如:11B 5.实用性实用性:
3、问题和数据来自于实际,解决方法切合于实际,问题和数据来自于实际,解决方法切合于实际,模型和结果可以应用于实际。模型和结果可以应用于实际。6.即时性:即时性:国内外的大事,社会的热点,生活的焦点,近期国内外的大事,社会的热点,生活的焦点,近期发生和即将发生被关注的问题。发生和即将发生被关注的问题。本讲稿第三页,共一百零二页拿到赛题后大家需要思考的问题 题目属于哪种类型:连续的、离散的需要解决什么问题:最优化方案、预测模型、最短路径等等;将问题分解。可以用哪些相关模型、算法求解、需 要什么数学工具。本讲稿第四页,共一百零二页1、数学建模的过程、数学建模的过程(2)整个数学建模过程应当由三个阶段:整
4、个数学建模过程应当由三个阶段:1.建立模型:实际问题建立模型:实际问题数学问题;数学问题;2.数学解答:数学问题数学解答:数学问题数学解;数学解;3.模型检验:数学解模型检验:数学解实际问题的解决。实际问题的解决。(1)流程图流程图模型应用模型应用问题分析问题分析模型假设模型假设建立模型建立模型模型求解模型求解模型分析模型分析模型检验模型检验本讲稿第五页,共一百零二页 解决问题涉及到的计算软件分析解决问题涉及到的计算软件分析 重要的是参赛选手具备编程计算、计算机仿真、重要的是参赛选手具备编程计算、计算机仿真、模拟能力。模拟能力。赛题常用的计算软件:赛题常用的计算软件:Matlab,SPSSMa
5、tlab,SPSS,EXCEL等等本讲稿第六页,共一百零二页参考网站1 全国大学生数学建模竞赛网:全国大学生数学建模竞赛网:http:/2 数学中国网站数学中国网站 http:/3 中国数学建模网站:中国数学建模网站:http:/本讲稿第七页,共一百零二页 从问题的解决方法上分析从问题的解决方法上分析 涉及到的涉及到的数学建模方法数学建模方法:几何理论、组合概率、统计几何理论、组合概率、统计(回归回归)分析分析;优化方法(规划)、图论与网络优化、层次分析优化方法(规划)、图论与网络优化、层次分析;差分方法、微分方程、模糊数学、随机决策、多差分方法、微分方程、模糊数学、随机决策、多目标决策目标决
6、策;插值与拟合、灰色系统理论、神经网络、时间序插值与拟合、灰色系统理论、神经网络、时间序列列;综合评价、机理分析等方法综合评价、机理分析等方法;本讲稿第八页,共一百零二页 用的最多的方法是用的最多的方法是优化方法和概率统计优化方法和概率统计用用到到优优化化方方法法的的共共有有26个个题题,其其中中整整数数规规划划4个个,线性规划线性规划7个,非线性规划个,非线性规划14个个,多目标规划多目标规划6个个。用到用到概率统计概率统计方法的有方法的有21个题,平均每年至少有个题,平均每年至少有一个题目用到概率统计的方法。一个题目用到概率统计的方法。用到用到图论与网络优化图论与网络优化方法的问题有方法的
7、问题有6个;个;用到用到层次分析层次分析方法的问题有个;方法的问题有个;本讲稿第九页,共一百零二页 用到插值拟合的问题有用到插值拟合的问题有6个;个;用灰色系统理论的用灰色系统理论的4个个;用到时间序列分析的至少用到时间序列分析的至少2个个;用到综合评价方法的至少用到综合评价方法的至少3个;个;大部分题目都可以用两种以上的方法来解决大部分题目都可以用两种以上的方法来解决,即综即综合性较强的题目有合性较强的题目有26个个本讲稿第十页,共一百零二页最优化概论最优化概论从数学意义上说,最优化方法是一种求极值的方法,即在一组约束为等式或不等式的条件下,使系统的目标函数达到极值,即最大值或最小值。从经济
8、意义上说,是在一定的人力、物力和财力资源条件下,使经济效果达到最大(如产值、利润),或者在完成规定的生产或经济任务下,使投入的人力、物力和财力等资源为最少。本讲稿第十一页,共一百零二页一、最优化概念一、最优化概念所有类似的这种课题统称为最优化问题,研究解决这些问题的科学一般就总称之为最优化理论和方法另外也可用学术味更浓的名称:“运筹学”。由于最优化问题背景十分广泛,涉及的知识不尽相同,学科分枝很多,因此这个学科名下到底包含哪些分枝,其说法也不一致。比较公认的是:“规划论”(包括线性和非线性规划、整数规划、动态规划、多目标规划和随机规划等),“组合最优化”,“对策论”及“最优控制”等等。本讲稿第
9、十二页,共一百零二页数学建模竞赛中的优化问题数学建模竞赛中的优化问题2000B 钢管订购和运输问题 组合优化2001B 公交车优化调度图论2002B 彩票中的数学 决策分析2003B 露天矿生产的车辆安排问题 离散优化2004A 奥运会临时超市网点设计问题 图论2005B DVD在线租赁 离散优化2006A 出版社的资源配置问题 决策分析本讲稿第十三页,共一百零二页07B 乘公交,看奥运 图论 整数规划08B 高等教育学费探讨 层次分析法 多目标优化09B 眼科病床的合理安排动态规划10B 上海世博会经济影响力定量评估 决策分析11B 交巡警服务平台的设置与调度图论 多目标规划12B 太阳能小
10、屋的设计 离散优化13A 车道被占用对城市道路通行能力的影响 离散优化本讲稿第十四页,共一百零二页从数学上来看,所谓最优化问题可以概括为这样一种数学模型:给定一个“函数”,F(X),以及“自变量”X应满足的一定条件,求X为怎样的值时,F(X)取得其最大值或最小值。通常,称F(X)为“目标函数”,X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为:XD。求目标函数F(X)在约束条件XD下的最小值或最大值问题,就是一般最优问题的数学模型本讲稿第十五页,共一百零二页无约束最优化问题无约束最优化问题目标函数目标函数 二、最优化问题的一般形式二、最优化问题的一般形式约束最优化问题约束最优化问题
11、约束函数约束函数 最优解;最优值最优解;最优值本讲稿第十六页,共一百零二页三、最优化问题分类三、最优化问题分类分类分类1 1:无约束最优化无约束最优化 约束最优化约束最优化 非线性规划:非线性规划:目标函数与约束函数中至少有一个是变目标函数与约束函数中至少有一个是变量量x x的非线性函数;的非线性函数;线性规划:线性规划:目标函数与约束函数均为线性函数;目标函数与约束函数均为线性函数;分类分类2 2:线性规划线性规划 非线性规划非线性规划本讲稿第十七页,共一百零二页三、最优化问题分类三、最优化问题分类 分类分类3 3(根据决策变量、(根据决策变量、目标函数和要求不目标函数和要求不同)同)整数规
12、划整数规划动态规划动态规划网络规划网络规划随机规划随机规划多目标规划多目标规划本讲稿第十八页,共一百零二页三、最优化问题分类三、最优化问题分类函数最优化函数最优化组合最优化组合最优化分类分类函数最优化:函数最优化:决策变量是一定区间内的连续变量决策变量是一定区间内的连续变量 组合最优化:组合最优化:决策变量是离散状态,同时可行域是由决策变量是离散状态,同时可行域是由有限个点组成的集合有限个点组成的集合 本讲稿第十九页,共一百零二页最优化方法解决问题的步骤最优化方法解决问题的步骤最优化方法解决问题的步骤最优化方法解决问题的步骤(1)确定变量,写出目标函数和有关约束条件,建立数学模型。(2)分析模
13、型,搞清它属于运筹学哪一分枝,选择合适的最优化方法;(3)编程求解;尽量利用现有的数学软件或最优化软件,比如 Matlab,Mathematica,Lindo,Lingo等,来计算。(4)最优解的验证和实施。本讲稿第二十页,共一百零二页Chapter1 线性规划线性规划(Linear Programming)(Linear Programming)LP的数学模型的数学模型 LP模型的应用模型的应用本章主要内容:本章主要内容:本章主要内容:本章主要内容:本讲稿第二十一页,共一百零二页线性规划问题的数学模型线性规划问题的数学模型1.规划问题规划问题生产和经营管理中经常提出如何合理安排,使人力、物力
14、生产和经营管理中经常提出如何合理安排,使人力、物力等各种资源得到充分利用,获得最大的效益,这就是规划等各种资源得到充分利用,获得最大的效益,这就是规划问题。问题。线性规划通常解决下列两类问题:线性规划通常解决下列两类问题:线性规划通常解决下列两类问题:线性规划通常解决下列两类问题:(1 1)当任务或目标确定后,如何统筹兼顾,合理安排,用最少的)当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源资源 (如资金、设备、原材料、人工、时间等)去完成确定的任务(如资金、设备、原材料、人工、时间等)去完成确定的任务或目标或目标(2 2)在一定的资源条件限制下,如何组织安排生产获得最好的)在一定的资
15、源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多经济效益(如产品量最多 、利润最大、利润最大.)本讲稿第二十二页,共一百零二页线性规划问题的数学模型线性规划问题的数学模型例例1 某企业计划生产甲、乙两种产品。这些产品分别要在某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定,单件、四种不同的设备上加工。按工艺资料规定,单件产品在不同设备上加工所需要的台时如下表所示,企业决策产品在不同设备上加工所需要的台时如下表所示,企业决策者应如何安排生产计划,使企业总的利润最大?者应如何安排生产计划,使企业总的利润最大?设 备产 品 A B C
16、D利润(元)甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 台 时 12 8 16 12本讲稿第二十三页,共一百零二页线性规划问题的数学模型线性规划问题的数学模型解:设解:设x1、x2分别为甲、乙两种产品的产量,则数学模型为:分别为甲、乙两种产品的产量,则数学模型为:max Z=2xmax Z=2x1 1+3x+3x2 2 x x1 1 0,x 0,x2 2 0 0s.t.s.t.2x 2x1 1+2x+2x2 2 12 12 x x1 1+2x+2x2 2 8 8 4x 4x1 1 16 16 4x 4x2 2 12 12本讲稿第二十四页,共一百零二页 这这是是一一个个典典型型的的利
17、利润润最最大大化化的的生生产产计计划划问问题题。其其中中,“Max”Max”是是英英文文单单词词“Maximize”Maximize”的的缩缩写写,含含义义为为“最最大大化化”;“s.t.”s.t.”是是“subject subject to”to”的的缩缩写写,表表示示“满满足足于于”。因因此此,上上述述模模型型的的含含义义是是:在在给给定定条条件件限限制制下下,求求使使目目标标函函数数 z 达达到到最最大大的的x1,x2 的取值。的取值。本讲稿第二十五页,共一百零二页线性规划问题的数学模型线性规划问题的数学模型2.2.2.2.线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成
18、线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成决策变量决策变量决策变量决策变量 Decision variables Decision variables 目标函数目标函数目标函数目标函数 Objective function Objective function约束条件约束条件约束条件约束条件 Constraints Constraints其特征是:其特征是:其特征是:其特征是:(1 1 1 1)问题的目标函数是多个决策变量的)问题的目标函数是多个决策变量的)问题的目标函数是多个决策变量的)问题的目标函数是多个决策变量的线性线性线性线性函数,通常是求函数,通常是求函数,通常
19、是求函数,通常是求最大值或最小值;最大值或最小值;最大值或最小值;最大值或最小值;(2 2 2 2)问题的约束条件是一组多个决策变量的)问题的约束条件是一组多个决策变量的)问题的约束条件是一组多个决策变量的)问题的约束条件是一组多个决策变量的线性线性线性线性不等式不等式不等式不等式或等式。或等式。或等式。或等式。怎样辨别一个模型是线性规划模型?怎样辨别一个模型是线性规划模型?怎样辨别一个模型是线性规划模型?怎样辨别一个模型是线性规划模型?本讲稿第二十六页,共一百零二页线性规划问题的数学模型线性规划问题的数学模型目标函数:目标函数:目标函数:目标函数:约束条件:约束条件:约束条件:约束条件:3.
20、3.线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式简写为:简写为:本讲稿第二十七页,共一百零二页线性规划问题的数学模型线性规划问题的数学模型矩阵形式:矩阵形式:矩阵形式:矩阵形式:其中:其中:本讲稿第二十八页,共一百零二页线性规划问题的数学模型线性规划问题的数学模型3.线性规划问题的标准形式线性规划问题的标准形式特点:特点:(1)目标函数求最大值。目标函数求最大值。(2)约束条件都为等式方程,且右端常数项约束条件都为等式方程,且右端常数项bi都大于或等于零都大于或等于零(3)决策变量决策变量xj为非负。为非负。本讲稿第二十九页,共一百零
21、二页线性规划问题的数学模型线性规划问题的数学模型(2 2 2 2)如何化标准形式)如何化标准形式)如何化标准形式)如何化标准形式 目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ,则可将目标函数乘以,则可将目标函数乘以(-1)(-1),可化,可化为求极大值问题。为求极大值问题。也就是:令也就是:令 ,可得到上式。,可得到上式。即即 若存在取值无约束的变量若存在取值无约束的变量 ,可令可令 其中:其中:变量的变换变量的变换本讲稿第三十页,共一百零二页线性规划问题的数学模型线性规划问题的数学模型 约束方程的转换:由不等式转换为等式。约束方程的转换:由不等式转换为等式。称为松弛变量称
22、为松弛变量称为剩余变量称为剩余变量 变量变量 的变换的变换 可令可令本讲稿第三十一页,共一百零二页线性规划问题的数学模型线性规划问题的数学模型4.4.线性规划问题的解线性规划问题的解线性规划问题线性规划问题求解线性规划问题,就是从满足约束条件求解线性规划问题,就是从满足约束条件(2)、(3)的方程组中找出一的方程组中找出一个解,使目标函数个解,使目标函数(1)达到最大值。达到最大值。本讲稿第三十二页,共一百零二页线性规划问题的数学模型线性规划问题的数学模型 可行解可行解:满足约束条件:满足约束条件、的解为可行解。所有可行解的解为可行解。所有可行解的集合为可行域。的集合为可行域。最优解最优解:使
23、目标函数达到最大值的可行解。:使目标函数达到最大值的可行解。线性规划解的情况:有线性规划解的情况:有唯一最优解;有无穷多最优解;唯一最优解;有无穷多最优解;无界解;无可行解无界解;无可行解 本讲稿第三十三页,共一百零二页 建立线性规划模型的过程可以分为四个步骤:建立线性规划模型的过程可以分为四个步骤:(1)(1)设立决策变量;设立决策变量;(2)(2)明明确确所所有有的的约约束束条条件件并并用用决决策策变变量量的的线线性性等等式式或或不不等等式式表表示示出来;出来;(3)(3)用用决决策策变变量量的的线线性性函函数数表表示示目目标标,并并确确定定是是求求极极大大(MaxMax)还是极小()还是
24、极小(MinMin););(4)(4)根据决策变量的物理性质研究变量是否有非负性。根据决策变量的物理性质研究变量是否有非负性。求解方法:用求解方法:用MATLABMATLAB软件直接求解。软件直接求解。本讲稿第三十四页,共一百零二页Chapter2 运输运输问题问题(Transportation Problem)(Transportation Problem)运输问题的数学模型运输问题的数学模型运输问题的应用运输问题的应用 本章主要内容:本章主要内容:本章主要内容:本章主要内容:本讲稿第三十五页,共一百零二页1.运输问题模型及有关概念问题的提出问题的提出 一一般般的的运运输输问问题题就就是是要
25、要解解决决把把某某种种产产品品从从若若干干个个产产地地调调运运到到若若干干个个销销地地,在在每每个个产产地地的的供供应应量量与与每每个个销销地地的的需需求求量量已已知知,并并知知道道各各地地之之间间的的运运输输单单价价的的前前提提下下,如如何何确确定定一一个个使使得得总总的的运运输输费费用用最最小小的方案。的方案。本讲稿第三十六页,共一百零二页运输问题的数学模型运输问题的数学模型例例2.1 某公司从两个产地某公司从两个产地A1、A2将物品运往三个销地将物品运往三个销地B1,B2,B3,各产地的产量、各销地的销量和各产地运往各销地每件,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散 优化 数学 建模 精选 文档
限制150内