数学建模竞赛评阅标准

数学建模竞赛评阅标准第一页，共八十九页，编辑于2023年，星期三简要提纲数学建模的重要性-----数学建模竞赛的起源与发展竞赛对大学生综合素质的促进作用-----创新能力/实践能力/团队精神等竞赛的广泛影响竞赛评阅标准（重点介绍）-----一般原则及几个例子第二页，共八十九页，编辑于2023年，星期三数学的重要性：众所周知英国物理学家伦琴回答“科学家需要什么样的修养”：

“第一是数学，第二是数学，第三还是数学。”马克思：一门科学只有成功地运用数学时,才算达到了完善的地步。“进一步繁荣美国数学的报告

”(1984):高科技的出现把我们的社会推进到数学工程技术的新时代。E.E.DavidJr.:(NoticesofAMS,v31,n2,1984,P142)……现今被如此称颂的“高技术”本质上是数学技术。第三页，共八十九页，编辑于2023年，星期三数学技术的重要性：广泛渗透数学技术已经成为当代高新技术的重要组成部分数学建模和与之相伴的科学计算正在成为众多领域中的关键工具

随着计算机技术的迅速发展，数学的应用不仅在工程技术、自然科学等领域发挥作用,而且以空前的广度和深度向经济、金融、生物、医学、环境、地质、人口、交通等新的领域渗透

数学技术数学建模＋科学计算第四页，共八十九页，编辑于2023年，星期三既要学好“算数学”,更要培养“用数学”的能力利用计算机和数学软件,培养分析、思考能力感受“用数学”的酸甜苦辣,激发学好数学的愿望数学的重要性：似是而非？不少同学（甚至社会）的反映：----无用----难学原因：很少用；用不好最常用的大学数学内容有哪些?第五页，共八十九页，编辑于2023年，星期三纯粹数学(PureMath)–基础/核心(Core)数学？应用数学(AppliedMath)计算数学(ComputationalMath)概率论与数理统计–随机/统计数学？运筹学(OR)与控制论–运筹数学？数学的二级学科(研究生专业)应用数学

Core具体应用学科具体应用学科应用数学应用数学第六页，共八十九页，编辑于2023年，星期三数学建模：数学与实际问题的桥梁数学建模:应用数学知识解决实际问题的第一步数学建模:通常有本质性的困难和原始性的创新(关键一步)PureMathvsAppliedMath:LogicvsProblemDriving“源”（Motivation）远“流”（Impact）长实际问题数学MathematicalModeling

第七页，共八十九页，编辑于2023年，星期三数学模型(MathematicalModel)和数学建模（MathematicalModeling)数学模型:对于一个现实对象，为了一个特定目的,作出必要的简化假设，根据对象的内在规律，运用适当的数学工具，得到的一个数学结构。现实对象的信息数学模型现实对象的解答数学模型的解答表述求解解释验证(归纳)(演绎)数学建模的全过程第八页，共八十九页，编辑于2023年，星期三数学知识数学技巧数学应用数学发现……应用数学数学技术数学实验……随机数学代数与几何微积分……数学美学数学哲学数学精神数学素质数学文化数学：几个层次的理解第九页，共八十九页，编辑于2023年，星期三数学：科学的皇后与仆人自然科学（理学）工程技术科学（工学）人文社会科学其他科学思维科学（哲学）

数学？第十页，共八十九页，编辑于2023年，星期三数学建模教学活动的起源教育特别是大学教育应该及时反映并满足科技和社会发展的需要一些西方国家的大学在二十世纪六、七十年代开始开设《数学模型》或《数学建模》课程我国在八十年代初将《数学建模》引入课堂大学数学课程是学生掌握数学工具的主要课程、培养理性思维的重要载体和接受美感熏陶的一条途径

数学教育本质上是一种素质教育，大学数学教育的质量直接关系到一个国家大学人才培养的素质和能力第十一页，共八十九页，编辑于2023年，星期三（美国大学生）数学建模竞赛(MCM)1985年开始举办，每年一次(2月)；“国际竞赛”我国(清华等校)1989年开始每年参加，英文答卷MCM-2008有约10国(地区)1164队参赛，其中我国占73%;ICM-2008有380队参赛，其中我国占93%每年赛题和优秀答卷刊登于同年UMAP杂志1999年起又同时推出交叉学科竞赛（InterdisciplinaryContestinModeling–ICM)

