数学建模讲座CUMCMB赛题分析市公开课一等奖百校联赛特等奖课件.pptx

谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.数学建模讲座数学建模讲座CUMCM-B 赛题分析赛题分析谢金星谢金星100084北京清华大学数学科学系北京清华大学数学科学系Tel:010-62787812，Fax:[phone]Email: http:/ 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.简明提要简明提要 应用数学与数学建模应用数学与数学建模 -建模及建模竞赛意义建模及建模竞赛意义 竞赛评阅标准竞赛评阅标准 -普通标准及主要问题普通标准及主要问题 优化模型创新优化模型创新 -B题分析题分析第2页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.数学知识数学知识数学技巧数学技巧数学应用数学应用数学发觉数学发觉应用数学应用数学数学技术数学技术数学试验数学试验随机数学随机数学代数与几何代数与几何微微积分积分数学美学数学美学数学哲学数学哲学数学精神数学精神数学素质数学素质数学文化数学文化数学：几个层次了解第3页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.数学建模：实际与数学之间桥梁实际问题实际问题数学数学Mathematical Modeling 现实对象信息现实对象信息数学模型数学模型现实对象解答现实对象解答数学模型解答数学模型解答表述表述求解求解解释解释验证验证(归纳)(演绎)数学建模数学建模全过程全过程第4页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.美国MCM+ICM竞赛规模第5页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.我国CUMCM竞赛规模第6页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.学生欢迎：学生欢迎：“一次参赛，终生受益一次参赛，终生受益”硕士导师们认同硕士导师们认同企业界认同赞助企业界认同赞助教育改革同行认同：教育改革同行认同：“成功范例成功范例”国际同行认同国际同行认同竞赛反响竞赛反响第7页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.IBM 中国研究中心中国研究中心-招聘条件招聘条件Position title:Business Optimization(BJ)1Background in industrial engineering,operations research,mathematics,Artificial Intelligence,management science etc.2.Knowledge in network design,job scheduling,data analysis,simulation and optimization 3.Award in mathematical contest in modeling is a plus 4.Experience in industry is a plus 5.Experience in eclipse or programming model/architecture design is a plus-Feb.18,http:/ 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.简明提要简明提要 应用数学与数学建模应用数学与数学建模 -建模及建模竞赛意义建模及建模竞赛意义 竞赛评阅标准竞赛评阅标准 -普通标准及主要问题普通标准及主要问题 创新能力培养创新能力培养 -几个例子（结合优化模型）几个例子（结合优化模型）第9页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.CUMCMCUMCM评阅标准评阅标准清楚性：摘要应了解为详细摘要，提要挈领清楚性：摘要应了解为详细摘要，提要挈领 表示严谨、简捷，思绪清新表示严谨、简捷，思绪清新 格式符合规范，禁止暴露身份格式符合规范，禁止暴露身份创造性：尤其观赏独树一帜、标新立异，但要合理创造性：尤其观赏独树一帜、标新立异，但要合理假设合理性，建模创造性，假设合理性，建模创造性，结果正确性，表述清楚性。结果正确性，表述清楚性。正确性：正确性：不强调与不强调与“参考答案参考答案”一致性和结果精度；一致性和结果精度；好方法结果普通比很好；但不一定是最好好方法结果普通比很好；但不一定是最好合理性：关键假设；不观赏罗列大量无关紧要假设合理性：关键假设；不观赏罗列大量无关紧要假设 第10页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.CUMCMCUMCM评阅标准评阅标准:一些常见问题一些常见问题有论文过于简单，该交代内容省略了，难以看懂有论文过于简单，该交代内容省略了，难以看懂有队罗列一系列假设或模型，又不作比较、评价，有队罗列一系列假设或模型，又不作比较、评价，希望碰上希望碰上“参考答案参考答案”或或“评阅思绪评阅思绪”，弄巧成拙，弄巧成拙数学模型最好数学模型最好明确、合理、简练：明确、合理、简练：有些论文不给出明确模型，只是依据赛题情况，有些论文不给出明确模型，只是依据赛题情况，实际上是用实际上是用“凑凑”方法给出结果，即使结果大致是对方法给出结果，即使结果大致是对，没有普通性，不是数学建模正确思绪。，没有普通性，不是数学建模正确思绪。有论文参考文件不全，或引用他人结果不作交代有论文参考文件不全，或引用他人结果不作交代第11页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.从论文评阅看学生参加竞赛中问题从论文评阅看学生参加竞赛中问题 吃透题意方面不足，没有抓住和处理主要问题；吃透题意方面不足，没有抓住和处理主要问题；就事论事，形成数学模型意识和能力欠缺；就事论事，形成数学模型意识和能力欠缺；对所用方法一知半解，不论详细条件，套用现成方对所用方法一知半解，不论详细条件，套用现成方法，造成错误；法，造成错误；对结果分析不够，怎样符合实际考虑不周；对结果分析不够，怎样符合实际考虑不周；写作方面问题写作方面问题(摘要、简明、优缺点、参考文件摘要、简明、优缺点、参考文件);队员之间合作精神差，孤军奋战；队员之间合作精神差，孤军奋战；依赖心理重，甚至违纪（指导教师、依赖心理重，甚至违纪（指导教师、网络）。网络）。第12页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.参加竞赛前准备参加竞赛前准备 了解竞赛章程等相关信息；了解竞赛章程等相关信息；掌握数学建模基本方法（学过掌握数学建模基本方法（学过“数学模型数学模型”或或“数数学试验学试验”课最好，自学一些基本内容也能够）；课最好，自学一些基本内容也能够）；掌握基本数学软件（掌握基本数学软件（Matlab/Mathematica；LINGO；如能掌握；如能掌握SAS/JMP统计软件更加好）；统计软件更加好）；训练规范科技论文写作训练规范科技论文写作/表示能力表示能力(摘要、正文、优摘要、正文、优缺点、参考文件及引用等缺点、参考文件及引用等);试做几道以前赛题；试做几道以前赛题；培养合作精神。培养合作精神。第13页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.简明提要简明提要 应用数学与数学建模应用数学与数学建模 -建模及建模竞赛意义建模及建模竞赛意义 竞赛评阅标准竞赛评阅标准 -普通标准及主要问题普通标准及主要问题 创新能力培养创新能力培养 -B分析分析第14页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.优化问题三要素：优化问题三要素：决议变量决议变量；目标函数目标函数；约束条件约束条件约约束束条条件件决议变量决议变量优化问题普通形式优化问题普通形式目标函数目标函数有些人统计：有些人统计：优化问题占优化问题占CUMCM赛题二分之一以上赛题二分之一以上（1/32/3）第15页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.建模时需要注意几个基本问题建模时需要注意几个基本问题 1、尽可能使用实数优化，降低整数约束和整数变量尽可能使用实数优化，降低整数约束和整数变量2、尽可能使用光滑优化，降低非光滑约束个数尽可能使用光滑优化，降低非光滑约束个数 如：尽可能少使用绝对值、符号函数、多个变量求如：尽可能少使用绝对值、符号函数、多个变量求最大最大/最小值、四舍五入、取整函数等最小值、四舍五入、取整函数等3、尽可能使用线性模型，降低非线性约束和非线性变尽可能使用线性模型，降低非线性约束和非线性变量个数量个数 （如（如x/y 5 改为改为x5y）4、合理设定变量上下界，尽可能给出变量初始值合理设定变量上下界，尽可能给出变量初始值 5、模型中使用参数数量级要适当模型中使用参数数量级要适当 (如小于如小于103)第16页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.优化建模怎样创新？优化建模怎样创新？方法方法1：大胆创新，别出心裁：大胆创新，别出心裁 -采取有特色目标函数、约束条件等采取有特色目标函数、约束条件等 -你用非线性规划，我用线性规划你用非线性规划，我用线性规划 -你用整数你用整数/离散规划，我用连续规划离散规划，我用连续规划/网络优化网络优化 -方法方法2：细致入微，滴水不漏：细致入微，滴水不漏 -对目标函数、约束条件处理尤其细致对目标函数、约束条件处理尤其细致 -有算法设计和分析，不但仅是简单套用软件有算法设计和分析，不但仅是简单套用软件 -敏感性分析详细敏感性分析详细/全方面全方面 -第17页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.B命题背景命题背景 奥运相关题目：奥运相关题目：(时代特征时代特征,社会关注）社会关注）让运动员及时抵达场馆（车辆调度，路径安排等）让运动员及时抵达场馆（车辆调度，路径安排等）应急管理（紧急疏散，应急调度等）应急管理（紧急疏散，应急调度等）赛程安排（单一项目，多个项目）赛程安排（单一项目，多个项目）成绩排名（如循环赛，体操或跳水等）成绩排名（如循环赛，体操或跳水等）技术类，如技术类，如“刘翔运动鞋刘翔运动鞋”乘公交，看奥运：原名乘公交，看奥运：原名“自动问路机自动问路机”方沛辰（吉大），吴孟达（国防科大）提出方沛辰（吉大），吴孟达（国防科大）提出原拟作乙组题，似乎难度太大原拟作乙组题，似乎难度太大第18页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.命题背景命题背景 定位：公交路线选择（查询）模型与算法定位：公交路线选择（查询）模型与算法怎样给数据？怎样给数据？抽象数据实际数据？（减小规模，不给地理信息）抽象数据实际数据？（减小规模，不给地理信息）貌似简单，实则不然貌似简单，实则不然数据处理（转换）方面有一定难度数据处理（转换）方面有一定难度换乘次数多时简单搜索不易（计算复杂度高）换乘次数多时简单搜索不易（计算复杂度高）换乘时间步行时间等需要考虑周全换乘时间步行时间等需要考虑周全标准最短路算法（如标准最短路算法（如Dijkstra算法）并不适用算法）并不适用第19页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.乘公交，看奥运乘公交，看奥运公交线路选择问题自主查询计算机系统：关键是线公交线路选择问题自主查询计算机系统：关键是线路选择路选择模型与算法模型与算法应该从应该从实际情况出发实际情况出发考虑，满足查询者考虑，满足查询者各种不一样各种不一样需求需求1:仅考虑公汽线路，给出任意两公汽站点之间线路仅考虑公汽线路，给出任意两公汽站点之间线路选择问题选择问题普通普通数学模型与算法数学模型与算法 2:同时考虑公汽与地铁线路，处理以上问题同时考虑公汽与地铁线路，处理以上问题3:假设又知道全部站点之间步行时间，给出任意两假设又知道全部站点之间步行时间，给出任意两站点之间线路选择问题数学模型站点之间线路选择问题数学模型 第20页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.【附录【附录1】基本参数设定】基本参数设定相邻公汽站平均行驶时间(包含停站时间)：3分钟相邻地铁站平均行驶时间(包含停站时间)：2.5分钟公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标识于线路后；其中分段计价票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（不论地铁线路间是否换乘）推论：换乘公汽等候分钟，换乘地铁等候分钟【附录【附录2】公交线路及相关信息】公交线路及相关信息（见数据文件）（见数据文件）第21页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.线路数据中问题线路数据中问题线路数据中异常或不明确之处，同学可依据自己线路数据中异常或不明确之处，同学可依据自己了解了解作出作出假设假设和处理，普通不会影响实例计算结果和处理，普通不会影响实例计算结果个别线路相邻站点名相同，可去掉其中一点或不作处理等个别线路相邻站点名相同，可去掉其中一点或不作处理等L406未标明是环线，是否将其看成环线处理均可未标明是环线，是否将其看成环线处理均可L290标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为1477与与1479，可将全，可将全部线路中部线路中1477与与1479统一为统一为1477后计算。同学也能够按照各后计算。同学也能够按照各自认为合理方式处理，包含不妥作环线，或将自认为合理方式处理，包含不妥作环线，或将1479改为改为1477，或在，或在1479后增加后增加1477，等等，等等假如在假设中有明确约定，则环线单向或双向发车均应认可假如在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些）（按单向发车作假设，计算结果可能差些）第22页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.对经过地铁换乘了解对经过地铁换乘了解“假设同一地铁站对应任意两个公汽站之间能够经假设同一地铁站对应任意两个公汽站之间能够经过地铁站换乘过地铁站换乘(无需支付地铁费无需支付地铁费)”步行：公汽站步行：公汽站地铁站（通道）地铁站（通道）公汽站公汽站换乘耗时换乘耗时11min：步行：步行4+4=8min;等车等车3min第问（只考虑公汽）：可不考虑以上换乘第问（只考虑公汽）：可不考虑以上换乘有同学也考虑了如上换乘，只是不坐地铁，应该也能够有同学也考虑了如上换乘，只是不坐地铁，应该也能够此样处理时，第问和第问难度相近此样处理时，第问和第问难度相近第23页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.模型目标模型目标多目标优化问题多目标优化问题（最少考虑三方面）（最少考虑三方面）换乘次数最少换乘次数最少(N)、费用最省、费用最省(M)、时间最短、时间最短(T)从该问题实际背景来看，从该问题实际背景来看，加权加权太适当太适当 不少同学用层次分析法确定权不少同学用层次分析法确定权不少同学计算时间价值（平均收入工作时间）不少同学计算时间价值（平均收入工作时间）不一样目标不一样目标组合组合模型模型三个目标按优先级排序，组合成六个模型三个目标按优先级排序，组合成六个模型也可将一些目标作为约束也可将一些目标作为约束第24页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.多数队多数队仅仅采取搜索法（采取搜索法（70-80%?）直达；直达；一次换乘；一次换乘；二次换乘；二次换乘；ststs t求出全部线路；评价其目标求出全部线路；评价其目标(轻易计算轻易计算)；选优；选优第25页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.多数队多数队仅仅采取搜索法采取搜索法总体来看，技术含量较低（基本上是枚举）总体来看，技术含量较低（基本上是枚举）几乎没有建模，完全只有算法实现，算法也没什么创新几乎没有建模，完全只有算法实现，算法也没什么创新普通只考虑不超出两次换乘普通只考虑不超出两次换乘不少文章引用参考文件作为依据，实用中似乎够用不少文章引用参考文件作为依据，实用中似乎够用 题目难度大大降低，模型不够题目难度大大降低，模型不够普通普通换乘作为了换乘作为了第一目标第一目标，或作为一个，或作为一个最主要约束最主要约束任意次换乘时算法复杂度提升，难以处理任意次换乘时算法复杂度提升，难以处理结果不佳（如：从省时考虑，有些需次换乘）结果不佳（如：从省时考虑，有些需次换乘）第26页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.图论模型与最短路算法图论模型与最短路算法用图论做队也不少，但往往考虑不周用图论做队也不少，但往往考虑不周弧上赋权方式交代不清弧上赋权方式交代不清套用套用Dijkstra或或Floyd-Warshall算法，却不清楚其原理及算法，却不清楚其原理及适用问题适用问题需要建立一个带权有向图，节点表示站点，有向弧需要建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上权表示前一表示前一站点能够直达后一站点，弧上权表示前一站点直达后一站点所需付出代价站点直达后一站点所需付出代价(时间或费用时间或费用)图（网络）怎样描述和表示？图（网络）怎样描述和表示？基本要素：节点，有向弧（边），弧上赋权基本要素：节点，有向弧（边），弧上赋权邻接矩阵；关联矩阵（数学上处理方便，存放量较大）邻接矩阵；关联矩阵（数学上处理方便，存放量较大）链表（存放量较小，计算机上处理方便）链表（存放量较小，计算机上处理方便）第27页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.关联矩阵关联矩阵(Incidence Matrix)表示法表示法在线路选择问题中，当从在线路选择问题中，当从i i可直达可直达j j时，定义弧时，定义弧(i,j)(i,j)；其上权可为或成本；其上权可为或成本(时间或费用时间或费用)；多；多重弧可只保留一条（弧上权可取最小成本，如重弧可只保留一条（弧上权可取最小成本，如时间或费用）时间或费用）G=(V，A)是一个简单有向图；是一个简单有向图；|V|=n，|A|=m 主要数学性质：主要数学性质：关联矩阵是全幺模矩阵关联矩阵是全幺模矩阵图图 G=(V，A)邻邻 接接 矩矩 阵阵 C是是 以以 下下 定定 义义：C是是 一一 个个 矩阵，即矩阵，即第28页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.邻接矩阵邻接矩阵(Adjacency Matrix)表示法表示法图图 G=(V，A)邻邻 接接 矩矩 阵阵 C是是 以以 下下 定定 义义：C是是 一一 个个 0-1矩阵，即矩阵，即在线路选择问题中，当从在线路选择问题中，当从i i可直达可直达j j时，定义弧时，定义弧(i,j)(i,j)；其上权可为或成本；其上权可为或成本(时间或费用时间或费用)G=(V，A)是一个简单有向图；是一个简单有向图；|V|=n，|A|=m 有向图有向图“传递闭包算法传递闭包算法”(可用于普通二元关系可用于普通二元关系)权取权取0-10-1时，时，C C(0)(0)=C=C可称为可称为直达矩阵直达矩阵；C C(1)(1)=C*C=C*C 为为次可达矩阵次可达矩阵；C C(2)(2)=C=C(1)(1)*C*C 为为2次可达矩阵次可达矩阵；第29页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.链表（邻接表）表示法链表（邻接表）表示法 122345283904602403053036470单向链表(指针数组)A(1)=2,3A(2)=4A(3)=2A(4)=3,5A(5)=3,412345第30页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.DijkstraDijkstra算法（标号算法，算法（标号算法，19591959）STEP1.假如S=V,则uj为节点s到节点j最短路路长(最短路能够经过数组pred所统计信息反向追踪取得),结束.不然继续.STEP0.(初始化)令S=，=V，；对V 中顶点j(j s)令初始距离标号 .STEP2.从 中找到距离标号最小距离标号最小节点i，把它从 删除，加入S.对于全部全部从i出发弧 ,若 ，则令 转STEP1.特点：特点：1.算法求出从源点算法求出从源点s到全部点最短路长到全部点最短路长 2.每每点点给给一一对对标标号号(uj,predj)，uj是是从从s到到j最短路长；最短路长；predj是从是从s到到j最短路中最短路中j点前一点点前一点第31页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.Example第32页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.DijkstraDijkstra算法（标号设定算法）算法（标号设定算法）适合用于正费用网络：适合用于正费用网络：“分层分层”设定标号设定标号永久标号：永久标号：S中点，中点，uj是最短路长是最短路长暂时标号；暂时标号；其它点，其它点，uj是只经过是只经过S中点最短路长中点最短路长对对于于稠稠密密网网络络，这这是是求求解解最最短短路路问问题题可可能能到到达达最最小小复复杂杂度度,因因为为任何算法都最少必须对每条弧考虑一次任何算法都最少必须对每条弧考虑一次.对于稀疏网络，利用各种形式对于稀疏网络，利用各种形式堆（堆（HeapHeap），其复杂度可降为，其复杂度可降为 或或 等等算法复杂度算法复杂度O(n2+m)：如链表或邻接矩阵实现：如链表或邻接矩阵实现找最小标号点修改标号找最小标号点修改标号第33页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.特点：求全部点对间最短路特点：求全部点对间最短路基本思想：逐步迫近，迭代求解最短路方程基本思想：逐步迫近，迭代求解最短路方程:O(n3)Floyd-Warshall算法算法（标号修正算法标号修正算法，1962)1962)暂暂时时标标号号 是是不不经经过过k，k+1，,n 节节点点(i,j 除除外外)时时从从节节点点i到节点到节点j最短路路长最短路路长.第34页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.Floyd-Warshall算法详细实现算法详细实现:O(n3)因因为为要要统统计计全全部部节节点点之之间间最最短短路路信信息息,所所以以这这里里我我们们要要用用一一个个二二维数组维数组P；可依据可依据P,采取采取“正向追踪正向追踪”方式得到最短路方式得到最短路.STEP2：假如：假如k=n,结束结束;不然转不然转STEP1.STEP0:k=0.对于全部节点对于全部节点i和和j:令令 ，,(，若节点，若节点i和和j之间没有弧之间没有弧,认为认为 ).STEP1:k=k+1.对于全部节点对于全部节点i和和j:若若 ,令令 ,;不然令不然令 ,.第35页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.Floyd-Warshall算法算法矩阵迭代法实现：矩阵迭代法实现：O(n4)令令D为权矩阵为权矩阵(直达最短路长直达最短路长)Dm为恰好经过为恰好经过m条弧从条弧从i到到j最短路长最短路长第36页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.问题问题1和和2一个详细建模方法一个详细建模方法(赋权赋权)在线路选择问题中，当从在线路选择问题中，当从i i可直达可直达j j时（时（同为公同为公汽或地铁站点汽或地铁站点），定义弧），定义弧(i,j)(i,j)；其上权为；其上权为lij表示由i直达j付出代价，可认为时间或费用(不包含换乘代价；多条线路可达时只保留最小代价)初始等车时间2(3)min也不包含在内，最终结果可加上注意：D=D(0)不是对称矩阵(“直达矩阵”)dij(0)=dij第37页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.问题一个详细建模方法问题一个详细建模方法i站点是公汽站点，站点是公汽站点，j站点为地铁站点：站点为地铁站点：（1）若若j站站点点对对应应全全部部换换乘乘(公公汽汽)站站点点k，均均不不能能从从i直达直达(不在不在i站点所在公汽线路站点所在公汽线路L上上)，则，则dij(0)=.（2）若若j站站点点对对应应换换乘乘站站点点(k),可可从从i站站点点直直达达k，则则费费用用为为dij(0)=dik(0)；对对于于时时间间则则需需要要加加上上k到到j步步行行时间时间.(若有各种选择，取最小成本者即可若有各种选择，取最小成本者即可)ikj第38页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.问题一个详细建模方法问题一个详细建模方法j站点是公汽站点，站点是公汽站点，i站点为地铁站点：站点为地铁站点：（1）若若从从i站站点点对对应应任任何何换换乘乘(公公汽汽)站站点点k，均均不不能能直直达达j站站点，则点，则dij(0)=.（2）若若从从i站站点点对对应应换换乘乘(公公汽汽)站站点点k，能能直直达达j站站点点，则则费费用为用为dij(0)=dkj(0)；对于时间则需要；对于时间则需要加上加上i到到k步行步行时间时间.ikj第39页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.问题：最小费用或时间问题：最小费用或时间 定义矩阵算子定义矩阵算子“”以下：设以下：设A、B均为均为n阶方阵，阶方阵，C=A B (考虑考虑换乘代价换乘代价)当考当考虑费虑费用矩用矩阵阵之之间间运算运算时时，表示在表示在k换乘时间换乘时间 当考当考虑时间虑时间矩矩阵阵之之间间运算运算时时，D(k)=D(k-1)D 表示表示k次换乘最低代价次换乘最低代价(费用或时间费用或时间)该算法大致相当于求最短路该算法大致相当于求最短路Floyd-Warshall算法，但算法，但考虑了换乘原因，可称为改进考虑了换乘原因，可称为改进Floyd-Warshall算法算法 类似地类似地,经过修改经过修改Dijkstra算法求解也可算法求解也可第40页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.问题：最小费用或时间问题：最小费用或时间i,j,ki,j,k表示换乘时间表示换乘时间 i=j 或或k=i，j时，时，i,j,ki,j,k=0其它情形：其它情形：若不可换乘若不可换乘(当当i，j为公汽站点而为公汽站点而k为地铁站点，或为地铁站点，或者者i，j为地铁站点而为地铁站点而k为公汽站点时为公汽站点时)，则，则 i,j,ki,j,k=0若可换乘，则若可换乘，则k这只是等候时间，因为步这只是等候时间，因为步行时间已在行时间已在D中考虑了中考虑了ij第41页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.第问：已知全部站点间步行时间第问：已知全部站点间步行时间多数队没有给出普通模型多数队没有给出普通模型,而只考虑最多一次换乘而只考虑最多一次换乘多数队想法：假设多数队想法：假设“起点步行起点步行”，“换乘步行换乘步行”，“终点步行终点步行”三种模式，限定三种模式，限定步行最大时间步行最大时间后后搜索搜索ikj第42页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.其它：最短路问题线性规划模型其它：最短路问题线性规划模型xij表示弧（表示弧（i，j）是否位于）是否位于s-t路上：当路上：当xij=1时，表示弧（时，表示弧（i，j）位于位于s-t路上，当路上，当xij=0时，表示弧（时，表示弧（i，j）不在）不在s-t路上路上.关联矩阵是全么模矩阵，所以关联矩阵是全么模矩阵，所以0-10-1变量能够松弛为变量能够松弛为区间区间0,10,1中实数中实数 不含负圈不含负圈，变量直接松弛为全部非负实数，变量直接松弛为全部非负实数思索：为何思索：为何xij 能够不限定为能够不限定为0，1(0-1规划规划)?第43页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.最短路问题线性规划模型最短路问题线性规划模型线性规划模型，应该能够计算到比较大规模问题线性规划模型，应该能够计算到比较大规模问题有些队写出了上述模型，但并未用该模型求解有些队写出了上述模型，但并未用该模型求解可能需要强大优化软件，数据输入工作量也较大可能需要强大优化软件，数据输入工作量也较大换乘代价不易考虑（网络上权不易定义，或不具可换乘代价不易考虑（网络上权不易定义，或不具可加性）加性）有些同学提到有些同学提到动态规划动态规划,但要么与这里介绍最短路但要么与这里介绍最短路算法等价算法等价,要么处理有误要么处理有误,或只是搜索法变种或只是搜索法变种第44页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.有些队讨论有些队讨论“交通阻抗交通阻抗”:“”:“文不对题文不对题”道路阻抗在交通流分配中能够经过道路阻抗在交通流分配中能够经过路阻函数路阻函数来描述来描述所谓路阻函数是指路段行驶时间与路段交通负荷，交所谓路阻函数是指路段行驶时间与路段交通负荷，交叉口延误与交叉口负荷之间关系叉口延误与交叉口负荷之间关系在详细分配过程中，由路段行驶时间及交叉口延误共在详细分配过程中，由路段行驶时间及交叉口延误共同组成出行交通阻抗同组成出行交通阻抗交通网络上路阻，应包含反应交通时间、交通安全、交通网络上路阻，应包含反应交通时间、交通安全、交通成本、舒适程度、便捷性和按时性等等许多原因交通成本、舒适程度、便捷性和按时性等等许多原因第45页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.同学论文中存在主要问题同学论文中存在主要问题2.目标不妥，或不完整目标不妥，或不完整 3.换乘时间处理不妥换乘时间处理不妥-尤其地铁站与公汽站之间，以及尤其地铁站与公汽站之间，以及-经过地铁通道换乘公汽站之间经过地铁通道换乘公汽站之间1.几乎没有模型，只有算法（普通是搜索法）几乎没有模型，只有算法（普通是搜索法）4.算法使用不妥，或滥用算法使用不妥，或滥用5.对第问，极少认真进行讨论和建模对第问，极少认真进行讨论和建模6.全文表示不清，思绪混乱全文表示不清，思绪混乱第46页 谢金星谢金星,清华大学数学科学系清华大学数学科学系,2007-2008.Thats all.Any Questions?Thank you for your attendance!最终，祝大家在数学建模活动中取得更大成绩！谢金星,清华大学数学科学系,-.第47页