信息与计算机科学毕业论文.doc
《信息与计算机科学毕业论文.doc》由会员分享,可在线阅读,更多相关《信息与计算机科学毕业论文.doc(30页珍藏版)》请在三一文库上搜索。
1、本科毕业论文本科毕业论文(设计设计) 生活中的一些最优化问题研究生活中的一些最优化问题研究 院院 (系)(系)数学与计算科学学院 专专 业业信息与计算科学 学学 号号08251001133 学生姓名学生姓名游佳能 指导教师指导教师柴啸龙 提交日期提交日期2012 年 5 月 20 日 2012-JX16- 广广 东东 商学院商学院 毕业论文毕业论文( (设计设计) )成绩评定表成绩评定表 毕业论文(设计)指导教师评语及成绩毕业论文(设计)指导教师评语及成绩 成绩成绩 指导教师签名指导教师签名 年年 月月 日日 毕业论文(设计)复评教师评语及成绩毕业论文(设计)复评教师评语及成绩 成绩成绩 复评
2、教师签名复评教师签名 年年 月月 日日 毕业论文(设计)答辩评语及成绩毕业论文(设计)答辩评语及成绩 成绩成绩 答辩委员会主席签名答辩委员会主席签名 年年 月月 日日 毕业论文(设计)总成绩(五级记分制)毕业论文(设计)总成绩(五级记分制) 院(系)负责人签名院(系)负责人签名 年年 月月 日日 TITLE: Some Optimization Problem Research in Life MAJOR: Information and Computing Science APPLICANT: Jia-Neng YOU SUPERVISOR: Xiao-Long CHAI 内容摘要内容摘要
3、数学与我们日常生活密切相关,日常生活中的许多问题来源于数学 思想的应用。在掌握一定的数学基础的前提下,结合日常当中可能出现 的数学问题,通过适当的规划安排,运用数学原理求解出行之有效的最 优化方案。 本文的主要研究方向是通过对日常生活中经常涉及到的若干最优化 问题进行归纳总结,分析其所涉及的数学原理并将其推广应用到其他生 活案例当中去。本文的主要贡献是通过对运输成本问题和效益分配问题 的最优化分析,详细地介绍了表上作业法和 Shapley 值法的求解过程, 指出了模型存在的缺陷和不足,并对模型进行修改以及推广应用。 关键词关键词: : 最优化;表上作业法;Shapley 值;推广应用 Abst
4、ract Mathematics to our daily lives are closely related to many of the problems in our daily life from the application of mathematical thinking. Master the mathematical basis of the premise of the mathematical problems that may arise in day-to-day which, through appropriate planning arrangements, th
5、e use of mathematical principles for solving optimization program effective. The main research directions to daily life often related to certain optimization problem to summarize,analyze its mathematical principles involved and promote the application to which the case of other life to go.The main c
6、ontribution of this paper is the optimization analysis on transportation costs and efficiency of the distribution of the mostdetailed description of the solution process of the tabular method and the Shapley Value,pointed out that the model defects and deficiencies,and to modify the model and applic
7、ation. Keywords: Optimization; Tabular method; Shapley method; Application 广东商学院数学与计算科学学院 生活中的一些最优化问题研究 目目 录录 1 1 研究的意义研究的意义与与目的目的 1 1 2 2 研究现状分析研究现状分析 1 1 2.1 研究的方法 .1 2.2 研究现状 .2 3 3 本文研究方向本文研究方向 2 2 3.1 运输调配方向 .3 3.2 效益分配方向.3 4 4 运输调配问题最优化研究运输调配问题最优化研究 3 3 4.1 初始方案的给定 .4 4.2 最优性检验与方案的调整 .6 4.3 表上
8、作业法的总结 .8 4.4 表上作业法的改进及其推广应用 .9 5 5 效益分配问题最优化研究效益分配问题最优化研究 1212 5.1 n 人合作对策和 Shapley 值.12 5.2 Shapley 值的推广应用.14 5.3 Shapley 值法存在的缺陷.16 5.4 其他求解方法17 5.4.1 协商解 17 5.4.2 Raiffa 解 18 6 6 传统模型的改进设想传统模型的改进设想 1818 6.1 最小元素法的改进设想 18 6.2 效益分配的改进设想 20 7 7 总结与展望总结与展望 2020 7.1 本文的主要贡献 20 7.2 本文主要的改进方案 21 7.3 研究
9、展望 21 参考文献参考文献 2222 致谢致谢 2323 广东商学院数学与计算科学学院 生活中的一些最优化问题研究 第第 1 1 页页 生活中的一些最优化问题研究生活中的一些最优化问题研究 1 1 研究的意义与目的研究的意义与目的 最优化问题,是指在日常生活中通过适当的规划安排,使得完成一件事所 用的费用最少、路线最短、时间最短、产值最高、容积最大等的效率与分配问 题,也就是要在各种方案中,寻求一个最节约、合理的方案。解决这类问题要 注意两点: 一是明确问题,即通过问题描述中已知的数量关系把生活问题转化 为单纯的数学问题,我们称之为数学建模的过程;二是建模后的求解问题,即 用相关的数学知识求
10、解出最优的处理方案1。 数学与我们日常生活密切相关,日常生活中的许多问题来源于数学思想的 应用。在掌握一定的数学基础的前提下,结合日常生活当中可能出现的数学问 题,通过适当的规划安排,运用数学原理求解出行之有效的最优化方案。本文 通过对日常生活中经常涉及到的若干最优化问题进行归纳总结,分析其所涉及 的数学原理并将其推广应用到其他生活案例当中去2。因而,引导学生学习应 用数学,从众多的解决方案中寻求到最优化的方案,使他们感受到数学的应用 价值,是一种能够调动高校学生积极学习数学的办法3。 2 2 研究现状分析研究现状分析 2.1 研究的方法 不同类型的最优化问题可以有不同的最优化方法,即使同一类
11、型的问题也 可有多种最优化方法。反之,某些最优化方法可适用于不同类型的模型。目前, 最优化问题的求解方法大致可分成解析法、直接法、数值计算法。解析法: 这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法 是:先求出最优的必要条件,得到一组方程或不等式,再求解这组方程或不等 式,一般是用求导数的方法或变分法求出必要条件,通过必要条件将问题简化, 广东商学院数学与计算科学学院 生活中的一些最优化问题研究 第第 2 2 页页 因此也称间接法。直接法:当目标函数较为复杂或者不能用变量显函数描述 时,无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜 索到最优点。这种方法
12、常常根据经验或通过试验得到所需结果。对于一维搜索 (单变量极值问题),主要用消去法或多项式插值法;对于多维搜索问题(多变量 极值问题)主要应用爬山法。数值计算法:这种方法也是一种直接法。它以梯 度法为基础,所以是一种解析与数值计算相结合的方法4。 2.2 研究现状 最优化一般可以分为最优设计、最优计划、最优管理和最优控制等四个方 面。最优设计:世界各国工程技术界,尤其是飞机、造船、机械、建筑等部门都 已广泛应用最优化方法于设计中,从各种设计参数的优选到最佳结构形状的选 取等,结合有限元方法已使许多设计优化问题得到解决5。最优计划:现代国民 经济或部门经济的计划,直至企业的发展规划和年度生产计划
13、,尤其是农业规 划、种植计划、能源规划和其他资源、环境和生态规划的制订,都已开始应用最 优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策。最优管理: 一般在日常生产计划的制订、调度和运行中都可应用最优化方法。随着管理信 息系统和决策支持系统的建立和使用,使最优管理得到迅速的发展。最优控制: 主要用于对各种控制系统的优化。例如,导弹系统的最优控制,能保证用最少 燃料完成飞行任务,用最短时间达到目标;再如飞机、船舶、电力系统等的最优 控制,化工、冶金等工厂的最佳工况的控制。计算机接口装置不断完善和优化 方法的进一步发展,还为计算机在线生产控制创造了有利条件。最优控制的对 象也将从对机械、
14、电气、化工等硬系统的控制转向对生态、环境以至社会经济 系统的控制6。 3 3 本文研究方向本文研究方向 虽然现今最优化问题研究渐趋成熟,也应用到很多不同的领域,但对日常 生活存在的最优化问题的研究仍存在一定的空缺。本文将通过对日常生活中经 常涉及到的一些最优化问题进行归纳总结,分析其所涉及的数学原理并将其推 广应用到其他生活案例当中去。因而,如何运用最优化原理解决生活中存在的 实际问题将是本文研究的主要方向,主要针对生活中的运输成本问题和效益公 平分配问题进行研究分析7。 广东商学院数学与计算科学学院 生活中的一些最优化问题研究 第第 3 3 页页 3.1 运输调配方向 运输成本问题涉及了很多
15、生活领域,生产运输、物流运输、仓库调配等等, 但其主要的数学模型都是相似的,因此掌握这种问题的解决方法有着重要的作 用。文中通过对生产运输问题进行分析,运用表上作业法列出详细的求解过程, 并进行推广应用8。 3.2 效益分配方向 在日常的社会生活中,若干实体相互合作结成联盟或集团,常能比个体单 独行动获得更多的经济利益或社会效益。但是效益公平分配问题经常成为他们 合作的阻碍,如何合理地分配这些效益是促进合作的前提,也能给合作带来更 多的效益。文中通过对合作效益分配问题进行分析研究,运用 Shapley 法列出 详细的求解过程,并对模型进行修改推广。 4 4 运输调配问题最优化研究运输调配问题最
16、优化研究 运输问题是社会经济生活和军事活动中经常出现的优化问题,是特殊的线 性规划问题,它是早期的线性网络最优化的一个例子。最早研究这类问题的 Hitchcock以及后来的Koopmans独立地提出运输问题并详细地对该问题加以讨论; 同时KahTopoBny也围绕着运输问题作了大量的研究,因此运输问题又称为 Hitchcock问题或Kantorvich问题。运输问题不仅代表了物资合理调运、车辆合理 调度等问题,有些其他类型的问题经过适当变换后也可以归结为运输问题,如 指派问题、最短路问题、最小费用流问题可转化为运输问题或转运问题9。 运输问题在运筹学教学过程中占有重要地位,并且得到了众多学者的
17、广泛 关注,取得了许多重要的研究成果。但就在常用的运筹学教材中仅仅介绍运输 问题的基础知识,对于运输问题的前沿发展涉及甚少,这远远不能反映当前对 运输问题的深入研究。为此,在介绍运输问题的基本理论和方法的基础上,运 用表上作业法对类似问题进行推广运用10。 【例 1】某食品加工公司经销的主要产品之一是酸奶。该公司下面设有三个加 工厂,每天酸奶的生产量分别为:,。该公司把这些酸 1 7At 2 4At 3 9At 奶分别运往四个地区的门市部进行销售,各地区每天的销售量分别为: ,。已知从每个加工厂到对应的各销售门市部 1 3Bt 2 6Bt 3 5Bt 4 6Bt 广东商学院数学与计算科学学院
18、生活中的一些最优化问题研究 第第 4 4 页页 每吨酸奶的运价如表 4-1 所示,问该食品公司该如何调运,在满足各门市部销 售需要的前提下,使得总运费支出达到最少。 表 4-1 1 B 2 B 3 B 4 B 1 A 2 A 3 A 3 11 3 10 1 9 2 8 7 4 10 5 以下运用表上作业法求解运输问题,首先给出一个初始方案,一般来讲,这个 方案不会是最好的。因此需要给出一个判别准则,并对初始方案通过不断地调 整、改进,一直到求得最优方案为止10。 先列出这个问题的的产销平衡表和单位运价表,见表 4-2 和表 4-3 表 4-2 产销平衡表 1 B 2 B 3 B 4 B产量 1
19、 A 2 A 3 A 7 4 9 销量3 6 5 6 表 4-3 单位运价表 1 B 2 B 3 B 4 B 1 A 2 A 3 A 3 11 3 10 1 9 2 8 7 4 10 5 4.1 初始方案的给定 给定初始方案的方法有很多,一般希望方法简便易行,尽量能给出较好的 方案,减少迭代的次数,这里采用最小元素法。最小元素法的基本思想是就近 供应,即从单位运价表中最小的运价开始确定供销关系,依此类推,一直到给 出全部方案为止10。 门市部 加工厂 销地 产地 销地 产地 广东商学院数学与计算科学学院 生活中的一些最优化问题研究 第第 5 5 页页 第一步:从表 4-3 的单位运价表中找出最
20、小运价为 1(如果有两个最小运价时 任选其一) ,即从生产的酸奶首先供应需求。由于每天生产 4t,每天 2 A 1 B 2 A 1 B 需要 3t,即每天生产的除了要满足全部需求之外,还剩下 1t。因此在表 4- 2 A 1 B 2 中(,)的交叉格中填上数字 3,表示调运 3t 酸奶给,再在表 4-3 2 A 1 B 2 A 1 B 中将所在的这一列运价划去,表示已经满足的需求,无需继续调运给它。 1 B 1 B 第一步得到的结果如表 4-4 和表 4-5 所示。 表 4-4 1 B 2 B 3 B 4 B产量 1 A 2 A 3 A 3 7 4 9 销量3 6 5 6 表 4-5 1 B
21、2 B 3 B 4 B 1 A 2 A 3 A 3 11 3 10 1 9 2 8 7 4 10 5 第二步:从表 4-5 中未划去的元素之中找出最小的运价为 2,即每天剩余的 2 A 酸奶要供应给。每天需要 5t,每天只能供应 1t,因此在表 4-4(, 3 B 3 B 2 A 2 A )交叉处填写 1,划去表 4-5 所在的这一行运价,表示生产的酸奶已 3 B 2 A 2 A 分配完,其结果见表 4-6 和表 4-7. 表 4-6 1 B 2 B 3 B 4 B产量 1 A 2 A 3 A 3 1 7 4 9 销量3 6 5 6 销地 产地 销地 产地 销地 产地 广东商学院数学与计算科学
22、学院 生活中的一些最优化问题研究 第第 6 6 页页 表 4-7 1 B 2 B 3 B 4 B 1 A 2 A 3 A 3 11 3 10 1 9 2 8 7 4 10 5 第三步:同理再从表 4-7 中未划去的元素之中找出最小的元素为 3,即生产 1 A 的酸奶应优先满足需求。每天生产 7t,还缺 4t。因此在表中 3 B 1 A 3 B (,)交叉格内填上 4,由于的需求此时已经满足,在表 4-7 中划去 1 A 3 B 3 B 所在列的元素。 3 B 这样一步一步地进行下去,直到单位运价表上所有元素都被划去为止,这时在 产销平衡表上可以得到一个调动方案(见表 4-8) ,这个调动方案总
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息 计算机科学 毕业论文
链接地址:https://www.31doc.com/p-3261326.html