网址：第十二页，共八十九页，编辑于2023年，星期三美国MCM+ICM竞赛规模第十三页，共八十九页，编辑于2023年，星期三中国大学生数学建模竞赛（CUMCM）1992年中国工业与应用数学学会(CSIAM)开始组织1994年起教育部高教司和CSIAM共同举办(每年9月)2008年有31省/市/区的1022所学校12836队参加赛题和优秀答卷刊登于次年“数学的实践与认识”（2001年起刊登于当年“工程数学学报”）网址：奖励：证书（“一次参赛，终身受益”）等级：全国一等~2%、二等~7%；赛区奖~1/3第十四页，共八十九页，编辑于2023年，星期三我国CUMCM竞赛规模第十五页，共八十九页，编辑于2023年，星期三简要提纲数学建模的重要性-----数学建模竞赛的起源与发展竞赛对大学生综合素质的促进作用-----创新能力/实践能力/团队精神等竞赛的广泛影响竞赛评阅标准-----竞赛准备及一些注意事项第十六页，共八十九页，编辑于2023年，星期三我国传统数学教育的不足内容相对陈旧、体系单一、知识面窄、偏重符号演算和解题技巧、脱离实际应用

我国传统的数学教育在培养学生逻辑思维、演算能力等方面有优良的传统和较好的基础，值得保持发扬

缺乏应用数学知识解决实际问题的实践意识和能力创新精神和创新能力不足教学方式单一，“满堂灌”，效果差应试为主，学习自主性不强，学习动力不足第十七页，共八十九页，编辑于2023年，星期三竞赛内容与形式内容赛题：工程、管理中经过简化的实际问题答卷：一篇包含问题分析、模型假设、建立、求解(通常用计算机)、结果分析和检验等的论文形式3名大学生组队，在3天内完成的通讯比赛可使用任何“死”材料(图书/互联网/软件等),但不得与队外任何人讨论（包括上网讨论）宗旨创新意识团队精神重在参与公平竞争标准假设的合理性，建模的创造性，结果的正确性，表述的清晰性。第十八页，共八十九页，编辑于2023年，星期三竞赛培养实践能力、创新精神赛题不是纯数学问题，而是由工程、经管、社会等领域的实际问题加工而成，具有很强的实用性和挑战性赛题紧密结合科技和社会热点问题，吸引学生关心、投身国家的各项建设事业，培养理论联系实际的学风和实践能力

解决方法没有任何限制，同学可以运用自己认为合适的任何数学方法和计算机技术加以分析、解决，必须充分发挥创造力和想象力，培养了创新意识及主动学习、独立研究的能力

没有事先设定的标准答案，但留有充分余地供参赛者发挥其聪明才智和创造精神

第十九页，共八十九页，编辑于2023年，星期三竞赛培养综合素质评奖标准：假设的合理性、建模的创造性、结果的正确性、表述的清晰性

信息获取能力：通讯形式，三天内同学可以自由地使用图书馆和互联网以及计算机和软件，需要学生在很短时间内获取与赛题有关的知识和能力

团队精神和组织协调能力:三人一队，分工合作、取长补短、求同存异、相互启发、相互学习、相互争论、同舟共济

文字表达水平:每队完成一篇用数学建模方法解决实际问题的完整的科技论文第二十页，共八十九页，编辑于2023年，星期三竞赛培养综合素质诚信意识和自律精神：开放型竞赛，三天中同学自觉地遵守竞赛纪律，不得与队外任何人（包括指导教师在内）以任何方式讨论赛题，公平竞争这项竞赛是大学阶段除毕业设计外难得的一次“真刀真枪”的训练，相当程度上模拟了学生毕业后工作时的情况丰富、活跃了广大同学的课外生活为优秀学生脱颖而出创造了条件

第二十一页，共八十九页，编辑于2023年，星期三赛后继续研讨三个阶段:赛前培训阶段、竞赛阶段、赛后继续阶段2004年的“饮酒驾车”赛题是让学生分析、估计司机饮用少量酒后多长时间驾车才符合交通规则重庆某学校的师生与当地的交警大队联系，由交警大队安排司机做试验，学校师生进行分析，根据司机肇事时的血液酒精浓度推测他饮用了多少酒成果在交警队得到应用成果是重庆市“唯一”、全国应用型高校“唯一”参加第九届“挑战杯”全国大学生课外学术科技作品竞赛全国终审决赛获全国奖的“数理类”作品

