谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 数学建模讲座CUMCM2007B赛题分析Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 简要提纲简要提纲 应用数学与数学建模应用数学与数学建模 - 建模及建模竞赛的意义建模及建模竞赛的意义 竞赛评阅标准竞赛评阅标准 - 一般原则及主要问题一般原则及主要问题 优化模型的创新优化模型的创新 - 2007B题分析题分析 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 数学知识数学知识数学技巧数学技巧数学应用数学应用数学发现数学发现应用数学应用数学数学技术数学技术数学实验数学实验随机数学随机数学代数与几何代数与几何微微积分积分数学美学数学美学数学哲学数学哲学数学精神数学精神数学素质数学素质数学文化数学文化数学：几个层次的理解 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 数学建模：实际与数学之间的桥梁实际问题实际问题数学数学Mathematical Modeling 现实对象的信息现实对象的信息数学模型数学模型现实对象的解答现实对象的解答数学模型的解答数学模型的解答表述表述求解求解解释解释验证验证(归纳)(演绎)数学建模数学建模的全过程的全过程 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 美国MCM+ICM竞赛规模 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 我国CUMCM竞赛规模 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 学生欢迎：学生欢迎：“一次参赛，终身受益一次参赛，终身受益”研究生导师们的认同研究生导师们的认同企业界的认同赞助企业界的认同赞助教育改革同行的认同：教育改革同行的认同：“成功范例成功范例”国际同行的认同国际同行的认同竞赛的反响竞赛的反响 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 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, 2006, http:/www-900.ibm.com/cn/ibm/crl/careers/condition.shtml竞赛的反响（一例）竞赛的反响（一例） 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 简要提纲简要提纲 应用数学与数学建模应用数学与数学建模 - 建模及建模竞赛的意义建模及建模竞赛的意义 竞赛评阅标准竞赛评阅标准 - 一般原则及主要问题一般原则及主要问题 创新能力培养创新能力培养 -几个例子（结合优化模型）几个例子（结合优化模型） 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. CUMCMCUMCM评阅标准评阅标准清晰性：摘要应理解为详细摘要，提纲挈领清晰性：摘要应理解为详细摘要，提纲挈领 表达严谨、简捷，思路清新表达严谨、简捷，思路清新 格式符合规范，严禁暴露身份格式符合规范，严禁暴露身份创造性：特别欣赏独树一帜、标新立异，但要合理创造性：特别欣赏独树一帜、标新立异，但要合理假设的合理性，建模的创造性，假设的合理性，建模的创造性，结果的正确性，表述的清晰性。结果的正确性，表述的清晰性。正确性：正确性：不强调与不强调与“参考答案参考答案”的一致性和结果的精度；的一致性和结果的精度； 好方法的结果一般比较好；但不一定是最好的好方法的结果一般比较好；但不一定是最好的合理性：关键假设；不欣赏罗列大量无关紧要的假设合理性：关键假设；不欣赏罗列大量无关紧要的假设 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. CUMCMCUMCM评阅标准评阅标准: 一些常见问题一些常见问题有的论文过于简单，该交代的内容省略了，难以看懂有的论文过于简单，该交代的内容省略了，难以看懂有的队罗列一系列假设或模型，又不作比较、评价，有的队罗列一系列假设或模型，又不作比较、评价，希望碰上希望碰上“参考答案参考答案”或或“评阅思路评阅思路”，弄巧成拙，弄巧成拙数学模型最好数学模型最好明确、合理、简洁：明确、合理、简洁：有些论文不给出明确的模型，只是根据赛题的情况，有些论文不给出明确的模型，只是根据赛题的情况，实际上是用实际上是用“凑凑”的方法给出结果，虽然结果大致是的方法给出结果，虽然结果大致是对对的，没有一般性，不是数学建模的正确思路。的，没有一般性，不是数学建模的正确思路。有的论文参考文献不全，或引用他人结果不作交代有的论文参考文献不全，或引用他人结果不作交代 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 从论文评阅看学生参加竞赛中的问题从论文评阅看学生参加竞赛中的问题 吃透题意方面不足，没有抓住和解决主要问题；吃透题意方面不足，没有抓住和解决主要问题； 就事论事，形成数学模型的意识和能力欠缺；就事论事，形成数学模型的意识和能力欠缺； 对所用方法一知半解，不管具体条件，套用现成的对所用方法一知半解，不管具体条件，套用现成的方法，导致错误；方法，导致错误； 对结果的分析不够，怎样符合实际考虑不周；对结果的分析不够，怎样符合实际考虑不周； 写作方面的问题写作方面的问题(摘要、简明、优缺点、参考文献摘要、简明、优缺点、参考文献); 队员之间合作精神差，孤军奋战；队员之间合作精神差，孤军奋战； 依赖心理重，甚至违纪（指导教师、依赖心理重，甚至违纪（指导教师、 网络）。网络）。 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 参加竞赛前的准备参加竞赛前的准备 了解竞赛章程等相关信息；了解竞赛章程等相关信息； 掌握数学建模的基本方法（学过掌握数学建模的基本方法（学过“数学模型数学模型”或或“数学实验数学实验”课最好，自学一些基本内容也可以）；课最好，自学一些基本内容也可以）； 掌握基本的数学软件（掌握基本的数学软件（Matlab/Mathematica；LINGO；如能掌握；如能掌握SAS/JMP统计软件更好）；统计软件更好）； 训练规范的科技论文写作训练规范的科技论文写作/表达能力表达能力 (摘要、正文、摘要、正文、优缺点、参考文献及引用等优缺点、参考文献及引用等); 试做几道以前的赛题；试做几道以前的赛题； 培养合作精神。培养合作精神。 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 简要提纲简要提纲 应用数学与数学建模应用数学与数学建模 - 建模及建模竞赛的意义建模及建模竞赛的意义 竞赛评阅标准竞赛评阅标准 - 一般原则及主要问题一般原则及主要问题 创新能力培养创新能力培养 - 2007B分析分析 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 优化问题三要素：优化问题三要素：决策变量决策变量；目标函数目标函数；约束条件约束条件约约束束条条件件决策变量决策变量优化问题的一般形式优化问题的一般形式目标函数目标函数有人统计：有人统计： 优化问题占优化问题占CUMCM赛题的一半以上（赛题的一半以上（1/32/3） 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 建模时需要注意的几个基本问题建模时需要注意的几个基本问题 1、尽量使用实数优化，减少整数约束和整数变量尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最如：尽量少使用绝对值、符号函数、多个变量求最大大/最小值、四舍五入、取整函数等最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量尽量使用线性模型，减少非线性约束和非线性变量的个数的个数 （如（如x/y 5 改为改为x5y）4、合理设定变量上下界，尽可能给出变量初始值合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当模型中使用的参数数量级要适当 (如小于如小于103) 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 优化建模如何创新？优化建模如何创新？ 方法方法1：大胆创新，别出心裁：大胆创新，别出心裁 - 采用有特色的目标函数、约束条件等采用有特色的目标函数、约束条件等 - 你用非线性规划，我用线性规划你用非线性规划，我用线性规划 - 你用整数你用整数/离散规划，我用连续规划离散规划，我用连续规划/网络优化网络优化 - 方法方法2：细致入微，滴水不漏：细致入微，滴水不漏 - 对目标函数、约束条件处理特别细致对目标函数、约束条件处理特别细致 - 有算法设计和分析，不仅仅是简单套用软件有算法设计和分析，不仅仅是简单套用软件 - 敏感性分析详细敏感性分析详细 / 全面全面 - 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 2007B命题背景命题背景 奥运相关的题目：奥运相关的题目：(时代特性时代特性, 社会关注）社会关注）让运动员及时到达场馆（车辆调度，路径安排等）让运动员及时到达场馆（车辆调度，路径安排等） 应急管理（紧急疏散，应急调度等）应急管理（紧急疏散，应急调度等）赛程安排（单一项目，多个项目）赛程安排（单一项目，多个项目）成绩排名（如循环赛，体操或跳水等）成绩排名（如循环赛，体操或跳水等）技术类，如技术类，如“刘翔的运动鞋刘翔的运动鞋”乘公交，看奥运：原名乘公交，看奥运：原名“自动问路机自动问路机”方沛辰（吉大），吴孟达（国防科大）提出方沛辰（吉大），吴孟达（国防科大）提出原拟作乙组题，似乎难度太大原拟作乙组题，似乎难度太大 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 命题背景命题背景 定位：公交路线选择（查询）模型与算法定位：公交路线选择（查询）模型与算法如何给数据？如何给数据？抽象数据实际数据？（减小规模，不给地理信息）抽象数据实际数据？（减小规模，不给地理信息）貌似简单，实则不然貌似简单，实则不然数据处理（转换）方面有一定难度数据处理（转换）方面有一定难度换乘次数多时简单搜索不易（计算复杂度高）换乘次数多时简单搜索不易（计算复杂度高）换乘时间步行时间等需要考虑周全换乘时间步行时间等需要考虑周全标准的最短路算法（如标准的最短路算法（如Dijkstra算法）并不适用算法）并不适用 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 乘公交，看奥运乘公交，看奥运公交线路选择问题的自主查询计算机系统：核心是公交线路选择问题的自主查询计算机系统：核心是线路选择的线路选择的模型与算法模型与算法应该从应该从实际情况出发实际情况出发考虑，满足查询者的考虑，满足查询者的各种不同各种不同需求需求1: 仅考虑公汽线路，给出任意两公汽站点之间线路仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的选择问题的一般一般数学模型与算法数学模型与算法 2: 同时考虑公汽与地铁线路，解决以上问题同时考虑公汽与地铁线路，解决以上问题3: 假设又知道所有站点之间的步行时间，给出任意假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型两站点之间线路选择问题的数学模型 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 【附录【附录1】基本参数设定】基本参数设定相邻公汽站平均行驶时间(包括停站时间)： 3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）推论：换乘公汽等待分钟，换乘地铁等待分钟【附录【附录2】公交线路及相关信息】公交线路及相关信息 （见数据文件）（见数据文件） 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 线路数据中的问题线路数据中的问题线路数据中的异常或不明确之处，同学可根据自己的线路数据中的异常或不明确之处，同学可根据自己的理解理解作出作出假设假设和处理，一般不会影响实例的计算结果和处理，一般不会影响实例的计算结果个别线路相邻站点名相同，可去掉其中一点或不作处理等个别线路相邻站点名相同，可去掉其中一点或不作处理等L406未标明是环线，是否将其当作环线处理均可未标明是环线，是否将其当作环线处理均可L290标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为1477与与1479，可将所，可将所有线路中有线路中1477与与1479统一为统一为1477后计算。同学也可以按照各后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将自认为合理的方式处理，包括不当作环线，或将1479改为改为1477，或在，或在1479后增加后增加1477，等等，等等如果在假设中有明确约定，则环线单向或双向发车均应认可如果在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些）（按单向发车作假设，计算结果可能差些） 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 对通过地铁换乘的理解对通过地铁换乘的理解“假设同一地铁站对应的任意两个公汽站之间可以假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘通过地铁站换乘(无需支付地铁费无需支付地铁费)”步行：公汽站步行：公汽站地铁站（通道）地铁站（通道）公汽站公汽站换乘耗时换乘耗时11min：步行：步行4+4=8min; 等车等车3min第问（只考虑公汽）：可不考虑以上换乘第问（只考虑公汽）：可不考虑以上换乘有同学也考虑了如上换乘，只是不坐地铁，应该也可以有同学也考虑了如上换乘，只是不坐地铁，应该也可以此样处理时，第问和第问的难度相近此样处理时，第问和第问的难度相近 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 模型的目标模型的目标多目标优化问题多目标优化问题（至少考虑三方面）（至少考虑三方面）换乘次数最少换乘次数最少(N)、费用最省、费用最省(M)、时间最短、时间最短(T)从该问题的实际背景来看，从该问题的实际背景来看，加权加权太合适太合适 不少同学用层次分析法确定权不少同学用层次分析法确定权不少同学计算时间的价值（平均收入工作时间）不少同学计算时间的价值（平均收入工作时间）不同目标不同目标组合组合的模型的模型三个目标按优先级排序，组合成六个模型三个目标按优先级排序，组合成六个模型也可将某些目标作为约束也可将某些目标作为约束 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 多数队多数队仅仅采用搜索法（采用搜索法（70-80%?）直达；直达； 一次换乘；一次换乘； 二次换乘；二次换乘；ststs t求出所有线路；评价其目标求出所有线路；评价其目标(容易计算容易计算)；选优；选优 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 多数队多数队仅仅采用搜索法采用搜索法总体来看，技术含量较低（基本上是枚举）总体来看，技术含量较低（基本上是枚举）几乎没有建模，完全只有算法实现，算法也没什么创新几乎没有建模，完全只有算法实现，算法也没什么创新一般只考虑不超过两次换乘一般只考虑不超过两次换乘不少文章引用参考文献作为依据，实用中似乎够用不少文章引用参考文献作为依据，实用中似乎够用 题目难度大大降低，模型不够题目难度大大降低，模型不够一般一般换乘作为了换乘作为了第一目标第一目标，或作为一个，或作为一个最重要的约束最重要的约束任意次换乘时算法复杂度提高，难以处理任意次换乘时算法复杂度提高，难以处理结果不佳（如：从省时考虑，有些需次换乘）结果不佳（如：从省时考虑，有些需次换乘） 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 图论模型与最短路算法图论模型与最短路算法用图论做的队也不少，但往往考虑不周用图论做的队也不少，但往往考虑不周弧上赋权方式交代不清弧上赋权方式交代不清套用套用Dijkstra或或Floyd-Warshall算法，却不清楚其原理及算法，却不清楚其原理及适用的问题适用的问题需要建立一个带权有向图，节点表示站点，有向弧需要建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上的权表示前表示前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价一站点直达后一站点所需付出的代价(时间或费用时间或费用)图（网络）如何描述和表示？图（网络）如何描述和表示？基本要素：节点，有向弧（边），弧上赋权基本要素：节点，有向弧（边），弧上赋权邻接矩阵；关联矩阵（数学上处理方便，存储量较大）邻接矩阵；关联矩阵（数学上处理方便，存储量较大）链表（存储量较小，计算机上处理方便）链表（存储量较小，计算机上处理方便） 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 关联矩阵关联矩阵(Incidence Matrix)表示法表示法在线路选择问题中，当从在线路选择问题中，当从i i可直达可直达j j时，定义弧时，定义弧(i,j)(i,j)；其上的权可为或成本；其上的权可为或成本( (时间或费用时间或费用) )；多重弧可只保留一条（弧上的权可取最小的成多重弧可只保留一条（弧上的权可取最小的成本，如时间或费用）本，如时间或费用）G=(V，A)是一个简单有向图；是一个简单有向图；|V|=n，|A|=m 重要数学性质：重要数学性质：关联矩阵是全幺模矩阵关联矩阵是全幺模矩阵图图G=(V，A)的的邻邻接接矩矩阵阵C是是如如下下定定义义的的：C是是一一个个 的矩阵，即的矩阵，即 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 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次可达矩阵次可达矩阵； 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 链表（邻接表）表示法链表（邻接表）表示法 122345283904602403053036470单向链表(指针数组) A(1)=2,3A(2)=4A(3)=2A(4)=3,5A(5)=3,412345 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 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点的前一点点的前一点 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. Example 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. DijkstraDijkstra算法（标号设定算法）算法（标号设定算法）适用于正费用网络：适用于正费用网络：“分层分层”设定标号设定标号永久标号：永久标号：S中的点，中的点，uj是最短路长是最短路长临时标号；临时标号；其他点，其他点， uj是只通过是只通过S中的点的最短路长中的点的最短路长对对于于稠稠密密网网络络，这这是是求求解解最最短短路路问问题题可可能能达达到到的的最最小小的的复复杂杂度度, ,因为任何算法都至少必须对每条弧考虑一次因为任何算法都至少必须对每条弧考虑一次. .对于稀疏网络，利用各种形式的对于稀疏网络，利用各种形式的堆（堆（HeapHeap），其复杂度可降为，其复杂度可降为 或或 等等算法复杂度算法复杂度O( n2+m)：如链表或邻接矩阵实现：如链表或邻接矩阵实现找最小标号点修改标号找最小标号点修改标号 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 特点：求所有点对间最短路特点：求所有点对间最短路基本思想：逐步逼近，迭代求解最短路方程基本思想：逐步逼近，迭代求解最短路方程: : O(n3)Floyd-Warshall算法算法 （标号修正算法标号修正算法，1962)1962)临临时时标标号号 是是不不通通过过k，k+1，,n 节节点点(i,j 除除外外)时时从从节节点点i到节点到节点j的最短路路长的最短路路长. 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 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: 若若 , 令令 , ; 否则令否则令 , . 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. Floyd-Warshall算法的算法的矩阵迭代法实现：矩阵迭代法实现：O(n4)令令D为权矩阵为权矩阵(直达最短路长直达最短路长)Dm为正好经过为正好经过m条弧从条弧从i到到j的最短路长的最短路长 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 问题问题1和和2的一种具体建模方法的一种具体建模方法(赋权赋权)在线路选择问题中，当从在线路选择问题中，当从i i可直达可直达j j时（时（同为公同为公汽或地铁站点汽或地铁站点），定义弧），定义弧(i,j)(i,j)；其上的权为；其上的权为lij表示由表示由i直达直达j付出的代价，可以为时间或费用付出的代价，可以为时间或费用 (不包不包括换乘代价；多条线路可达时只保留最小代价括换乘代价；多条线路可达时只保留最小代价)初始等车时间初始等车时间2(3)min也不包括在内，最后结果可加上也不包括在内，最后结果可加上注意：注意：D=D(0)不是对称矩阵不是对称矩阵(“直达矩阵直达矩阵”)dij(0)=dij 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 问题的一种具体建模方法问题的一种具体建模方法i站点是公汽站点，站点是公汽站点，j站点为地铁站点：站点为地铁站点：（1）若若j站站点点对对应应的的所所有有换换乘乘(公公汽汽)站站点点k，均均不不能能从从i直直达达(不不在在i站站点点所所在在公公汽汽线线路路L上上)，则则dij(0) =. （2）若若j站站点点对对应应的的换换乘乘站站点点(k), 可可从从i站站点点直直达达k，则则费费用用为为dij(0) = dik(0)；对对于于时时间间则则需需要要加加上上k到到j的步行的步行时间. (若有多种选择，取最小成本者即可若有多种选择，取最小成本者即可)ikj 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 问题的一种具体建模方法问题的一种具体建模方法j站点是公汽站点，站点是公汽站点，i站点为地铁站点：站点为地铁站点：（1）若若从从i站站点点对对应应的的任任何何换换乘乘(公公汽汽)站站点点k，均均不不能能直直达达j站点，则站点，则dij(0) =. （2）若若从从i站站点点对对应应的的换换乘乘(公公汽汽)站站点点k，能能直直达达j站站点点， 则则费用为费用为dij(0) = dkj(0)；对于时间则需要；对于时间则需要加上加上i到到k的步行的步行时间. ikj 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 问题：最小费用或时间问题：最小费用或时间 定义矩阵算子定义矩阵算子“ ”如下：设如下：设A、B均为均为n阶方阵，阶方阵， C = A B (考虑考虑换乘代价换乘代价)当考当考虑费用矩用矩阵之之间的运算的运算时，表示在表示在k的换乘时间的换乘时间 当考当考虑时间矩矩阵之之间的运算的运算时， D(k)= D(k-1) D 表示表示k次换乘的最低代价次换乘的最低代价(费用或时间费用或时间) 该算法大体相当于求最短路的该算法大体相当于求最短路的Floyd-Warshall算法，算法，但考虑了换乘因素，可称为改进但考虑了换乘因素，可称为改进Floyd-Warshall算法算法 类似地类似地,通过修改通过修改Dijkstra算法求解也可算法求解也可 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 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 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 第问：已知所有站点间步行时间第问：已知所有站点间步行时间多数队没有给出一般模型多数队没有给出一般模型, 而只考虑最多一次换乘而只考虑最多一次换乘多数队的想法：假设多数队的想法：假设“起点步行起点步行”，“换乘步行换乘步行”，“终点步行终点步行”三种模式，限定三种模式，限定步行最大时间步行最大时间后搜索后搜索ikj 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 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规划规划) ? 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 最短路问题的线性规划模型最短路问题的线性规划模型线性规划模型，应该可以计算到比较大规模的问题线性规划模型，应该可以计算到比较大规模的问题有些队写出了上述模型，但并未用该模型求解有些队写出了上述模型，但并未用该模型求解可能需要强大的优化软件，数据输入工作量也较大可能需要强大的优化软件，数据输入工作量也较大换乘代价不易考虑（网络上的权不易定义，或不具换乘代价不易考虑（网络上的权不易定义，或不具可加性）可加性） 有些同学提到有些同学提到动态规划动态规划, 但要么与这里介绍的最短但要么与这里介绍的最短路算法等价路算法等价, 要么处理有误要么处理有误, 或只是搜索法的变种或只是搜索法的变种 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 有些队讨论有些队讨论“交通阻抗交通阻抗”:“”:“文不对题文不对题”道路阻抗在交通流分配中可以通过道路阻抗在交通流分配中可以通过路阻函数路阻函数来描述来描述所谓路阻函数是指路段行驶时间与路段交通负荷，交所谓路阻函数是指路段行驶时间与路段交通负荷，交叉口延误与交叉口负荷之间的关系叉口延误与交叉口负荷之间的关系在具体分配过程中，由路段行驶时间及交叉口延误共在具体分配过程中，由路段行驶时间及交叉口延误共同组成出行交通阻抗同组成出行交通阻抗交通网络上的路阻，应包含反映交通时间、交通安全、交通网络上的路阻，应包含反映交通时间、交通安全、交通成本、舒适程度、便捷性和准时性等等许多因素交通成本、舒适程度、便捷性和准时性等等许多因素 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. 同学论文中存在的主要问题同学论文中存在的主要问题2. 目标不当，或不完整目标不当，或不完整 3. 换乘时间处理不当换乘时间处理不当- 尤其地铁站与公汽站之间，以及尤其地铁站与公汽站之间，以及- 通过地铁通道换乘的公汽站之间通过地铁通道换乘的公汽站之间1. 几乎没有模型，只有算法（一般是搜索法）几乎没有模型，只有算法（一般是搜索法）4. 算法使用不当，或滥用算法使用不当，或滥用5. 对第问，很少认真进行讨论和建模对第问，很少认真进行讨论和建模6. 全文表达不清，思路混乱全文表达不清，思路混乱 谢金星谢金星, 清华大学数学科学系清华大学数学科学系, 2007-2008. Thats all. Any Questions? Thank you for your attendance! 最后，祝大家在数学建模活动中取得更大的成绩！谢金星, 清华大学数学科学系, 2007-2008.