数学建模常用优化算法
前言：想要写出一篇令人眼前一亮的文章吗？我们特意为您整理了5篇数学建模常用优化算法范文，相信会为您的写作带来帮助，发现更多的写作思路和灵感。
数学建模常用优化算法范文第1篇
中图分类号：G642.0 文献标志码：A 文章编号：1674-9324（2014）41-0068-03
随着我国现代物流业的迅速发展，物流专业人才成为近年来社会的紧缺人才。2012年，教育部将物流工程及物流管理批准为一级学科，全国各工科院校几乎都增设了物流专业，也培养了大批的物流专业技术人员。由于物流专业涉及的领域广，涵盖了许多方向，如物流机械、物流管理、物流工程、物流金融、物流信息等。虽然都称为是物流专业，但各院校针对本校的特点培养的方向有所不同，各院校为不同方向的物流专业所设置的培养方案和课程内容也相差很大。有偏重物流系统规划设计类的，有偏重运输与仓储管理类的，有偏重企业供应链管理类的，有偏重物流信息技术及物联网软件开发类的，也有偏重物流机械设备设计与配置类等。但无论培养物流专业的何种方向的人才，各校都十分注重加强对学生的物流建模方法的培养和训练，提高其科学解决实际问题的能力和管理水平。
一、现代物流系统中常见的优化问题及求解方法
物流被称为是企业的第三利润源泉，通过规划建设现代物流系统和改变传统的物流运作模式，可大大降低制造企业的物流成本，提高物流作业效率，从而为企业创造更大的效益。物流专业人才之所以缺乏，是由于在物流系统规划和运营管理各个环节中，处处都是较难解决的优化决策问题，必须应用科学的理论和先进的技术方法才能得到好的结果。目前在这方面的研究成果有很多，以下列举一些现代物流系统规划与运营管理中常见的优化问题和解决方法。
1.物流需求预测。在物流系统规划中物流设施（仓库、设备、停车场、车辆数等）规模的确定，物流管理中的物流仓储控制等都需有科学准确的物流需求预测作为决策基础。然而由于受多种不确定因素的影响，如何准确预测物流需求是相当困难的问题。物流需求预测问题分为单品种货物与多品种货物的物流需求预测、单个节点与区域内总物流需求预测、近期与中远期物流需求预测等多类问题。目前各种中样的需求预测模型非常多，据不完全统计约有一百多种。除定性预测外，常见应用于物流需求的定量预测模型有增长系数法、趋势外推法、曲线拟合法、弹性系数法、回归分析法、时间序列法、原单位（生成率）法、类别生成法、生长曲线法等。目前较流行的还有应用一些启发式或亚启发式算法进行区域内的物流需求预测，如神经网络模型、灰色系统模型、动态预测模型等。在实际的物流需求预测时，经常同时应用以上多种模型构成组合模型进行预测。以上各类模型的理论基础是高等数学、数理统计学、数理逻辑学、计算机算法设计等。
2.物流系统总体设计。物流系统设计方案的优劣直接影响物流的运营成本及运作效率。物流系统设计内容主要包括区域内系统物流节点的数量、规模和位置的确定;各物流节点的功能定位和功能设施（含停车场）的合理配置;物流节点内部设施布局;物流运输通道设计及能力分析等问题。其中区域内物流节点的数量和规模的确定主要依赖于对区域内物流总需求的预测结果。常见的模型有成本分析模型、随机报童模型、数据包络模型以及参数标定法等。物流节点的选址问题是物流系统规划中的关键技术问题，根据研究对象和研究方法可分为许多类型，如单一设施选址与多设施选址、连续区域选址与离散点选址、单纯位置选址与具有客户最优分配的选址、有能力约束选址与无能力约束选址等。本科生需掌握的典型物流选址模型和方法有：重心模型及不动点算法、交叉中值模型、线性规划模型、因素评分模型及层次分析法、多点解析模型及鲍摩・瓦乐夫启发式算法、奎汉・哈姆勃兹启发式算法、P-中值模型、集合覆盖模型、最大覆盖模型等。目前较常用的还有设计计算机算法进行仿真模拟计算，如遗传算法、蚁群算法、粒子算法、模拟退火算法、模糊群决策法等。这些算法的思路物流专业的本科生也应有所了解。物流节点内部设施布局是指在物流节点的规模与功能已确定的条件下，进一步设计节点内各设施间的位置关系，大多是引用工业工程法中的一些设计方法，常用的模型和算法有系统布局法、关系表布局法、CORELAP布局算法、ALDEP布局算法、CRAFT布局算法、MultiPLE布局算法、数据包络分析布局模型等。以上各类模型的理论基础是高等数学、概率论与数理统计、线性代数、系统工程学、工业工程学、运筹学和计算机算法设计等。
3.物流运输组织与运输管理。降低货物运输成本是减少物流总成本的重要手段，在货物运输组织中存在大量的优化管理问题，如运输方式（工具）、运输线路、运输链的优化选择;车辆与货物间的最优配载、配送计划及配装计划的优化编制;物流企业车辆的最佳拥有台数、运用与维护方案;车辆、船只及集装箱等的优化调度等问题。常见的模型有总费用分析法、综合性能评价法、公路货运交易优化配载模型、物资调运模型等。其中有关配送计划的优化编制问题是实际应用最广、理论上最为困难的问题之一。该问题根据研究对象和研究所考虑的因素分为了许多类型，如纯装问题、纯卸问题和装卸混合问题、对弧服务问题和对点服务问题、车辆满载与车辆非满载问题、单配送中心和多配送中心问题、运输车辆有距离上限约束和无距离约束问题、路网上线路距离无方向（对称）和有方向（非对称）问题、运输车辆是同类和异类问题、客户装卸点有时间窗约束和无时间窗约束问题等。由于每一类问题在理论上都属于NP-困难问题，在实际应用中常设计近似算法进行求解，求精确解的算法，可求解小型的配送问题，如分枝定界法、割平面法、网络流算法以及动态规划方法等。以上各类模型的理论基础是高等数学、线性代数、数学建模基础、图论、运筹学和计算机算法设计等。
4.物流仓储管理与库存控制。库存具有对不同部门间的需求进行调节的功能，库存物品过剩或者枯竭，是造成企业生产活动混乱的主要原因。由于货物供应及需求受大量因素的随机性和波动性影响，库存控制也是物流管理中较为困难的决策问题。库存控制包括单级库存与多级（供应链）库存、确定型库存与随机型库存、单品种与多品种库存等问题。物流仓储管理还包括仓位计划和拣货计划的编制、物流成本分析及风险分析等内容。物流库存管理的典型模型有经济批量订货模型、二次方策略模型、有数量折扣的EOQ模型、一次性进货报童模型、定期盘点库存模型、（s，S）型存储策略模型、鞭打效应分析模型、多级批量定货模型和直列系统多级库存模型、单级和多级概率库存模型、动态规划模型、最优匹配模型和网络最短路模型、成本分析模型等。以上模型主要用到的理论基础是运筹学、图论和算法设计等。
二、物流专业的数学基础要求
通过以上对物流系统规划设计及物流运营管理中的各类优化决策问题的介绍可知，要培养从事物流专业的高级管理人才必须具备扎实宽广的基础理论知识，尤其是数学和计算机的相关知识，具体来说，物流专业本科生应具备以下基础理论知识结构。
1.基础数学知识。包括高等数学、线性代数、概率论与数理统计等，目前国内外几乎所有的工科专业本科都会开设这些课程，而物流专业应特别加强统计分析方法的学习，包括时间序列分析、多变量解析、回归分析等内容。
2.建模及优化理论。主要包含数学建模方法和运筹学理论，我国大多数物流工程及物流管理专业都开设了这两门课，也有的学校还开设了“物流系统模型”或“物流运筹”等课程。其中运筹学是解决物流优化决策问题的重要方法，如规划论（线性规划、非线性规划、整数规划、动态规划）、存贮论、排队论、决策论、模拟模型法、图与网络理论、启发式方法、数值分析法、费用便利分析等方法。
3.计算机算法设计及仿真。计算机算法设计及计算机仿真是求解物流系统中各类优化模型的基本工具，要使所培养的物流管理人才具有独立解决实际问题的能力，必须具备较强的计算机动手能力。目前大多数院校的物流专业都开设了“计算机应用基础”、“程序设计”、“数据库原理及应用”、“管理信息系统”等课程，为求解物流系统中的优化决策问题，建议还应开设“数值计算与算法设计”、“系统仿真基础”等课程。
4.系统设计与分析理论。在物流系统规划与管理过程中，还要应用一些系统设计及系统分析理论，如系统分析（系统工程）、大系统理论、系统控制论、系统动力学、IE（工业工程）法等。虽然对物流专业本科生不能要求都掌握这些理论，但需对这些理论的研究内容应有所了解。
三、加强物流专业本科生建模能力的培养措施
由以上对物流专业本科生基础知识结构要求的分析可以看到，物流专业学生需具有扎实的基础理论知识，但学生在学习基础课时还未涉及专业内容，各项基础理论不知道如何应用，往往是学过了就忘。而在学习物流专业课时，较注重具体管理方法的使用，不知这些方法是如何得到的，使得学生当遇到没有学过的问题就不知如何解决。因此需有一门课程将基础理论与专业知识之间搭建一座桥梁，通过提出物流系统规划与管理中各类优化决策问题，帮助学生应用各种已学到的基础理论对这些问题进行分析和研究，建立这些问题的数学模型、设计求解这些模型的计算机算法、分析比较各种求解方法的优劣，我们将这门课程称之为“物流系统模型”或“物流运筹”。属于物流专业的专业基础课，它与基础课与专业课之间的关系如下图所示：
“物流系统模型”课程主要有以下三大教学内容。
1.常用物流系统模型的推导及介绍。提出以上物流规划与管理中所列举的优化决策问题，介绍解决这些问题的典型模型及求解思路。对相对简单的模型及算法，引导学生应用已学过的基础理论来推导解决该问题的模型和方法，使得学生在后面学习专业课时遇到这些问题和方法时有较深刻的印象。
2.介绍一些新的优化理论和相关算法知识。如系统分析理论、系统控制论、系统动力学、IE（工业工程）法等，让学生了解相关理论的研究内容和研究方法，开扩学生的视野和解决实际问题的思路。
数学建模常用优化算法范文第2篇
1 引言
当今世界,创新取代了传统的比较优势,已经无可替代地成为国家竞争战略的基础。
因此,加强创新精神和创新能力的培养,已是世界各国 教育 改革的共同趋势,也是我国实现“科教兴国”战略的基本要求,创新教育已经成为高等教育的核心,多年来的教育实践证明,数学建模的教学与竞赛活动在高等学校的创新教育中的地位和意义已是举足轻重.
一年一度的全国大学生数学建模竞赛活动是由国家教育部高教司直接组织领导,面向全国高校,规模最大,参与院校最多,涉及面最广的一项科技竞赛活动.其宗旨是“创新意识,团队精神;重在参与,公平竞争”。自1992年举办第一届竞赛以来,参赛队数以平均每年近30%的速度增加,2006年已达到864所院校9985个参赛队的规模.正是由于数学建模竞赛活动的深入开展,它积极地推动了大学数学教学改革的开展,并已取得了显著的成果。
2 数学建模对培养学生创新能力的意义
高校作为人才培养的基地,围绕加快培养创新型人才这个主题,积极探索教学改革之路,是广大教育工作者面临的一项重要任务。正是在这种形势下,数学建模与数学建模竞赛,这个我国教育史上新生事物的出现,受到了各级教育管理部门的关心和重视,也得到了科技界和教育界的普遍关注。这主要是数学建模的教学和竞赛活动有利于人才的培养,特别是人才的综合能力、创新意识、科研素质的培养.也正因为如此,数学建模活动的实际效果正在不断的显现出来,“数学建模的人才”和“数学建模的能力”正在实际工作中发挥着积极的作用。
数学建模本身就是一个创造性的思维过程。数学建模的教学内容、教学方法以及数学建模竞赛培训都是围绕创新能力的培养这一核心主题进行的,其内容取材于实际,方法结合于实际,结果应用于实际.数学建模的教学和竞赛培训,为学生的探索性学习和研究性学习搭建了平台。数学建模的教学和竞赛,注重培养学生敏锐的观察力、 科学 的思维力和丰富的想象力,既要求学生具有丰富的知识,又要求学生具有较强的实践操作能力;既有智力和能力要求,又有良好的个性心理品质要求;既要求敢于竞争,又要求善于合作.数学建模真正体现了开发学生潜能、培养学生优秀心理品质以及积极探索态度的良好结合.在数学建模的教学与竞赛中,特别注重发挥学生的主动性、积极性、创造性、耐挫折性,特别是提倡探索精神、创造精神、批判精神、团队协作精神等.知识创新、方法创新、结果创新、应用创新无不在数学建模的过程中得到体现.实践正在证明,数学建模的教学与竞赛活动是培养大学生创新思维和创新能力的一种极其重要的方法和途径。
3 在数学建模的教学中培养学生的创新思维
创新型人才是指具有较强的创新精神、创造意识和创新能力,并善于将创造能力化为创造性成果和产品的人才.尽管创新精神、创造意识和创新能力的培养不是一个学科或一门课程的教学所能完成的,但大量的中外教育实践充分证明,数学教育在创新型人才的培养中具有其他学科不可替代的优势和作用.因为数学中的理论和方法是人们从量的侧面研究现实世界所得到的客观 规律 ,是研究各种科学技术不可缺少的语言和工具.
而数学建模的过程则恰好是将数学中的理论和方法又重新应用于解决现实问题,即是理论来源于实践又要服务于实践的一个完美体现.这一过程高度反映了人的创新精神、创造意识和创新能力。
数学本身包含着许多重要的思想方法,比如由特殊到一般的思想、从有限到无限的思想、归纳类比的思想、倒推逆向分析思维、试探思想等,其本质都是创造性思维方法.我们在数学建模的教学过程中不刻意地去追求运算技巧和方法,而将重点放在数学思想方法的传授上,运用对数学思想方法的体会去启迪学生的创新思维,激发学生的创新欲望。
数学上的归纳和类比思维是一种非常典型的创新思维,著名的数学家拉普拉斯说过“在数学里,发现真理的主要工具和手段是归纳和类比”.而大多数数学模型的建立、修改或改进,很多时侯都是依靠这种归纳与类比思维.在寻找模型求解的算法时,也常常用类比思维,利用相似的算法加以优化和改进而得到,有时甚至可以发现新的更好的算法.
发散思维是许多科学家非常重视的一种思维形式,科学家运用发散思维获得重要发现的例子不胜枚举.我们在数学建模的教学过程中倡导学生养成发散思维的习惯,通过一些具体的建模实例,让学生感受到在科学上要敢于联想,敢于突破条条框框,敢于标新立异。
逆向思维,即“反过来想一想”。人们思考问题时常常只注重于已有的联系,沿着合乎习惯的正向顺推,但有时如果采用“倒过来”思考的逆向思维方式,往往会产生意想不到的效果.比如,2004年全国大学生数学建模竞赛A题:奥运会临时超市网点设计中的第三个问题:若有两种大小不同规模的迷你超市(Mini-Supermarket)类型供选择,给出图2中20个商区MS网点的设计方案(即每个商区内不同类型MS的个数,并满足题中三个基本要求:满足奥运会期间的购物需求、分布基本均衡、商业上盈利).在设计MS网点时为考虑满足商业上盈利这一要求,如果单从正面去考虑商业上的盈利模型,则有很多未知的因素无法确定,诸如商品种类、数量、价格、销售额等,因而无法建立模型.但若运用逆向思维,从市场需求去预测可能的盈利能力,因为市场需求量可利用前述问题中已得到的商区的人流量的分布,从而为后面的规划模型的建立与求解提供了关键性的办法。
数学建模常用优化算法范文第3篇
【关键词】 物流系统;仿真;仿真优化;综合仿真环境
物流系统是复杂的离散事件系统,在系统设计与控制过程中存在许多优化问题,用传统的解析方法难以获得最优解或满意解。仿真是建立数学逻辑模型并在计算机上运行该模型进行试验的过程,仿真建模要模仿真实系统的行为。仿真是决策者用于物流系统设计和操作的最有力的工具之一,它不仅可提供用于决策的定量信息而且可以提高决策者对物流系统工作原理的理解水平,仿真技术提供了技术性和经济性的最佳结合点和直观有效的分析方法。目前,仿真已经成为管理科学与运筹学领域应用最广泛的技术手段之一。
一、物流系统仿真应用研究进展
物流系统是指在一定的时间和空间里,由物资、包装设备、装卸搬运机械、运输工具、仓储设施、人员和通信联系等若干相互制约的动态要素所构成的具有特定功能的有机整体。早期的物流系统仿真主要是针对生产物流过程中的控制与优化问题来进行,随着供应链的兴起与发展,更多的研究关注于集采购、生产和销售一体化的供应链仿真。随着物流网络规模的扩大和物流量的巨大增长,配送物流的瓶颈作用越来越突出,一些学者开始用仿真的手段来解决物流配送系统中存在的问题。
二、物流系统仿真优化研究进展
计算机仿真技术是研究复杂系统的有效方法。用仿真语言或者商用的仿真软件能够很容易的建立物流系统的仿真模型,与解析方法相比仿真模型能更加全面地反映实际物流系统的特征。仿真模型仅是对问题的直观描述,仿真运行只能提供一定条件下的可行方案,它并不能给出问题的最优解或满意解,需要将仿真与优化技术结合起来,以便在仿真环境下使输出响应不断地改进,可以形成各种仿真的优化结构,进而实现系统性能的优化。仿真优化是研究基于仿真的目标优化问题,即基于模型仿真给出的输入输出关系,通过优化算法得到最佳的输入量。仿真优化在物流领域的应用研究进展缓慢,到目前为止,基本上还没有大规模的实际问题用仿真优化的方法加以解决,并且仿真优化方法在解决物流系统控制与调度问题时还存在着以下不足:仿真优化方法解决物流调度这一问题时,计算时间长,算法效率不高;没有从系统的角度对仿真优化进行研究和规划,当前仿真优化的大量工作集中在算法研究上,很少从系统的角度考虑算法与系统建模方法的关系,使得仿真优化缺乏进一步研究和应用的基础;仿真优化系统缺乏与专家系统或智能决策系统的集成,智能化程度不高;大多数研究都还停留在理论层面上,应用方面缺乏,仿真优化方法几乎没有解决有一定规模的实际问题。
三、物流系统综合仿真环境研究进展
系统仿真技术作为系统分析,优化的有效工具,已广泛应用于各类复杂系统的规划设计、系统优化、方案比较、流程运作控制等领域。在现代物流行业,国内外许多的物流中心设计、自动化仓储系统和物料搬运系统等工程设计中也都开始应用仿真技术作为有效实用的辅助设计手段。为了使系统人员、模型开发人员、软件人员、仿真研究人员更好地利用仿真技术,仿真建模方法和相应的仿真软件由传统的运用通用编程语言和仿真语言向着一体化、智能化、虚拟现实环境和面向对象的趋势发展,出现了不少具有相似功能的一体化的建模/仿真开发环境仿真软件产品。综合仿真环境具有通用性强、交互性好、标准化程度高,可重构重用性强等特点。在物流系统仿真过程中常用的综合仿真环境:美国AutoSimulation公司的AUTOMOD仿真软件,美国System Modeling公司开发的Arena,英国推出的面向对象的仿真环境WITNESS,以色列Tecnomatix Technologies公司开发的关于生产、物流和工程的仿真软件eM-plant和IBM公司开发的通用仿真系统SIMPROCESS等。
系统仿真作为解决复杂物流系统问题的有效手段,已经广泛应用于生产物流系统、供应链及物流配送系统等研究领域,对物流配送系统仿真也进行了初步的研究,在物流系统仿真优化方面也已经取得了一定的研究成果,但其进展比较缓慢,在解决物流系统问题时还存在算法效率不高、智能化程度不高、还没有解决大规模实际问题的能力等方面的缺陷,综合仿真环境已经成为物流系统仿真的主要工具。物流系统仿真应在分布式交互仿真、基于 Multi-Agent 的仿真建模方法、仿真优化方法、物流系统可视化仿真环境的开发等方面作进一步的研究。
参考文献
[1]张晓萍,颜永年,吴耀华,荆明.现代生产物流及仿真[M].北京:清华大学出版社,1998.
数学建模常用优化算法范文第4篇
关键词：数学建模；图论；实践
中图分类号：G642.0 文献标志码：A 文章编号：1674-9324（2013）45-0233-03
一、引言
图论是组合数学的一个重要分支。它以图为研究对象，这种图由若干给定的点及连接两点的边所构成，通常用来描述某些事物之间的某种特定关系，以点代表事物，以连接两点的边表示两个事物间具有这种关系。图论的应用非常广泛，在实际的生活生产中，有很多问题可以用图论的知识和方法来解决，其应用性已涉及物理学、化学、信息论、控制论、网络理论、博弈、运输网络、社会科学以及管理科学等诸多领域。目前高校很多课程都涉及到图论知识，例如离散数学、数据结构、算法分析与设计、运筹学、组合数学、拓扑学、网络优化等。甚至有些专业将图论作为一门必修或选修课程来开设。
由于图论课程具有概念多、公式复杂和定理难证明、难理解等特点，在一定程度上造成教学难，证明抽象度高，学生难以理解，学生不能真正理解图论思想，更谈不上灵活运用图论知识来解决各种实际问题。从而会使学生感到图论的学习非常枯燥。大学数学课程教学改革的趋势，越来越注重数学的应用性，而数学建模过程就是利用已经掌握的数学知识来解决实际问题的过程。在当前实现数学作为一种应用能力的过程中，使用数学解决实际问题的能力培养是非常重要和必需的。因此，在大学数学类课程的教学中融入数学建模思想是目前数学课程教学改革的一个大的趋势。由于图论的概念和定理大多是从实际问题中抽象出来的，因此图论中的诸多模型和算法是数学建模强有力的理论依据。所以在图论课程教学中注重介绍这些概念和理论的实际背景，引导学生利用数学建模思想方法学习图论的相关概念和定理，探究图论的发展规律，从而将更好地帮助学生理解和掌握这些概念和理论。
二、数学建模思想方法
数学模型就是用数学语言，通过抽象、简化，建立起来的描述客观事物的特征及其内在联系的数学结构。这个结构可以是公式、方程、表格、图形等。把现实模型抽象、简化为某种数学结构（即数学模型）之后，我们就可以用相关的数学知识来求出这个模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，这个过程便称为数学建模。其目的是将复杂的客观事物或联系简单化并用数学手段对其进行分析和处理。建立数学模型解决现实问题要经过模型准备、模型假设、模型构成、模型求解和模型分析这五个步骤。模型准备就是了解问题的实际背景，明确建模目的，搜集必要的各种信息，尽量弄清对象的特征，形成一个比较明晰的“问题”。模型假设是根据对象的特征和建模目的，抓住问题的本质，做出必要的、合理的简化假设。模型构成是根据所作的假设，用数学的语言、符号描述对象的内在规律，建立包含常量、变量等的数学模型。模型求解是采用解方程、画图形、优化方法、数值计算、统计分析等各种数学方法，特别是数学软件和计算机技术求解。模型分析就是对求解结果进行数学上的分析，并解释为对现实问题的解答。由此可见，思想数学建模就是将数学的理论知识应用于解决实际问题，培养数学建模思想就是锻炼应用数学的能力。
在图论的教学中引入数学建模思想，将生活中的实际问题引入课堂，利用图论知识分析实际问题，让学生感受到图论贴近生活。教学中可以引导学生自己寻找与图论相关的实际问题，利用图论知识建立实际问题的数学模型，并进行报告和讨论，让学生发表自己的见解和看法，在此过程中有助于学生对所学知识的融会贯通和掌握，大大提高学生学习图论的兴趣。
三、数学建模思想方法融入图论教学的实践
目前，各门数学课程教学改革所面临的一个课题是如何增强应用数学知识解决实际问题的意识。在这样的背景下，加之图论知识的应用广泛性，从而，将数学建模的思想方法融入到图论课程教学中的研究和实践已显得刻不容缓。因此，结合图论教学内容有机地增加数学建模教学内容，使广大的学生能学习和体会到数学建模的基本思想方法，在日常的学习中培养学生应用图论知识的意识，激发了学生学习图论的积极性。
（一）在图论定理公式中渗入建模的案例
在图论某些定理证明的教学过程中可以适当地融入数学建模的思想与方法，把定理的结论看作一个特定的模型，需要去建立它。于是，当把定理的条件看作是模型的假设时，可根据预先设置的问题，情景引导学生发现定理的结论，从而定理证明的方法也随之显现。
案例1：设为任意无向图，V={v1，v2，…，vn}，|E|=m，证明所有顶点的度数和=2m，并且奇点个数为偶数。
解析：证明该结论之前，首先任意选取若干个学生让其随机互相握手，并记下每个人的握手次数和每两人之间握手的次数，由此可得每个人握手次数总和是每两人之间握手次数的2倍以及握过奇数次手的人数一定是偶数。互动之后介绍该定理称之为握手定理，从互动过程中可以建立定理结论的模型，并且证明的思路也是显而易见的。
（二）在应用性例题中渗入数学建模的方法
案例2：一家公司生产有c1，c2，c3，c4，c5，c6，c7七种化学制剂，其中制剂（c1，c2），（c1，c4），（c2，c3），（c2，c5），（c2，c7），（c3，c4），（c3，c5），（c3，c6），（c4，c5），（c4，c7），（c5，c6），（c6，c7）之间是互不相容的，如果放在一起能发生化学反应，引起危险。因此，作为一种预防措施，该公司必须把仓库分成互相隔离的若干区，以便把不相容的制品储藏在不同的区，问至少要划分多少小区，怎样存放才能保证安全。
解析：首先建立模型，用图来表示实例中这些制剂和他们之间关系，用顶点v1，v2，v3，v4，v5，v6，v7，表示c1，c2，c3，c4，c5，c6，c7表示七种化学制品，把不能放在一起的两种制品对应的顶点用一条边连接起来，如图1。
模型求解：由图可得极小覆盖的逻辑表达式为：
（v1+v2v4）（v2+v1v3v5v7）（v3+v2v4v5v6）（v4+v1v3v5v7）（v5+v23v4v6）（v6+v3v5v7）（v7+v2v4v6）
利用逻辑代数法则简化上述逻辑表达式为：
v1v3v5v7+v2v3v4v5v6+v2v4v5v6+v2v3v4v6
从而可得全部极小覆盖为：
（v1，v3，v5，v7），（v2，v3，v4，v5，v7），（v2，v4，v5，v6），（v2，v3，v4，v6）
由于极大独立集与极小覆盖集之间互补的关系，所以上图的所有极大独立集为（v2，v4，v6），（v1，v6），（v1，v3，v7），（v1，v5，v7）.取图G的一个极大独立集V1=（v2，v4，v6），将其着第一种颜色。在VG-V1中，所有极大独立集为，（v1，v3，v7），（v1，v5，v7），取V2=（v1，v3，v7）将其着第二种颜色。在VG-V1-V2中仅有点v5，将其着第三种颜色，故χ（G）=3.
于是得到该化学制品的存放方案：至少需要把仓库划分为3个区，可以将c2，c4，c6三种制品，c1，c3，c7三种制品和制品c5分别存放在一个区。
（三）设计相关数学建模问题，提高学生应用图论知识解决实际问题的能力
由于教学课时的限制，将数学建模的思想方法融入图论课程教学时，不能专门地让学生学习建模，只能通过一些简单的模型给学生介绍数学建模的思想及方法。图论是现代数学的一个重要分支，在自然科学、社会科学、机械工程中有重要的意义，其求解思想渗透到自然学科的各个领域。因此，可以通过设计一些与图论课程相关的课外建模活动，选择符合学生实际并贴近生活的一些图论问题，启迪学生的论文查阅意识和能力，指导学生阅读相关论文，最后以解题报告或小论文的形式提交他们的结果。促进学生应用图论知识解决实际问题的能力。
四、结语
将数学建模思想方法融入图论课程的教学中，使图论课程教学与数学建模有机结合起来，激发学生学习图论的兴趣，培养学生勇于探索的精神，提高学生的动手能力，实践表明这些方法能较好地提高图论课程的教学效果。
参考文献：
[1]Bondy J A，Murty U S R.Graph theory with applications[M].North-Holland：Elsevier，1976.
[2]翟明清.浅析图论教学[J].大学数学，2011，27（5）：23-26.
[3]定向峰.将数学建模的思想和方法融入图论课程教学中的一点尝试[J].重庆教育学院学报，2006，19（6）：28-31.
[4]张清华，陈六新，李永红.图论教育教学改革与实践[J].电脑知识与技术，2012，8（34）：8235-8237.
[5]姜启源，谢金星，叶俊.数学模型[M].第4版.北京：高等教育出版社，2011.
数学建模常用优化算法范文第5篇
关键词：蚁群算法；数学建模；最优解
1 群体智能简介
蚁群算法，英文名称：Ant Colony Optimization，（ACO），在有些文献中亦称为蚂蚁算法，由DORIGO博士从观察蚂蚁寻找食物的过程中逐步发现路径的行为而获得灵感。蚁群算法的本质是一种模拟进化算法，具有很多优良的性质，根据数值仿真实验，蚁群算法具有现实的有效性和很高的应用价值，但在熟悉蚁群算法和对蚁群建立理想模型之前，应该首先讨论群体智能的相关概念。
由于蚂蚁是一种社会化协作的昆虫，蚂蚁群体是由许多能力单一而且有限的单一蚂蚁组成的群体，但是蚂蚁的每个个体又可以通过彼此间简单的合作，完成一个较为复杂的整体性的工作，在混沌理论里，将蚂蚁种群的这种能力称为“群体智能”。和蚂蚁群体类似，蜂群的单个个体智能水平亦不高，同样没有统一的指挥，但是蜂群却可以建起巨大的蜂巢、运送食物、繁殖后代，因为蜂群和蚁群一样，都是一种拥有完备结构和社会组织的分布式系统。由于群体组织的原因，依靠单个个体，无法完成任何复杂的工作，若依靠整个群体的力量，蚂蚁可以完成非常复杂的任务。
2 蚁群算法的数学模型
虽然蚁群算法有着智能化、自组织性等诸多优点，但也存在搜索时间过长、易于停滞的问题，为了克服经典算法的这些缺点，很多国家和地区的学者提出了不少改进算法。
1996年L.M.Gambardella和M.Dorigo又提出了一种修正算法，他们称之为蚂蚁种群系统算法[5]ACS，并且将AS算法和ACS算法定义为蚂蚁种群优化算法ACO。
1997年T.Stitzle提出了改进的最大最小蚂蚁系统MMAS算法[6]。
1999年，我国学者吴庆洪提出了具有变异特性的蚁群算法[7]。
1999年，意大利学者F.Abbattista等提出了和遗传算法相结合的算法[8]。
由于文章讨论洛阳机场的飞机起降顺序问题，数据量较小，问题并不复杂，所以在算法的选择上以M.Dorigo的经典蚁群优化算法为主，下面就以基于蚁群的蚂蚁系统的算法数学模型为例，介绍经典蚁群优化算法的数学模型和优化思路，下面求解著名的n个城市的旅行商问题为例来说明经典蚁群算法模型。
2.1 问题简述
给定n个城市以及各城市间的距离，旅行商问题可以描述为求一条经过各城市一次且仅一次的最短路线问题。
2.2 模型建立
对n个城市建立理想平面坐标系，城市i的坐标为（xi，yi），城市j的坐标为（xj，yj），设dij为城市i与j之间的欧拉距离，则：
dij=■
其图论描述为：给定图G=（N，E），其中N为城市集合，E为城市之间相互连接组成的边的集合，已知城市间链接距离，要求确定一条长度最短的回路。即走完所有城市一次且仅一次的最短回路，此问题可以描述为：“适当选择图上所有顶点的一个排列以组成最短路径”
引入决策变量：
Xij=1（访问i后访问j）0（其他情况）
则目标函数可以表示为：
minZ=■Xijdij
将最短距离的寻找交给蚁群来解决：
令：
bi（t），（i=1，2，…，n）
为在时间t在城市i的蚂蚁的数目，令：
m=■bi（t）
为蚂蚁的总数，且每个蚂蚁都是有如下特征的简单智能体：
（1）它会根据某种概率选择走哪一个城市，这个概率是城市距离和同他连接路径的信息素的数量的函数。（2）为了使得蚂蚁能够完全合理的旅行，必须禁止蚂蚁旅行访问过的城市，这个可以通过一个紧急表格来实现。（3）当蚂蚁完成了一次旅行，它就在走过的每个路径上（i，j）释放适量的信息素。
令？灼ij（t）是时间t路径上（i，j）上的信息素强度。每个蚂蚁在时间t时刻选择下一个时间t+1要到达的城市，在时间间隔（t，t+1）内，对m个蚂蚁，调用蚂蚁系统迭代算法一次，算法的n次迭代叫做一圈，每一只蚂蚁完成了遍历所有城市一遍的一次旅行。在每只蚂蚁k构造出一个完整闭合路径并计算了相应长度之后（用Lk表示），路径上的信息素强度会根据以下公式得到更新：
？灼ij（t+n）=？籽×？灼ij（t）+？灼ij
其中？籽（0？燮？籽？燮1）是一个常数，它表示信息素挥发后的剩余度，即蚂蚁爬行轨迹的持久性，1-？渍表示在时间t和时间t+n内信息素的挥发，并且在上述公式里面有：
？灼ij=■？灼ijk
？灼ij（t）表示路径（i，j）在t时刻的信息素轨迹强度，？灼ijk表示蚂蚁在时间间隔（t，t+n）内路径（i，j）上留下来的单位长度的路径信息素数量，其具体公式为：
其中Q是个常数，且Lk表示没一个蚂蚁k旅行过的路径总长度。
为了确保每一只蚂蚁访问每一个节点一次，并且避免重复，没一个蚂蚁都已一个禁忌表forbidk，用来存储蚂蚁当前访问过的城市（节点），用禁忌表使蚂蚁到这些城市的转移概率为0，用计算机语言来讲，就是禁止“蚂蚁”访问这些节点。当一次旅行完成之后，用禁忌表来计算问题现在的点。然后清空禁忌表，蚂蚁就可以重新自由的选择新的路径了。forbidk（S）表示禁忌表中第s个元素，表示在现在的一次旅行中k个蚂蚁访问的第s个城市。
因为要讨论每个蚂蚁选择一个城市的概率，这里引入一个能见度的概念，用？浊ij来表示，则有：
？浊ij=■
表示路径（i，j）的能见度，对于每一个蚂蚁k来说，从城市i到城市j的额转移概率为：
在上式中allowedk={N-forbidk}，α和β是控制路径能见度相对重要性的参数，若（i，j）之间的距离比较短，则？浊ij较大，pij也较大。也就是说，距离较近的城市以较大的概率被选择。
这样就构建好了蚁群算法的基本模型。
2.3 模型解释
下面文章以计算机编程的思想表述蚁群算法的基本模型，整个系统在0时刻进行初始化过程，给每一条边（i，j）设定一个初始信息素强度值？灼ij（0）。每一只蚂蚁的forbidk的第一个元素为这个蚂蚁出发的城市，即它的初始城市。每一只蚂蚁从城市i移动到城市j，蚂蚁会根据两个城市之间的概率函数选择移动城市，在城市从i到j移动的概率即为p■■■■（t）。此时有两个原则需要注意：（1）信息素强度：表征过去有多少蚂蚁选择了这条路径（i，j）；（2）能见度函数：说明了越近的城市，被访问的期望值就越大。
显然在p■■（t）函数中，如果α=0，就不在考虑路径上的信息素的作用，因为（？灼ij（t））α=1为定常数，这样模型就简化称为一个具有多起点的随机贪心搜索算法。在n次循环以后，所有的蚂蚁都对所有的路径完成了一次遍历，所以每一只蚂蚁的forbidk就会满。在此时就可以计算每一个蚂蚁k旅行过的路径总长度Lk，？灼ijk也会随着信息素强度的更新方程而更新。与此同时，由蚂蚁找到最短路径（即minkLk，k=1，2，3，…m）将被系统保存，所有禁忌表将被清空。重复这一过程，直到周游计数器达到最大NcMax或者所有蚂蚁都走同一条路线。
3 洛阳机场飞机起顺序问题的模型建立
洛阳机场飞机起降环境比较复杂，机型众多，就目前的起飞情况来看，主要有SR20机型，PA-44机型，MA600机型，和航班的A320机型，以及少量B737机型，如果想建立数学模型，则必须将一些问题简单化、抽象化、理想化。模型的建立对实际的运营情况具有现实的指导意义。
3.1 模型描述
洛阳机场停机坪目前共分为三块区域：为了便于表述，本论文给三块区域分别编号：
1号区域：C、D、E号机库门口，主要用于停放SR20，可以用于停放PA-44但几率很少。
2号区域：A、B号机库门口至二号道口北侧停机坪，主要用于停放SR20、PA-44和MA600。
3号区域：航站楼北侧，有廊桥的区域，主要用于停放A320，
B737等重型民航客机。
标准模型下有如下假设：（1）所有停放在机坪上的飞机分布合理，即任何一架飞机划出进入跑道都是顺畅的、无阻碍的，都不会受其他飞机位置的影响。（2）每一架飞机无论是小型飞机还是中大型飞机，从飞机开始滑行至滑行到跑道端头，所花的时间t相同。即影响起飞效率的单一变量就是起飞间隔。（3）理想化起飞，飞机起飞不受环境因素限制。
标准模型下的几点说明：（1）为了考虑软件的通用性，任
何区域所停放的飞机种类可以自定义；（2）不同类型飞机的起飞间隔可以自定义；（3）涉及蚁群算法的各种常用参数可以自定义。
有以上说明后，模型可以表述如下：
假设洛阳机场1号区域停放了a1架SR20，b1架PA-44，c1架MA600/A320/B-737（可根据实际情况令相应种类的飞机数量为0）；2号区域停放了a2架SR20，b2架PA-44，c2架MA600/A320/B-737；3号区域停放了a3架SR20，b3架PA-44，c3架MA600/A320/B-737。不同种类飞机的起飞受飞机种类的限制，这个数值一般和飞机的起飞重量，体积等参数有关，例如，SR20属于轻型飞机，一架SR20起飞以后，紧接着让一架SR20飞机起飞，则前后两种都属于轻型飞机，他们之间的起飞间隔应该为t1，如果前面是一架SR20，后面是一架中型的PA-44，则起飞时间间隔为t2…t9，则一共有如表1的几种排列组合。
最终所求问题就是：合理安排各个飞机的起飞顺序，使总得起飞时间最小。
3.2 程序设计解决实际模型
考虑程序的通用性，本设计将很多涉及蚁群算法的常数参数可以进行自定义，在实际运算过程中，这些参数是可以通过实验来测算的，在使用本软件的时候只要将不同机场的测算结果进行填入本软件，既可以计算相应的排序结果，所以本软件在设计之初就考虑了软件的通用性。
洛阳机场一共有三个停机位，暂定名为1号，2号，3号停机位，原则上，1号机位只能用来停SR20，2号机位可以停SR20，PA-44，MA600，3号机位只能停A320，B737，为了增加软件的通用性，本设计可以任意自定义每种机型的数目，如果不能停的机型，就可以将其的数量设置为0。此外，为了让本软件可以有广泛的应用，本设计设置了7个停机坪号，以应付中国绝大多数机场的应用场景，同样，用不到的机坪，可以直接在飞机数目框中填0。软件设计图如图1所示。
图1 程序主界面
由前面的论述我们可知，蚁群算法在实际应用过程中要确定五个常数参数他们分别是：α，β，ρ，Q和NcMax，根据前面的理论概述，我们可以得到每个常数参数所代表的含义：（1）α和β控制路径和能见度相对重要性的参数，如果要计算具体环境走完路径的真实值，α和β应由实验测得，在本软件中，如果只做定性排序，则只要α和β大于1即可。（2）ρ表示信息素挥发后的剩余度，且0≤ρ≤1），在真实环境中同样由实验测得，定性分析不影响排序结果。（3）Q为常数，它可以决定每段路径的信息素总量，亦表征蚂蚁个体散播信息素的能力，只要Q设定为普通自然数，不影响排序结果。（4）NcMax在本软件中表示循环次数，NcMax越大，列出的可能性越多，则最短时间越接近真实最短时间。当NcMax≤A■■，继续增大NcMax就不再有意义，因此如果想得到真实的最短时间，应该让NcMax≥A■■。
点击主界面的“参数”按钮，就可以进行算法设置本。设计的参数输入框如图2所示。
表1所讨论的起飞间隔参数，在主界面的“间隔”按钮下进行设置，其截面如图3所示。
图3 起飞间隔设置
将参数设置好以后，点击“排序”按钮就可以计算出，最优的起飞顺序，并且给出起飞时间，图4为排序结果的事例。
图4
针对以上排序结果，做如下解释：L代表轻型飞机，1代表1号停机坪，A代表此停机坪的第一架飞机，B代表第二架，一次类推，则排序结果如上述所示。
4 结束语
通过多方的建模验证，本程序可以很好地解决航班起飞顺序排序最优解问题，当然，通过和空管部门有关同志的交流得知，实际安排飞机起飞顺序和多方面因素有关系，不能一味追求最短时间。因此本程序只是用创新的方法解决一个工程问题，只作为纯技术应用的讨论，或作为洛阳机场空管部门安排飞机起飞顺序的参考，并不作为安排起飞顺序的指导程序。
另外，由于软件在设计之初就考虑了软件的通用性，因此，本软件并不仅仅局限于给航班起飞顺序排序，理论上，本软件适用于解决多种有时间间隔要求的排序最优解问题。
参考文献
[1]李丽香，彭海朋，杨义先.混沌蚁群算法及应用[M].中国科学技术出版社，2003.
[2]李士勇.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社，2004.
[3]吴启迪，汪镭.智能蚁群算法及应用[M].上海：上海科技出版社，2002.
[4]马良，朱刚.蚁群优化算法[M].科技出版社，2008.
[5]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.
[6]刘浩.MATLAB R2012a完全自学一本通[M].电子工业出版社，2013.
[8]司守奎.数学建模与应用[M].长沙：国防工业出版社，2011.