第二十二页，共八十九页，编辑于2023年，星期三赛后继续研讨2006年赛题“出版社的资源配置”由高教社提供的素材形成高教社特别批准了与该题相关的研究项目，吸取竞赛优秀论文的创意和一些大学生参加，进行实用研究

“一次参赛，终生受益”

学生主动学习和科研能力明显提高，不少人免试读研，在专业课学习、毕业设计、研究生阶段的学习以及进入社会后的发展中表现出明显的优势，得到用人单位和研究生导师的普遍欢迎和认可

第二十三页，共八十九页，编辑于2023年，星期三简要提纲数学建模的重要性-----数学建模竞赛的起源与发展竞赛对大学生综合素质的促进作用-----创新能力/实践能力/团队精神等竞赛的广泛影响竞赛评阅标准-----竞赛准备及一些注意事项第二十四页，共八十九页，编辑于2023年，星期三竞赛受益面1992年74所院校314队，2008年1000多所院校12800多队1999年起竞赛分为本科组(甲组)、专科组(乙组)

目前参赛同学90%左右来自非数学专业，其中10%左右来自人文社会科学类专业17年来直接参加全国赛的学生超过23万人；至少有200万名学生在竞赛的各个层面上得到培养锻炼

高校普遍开设数学建模系列课程，举办校内竞赛地区性、行业性的数学建模联赛（或邀请赛）

组织数学建模协会，约1/3被评为校优秀学生社团两次全国性的大学生数学建模夏令营（2001;2006）

第二十五页，共八十九页，编辑于2023年，星期三学生欢迎：“一次参赛，终身受益”研究生导师们的认同企业界的认同／赞助教育改革同行的认同：“成功范例”国际同行的认同竞赛的反响第二十六页，共八十九页，编辑于2023年，星期三IBM中国研究中心-招聘条件Positiontitle:BusinessOptimization(BJ)

1．Backgroundinindustrialengineering,operationsresearch,mathematics,ArtificialIntelligence,managementscienceetc.

2.Knowledgeinnetworkdesign,jobscheduling,dataanalysis,simulationandoptimization

3.Awardinmathematicalcontestinmodelingisaplus

4.Experienceinindustryisaplus

5.Experienceineclipseorprogrammingmodel/architecturedesignisaplus

--Feb.18,2006,/cn/ibm/crl/careers/condition.shtml竞赛的反响（一例）第二十七页，共八十九页，编辑于2023年，星期三竞赛的国际影响我国占美国赛(MCM+ICM)参赛总队数80%左右我国多所高校相继获得最高奖（Outstanding）2008年在ICM的3个获最高奖的队中，两个是中国队积极与国际同行交流：国际数学建模教学和应用会议(ICTMA)在国际上展示了中国大学生的能力与风采，显示了中国高等教育的成就英国等国家的专家正在研究我国的大学生数学建模竞赛及其对教学改革的推动的经验第二十八页，共八十九页，编辑于2023年，星期三简要提纲数学建模的重要性-----数学建模竞赛的起源与发展竞赛对大学生综合素质的促进作用-----创新能力/实践能力/团队精神等竞赛的广泛影响竞赛评阅标准-----竞赛准备及一些注意事项第二十九页，共八十九页，编辑于2023年，星期三选修或自学数学模型课,或参加赛前培训2.了解和掌握常用数学软件的基本用法（Matlab/Mathematica,Lingo,…）3.了解竞赛基本信息（竞赛章程，特别是纪律；论文写作规范；…)4.参加各种类型的数学建模竞赛或模拟赛（校内赛，地区赛，全国赛，美国赛,…)建议：参赛前的准备第三十页，共八十九页，编辑于2023年，星期三CUMCM评阅标准清晰性：摘要应理解为详细摘要，提纲挈领

