《数学建模赛题分析建模方法课件.ppt》由会员分享，可在线阅读，更多相关《数学建模赛题分析建模方法课件.ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学建模赛题分析建模方法第1页，此课件共57页哦简要提要提纲 n n 应用数学与数学建模应用数学与数学建模应用数学与数学建模应用数学与数学建模 -建模及建模竞赛的意义建模及建模竞赛的意义建模及建模竞赛的意义建模及建模竞赛的意义n 竞赛评阅标准竞赛评阅标准 -一般原则及主要问题一般原则及主要问题n n 优化模型的创新优化模型的创新优化模型的创新优化模型的创新 -2007B-2007B题分析题分析题分析题分析第2页，此课件共57页哦数学知识数学知识数学知识数学知识数学技巧数学技巧数学技巧数学技巧数学应用数学应用数学发现数学发现应用数学用数学数学技数学技术数学数学实验随机数学随机数学随机数学随机数学
2、代数与几何代数与几何代数与几何代数与几何微微微微积积分分分分数学美学数学美学数学哲学数学哲学数学精神数学精神数学素质数学素质数学文化数学文化数学：几个层次的理解第3页，此课件共57页哦数学建模：实际与数学之间的桥梁实际问题实际问题实际问题实际问题数学数学数学数学Mathematical ModelingMathematical Modeling 现实对象的信息现实对象的信息现实对象的信息现实对象的信息数学模型数学模型数学模型数学模型现实对象的解答现实对象的解答现实对象的解答现实对象的解答数学模型的解答数学模型的解答数学模型的解答数学模型的解答表述表述表述表述求解求解求解求解解解解解释释验证验证
3、(归纳归纳)(演绎)数学建模数学建模的全过程的全过程第4页，此课件共57页哦美国MCM+ICM竞赛规模第5页，此课件共57页哦我国CUMCM竞赛规模第6页，此课件共57页哦n n学生欢迎：学生欢迎：学生欢迎：学生欢迎：“一次参赛，终身受益一次参赛，终身受益一次参赛，终身受益一次参赛，终身受益”n n研究生导师们的认同研究生导师们的认同研究生导师们的认同研究生导师们的认同n n企业界的认同赞助企业界的认同赞助企业界的认同赞助企业界的认同赞助n n教育改革同行的认同：教育改革同行的认同：教育改革同行的认同：教育改革同行的认同：“成功范例成功范例成功范例成功范例”n n国际同行的认同国际同行的认同国
4、际同行的认同国际同行的认同竞赛的反响的反响第7页，此课件共57页哦IBM IBM 中国研究中心中国研究中心中国研究中心中国研究中心-招聘条件招聘条件Position title:Business Optimization(BJ)Position title:Business Optimization(BJ)1 1Background in industrial engineering,operations research,Background in industrial engineering,operations research,mathematics,Artificial Intell
5、igence,management science etc.mathematics,Artificial Intelligence,management science etc.2.2.Knowledge in network design,job scheduling,data analysis,Knowledge in network design,job scheduling,data analysis,simulation and optimization simulation and optimization 3.Award in mathematical contest in mo
6、deling is a plus3.Award in mathematical contest in modeling is a plus 4.Experience in industry is a plus Experience in industry is a plus 5.Experience in eclipse or programming model/architecture Experience in eclipse or programming model/architecture design is a plusdesign is a plus-Feb.18,2006,htt
7、p:/ n n 应用数学与数学建模应用数学与数学建模应用数学与数学建模应用数学与数学建模 -建模及建模竞赛的意义建模及建模竞赛的意义建模及建模竞赛的意义建模及建模竞赛的意义n 竞赛评阅标准竞赛评阅标准 -一般原则及主要问题一般原则及主要问题一般原则及主要问题一般原则及主要问题n n 创新能力培养创新能力培养创新能力培养创新能力培养 -几个例子（结合优化模型）几个例子（结合优化模型）几个例子（结合优化模型）几个例子（结合优化模型）第9页，此课件共57页哦CUMCMCUMCM评阅标准评阅标准清晰性：摘要应理解为详细摘要，提纲挈领清晰性：摘要应理解为详细摘要，提纲挈领清晰性：摘要应理解为详细摘要，提
8、纲挈领清晰性：摘要应理解为详细摘要，提纲挈领 表达严谨、简捷，思路清新表达严谨、简捷，思路清新表达严谨、简捷，思路清新表达严谨、简捷，思路清新 格式符合规范，严禁暴露身份格式符合规范，严禁暴露身份创造性：特别欣赏独树一帜、标新立异，但要合理创造性：特别欣赏独树一帜、标新立异，但要合理假设的合理性，建模的创造性，假设的合理性，建模的创造性，假设的合理性，建模的创造性，假设的合理性，建模的创造性，结果的正确性，表述的清晰性。结果的正确性，表述的清晰性。结果的正确性，表述的清晰性。结果的正确性，表述的清晰性。正确性：正确性：正确性：正确性：不强调与不强调与不强调与不强调与“参考答案参考答案参考答案参
9、考答案”的一致性和结果的精度；的一致性和结果的精度；的一致性和结果的精度；的一致性和结果的精度；好方法的结果一般比较好；但不一定是最好的好方法的结果一般比较好；但不一定是最好的好方法的结果一般比较好；但不一定是最好的好方法的结果一般比较好；但不一定是最好的合理性：关键假设；不欣赏罗列大量无关紧要的假设合理性：关键假设；不欣赏罗列大量无关紧要的假设合理性：关键假设；不欣赏罗列大量无关紧要的假设合理性：关键假设；不欣赏罗列大量无关紧要的假设 第10页，此课件共57页哦CUMCMCUMCM评阅标准评阅标准:一些常见问题一些常见问题有的论文过于简单，该交代的内容省略了，难以看懂有的论文过于简单，该交代
10、的内容省略了，难以看懂有的队罗列一系列假设或模型，又不作比较、评价，有的队罗列一系列假设或模型，又不作比较、评价，有的队罗列一系列假设或模型，又不作比较、评价，有的队罗列一系列假设或模型，又不作比较、评价，希望碰上希望碰上希望碰上希望碰上“参考答案参考答案参考答案参考答案”或或或或“评阅思路评阅思路评阅思路评阅思路”，弄巧成拙，弄巧成拙，弄巧成拙，弄巧成拙数学模型最好数学模型最好明确、合理、简洁：明确、合理、简洁：明确、合理、简洁：明确、合理、简洁：有些论文不给出明确的模型，只是根据赛题的情况，有些论文不给出明确的模型，只是根据赛题的情况，有些论文不给出明确的模型，只是根据赛题的情况，有些论文
11、不给出明确的模型，只是根据赛题的情况，实际上是用实际上是用实际上是用实际上是用“凑凑凑凑”的方法给出结果，虽然结果大致是对的方法给出结果，虽然结果大致是对的方法给出结果，虽然结果大致是对的方法给出结果，虽然结果大致是对的，没有一般性，不是数学建模的正确思路。的，没有一般性，不是数学建模的正确思路。的，没有一般性，不是数学建模的正确思路。的，没有一般性，不是数学建模的正确思路。有的论文参考文献不全，或引用他人结果不作交代有的论文参考文献不全，或引用他人结果不作交代有的论文参考文献不全，或引用他人结果不作交代有的论文参考文献不全，或引用他人结果不作交代第11页，此课件共57页哦从从论文文评阅看学生
12、参加看学生参加竞赛中的中的问题n n 吃透题意方面不足，没有抓住和解决主要问题；吃透题意方面不足，没有抓住和解决主要问题；吃透题意方面不足，没有抓住和解决主要问题；吃透题意方面不足，没有抓住和解决主要问题；n n 就事论事，形成数学模型的意识和能力欠缺；就事论事，形成数学模型的意识和能力欠缺；就事论事，形成数学模型的意识和能力欠缺；就事论事，形成数学模型的意识和能力欠缺；n 对所用方法一知半解，不管具体条件，套用现成的方对所用方法一知半解，不管具体条件，套用现成的方法，导致错误；法，导致错误；n 对结果的分析不够，怎样符合实际考虑不周；对结果的分析不够，怎样符合实际考虑不周；n n 写作方面的
13、问题写作方面的问题写作方面的问题写作方面的问题(摘要、简明、优缺点、参考文献摘要、简明、优缺点、参考文献摘要、简明、优缺点、参考文献摘要、简明、优缺点、参考文献););n n 队员之间合作精神差，孤军奋战；队员之间合作精神差，孤军奋战；队员之间合作精神差，孤军奋战；队员之间合作精神差，孤军奋战；n 依赖心理重，甚至违纪（指导教师、依赖心理重，甚至违纪（指导教师、网络）。网络）。第12页，此课件共57页哦简要提要提纲 n n 应用数学与数学建模应用数学与数学建模 -建模及建模竞赛的意义建模及建模竞赛的意义建模及建模竞赛的意义建模及建模竞赛的意义n 竞赛评阅标准竞赛评阅标准 -一般原则及主要问题一
14、般原则及主要问题一般原则及主要问题一般原则及主要问题n n 创新能力培养创新能力培养创新能力培养创新能力培养 -2007B-2007B分析分析分析分析第13页，此课件共57页哦n n 优优化化化化问题问题三要素：三要素：三要素：三要素：决策决策变量量；目目目目标标函数函数函数函数；约约束条件束条件束条件束条件约束束条条件件决策决策变量量优化化问题的一般形式的一般形式目目标函数函数n n有人统计：有人统计：有人统计：有人统计：优化问题占优化问题占优化问题占优化问题占CUMCMCUMCM赛题的一半以上（赛题的一半以上（赛题的一半以上（赛题的一半以上（1/32/31/32/3）2022/10/514
15、第14页，此课件共57页哦 建模建模时需要注意的几个基本需要注意的几个基本问题 1 1、尽量使用实数优化，减少整数约束和整数变量尽量使用实数优化，减少整数约束和整数变量尽量使用实数优化，减少整数约束和整数变量尽量使用实数优化，减少整数约束和整数变量2 2、尽量使用光滑优化，减少非光滑约束的个数尽量使用光滑优化，减少非光滑约束的个数尽量使用光滑优化，减少非光滑约束的个数尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大如：尽量少使用绝对值、符号函数、多个变量求最大如：尽量少使用绝对值、符号函数、多个变量求最大如：尽量少使用绝对值、符号函数、多个变量求最大/最小
16、值、最小值、最小值、最小值、四舍五入、取整函数等四舍五入、取整函数等四舍五入、取整函数等四舍五入、取整函数等3 3、尽量使用线性模型，减少非线性约束和非线性变量的个数尽量使用线性模型，减少非线性约束和非线性变量的个数尽量使用线性模型，减少非线性约束和非线性变量的个数尽量使用线性模型，减少非线性约束和非线性变量的个数 （如（如（如（如x/yx/y 5 5 改为改为改为改为xx5 5y y）4 4、合理设定变量上下界，尽可能给出变量初始值合理设定变量上下界，尽可能给出变量初始值合理设定变量上下界，尽可能给出变量初始值合理设定变量上下界，尽可能给出变量初始值 5 5、模型中使用的参数数量级要适当模型
17、中使用的参数数量级要适当模型中使用的参数数量级要适当模型中使用的参数数量级要适当 (如小于如小于如小于如小于10103 3)第15页，此课件共57页哦优化建模如何化建模如何创新？新？n 方法方法方法方法1 1：大胆创新，别出心裁：大胆创新，别出心裁：大胆创新，别出心裁：大胆创新，别出心裁 -采用有特色的目标函数、约束条件等采用有特色的目标函数、约束条件等采用有特色的目标函数、约束条件等采用有特色的目标函数、约束条件等 -你用非线性规划，我用线性规划你用非线性规划，我用线性规划你用非线性规划，我用线性规划你用非线性规划，我用线性规划 -你用整数你用整数你用整数你用整数/离散规划，我用连续规划离散
18、规划，我用连续规划离散规划，我用连续规划离散规划，我用连续规划/网络优化网络优化网络优化网络优化 -n 方法方法方法方法2：细致入微，滴水不漏：细致入微，滴水不漏 -对目标函数、约束条件处理特别细致对目标函数、约束条件处理特别细致对目标函数、约束条件处理特别细致对目标函数、约束条件处理特别细致 -有算法设计和分析，不仅仅是简单套用软件有算法设计和分析，不仅仅是简单套用软件有算法设计和分析，不仅仅是简单套用软件有算法设计和分析，不仅仅是简单套用软件 -敏感性分析详细敏感性分析详细敏感性分析详细敏感性分析详细 /全面全面全面全面 -第16页，此课件共57页哦2007B命题背景命题背景 n n奥运相
19、关的题目：奥运相关的题目：(时代特性时代特性时代特性时代特性,社会关注）社会关注）uu让运动员及时到达场馆（车辆调度，路径安排等）让运动员及时到达场馆（车辆调度，路径安排等）让运动员及时到达场馆（车辆调度，路径安排等）让运动员及时到达场馆（车辆调度，路径安排等）uu应急管理（紧急疏散，应急调度等）应急管理（紧急疏散，应急调度等）应急管理（紧急疏散，应急调度等）应急管理（紧急疏散，应急调度等）uu赛程安排（单一项目，多个项目）赛程安排（单一项目，多个项目）赛程安排（单一项目，多个项目）赛程安排（单一项目，多个项目）uu成绩排名（如循环赛，体操或跳水等）成绩排名（如循环赛，体操或跳水等）成绩排名（
20、如循环赛，体操或跳水等）成绩排名（如循环赛，体操或跳水等）uu技术类，如技术类，如技术类，如技术类，如“刘翔的运动鞋刘翔的运动鞋刘翔的运动鞋刘翔的运动鞋”n n乘公交，看奥运：原名乘公交，看奥运：原名乘公交，看奥运：原名乘公交，看奥运：原名“自动问路机自动问路机自动问路机自动问路机”uu方沛辰（吉大），吴孟达（国防科大）提出方沛辰（吉大），吴孟达（国防科大）提出方沛辰（吉大），吴孟达（国防科大）提出方沛辰（吉大），吴孟达（国防科大）提出uu原拟作乙组题，似乎难度太大原拟作乙组题，似乎难度太大原拟作乙组题，似乎难度太大原拟作乙组题，似乎难度太大第17页，此课件共57页哦命题背景命题背景 n n定
21、位：公交路线选择（查询）模型与算法定位：公交路线选择（查询）模型与算法n n如何给数据？如何给数据？如何给数据？如何给数据？uu抽象数据实际数据？（减小规模，不给地理信息）抽象数据实际数据？（减小规模，不给地理信息）抽象数据实际数据？（减小规模，不给地理信息）抽象数据实际数据？（减小规模，不给地理信息）n n貌似简单，实则不然貌似简单，实则不然貌似简单，实则不然貌似简单，实则不然uu数据处理（转换）方面有一定难度数据处理（转换）方面有一定难度数据处理（转换）方面有一定难度数据处理（转换）方面有一定难度uu换乘次数多时简单搜索不易（计算复杂度高）换乘次数多时简单搜索不易（计算复杂度高）换乘次数多
22、时简单搜索不易（计算复杂度高）换乘次数多时简单搜索不易（计算复杂度高）uu换乘时间步行时间等需要考虑周全换乘时间步行时间等需要考虑周全换乘时间步行时间等需要考虑周全换乘时间步行时间等需要考虑周全uu标准的最短路算法（如标准的最短路算法（如标准的最短路算法（如标准的最短路算法（如DijkstraDijkstra算法）并不适用算法）并不适用算法）并不适用算法）并不适用第18页，此课件共57页哦 B B题：乘公交，看奥运题：乘公交，看奥运题：乘公交，看奥运题：乘公交，看奥运 第第第第2929届奥运会届奥运会届奥运会届奥运会0808年年年年8月将在北京举行，届时有大量观众到现月将在北京举行，届时有大量
23、观众到现月将在北京举行，届时有大量观众到现月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。北京市的公交线路已达公交，包括公汽、地铁等）出行。北京市的公交线路已达公交，包括公汽、地铁等）出行。北京市的公交线路已达公交，包括公汽、地铁等）出行。北京市的公交线路已达800800条以上，使得公众的出行更加通畅、便利，但同时也面条以上，使得公众的出行更加通畅、便利，但同时也面
24、临多条线路的选择问题。针对市场需求，某公司准备研临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系制开发一个解决公交线路选择问题的自主查询计算机系统。统。应该应该应该应该从实际情况出发考虑，满足查询者从实际情况出发考虑，满足查询者从实际情况出发考虑，满足查询者从实际情况出发考虑，满足查询者的各种不同需求。的各种不同需求。的各种不同需求。的各种不同需求。07-B 题题 解解 题题 分分 析析 为了设计这样一个系统，其为了设计这样一个系统，其为了设计这样一个系统，其为了设计这样一个系统，其核心是核心是核心是核心是线路选择的模型与算法线路选择的模型与算法
25、线路选择的模型与算法线路选择的模型与算法。第19页，此课件共57页哦07-B 题题 解解 题题 分分 析析请解决如下问题：请解决如下问题：请解决如下问题：请解决如下问题：1、仅考虑公汽线路，给出、仅考虑公汽线路，给出、仅考虑公汽线路，给出、仅考虑公汽线路，给出任意两公汽站点之间线路任意两公汽站点之间线路任意两公汽站点之间线路任意两公汽站点之间线路选择问题的一般数学模型与算法选择问题的一般数学模型与算法选择问题的一般数学模型与算法选择问题的一般数学模型与算法。并根据附录数据，利用。并根据附录数据，利用。并根据附录数据，利用。并根据附录数据，利用你们的模型与算法，求出以下你们的模型与算法，求出以下
26、你们的模型与算法，求出以下你们的模型与算法，求出以下6 6对起始站对起始站对起始站对起始站终到站之间的终到站之间的终到站之间的终到站之间的最佳路线（最佳路线（最佳路线（最佳路线（要有清晰的评价说明要有清晰的评价说明）。）。）。）。(1)(1)、S3359S1828 (2)S3359S1828 (2)、S1557S0481 S1557S0481 (3)(3)、S0971S0485 (4)、S0008S0073 S0008S0073 (5)(5)、S0148S0485 (6)S0148S0485 (6)、S0087S3676S0087S36762 2、同时考虑公汽与地铁线路，解决以上问题。、同时考
27、虑公汽与地铁线路，解决以上问题。3 3、假设又知道所有站点之间的步行时间、假设又知道所有站点之间的步行时间、假设又知道所有站点之间的步行时间、假设又知道所有站点之间的步行时间,请你请你请你请你给出任意两站点之间线路选择问题的数学模型。给出任意两站点之间线路选择问题的数学模型。给出任意两站点之间线路选择问题的数学模型。给出任意两站点之间线路选择问题的数学模型。第20页，此课件共57页哦07-B 题题 解解 题题 分分 析析【附录附录附录附录1 1】基本参数设定基本参数设定基本参数设定基本参数设定相邻公汽站平均行驶时间相邻公汽站平均行驶时间相邻公汽站平均行驶时间相邻公汽站平均行驶时间(包括停站时间
28、包括停站时间包括停站时间包括停站时间)：3 3分钟分钟分钟分钟相邻地铁站平均行驶时间相邻地铁站平均行驶时间相邻地铁站平均行驶时间相邻地铁站平均行驶时间(包括停站时间包括停站时间包括停站时间包括停站时间)：2.52.5分钟分钟分钟分钟公汽换乘公汽平均耗时：公汽换乘公汽平均耗时：公汽换乘公汽平均耗时：公汽换乘公汽平均耗时：5 5分钟分钟分钟分钟(其中步行时间其中步行时间其中步行时间其中步行时间2 2分钟分钟分钟分钟)地铁换乘地铁平均耗时：地铁换乘地铁平均耗时：地铁换乘地铁平均耗时：地铁换乘地铁平均耗时：4 4分钟分钟分钟分钟(其中步行时间其中步行时间其中步行时间其中步行时间2 2分钟分钟分钟分钟)
29、地铁换乘公汽平均耗时：地铁换乘公汽平均耗时：地铁换乘公汽平均耗时：地铁换乘公汽平均耗时：7 7分钟分钟分钟分钟(其中步行时间其中步行时间其中步行时间其中步行时间4 4分钟分钟分钟分钟)公汽换乘地铁平均耗时：公汽换乘地铁平均耗时：公汽换乘地铁平均耗时：公汽换乘地铁平均耗时：6 6分钟分钟分钟分钟(其中步行时间其中步行时间其中步行时间其中步行时间4 4分钟分钟分钟分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；公汽票价：分为单一票价与分段计价两种，标记于线路后；公汽票价：分为单一票价与分段计价两种，标记于线路后；公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：其
30、中分段计价的票价为：其中分段计价的票价为：其中分段计价的票价为：0 02020站：站：站：站：1 1元；元；元；元；21214040站：站：站：站：2 2元；元；元；元；4040站以上：站以上：站以上：站以上：3 3元元元元地铁票价：地铁票价：地铁票价：地铁票价：3 3元（无论地铁线路间是否换乘）元（无论地铁线路间是否换乘）元（无论地铁线路间是否换乘）元（无论地铁线路间是否换乘）【附录附录附录附录2 2】公交线路及相关信息公交线路及相关信息公交线路及相关信息公交线路及相关信息 （见数据文件（见数据文件（见数据文件（见数据文件B2007data.rarB2007data.rar）第21页，此课件
31、共57页哦线路数据中的问题线路数据中的问题线路数据中的异常或不明确之处，同学可根据自己的线路数据中的异常或不明确之处，同学可根据自己的线路数据中的异常或不明确之处，同学可根据自己的线路数据中的异常或不明确之处，同学可根据自己的理解理解理解理解作出作出作出作出假设假设假设假设和处和处和处和处理，一般不会影响实例的计算结果理，一般不会影响实例的计算结果理，一般不会影响实例的计算结果理，一般不会影响实例的计算结果uu个别线路相邻站点名相同，可去掉其中一点或不作处理等个别线路相邻站点名相同，可去掉其中一点或不作处理等个别线路相邻站点名相同，可去掉其中一点或不作处理等个别线路相邻站点名相同，可去掉其中一
32、点或不作处理等uuL406L406未标明是环线，是否将其当作环线处理均可未标明是环线，是否将其当作环线处理均可未标明是环线，是否将其当作环线处理均可未标明是环线，是否将其当作环线处理均可uuL290L290标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为14771477与与与与14791479，可将所有线路，可将所有线路，可将所有线路，可将所有线路中中中中14771477与与与与14791479统一为统一为统一为统一为14771477后计算。同学也可以按照各自认为合理后计算。同学也可以按照各自认为合理后计算。同学也可以按照各自认为
33、合理后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将的方式处理，包括不当作环线，或将的方式处理，包括不当作环线，或将的方式处理，包括不当作环线，或将14791479改为改为改为改为14771477，或在，或在，或在，或在14791479后后后后增加增加增加增加14771477，等等，等等，等等，等等uu如果在假设中有明确约定，则环线单向或双向发车均应认可如果在假设中有明确约定，则环线单向或双向发车均应认可如果在假设中有明确约定，则环线单向或双向发车均应认可如果在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些）（按单向发车作假设，计算结果可能
34、差些）（按单向发车作假设，计算结果可能差些）（按单向发车作假设，计算结果可能差些）第22页，此课件共57页哦对通过地铁换乘的理解对通过地铁换乘的理解n n“假设同一地铁站对应的任意两个公汽站之间可以通过地假设同一地铁站对应的任意两个公汽站之间可以通过地假设同一地铁站对应的任意两个公汽站之间可以通过地假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘铁站换乘铁站换乘铁站换乘(无需支付地铁费无需支付地铁费)”n n步行：公汽站步行：公汽站步行：公汽站步行：公汽站地铁站（通道）地铁站（通道）地铁站（通道）地铁站（通道）公汽站公汽站公汽站公汽站n n换乘耗时换乘耗时换乘耗时换乘耗时11min：步
35、行：步行4+4=8min;等车等车等车等车3minn n第问（只考虑公汽）：可不考虑以上换乘第问（只考虑公汽）：可不考虑以上换乘uu有同学也考虑了如上换乘，只是不坐地铁，应该也可以有同学也考虑了如上换乘，只是不坐地铁，应该也可以有同学也考虑了如上换乘，只是不坐地铁，应该也可以有同学也考虑了如上换乘，只是不坐地铁，应该也可以uu此样处理时，第问和第问的难度相近此样处理时，第问和第问的难度相近此样处理时，第问和第问的难度相近此样处理时，第问和第问的难度相近第23页，此课件共57页哦07-B 题题 解解 题题 分分 析析 题目特点题目特点 1 1、本题根据公交线路查询系统研制的实际需求简本题根据公交
36、线路查询系统研制的实际需求简 化改编而成；化改编而成；化改编而成；化改编而成；2 2、问题容易理解，相关参考文献较多；、问题容易理解，相关参考文献较多；、问题容易理解，相关参考文献较多；、问题容易理解，相关参考文献较多；3 3、相关知识点：、相关知识点：、相关知识点：、相关知识点：（1 1）图论（最短路径）；）图论（最短路径）；（2 2）多目标规划。）多目标规划。）多目标规划。）多目标规划。4 4、题目开放度不够，可发挥余地不多。、题目开放度不够，可发挥余地不多。、题目开放度不够，可发挥余地不多。、题目开放度不够，可发挥余地不多。第24页，此课件共57页哦关于数据的预处理：关于数据的预处理：1
37、 1、对于原始数据中出现的一些异常数据，可根据自己的理解作出假设、对于原始数据中出现的一些异常数据，可根据自己的理解作出假设、对于原始数据中出现的一些异常数据，可根据自己的理解作出假设、对于原始数据中出现的一些异常数据，可根据自己的理解作出假设和处理。如：和处理。如：和处理。如：和处理。如：（1 1）对于个别线路相邻点名相同，可以采取去掉其中）对于个别线路相邻点名相同，可以采取去掉其中）对于个别线路相邻点名相同，可以采取去掉其中）对于个别线路相邻点名相同，可以采取去掉其中1 1点或不作处理等方式，点或不作处理等方式，点或不作处理等方式，点或不作处理等方式，一般不会影响实例计算中线路选择的结果。
38、一般不会影响实例计算中线路选择的结果。一般不会影响实例计算中线路选择的结果。一般不会影响实例计算中线路选择的结果。（2 2）对于）对于）对于）对于L406L406未标明是环行线的问题，无论学生是否将其当作环线处理，未标明是环行线的问题，无论学生是否将其当作环线处理，未标明是环行线的问题，无论学生是否将其当作环线处理，未标明是环行线的问题，无论学生是否将其当作环线处理，一般不会影响到实例的计算结果。一般不会影响到实例的计算结果。一般不会影响到实例的计算结果。一般不会影响到实例的计算结果。（3 3）对于）对于）对于）对于L290L290标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为标明是
39、环线，但首尾站点分别为标明是环线，但首尾站点分别为14771477与与与与14791479的问题，可将所的问题，可将所的问题，可将所的问题，可将所有线路中有线路中有线路中有线路中14771477与与与与14791479统一为统一为统一为统一为14771477后计算。也可以按照各自认为合理的方后计算。也可以按照各自认为合理的方后计算。也可以按照各自认为合理的方后计算。也可以按照各自认为合理的方式处理，包括不当作环线，实例计算用到的是该线路中部的几个站点，式处理，包括不当作环线，实例计算用到的是该线路中部的几个站点，式处理，包括不当作环线，实例计算用到的是该线路中部的几个站点，式处理，包括不当作环
40、线，实例计算用到的是该线路中部的几个站点，一般不会影响实例计算结果。一般不会影响实例计算结果。一般不会影响实例计算结果。一般不会影响实例计算结果。07-B 题题 解解 题题 分分 析析2 2、关于环行线路，可以假设为单向或双向。、关于环行线路，可以假设为单向或双向。、关于环行线路，可以假设为单向或双向。、关于环行线路，可以假设为单向或双向。3 3、线路数据格式需编程进行转换。、线路数据格式需编程进行转换。、线路数据格式需编程进行转换。、线路数据格式需编程进行转换。第25页，此课件共57页哦 模型的目标模型的目标n n多目标优化问题多目标优化问题多目标优化问题多目标优化问题（至少考虑三方面）（至
41、少考虑三方面）（至少考虑三方面）（至少考虑三方面）uu换乘次数最少换乘次数最少换乘次数最少换乘次数最少(N)(N)、费用最省、费用最省、费用最省、费用最省(M)(M)、时间最短、时间最短、时间最短、时间最短(T)(T)n n从该问题的实际背景来看，从该问题的实际背景来看，加权不加权不加权不加权不太合适太合适 uu不少同学用层次分析法确定权不少同学用层次分析法确定权不少同学用层次分析法确定权不少同学用层次分析法确定权uu不少同学计算时间的价值（平均收入工作时间）不少同学计算时间的价值（平均收入工作时间）不少同学计算时间的价值（平均收入工作时间）不少同学计算时间的价值（平均收入工作时间）n n不同
42、目标不同目标不同目标不同目标组合组合组合组合的模型的模型的模型的模型uu三个目标按优先级排序，组合成六个模型三个目标按优先级排序，组合成六个模型三个目标按优先级排序，组合成六个模型三个目标按优先级排序，组合成六个模型uu也可将某些目标作为约束也可将某些目标作为约束也可将某些目标作为约束也可将某些目标作为约束第26页，此课件共57页哦 多数队多数队仅仅采用搜索法（采用搜索法（70-80%?）n n直达；直达；一次换乘；一次换乘；二次换乘；二次换乘；s st ts st ts s t tn n求出所有线路；评价其目标求出所有线路；评价其目标求出所有线路；评价其目标求出所有线路；评价其目标(容易计算
43、容易计算容易计算容易计算)；选优；选优；选优；选优第27页，此课件共57页哦 多数队多数队仅仅采用搜索法采用搜索法n n总体来看，技术含量较低（基本上是枚举）总体来看，技术含量较低（基本上是枚举）uu几乎没有建模，完全只有算法实现，算法也没什么创新几乎没有建模，完全只有算法实现，算法也没什么创新几乎没有建模，完全只有算法实现，算法也没什么创新几乎没有建模，完全只有算法实现，算法也没什么创新n n一般只考虑不超过两次换乘一般只考虑不超过两次换乘一般只考虑不超过两次换乘一般只考虑不超过两次换乘uu不少文章引用参考文献作为依据，实用中似乎够用不少文章引用参考文献作为依据，实用中似乎够用不少文章引用参
44、考文献作为依据，实用中似乎够用不少文章引用参考文献作为依据，实用中似乎够用 uu题目难度大大降低，模型不够题目难度大大降低，模型不够题目难度大大降低，模型不够题目难度大大降低，模型不够一般一般一般一般n n换乘作为了换乘作为了换乘作为了换乘作为了第一目标第一目标第一目标第一目标，或作为一个，或作为一个，或作为一个，或作为一个最重要的约束最重要的约束n n任意次换乘时算法复杂度提高，难以处理任意次换乘时算法复杂度提高，难以处理uu结果不佳（如：从省时考虑，有些需次换乘）结果不佳（如：从省时考虑，有些需次换乘）结果不佳（如：从省时考虑，有些需次换乘）结果不佳（如：从省时考虑，有些需次换乘）第28页
45、，此课件共57页哦 图论模型与最短路算法图论模型与最短路算法n n用图论做的队也不少，但往往考虑不周用图论做的队也不少，但往往考虑不周用图论做的队也不少，但往往考虑不周用图论做的队也不少，但往往考虑不周uu弧上赋权方式交代不清弧上赋权方式交代不清弧上赋权方式交代不清弧上赋权方式交代不清uu套用套用套用套用DijkstraDijkstra或或或或Floyd-WarshallFloyd-Warshall算法，却不清楚其原理算法，却不清楚其原理算法，却不清楚其原理算法，却不清楚其原理及适用及适用及适用及适用的的的的问题问题问题问题n n需要建立一个带权有向图，节点表示站点，有向弧表示需要建立一个带权
46、有向图，节点表示站点，有向弧表示需要建立一个带权有向图，节点表示站点，有向弧表示需要建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上的权表示前一站点直前一站点能够直达后一站点，弧上的权表示前一站点直前一站点能够直达后一站点，弧上的权表示前一站点直前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价达后一站点所需付出的代价达后一站点所需付出的代价达后一站点所需付出的代价(时间或费用时间或费用)n n图（网络）如何描述和表示？图（网络）如何描述和表示？图（网络）如何描述和表示？图（网络）如何描述和表示？uu基本要素：节点，有向弧（边），弧上赋权基本要素
47、：节点，有向弧（边），弧上赋权基本要素：节点，有向弧（边），弧上赋权基本要素：节点，有向弧（边），弧上赋权uu邻接矩阵；关联矩阵（数学上处理方便，存储量较大）邻接矩阵；关联矩阵（数学上处理方便，存储量较大）邻接矩阵；关联矩阵（数学上处理方便，存储量较大）邻接矩阵；关联矩阵（数学上处理方便，存储量较大）uu链表（存储量较小，计算机上处理方便）链表（存储量较小，计算机上处理方便）链表（存储量较小，计算机上处理方便）链表（存储量较小，计算机上处理方便）第29页，此课件共57页哦 关联矩阵关联矩阵(Incidence Matrix)表示法表示法在线路选择问题中，当从在线路选择问题中，当从在线路选择问题
48、中，当从在线路选择问题中，当从i i i i可直达可直达可直达可直达j j j j时，定义弧时，定义弧时，定义弧时，定义弧(i,j)(i,j)(i,j)(i,j)；其上的；其上的；其上的；其上的权可为或成本权可为或成本权可为或成本权可为或成本(时间或费用时间或费用时间或费用时间或费用)；多重弧可只保留一条（弧上的权；多重弧可只保留一条（弧上的权；多重弧可只保留一条（弧上的权；多重弧可只保留一条（弧上的权可取最小的成本，如时间或费用）可取最小的成本，如时间或费用）可取最小的成本，如时间或费用）可取最小的成本，如时间或费用）G G=(=(V V，A A)是一个简单有向图；是一个简单有向图；是一个简
49、单有向图；是一个简单有向图；|V V|=|=n n，|A A|=|=mm 重要重要重要重要数学性质：数学性质：关联矩阵是全幺模矩阵关联矩阵是全幺模矩阵图图图图G G=(=(V V，A A)的邻接矩阵的邻接矩阵的邻接矩阵的邻接矩阵C C是如下定义的：是如下定义的：是如下定义的：是如下定义的：C C是一个是一个是一个是一个 的矩阵，即的矩阵，即的矩阵，即的矩阵，即第30页，此课件共57页哦 邻接矩阵邻接矩阵(Adjacency Matrix)(Adjacency Matrix)表示法表示法图图G G=(=(V V，A A)的的的的邻邻邻邻接接接接矩矩矩矩阵阵阵阵C是是是是如如如如下下下下定定定定义
50、义义义的的的的：C是是是是一一一一个个个个 的的的的0-10-1矩阵，即矩阵，即在线路选择问题中，当从在线路选择问题中，当从在线路选择问题中，当从在线路选择问题中，当从i i i i可直达可直达可直达可直达j j j j时，定义弧时，定义弧时，定义弧时，定义弧(i,j)(i,j)(i,j)(i,j)；其；其；其；其上的权可为或成本上的权可为或成本上的权可为或成本上的权可为或成本(时间或费用时间或费用时间或费用时间或费用)G G=(=(V V，A A)是一个简单有向图；是一个简单有向图；是一个简单有向图；是一个简单有向图；|V V|=n n，|A A|=mm 有向图的有向图的有向图的有向图的“传