数学建模竞赛暑期培训2010(讲义)

nullnull许春根 南京理工大学应用数学系 Tel: 84315877 Email: xuchung@mail.njust.edu.cn Home Page: http://www.njustmath.net/xuchung2010年数学建模竞赛培训 建模竞赛介绍,数学软件null简要提纲 培训安排 数学建模活动介绍 数学软件介绍(Mathematica) 一、培训安排一、培训安排课表安排,第一阶段6月2-26日,第二阶段8月11-22日,第三阶段夏季短学期 考核:(按队考核,队长负责制,第一阶段结束每队定队员,第二阶段结束决定最终参赛名单) 到课情况(60分:病事假扣1分,旷课扣5分)+三次小测验(90分,每次30分)+论文考核(50分)+学校竞赛获奖加分(一等30分,二等20分,三等10分) 总分200分+奖励分 研究生另通知,有事可以请假,决定参赛后不能退出(否则,追缴报名费300元) 关注网站通知: http://www.njustmath.netnull二、数学建模活动介绍 英国物理学家伦琴回答“科学家需要什么样的修养”： “第一是数学，第二是数学，第三还是数学。” 马克思： 一门科学只有成功地运用数学时,才算达到了完善的地步。“进一步繁荣美国数学的报告 ”(1984): 高科技的出现把我们的社会推进到数学工程技术的新时 代 。 E. E. David Jr.: (Notices of AMS, v31, n2, 1984, P142) ……现今被如此称颂的“高技术”本质上是数学技术。null数学技术的重要性：广泛渗透 数学技术已经成为当代高新技术的重要组成部分 数学建模和与之相伴的科学计算正在成为众多领域中的关键工具 随着计算机技术的迅速发展，数学的应用不仅在工程技术、自然科学等领域发挥作用, 而且以空前的广度和深度向经济、金融、生物、医学、环境、地质、人口、交通等新的领域渗透 数学技术　　数学建模　＋　科学计算数学建模：数学与实际问MATCH_ word word文档格式规范word作业纸小票打印word模板word简历模板免费word简历 _1714021464364_2的桥梁数学建模：数学与实际问题的桥梁数学建模: 应用数学知识解决实际问题的第一步 数学建模: 通常有本质性的困难和原始性的创新(关键一步) Pure Math vs Applied Math: Logic vs Problem Driving “源”（Motivation）远“流”（Impact）长实际问题数学Mathematical Modeling null数学模型 (Mathematical Model) 和 数学建模（Mathematical Modeling)数学模型: 对于一个现实对象，为了一个特定目的, 作出必要的简化假设，根据对象的内在规律， 运用适当的数学工具，得到的一个数学结构。现实对象的信息数学模型现实对象的解答数学模型的解答(归纳)(演绎)数学建模的全过程null 数学建模的一般步骤模 型 准 备了解实际背景明确建模目的搜集有关信息掌握对象特征形成一个 比较清晰 的‘问题’null模 型 假 设针对问题特点和建模目的作出合理的、简化的假设在合理与简化之间作出折中模 型 构 成用数学的语言、符号描述问题发挥想象力使用类比法尽量采用简单的数学工具 数学建模的一般步骤null模型 求解各种数学方法、软件和计算机技术如结果的误差分析、统计分析、 模型对数据的稳定性分析模型 分析模型 检验与实际现象、数据比较， 检验模型的合理性、适用性模型应用 数学建模的一般步骤null数学建模教学活动的起源 教育特别是大学教育应该及时反映并满足科技和社会发展的需要 一些西方国家的大学在二十世纪六、七十年代开始开设《数学模型》或《数学建模》课程 我国在八十年代初将《数学建模》引入课堂 大学数学课程是学生掌握数学工具的主要课程、培养理性思维的重要载体和接受美感熏陶的一条途径 数学教育本质上是一种素质教育，大学数学教育的质量直接关系到一个国家大学人才培养的素质和能力null（美国大学生）数学建模竞赛(MCM) 1985年开始举办，每年一次(2月)；“国际竞赛” 我国(清华等校) 1989年开始每年参加，英文答卷 MCM-2010有14国(地区)2254队参赛，其中我国占约80%; ICM-2010有356队参赛，其中我国占约90% 每年赛题和优秀答卷刊登于同年 UMAP杂志 1999年起又同时推出交叉学科竞赛（Interdisciplinary Contest in Modeling – ICM) 网址：http://www.comap.com美国MCM+ICM竞赛规模美国MCM+ICM竞赛规模null中国大学生数学建模竞赛（CUMCM） 1992年中国工业与应用数学学会(CSIAM)开始组织 1994年起教育部高教司和CSIAM共同举办(每年9月)2009年有33省/市/区的1137所院校、15042个队参加 赛题和优秀答卷刊登于次年“数学的实践与认识”（2001年起刊登于当年“工程数学学报”） 网址：http://mcm.edu.cn 奖励：证书 （“一次参赛，终身受益”） 等级：全国一等~2%、二等~ 7%；赛区奖~1/3 我国CUMCM竞赛规模我国CUMCM竞赛规模nullnullnullnull全国研究生数学建模竞赛旨在培养研究生创新能力和团队精神 提高研究生培养质量，被列为教育部研究生教育创新计划项目之一 第四届全国研究生数学建模竞赛在2007年十月举行，包括全国29个省、市、区的170所高校和中科院研究所在内的1206队研究生报名参赛，其中博士生100多名。经评审委员会全体委员并特邀部分高校的专家教授共50多人的数天评审，按竞赛章程，评选出一等奖55队（不超过4.6%，），二等奖192队，(一、二等奖总和约占总报名队的20%)，三等奖265队，总计512队，获奖比例不超过43%. 第五届全国研究生数学建模竞赛在2008年十月顺利举行,1307队研究生报名参赛，评选出一等奖52队（不超过4%），二等奖216队，(一、二等奖总和约占总报名队的20%)，三等奖312队，总计580队，获奖比例约为44%. 第六届全国研究生数学建模竞赛在2009年十月顺利举行,本次竞赛有1662队研究生报名参赛，评选出一等奖58队（不超过3.49%），二等奖286队(一、二等奖总和约占总报名队的20.6%)，三等奖383队，总计727队，获奖比例43.7%. null竞赛内容与形式内容 赛题：工程、管理中经过简化的实际问题 答卷：一篇包含问题分析、模型假设、建立、求解(通常用计算机)、结果分析和检验等的论文形式 3名大学生组队，在3天内完成的通讯比赛 可使用任何“死”材料(图书/互联网/软件等), 但不得与队外任何人讨论（包括上网讨论）宗旨创新意识 团队精神 重在参与 公平竞争 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 假设的合理性，建模的创造性，结果的正确性，表述的清晰性。null竞赛培养实践能力、创新精神 赛题不是纯数学问题，而是由工程、经管、社会等领域的实际问题加工而成，具有很强的实用性和挑战性 赛题紧密结合科技和社会热点问题，吸引学生关心、投身国家的各项建设事业，培养理论联系实际的学风和实践能力 解决方法没有任何限制，同学可以运用自己认为合适的任何数学方法和计算机技术加以分析、解决，必须充分发挥创造力和想象力，培养了创新意识及主动学习、独立研究的能力 没有事先设定的标准答案，但留有充分余地供参赛者发挥其聪明才智和创造精神 null竞赛培养综合素质 评奖标准：假设的合理性、建模的创造性、 　　　　　 结果的正确性、表述的清晰性 信息获取能力：通讯形式，三天内同学可以自由地使用图书馆和互联网以及计算机和软件，需要学生在很短时间内获取与赛题有关的知识和能力 团队精神和组织协调能力: 三人一队，分工合作、取长补短、求同存异、相互启发、相互学习、相互争论、同舟共济 文字表达水平: 每队完成一篇用数学建模方法解决实际问题的完整的科技论文null竞赛培养综合素质 诚信意识和自律精神：开放型竞赛，三天中同学自觉地遵守竞赛纪律，不得与队外任何人（包括指导教师在内）以任何方式讨论赛题，公平竞争这项竞赛是大学阶段除毕业 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 外难得的一次 “真刀真枪”的训练，相当程度上模拟了学生毕业后工作时的情况 丰富、活跃了广大同学的课外生活 为优秀学生脱颖而出创造了条件 null赛后继续研讨三个阶段: 赛前培训阶段、竞赛阶段、赛后继续阶段 2004年的“饮酒驾车”赛题是让学生分析、估计司机饮用少量酒后多长时间驾车才符合交通规则 重庆某学校的师生与当地的交警大队联系，由交警大队安排司机做试验，学校师生进行分析，根据司机肇事时的血液酒精浓度推测他饮用了多少酒 成果在交警队得到应用 成果是重庆市“唯一”、全国应用型高校“唯一”参加第九届“挑战杯”全国大学生课外学术科技作品竞赛全国终审决赛获全国奖的“数理类”作品 null竞赛受益面 1992年74所院校314队，2009年1137所院校、15042个队 1999年起竞赛分为本科组(甲组)、专科组(乙组) 目前参赛同学90%左右来自非数学专业，其中10%左右来自人文社会科学类专业 17年来直接参加全国赛的学生超过23万人；至少有200万名学生在竞赛的各个层面上得到培养锻炼 高校普遍开设数学建模系列课程，举办校内竞赛 地区性、行业性的数学建模联赛（或邀请赛） 组织数学建模协会，约1/3被评为校优秀学生社团 两次全国性的大学生数学建模夏令营（2001; 2006） null竞赛得到各方关注与支持null竞赛得到各方关注与支持null竞赛的国际影响 我国占美国赛(MCM+ICM)参赛总队数80%左右 我国多所高校相继获得最高奖（Outstanding） 2008年在ICM的3个获最高奖的队中，两个是中国队 积极与国际同行交流：国际数学建模教学和应用会议(ICTMA) 在国际上展示了中国大学生的能力与风采，显示了中国高等教育的成就 英国等国家的专家正在研究我国的大学生数学建模竞赛及其对教学改革的推动的经验 null选修或自学数学模型课, 或参加赛前培训 2. 了解和掌握常用数学软件的基本用法 　　（ Mathematica ,Matlab,SAS, Lingo, … 另:很多有名的算法要事前编好程序,比赛时修改就可以用） 3. 了解竞赛基本信息 　（竞赛章程，特别是纪律；论文写作规范；…) 4. 参加各种类型的数学建模竞赛或模拟赛 　（校内赛，地区赛，全国赛，美国赛,…)建议：参赛前的准备竞赛活动介绍:竞赛活动介绍:学校组织的比赛： 1.校内数学建模竞赛（选拨赛通知网址：http://www.njustmath.net 2.全国大学生(研究生)数学建模竞赛（9月） China Undergraduate Mathematical Contest in Modeling (CUMCM) 网址： http://mcm.edu.cn 3.国际（美国）大学生数学建模竞赛（2月份） The Mathematical Contest in Modeling (MCM) 网址：http://www.comap.com/undergraduate/contests/ null预备知识: 微积分(或高等数学)、线性代数、微分方程、概率论、计算机基础等。 参考书: 数学模型(第三版) 姜启源编 高等教育出版社 重点掌握内容: 优化,统计,计算 学习参考网站： 数学中国:http://www.madio.net/ 中国数学建模：http://www.shumo.com/ nullCUMCM评阅标准清晰性：摘要应理解为详细摘要，提纲挈领 表达严谨、简捷，思路清新 格式符合规范，严禁暴露身份创造性：特别欣赏独树一帜、标新立异，但要合理假设的合理性，建模的创造性， 结果的正确性，表述的清晰性。正确性：不强调与“参考答案”的一致性和结果的精度； 好方法的结果一般比较好；但不一定是最好的合理性：关键假设；不欣赏罗列大量无关紧要的假设 nullCUMCM评阅标准: 一些常见问题有的论文过于简单，该交代的内容省略了，难以看懂有的队罗列一系列假设或模型，又不作比较、评价， 希望碰上“参考答案”或“评阅思路”，弄巧成拙数学模型最好明确、合理、简洁： 有些论文不给出明确的模型，只是根据赛题的情况， 实际上是用“凑”的方法给出结果，虽然结果大致是对 的，没有一般性，不是数学建模的正确思路。有的论文参考文献不全，或引用他人结果不作交代null从论文评阅看学生参加竞赛中的问题 吃透题意方面不足，没有抓住和解决主要问题； 就事论事，形成数学模型的意识和能力欠缺； 对所用方法一知半解，不管具体条件，套用现成的方法，导致错误； 对结果的分析不够，怎样符合实际考虑不周； 写作方面的问题(摘要、简明、优缺点、参考文献); 队员之间合作精神差，孤军奋战； 依赖心理重，甚至违纪（指导教师、 网络）。小结： CUMCM评阅标准小结： CUMCM评阅标准模型完整明确 模型/算法创新 软件使用恰当假设的合理性，建模的创造性， 结果的正确性，表述的清晰性。深入思考/分析 表达规范严谨 严禁作弊抄袭null数学建模竞赛CUMCM近年题目null全国研究生数学建模竞赛历年题目nullCUMCM题目特点题目来源: 实际研究课题的简化、改编；有实际背景问题的编撰；合适的社会热点（或兴趣）问题题目背景尽量通俗易懂，涉及的专业知识不深题目需要的数学知识一般不超过本科的三门主干课（非数学专业）内容及统计、优化、计算等基本方法；专科题目力求少用大学数学内容解题所用的数学方法尽量多元化、综合化可以查阅到一些参考材料，但是无法照搬现成文献兼顾数据的处理与数据的收集二、数学软件介绍二、数学软件介绍数学建模一般借助于数学软件. 如：Mathematica、 Matlab、Maple、SAS、MathCAD S Plus… nullMathematica窗口简介Mathematica的画图功能Mathematica的画图功能null数学软件的种类及其特点数学软件的种类及其特点通用符号计算软件 通用数值运算软件 专业软件 计算程序库 教学、演示类软件符号计算软件符号计算软件Mathematica Maple Reduce MuMath Derive Eureke数值运算软件数值运算软件MATLAB MathCAD专业软件专业软件统计软件：SAS、SPSS 线性规划：Lindo 非线性规划: Lingo ... 有限元计算：ANSYS、SAP 神经网络：Neural Work Professional数学软件的应用数学软件的应用大规模运算 数值实验 辅助教学 Mathematica的基本功能Mathematica的基本功能数值运算（Numeric Computation） 符号运算（Algebric Computation） 图像处理（Graphics ） 语言功能（Programing Language)Mathematica在数学建模中的 应用举例Mathematica在数学建模中的 应用举例迭代计算与绘图 求最大、最小值 复杂积分的计算 微分方程的求解 方程[组)的求解、矩阵运算Matlab6.0窗口简介 Matlab6.0窗口简介 MATLAB是基于矩阵的一种计算工具，它已经成为世界各国高校和研究人员中最为流行的软件之一。它提供了丰富可靠的矩阵运算、数据处理、图形绘制、图像处理等便利工具，并且由于Matlab的广泛应用，很多理论的创始人在MATLAB上开发了相关的工具箱，现在MATLAB附带的各方面工具箱有：控制系统、通讯、符号运算、小波计算、偏微分方程、数据统计、图像、金融、LMI控制、QFT控制、数字信号处理、模糊控制、模型预估控制、频域辨识、高阶谱分析、统计学、非线性控制系统、图像处理、神经元网络、m 分析、信号处理、插值、优化、鲁棒控制、控制系统设计、系统辨识等等，并且MATLAB提供了图形化的时域仿真程序----Simulink，在高校中还开发有：振动理论、化学统计学、语音处理等等方面的工具箱。 初识Mathematica初识MathematicaMathematica的计算 函数图象:画函数 y=f(x) 在区间[a,b] 上的图象的语句: Plot [ f [x], {x,a,b} ] null sin(x)及其Tylor逼近。 sin(x)+sin(3x)/3+… sin(1/x)在x=0附近的性状。Sin(x) 及其 Tylor 逼近 Sin(x) 及其 Tylor 逼近 sin x+sin3x/3+…+sin nx/nsin x+sin3x/3+…+sin nx/n彩色图象彩色图象 Plot[f[x],{x,a,b}, PlotStyle -> {RGBColor[1,0,0]} ] RGBColor 表示红、绿、蓝三色的比例。求根、求最小值求根、求最小值 FindRoot[f[x],{x,a}] 求f(x)在 x=a 附近的根。 FindMinimum[f[x],{x,a}] 求f(x)在 x=a 附近的最小值点。Sin (1/x) 在 x=0 附近Sin (1/x) 在 x=0 附近画数据点集合画数据点集合d=Table[{1/n,Sin[n]}, {n,1,1000}] (定义点集） ListPlot[d] （画出点集） Show[fg1,fg2] (几个图象重新显示在同一坐标系里）nullSum[f[k],{k,1,n}] (求和） Product[f[k],{k,1,n}] (求积） f[x_,n_]:= (定义 x,n 的函数） Table[{1/n,Sin[n]}, {n,1,10000}] Table[{1/n,Sin[n]}, {n,1,10000}]null 附：几个例子A Joke: “Find x”A Joke: “Find x”“I can’t believe the teacher marked him wrong, he found it.”http://haha.nu/funny/funny-math/Another Joke: “Find x”Another Joke: “Find x”“Smart enough!”http://haha.nu/funny/funny-math/null0yxVOR2 x=629, y=375309.00 (1.30)864.3(2.0)飞机 x=?, y=?VOR1 x=764, y=1393161.20 (0.80)VOR3 x=1571, y=25945.10 (0.60)北DME x=155, y=987图中坐标和测量距离 的单位是“公里”案例: 飞机的精确定位问题 ［参考资料］谢金星、薛毅编著， 《优化建模与lindo/lingo软件》，请华大学出版社, 2005null飞机的精确定位模型null飞机的精确定位模型第1类模型: 不考虑误差因素超定方程组----非线性最小二乘！量纲不符！ or ？ ？ null飞机的精确定位模型第2类模型: 考虑误差因素(作为硬约束)Min x; Min y; Max x; Max y.非线性规划！ ？ ？ 仅部分考虑误差! 角度与距离的“地位”为何不同？其他： 误差非均匀分布！ 不等式组？null飞机的精确定位模型误差一般服从什么分布？正态分布！不同的量纲如何处理？无约束非线性最小二乘模型归一化处理！shili0702.m飞机坐标(978.31，723.98), 误差平方和0.6685 (<< 4) 角度需要进行预处理，如利用 Matlab的atan2函数, 值域(-pi, pi)第3类模型: 考虑误差因素(作为软约束); 且归一化null飞机的精确定位模型小技巧: LINGO中没有atan2函数, 怎么办？可以直接利用@tan函数！exam0507c.lg4同前面的模型/结果飞机坐标(980.21，727.30 ), 误差平方和2.6 与前面的结果有所不同, 为什么? 哪个模型合理些?最后: 思考以下模型:exam0507d.lg4null例 CUMCM-2000B 钢管订购和运输null钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）601 = 300 + 301 44 > 20 + 23 ?null（1）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？（3）讨论管道为树形图的情形null问题1的基本模型和解法总费用最小的优化问题总费用：订购，运输（由各厂Si经铁路、公路至各点Aj, i=1,…7; j=1, …15 ），铺设管道Aj Aj+1 （j=1, …14)由Si至Aj的最小购运费用路线及最小费用cij 由Si至Aj的最优运量xij 由Aj向Aj Aj-1段铺设的长度yj及向Aj Aj+1段铺设的长度zj最优购运计划约束条件钢厂产量约束：上限和下限（如果生产的话） 运量约束：xij对i求和等于zj 加yj； zj与 yj+1之和等于Aj Aj+1段的长度ljyj zjAjnull基本模型由Aj向Aj Aj-1段铺设的运量为 1+ … +yj= yj( yj+1)/2由Aj向Aj Aj+1段铺设的运量为 1+ … +zj= zj( zj+1)/2二次规划？null求解步骤1）求由Si至Aj的最小购运费用路线及最小费用cij 难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。A1需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。-- 至少求3次最短路如S7至A10的最小费用路线先铁路1130km，再公路70km, 运费为77（万元）先公路（经A15）40km, 再铁路1100km，再公路70km, 运费为76（万元）null实际上只有S4和S7需要分解成子问题求解每个子问题是标准的二次规划，决策变量为xij,yj,zj, 不超过135个 。nullfi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量 yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量 c) 比较好的方法：引入0-1变量LINDO/LINGO得到的结果比matlab得到的好yj zjjnull问题1的其它模型和解法1）运输问题的0-1规划模型将全长5171km的管道按公里分段，共5171个需求点，钢厂为7个供应点，构成如下的运输问题cij为从供应点i到需求点j的最小购运费xij=1表示从点i到点j购运1单位钢管求解时要针对规模问题寻求改进算法null2）最小费用网络流模型线性费用网络(只有产量上限)非线性费用网络(只有产量上限)边的标记（流量上限，单位费用）用标准算法(如最小费用路算法)求解无单位费用概念(f(f+1)/2), 需修改最小费用路算法null2）最小费用网络流模型产量有下限ri时的修正注：该模型获当年的惟一最高奖（网易杯）null3) 最小面积模型作图：Si到管道x单位钢管的最小购运费用c由各条Si首尾相连(横坐标)组成的一条折线对应一个购运方案，折线下面的面积对应方案的费用在产量约束下找面积最小的折线null问题2: 分析对购运计划和总费用影响(哪个钢厂销价变化影响最大；哪个钢厂产量上限变化影响最大)规划问题的灵敏度分析问题3：管道为树形图(jk)是连接Aj,Ak的边，E是树形图的边集， ljk是(jk)的长度， yjk是由Aj沿(jk)铺设的钢管数量null论文中发现的主要问题1）针对题目给的数据用凑的方法算出结果，没有解决这类问题的一般模型2）局部最优，如将管道分为左右两段，分别寻求方案；如将问题分为购运和铺设两部分，分别寻优（会导致每段管道都从两端铺到中点）4）由Si至Aj的最小购运费用路线及最小费用cij 不对5）数字结果相差较大(如最小费用应127.5至128.2亿元)null数学建模讲座 CUMCM-2007B (乘公交，看奥运) 赛题分析2007B命题背景 2007B命题背景 奥运相关的题目：(时代特性, 社会关注） 让运动员及时到达场馆（车辆调度，路径安排等） 应急管理（紧急疏散，应急调度等） 赛程安排（单一项目，多个项目） 成绩排名（如循环赛，体操或跳水等） 技术类，如“刘翔的运动鞋” 乘公交，看奥运：原名“自动问路机” 方沛辰（吉大），吴孟达（国防科大）提出 原拟作乙组题，似乎难度太大命题背景 命题背景 定位：公交路线选择（查询）模型与算法 如何给数据？ 抽象数据／实际数据？（减小规模，不给地理信息） 貌似简单，实则不然 数据处理（转换）方面有一定难度 换乘次数多时简单搜索不易（计算复杂度高） 换乘时间／步行时间等需要考虑周全 标准的最短路算法（如Dijkstra算法）并不适用乘公交，看奥运乘公交，看奥运公交线路选择问题的自主查询计算机系统：核心是线路选择的模型与算法 应该从实际情况出发考虑，满足查询者的各种不同需求 1: 仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法 2: 同时考虑公汽与地铁线路，解决以上问题 3: 假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型 null　【附录1】基本参数设定 相邻公汽站平均行驶时间(包括停站时间)： 3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元 地铁票价：3元（无论地铁线路间是否换乘） 推论：换乘公汽等待３分钟，换乘地铁等待２分钟 　【附录2】公交线路及相关信息 （见数据文件）线路数据中的问题线路数据中的问题　线路数据中的异常或不明确之处，同学可根据自己的理解作出假设和处理，一般不会影响实例的计算结果 个别线路相邻站点名相同，可去掉其中一点或不作处理等 L406未标明是环线，是否将其当作环线处理均可 L290标明是环线，但首尾站点分别为1477与1479，可将所有线路中1477与1479统一为1477后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将1479改为1477，或在1479后增加1477，等等 如果在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些） 对通过地铁换乘的理解对通过地铁换乘的理解“假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)”　 步行：公汽站地铁站（通道）公汽站 换乘耗时11min：步行4+4=8min; 等车3min 第１问（只考虑公汽）：可不考虑以上换乘 有同学也考虑了如上换乘，只是不坐地铁，应该也可以 此样处理时，第１问和第２问的难度相近模型的目标模型的目标多目标优化问题（至少考虑三方面） 换乘次数最少(N)、费用最省(M)、时间最短(T) 从该问题的实际背景来看，加权太合适 不少同学用层次分析法确定权 不少同学计算时间的价值（平均收入／工作时间） 不同目标组合的模型 三个目标按优先级排序，组合成六个模型 也可将某些目标作为约束多数队仅采用搜索法（70-80%?）多数队仅采用搜索法（70-80%?）直达； 　一次换乘；　 二次换乘；　…s ts ts t求出所有线路；评价其目标(容易计算)；选优 多数队仅采用搜索法多数队仅采用搜索法总体来看，技术含量较低（基本上是枚举） 几乎没有建模，完全只有算法实现，算法也没什么创新 一般只考虑不超过两次换乘 不少文章引用参考文献作为依据，实用中似乎够用 题目难度大大降低，模型不够一般 换乘作为了第一目标，或作为一个最重要的约束 任意次换乘时算法复杂度提高，难以处理 结果不佳（如：从省时考虑，有些需３－４次换乘）图论模型与最短路算法图论模型与最短路算法用图论做的队也不少，但往往考虑不周 弧上赋权方式交代不清 套用Dijkstra或Floyd-Warshall算法，却不清楚其原理及适用的问题 需要建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价(时间或费用) 图（网络）如何描述和表示？ 基本要素：节点，有向弧（边），弧上赋权 邻接矩阵；关联矩阵（数学上处理方便，存储量较大） 链表（存储量较小，计算机上处理方便）关联矩阵(Incidence Matrix)表示法关联矩阵(Incidence Matrix)表示法在线路选择问题中，当从i可直达j时，定义弧(i,j)；其上的权可为１或成本(时间或费用)；多重弧可只保留一条（弧上的权可取最小的成本，如时间或费用）G=(V，A)是一个简单有向图；|V|=n，|A|=m 重要数学性质：关联矩阵是全幺模矩阵图G=(V，A)的邻接矩阵C是如下定义的：C是一个 的矩阵，即邻接矩阵(Adjacency Matrix)表示法邻接矩阵(Adjacency Matrix)表示法图G=(V，A)的邻接矩阵C是如下定义的：C是一个 的0-1矩阵，即在线路选择问题中，当从i可直达j时，定义弧(i,j)；其上的权可为１或成本(时间或费用)G=(V，A)是一个简单有向图；|V|=n，|A|=m 有向图的“传递闭包算法”　(可用于一般二元关系) 权取0-1时，C(0)=C可称为直达矩阵 ；C(1)=C*C 为１次可达矩阵；C(2)=C(1)*C 为2次可达矩阵；……链表（邻接表）表示法 链表（邻接表）表示法 单向链表(指针数组) A(1)={2,3}A(2)={4}A(3)={2}A(4)={3,5}A(5)={3,4}nullDijkstra算法（标号算法，1959）STEP1. 如果S=V, 则uj为节点s到节点j的最短路路长(最短路可以通过数组pred所记录的信息反向追踪获得), 结束.否则继续. 特点：1. 算法求出从源点s到所有点的最短路长 2. 每点给一对标号 (uj, predj)，uj是从s到j的最短路长；predj是从s到j的最短路中j点的前一点ExampleExamplenullDijkstra算法（标号设定算法）适用于正费用网络：“分层”设定标号 永久标号：S中的点，uj是最短路长 临时标号；其他点， uj是只通过S中的点的最短路长Floyd-Warshall算法 （标号修正算法，1962)　特点：求所有点对间最短路 　基本思想：逐步逼近，迭代求解最短路方程: O(n3)Floyd-Warshall算法 （标号修正算法，1962)Floyd-Warshall算法的具体实现: O(n3)Floyd-Warshall算法的具体实现: O(n3)由于要记录所有节点之间最短路的信息, 所以这里我们要用一个二维数组P； 可依据P, 采用“正向追踪”的方式得到最短路. STEP2：如果k=n, 结束; 否则转STEP1. Floyd-Warshall算法的 矩阵迭代法实现：O(n4)Floyd-Warshall算法的 矩阵迭代法实现：O(n4)令D为权矩阵(直达最短路长) Dm为正好经过m条弧从i到j的最短路长问题1和2的一种具体建模方法(赋权)问题1和2的一种具体建模方法(赋权)在线路选择问题中，当从i可直达j时（同为公汽或地铁站点），定义弧(i,j)；其上的权为lij表示由i直达j付出的代价，可以为时间或费用 (不包括换乘代价；多条线路可达时只保留最小代价) 初始等车时间2(3)min也不包括在内，最后结果可加上 注意：D=D(0)不是对称矩阵(“直达矩阵”)dij(0)=dij 问题１－２的一种具体建模方法问题１－２的一种具体建模方法i站点是公汽站点，j站点为地铁站点：（1）若j站点对应的所有换乘(公汽)站点k，均不能从i直达(不在i站点所在公汽线路L上)，则dij(0) =∞. （2）若j站点对应的换乘站点(k), 可从i站点直达k，则费用为dij(0) = dik(0)；对于时间则需要加上k到j的步行时间. (若有多种选择，取最小成本者即可)ikj问题１－２的一种具体建模方法问题１－２的一种具体建模方法j站点是公汽站点，i站点为地铁站点：（1）若从i站点对应的任何换乘(公汽)站点k，均不能直达j站点，则dij(0) =∞. （2）若从i站点对应的换乘(公汽)站点k，能直达j站点， 则费用为dij(0) = dkj(0)；对于时间则需要加上i到k的步行时间. ikj问题１－２：最小费用或时间问题１－２：最小费用或时间 定义矩阵算子“⊙”如下：设A、B均为n阶方阵， C = A ⊙ B (考虑换乘代价) D(k)= D(k-1) ⊙ D 表示k次换乘的最低代价(费用或时间) 该算法大体相当于求最短路的Floyd-Warshall算法，但考虑了换乘因素，可称为改进Floyd-Warshall算法 类似地,　通过修改Dijkstra算法求解也可问题１－２：最小费用或时间问题１－２：最小费用或时间δi,j,k表示换乘时间 i = j 或k = i，j时，δi,j,k = 0 其他情形： 　　若不可换乘(当i ，j为公汽站点而k为地铁站点，或者i ，j为地铁站点而k为公汽站点时)，则 δi,j,k = 0 　　若可换乘，则k这只是等待时间，因为步行时间已在D中考虑了ij第３问：已知所有站点间步行时间第３问：已知所有站点间步行时间多数队没有给出一般模型, 而只考虑最多一次换乘 多数队的想法：假设“起点步行”，“换乘步行”，“终点步行”三种模式，限定步行最大时间后搜索ikj其他：最短路问题的线性规划模型其他：最短路问题的线性规划模型xij表示弧（i，j）是否位于s-t路上：当xij =1时，表示弧（i，j）位于s-t路上，当xij =0时，表示弧（i，j）不在s-t路上. 关联矩阵是全么模矩阵，因此0-1变量可以松弛为区间[0,1]中的实数 不含负圈，变量直接松弛为所有非负实数思考：为什么xij 可以不限定为{0，1} (0-1规划) ?最短路问题的线性规划模型最短路问题的线性规划模型　线性规划模型，应该可以计算到比较大规模的问题 　有些队写出了上述模型，但并未用该模型求解 　可能需要强大的优化软件，数据输入工作量也较大 　换乘代价不易考虑（网络上的权不易定义，或不具可加性） 有些同学提到动态规划, 但要么与这里介绍的最短路算法等价, 要么处理有误, 或只是搜索法的变种有些队讨论“交通阻抗”:“文不对题”有些队讨论“交通阻抗”:“文不对题”道路阻抗在交通流分配中可以通过路阻函数来描述 所谓路阻函数是指路段行驶时间与路段交通负荷，交叉口延误与交叉口负荷之间的关系 在具体分配过程中，由路段行驶时间及交叉口延误共同组成出行交通阻抗 交通网络上的路阻，应包含反映交通时间、交通安全、交通成本、舒适程度、便捷性和准时性等等许多因素同学论文中存在的主要问题同学论文中存在的主要问题2. 目标不当，或不完整 3. 换乘时间处理不当 尤其地铁站与公汽站之间，以及 通过地铁通道换乘的公汽站之间1. 几乎没有模型，只有算法（一般是搜索法）4. 算法使用不当，或滥用5. 对第３问，很少认真进行讨论和建模6. 全文 企业安全文化建设方案企业安全文化建设导则安全文明施工及保证措施创建安全文明校园实施方案创建安全文明工地监理工作情况 表达不清，思路混乱