表达严谨、简捷，思路清新格式符合规范，严禁暴露身份创造性：特别欣赏独树一帜、标新立异，但要合理假设的合理性，建模的创造性，结果的正确性，表述的清晰性。正确性：不强调与“参考答案”的一致性和结果的精度；好方法的结果一般比较好；但不一定是最好的合理性：关键假设；不欣赏罗列大量无关紧要的假设第三十一页，共八十九页，编辑于2023年，星期三CUMCM评阅标准:一些常见问题有的论文过于简单，该交代的内容省略了，难以看懂有的队罗列一系列假设或模型，又不作比较、评价，希望碰上“参考答案”或“评阅思路”，弄巧成拙数学模型最好明确、合理、简洁：有些论文不给出明确的模型，只是根据赛题的情况，实际上是用“凑”的方法给出结果，虽然结果大致是对的，没有一般性，不是数学建模的正确思路。有的论文参考文献不全，或引用他人结果不作交代第三十二页，共八十九页，编辑于2023年，星期三从论文评阅看学生参加竞赛中的问题吃透题意方面不足，没有抓住和解决主要问题；就事论事，形成数学模型的意识和能力欠缺；对所用方法一知半解，不管具体条件，套用现成的方法，导致错误；对结果的分析不够，怎样符合实际考虑不周；写作方面的问题(摘要、简明、优缺点、参考文献);队员之间合作精神差，孤军奋战；依赖心理重，甚至违纪（指导教师、网络）。第三十三页，共八十九页，编辑于2023年，星期三附：几个例子第三十四页，共八十九页，编辑于2023年，星期三AJoke:“Findx”“Ican’tbelievetheteachermarkedhimwrong,hefoundit.”http://haha.nu/funny/funny-math/第三十五页，共八十九页，编辑于2023年，星期三AnotherJoke:“Findx”“Smartenough!”http://haha.nu/funny/funny-math/第三十六页，共八十九页，编辑于2023年，星期三0yxVOR2x=629,y=375309.00(1.30)864.3(2.0)飞机x=?,y=?VOR1x=764,y=1393161.20(0.80)VOR3x=1571,y=25945.10(0.60)北DMEx=155,y=987图中坐标和测量距离的单位是“公里”案例:飞机的精确定位问题［参考资料］谢金星、薛毅编著，《优化建模与lindo/lingo软件》，请华大学出版社,2005第三十七页，共八十九页，编辑于2023年，星期三飞机的精确定位模型xiyi原始的(或d4）VO20（2.81347弧度）0.80（0.0140弧度）VOR262937545.10（0.78714弧度）0.60（0.0105弧度）VOR31571259309.00（5.39307弧度）1.30（0.0227弧度）DME155987d4=864.3（km）2.0（km）第三十八页，共八十九页，编辑于2023年，星期三飞机的精确定位模型第1类模型:不考虑误差因素超定方程组----非线性最小二乘！量纲不符！

or？

？

第三十九页，共八十九页，编辑于2023年，星期三飞机的精确定位模型第2类模型:考虑误差因素(作为硬约束)Minx;Miny;Maxx;Maxy.非线性规划！？？仅部分考虑误差!角度与距离的“地位”为何不同？其他：

误差非均匀分布！

不等式组？第四十页，共八十九页，编辑于2023年，星期三飞机的精确定位模型误差一般服从什么分布？正态分布！不同的量纲如何处理？无约束非线性最小二乘模型归一化处理！shili0702.m飞机坐标(978.31，723.98),误差平方和0.6685(<<4)角度需要进行预处理，如利用Matlab的atan2函数,值域(-pi,pi)第3类模型:考虑误差因素(作为软约束);且归一化第四十一页，共八十九页，编辑于2023年，星期三飞机的精确定位模型小技巧:LINGO中没有atan2函数,怎么办？可以直接利用@tan函数！exam0507c.lg4同前面的模型/结果飞机坐标(980.21，727.30),误差平方和2.6与前面的结果有所不同,为什么?哪个模型合理些?最后:思考以下模型:exam0507d.lg4第四十二页，共八十九页，编辑于2023年，星期三例CUMCM-2000B钢管订购和运输由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1~S7钢管厂火车站450里程（km)（沿管道建有公路）第四十三页，共八十九页，编辑于2023年，星期三钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管1单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）601=300+30144>20+23?第四十四页，共八十九页，编辑于2023年，星期三（1）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）讨论管道为树形图的情形第四十五页，共八十九页，编辑于2023年，星期三问题1的基本模型和解法总费用最小的优化问题总费用：订购，运输（由各厂Si经铁路、公路至各点Aj,

i=1,…7;j=1,…15

），铺设管道AjAj+1（j=1,…14)由Si至Aj的最小购运费用路线及最小费用cij

由Si至Aj的最优运量xij由Aj向AjAj-1段铺设的长度yj及向AjAj+1段铺设的长度zj最优购运计划约束条件钢厂产量约束：上限和下限（如果生产的话）运量约束：xij对i求和等于zj加yj；

zj与

yj+1之和等于AjAj+1段的长度ljyj

zjAj第四十六页，共八十九页，编辑于2023年，星期三基本模型由Aj向AjAj-1段铺设的运量为1+…+yj=yj(

yj+1)/2由Aj向AjAj+1段铺设的运量为1+…+zj=zj(

zj+1)/2二次规划？第四十七页，共八十九页，编辑于2023年，星期三求解步骤1）求由Si至Aj的最小购运费用路线及最小费用cij

难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。A17010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。--至少求3次最短路如S7至A10的最小费用路线先铁路1130km，再公路70km,运费为77（万元）先公路（经A15）40km,再铁路1100km，再公路70km,运费为76（万元）第四十八页，共八十九页，编辑于2023年，星期三实际上只有S4和S7需要分解成子问题求解每个子问题是标准的二次规划，决策变量为xij,yj,zj,不超过135个。第四十九页，共八十九页，编辑于2023年，星期三fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量

c)比较好的方法：引入0-1变量LINDO/LINGO得到的结果比matlab得到的好cumcm2000b.lg4yj

zjj第五十页，共八十九页，编辑于2023年，星期三问题1的其它模型和解法1）运输问题的0-1规划模型将全长5171km的管道按公里分段，共5171个需求点，钢厂为7个供应点，构成如下的运输问题cij为从供应点i到需求点j的最小购运费xij=1表示从点i到点j购运1单位钢管求解时要针对规模问题寻求改进算法第五十一页，共八十九页，编辑于2023年，星期三2）最小费用网络流模型SourceS1S2S7A1A2A15P11P1l1P21…………Sink(si,pi)(+,cij)(1,1),…(1,li)(1,0)SourceS1S2S7A1A2A15P1P2………Sink(si,pi)(+,cij)(li,f(f+1)/2)(li,0)线性费用网络(只有产量上限)非线性费用网络(只有产量上限)边的标记（流量上限，单位费用）用标准算法(如最小费用路算法)求解无单位费用概念(f(f+1)/2),需修改最小费用路算法第五十二页，共八十九页，编辑于2023年，星期三2）最小费用网络流模型产量有下限ri时的修正SourceSiSi’(si-ri,pi)(ri,0)(+,0)得到的结果应加上才是最小费用注：该模型获当年的惟一最高奖（网易杯）第五十三页，共八十九页，编辑于2023年，星期三S1S2S3S6S5S1S2S2S3S3S5S5S63)最小面积模型A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15cx作图：Si到管道x单位钢管的最小购运费用c由各条Si首尾相连(横坐标)组成的一条折线对应一个购运方案，折线下面的面积对应方案的费用在产量约束下找面积最小的折线第五十四页，共八十九页，编辑于2023年，星期三问题2:分析对购运计划和总费用影响(哪个钢厂销价变化影响最大；哪个钢厂产量上限变化影响最大)规划问题的灵敏度分析问题3：管道为树形图701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100(jk)是连接Aj,Ak的边，E是树形图的边集，ljk是(jk)的长度，yjk是由Aj沿(jk)铺设的钢管数量第五十五页，共八十九页，编辑于2023年，星期三论文中发现的主要问题1）针对题目给的数据用凑的方法算出结果，没有解决这类问题的一般模型2）局部最优，如将管道分为左右两段，分别寻求方案；如将问题分为购运和铺设两部分，分别寻优（会导致每段管道都从两端铺到中点）4）由Si至Aj的最小购运费用路线及最小费用cij不对5）数字结果相差较大(如最小费用应127.5至128.2亿元)第五十六页，共八十九页，编辑于2023年，星期三数学建模讲座CUMCM-2007B(乘公交，看奥运)赛题分析谢金星100084北京清华大学数学科学系TelFaxmail:jxie@

/~jxie第五十七页，共八十九页，编辑于2023年，星期三2007B命题背景奥运相关的题目：(时代特性,社会关注）让运动员及时到达场馆（车辆调度，路径安排等）应急管理（紧急疏散，应急调度等）赛程安排（单一项目，多个项目）成绩排名（如循环赛，体操或跳水等）技术类，如“刘翔的运动鞋”乘公交，看奥运：原名“自动问路机”方沛辰（吉大），吴孟达（国防科大）提出原拟作乙组题，似乎难度太大第五十八页，共八十九页，编辑于2023年，星期三命题背景定位：公交路线选择（查询）模型与算法如何给数据？抽象数据／实际数据？（减小规模，不给地理信息）貌似简单，实则不然数据处理（转换）方面有一定难度换乘次数多时简单搜索不易（计算复杂度高）换乘时间／步行时间等需要考虑周全标准的最短路算法（如Dijkstra算法）并不适用第五十九页，共八十九页，编辑于2023年，星期三乘公交，看奥运公交线路选择问题的自主查询计算机系统：核心是线路选择的模型与算法应该从实际情况出发考虑，满足查询者的各种不同需求1:仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法2:同时考虑公汽与地铁线路，解决以上问题3:假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型第六十页，共八十九页，编辑于2023年，星期三

【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）推论：换乘公汽等待３分钟，换乘地铁等待２分钟

【附录2】公交线路及相关信息（见数据文件）第六十一页，共八十九页，编辑于2023年，星期三线路数据中的问题线路数据中的异常或不明确之处，同学可根据自己的理解作出假设和处理，一般不会影响实例的计算结果个别线路相邻站点名相同，可去掉其中一点或不作处理等L406未标明是环线，是否将其当作环线处理均可L290标明是环线，但首尾站点分别为1477与1479，可将所有线路中1477与1479统一为1477后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将1479改为1477，或在1479后增加1477，等等如果在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些）

第六十二页，共八十九页，编辑于2023年，星期三对通过地铁换乘的理解“假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)”步行：公汽站地铁站（通道）公汽站换乘耗时11min：步行4+4=8min;等车3min第１问（只考虑公汽）：可不考虑以上换乘有同学也考虑了如上换乘，只是不坐地铁，应该也可以此样处理时，第１问和第２问的难度相近第六十三页，共八十九页，编辑于2023年，星期三模型的目标多目标优化问题（至少考虑三方面）换乘次数最少(N)、费用最省(M)、时间最短(T)从该问题的实际背景来看，加权太合适不少同学用层次分析法确定权不少同学计算时间的价值（平均收入／工作时间）不同目标组合的模型三个目标按优先级排序，组合成六个模型也可将某些目标作为约束第六十四页，共八十九页，编辑于2023年，星期三多数队仅采用搜索法（70-80%?）直达；一次换乘；二次换乘；…ststst求出所有线路；评价其目标(容易计算)；选优第六十五页，共八十九页，编辑于2023年，星期三多数队仅采用搜索法总体来看，技术含量较低（基本上是枚举）几乎没有建模，完全只有算法实现，算法也没什么创新一般只考虑不超过两次换乘不少文章引用参考文献作为依据，实用中似乎够用

题目难度大大降低，模型不够一般换乘作为了第一目标，或作为一个最重要的约束任意次换乘时算法复杂度提高，难以处理结果不佳（如：从省时考虑，有些需３－４次换乘）第六十六页，共八十九页，编辑于2023年，星期三图论模型与最短路算法用图论做的队也不少，但往往考虑不周弧上赋权方式交代不清套用Dijkstra或Floyd-Warshall算法，却不清楚其原理及适用的问题需要建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价(时间或费用)图（网络）如何描述和表示？基本要素：节点，有向弧（边），弧上赋权邻接矩阵；关联矩阵（数学上处理方便，存储量较大）链表（存储量较小，计算机上处理方便）第六十七页，共八十九页，编辑于2023年，星期三关联矩阵(IncidenceMatrix)表示法在线路选择问题中，当从i可直达j时，定义弧(i,j)；其上的权可为１或成本(时间或费用)；多重弧可只保留一条（弧上的权可取最小的成本，如时间或费用）G=(V，A)是一个简单有向图；|V|=n，|A|=m

重要数学性质：关联矩阵是全幺模矩阵图G=(V，A)的邻接矩阵C是如下定义的：C是一个的矩阵，即第六十八页，共八十九页，编辑于2023年，星期三邻接矩阵(AdjacencyMatrix)表示法图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次可达矩阵；……第六十九页，共八十九页，编辑于2023年，星期三链表（邻接表）表示法

122345283904602403053036470单向链表(指针数组)

A(1)={2,3}A(2)={4}A(3)={2}A(4)={3,5}A(5)={3,4}12345第七十页，共八十九页，编辑于2023年，星期三Dijkstra算法（标号算法，1959）STEP1.如果S=V,则uj为节点s到节点j的最短路路长(最短路可以通过数组pred所记录的信息反向追踪获得),结束.否则继续.STEP0.(初始化)令S=，=V，；对V中的顶点j(js)令初始距离标号.

STEP2.从中找到距离标号最小的节点i，把它从删除，加入S.对于所有从i出发的弧,若，则令

转STEP1.特点：1.算法求出从源点s到所有点的最短路长2.每点给一对标号(uj,predj)，uj是从s到j的最短路长；predj是从s到j的最短路中j点的前一点第七十一页，共八十九页，编辑于2023年，星期三Example第七十二页，共八十九页，编辑于2023年，星期三Dijkstra算法（标号设定算法）适用于正费用网络：“分层”设定标号永久标号：S中的点，uj是最短路长临时标号；其他点，uj是只通过S中的点的最短路长对于稠密网络，这是求解最短路问题可能达到的最小的复杂度,因为任何算法都至少必须对每条弧考虑一次.对于稀疏网络，利用各种形式的堆（Heap），其复杂度可降为或等算法复杂度O(n2+m)：如链表或邻接矩阵实现找最小标号点修改标号第七十三页，共八十九页，编辑于2023年，星期三特点：求所有点对间最短路基本思想：逐步逼近，迭代求解最短路方程:O(n3)Floyd-Warshall算法

（标号修正算法，1962)临时标号是不通过k，k+1，…,n节点(i,j除外)时从节点i到节点j的最短路路长.第七十四页，共八十九页，编辑于2023年，星期三Floyd-Warshall算法的具体实现:O(n3)由于要记录所有节点之间最短路的信息,所以这里我们要用一个二维数组P；

可依据P,采用“正向追踪”的方式得到最短路.STEP2：如果k=n,结束;否则转STEP1.STEP0:k=0.对于所有节点i和j:令，,(，若节点i和j之间没有弧,认为).

STEP1:k=k+1.对于所有节点i和j:若,令,;否则令,.第七十五页，共八十九页，编辑于2023年，星期三Floyd-Warshall算法的

矩阵迭代法实现：O(n4)令D为权矩阵(直达最短路长)Dm为正好经过m条弧从i到j的最短路长第七十六页，共八十九页，编辑于2023年，星期三问题1和2的一种具体建模方法(赋权)在线路选择问题中，当从i可直达j时（同为公汽或地铁站点），定义弧(i,j)；其上的权为lij表示由i直达j付出的代价，可以为时间或费用(不包括换乘代价；多条线路可达时只保留最小代价)初始等车时间2(3)min也不包括在内，最后结果可加上注意：D=D(0)不是对称矩阵(“直达矩阵”)dij(0)=dij第七十七页，共八十九页，编辑于2023年，星期三问题１－２的一种具体建模方法i站点是公汽站点，j站点为地铁站点：（1）若j站点对应的所有换乘(公汽)站点k，均不能从i直达(不在i站点所在公汽线路L上)，则dij(0)

=∞.

（2）若j站点对应的换乘站点(k),可从i站点直达k，则费用为dij(0)

=dik(0)；对于时间则需要加上k到j的步行时间.(若有多种选择，取最小成本者即可)ikj第七十八页，共八十九页，编辑于2023年，星期三问题１－２的一种具体建模方法j站点是公汽站点，i站点为地铁站点：（1）若从i站点对应的任何换乘(公汽)站点k，均不能直达j站点，则dij(0)

=∞.

（2）若从i站点对应的换乘(公汽)站点k，能直达j站点，则费用为dij(0)

=dkj(0)；对于时间则需要加上i到k的步行时间.

ikj第七十九页，共八十九页，编辑于20