《数学建模赛题分析(建模方法)精选PPT.ppt》由会员分享，可在线阅读，更多相关《数学建模赛题分析(建模方法)精选PPT.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于数学建模赛题分析(建模方法)第1页，讲稿共60张，创作于星期二简要提纲简要提纲 n 应用数学与数学建模应用数学与数学建模 -建模及建模竞赛的意义建模及建模竞赛的意义n 竞赛评阅标准竞赛评阅标准 -一般原则及主要问题一般原则及主要问题n 优化模型的创新优化模型的创新 -2007B题分析题分析第2页，讲稿共60张，创作于星期二数学知识数学知识数学技巧数学技巧数学应用数学应用数学发现数学发现应用数学应用数学数学技术数学技术数学实验数学实验随机数学随机数学代数与几何代数与几何微微积分积分数学美学数学美学数学哲学数学哲学数学精神数学精神数学素质数学素质数学文化数学文化数学：几个层次的理解第3页，讲稿
2、共60张，创作于星期二数学建模：实际与数学之间的桥梁实际问题实际问题数学数学Mathematical Modeling 现实对象的信息现实对象的信息数学模型数学模型现实对象的解答现实对象的解答数学模型的解答数学模型的解答表述表述求解求解解释解释验证验证(归纳)(演绎)数学建模数学建模的全过程的全过程第4页，讲稿共60张，创作于星期二美国MCM+ICM竞赛规模第5页，讲稿共60张，创作于星期二我国CUMCM竞赛规模第6页，讲稿共60张，创作于星期二n学生欢迎：学生欢迎：“一次参赛，终身受益一次参赛，终身受益”n研究生导师们的认同研究生导师们的认同n企业界的认同赞助企业界的认同赞助n教育改革同行的
3、认同：教育改革同行的认同：“成功范例成功范例”n国际同行的认同国际同行的认同竞赛的反响竞赛的反响第7页，讲稿共60张，创作于星期二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 ana
4、lysis,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:/ n 应用数学与数学建模应用数学与数学建模 -建模及建模竞赛的意义建模及建模竞赛的意义n 竞赛评阅标准竞赛评阅标准 -一般原则及主要问题一般原则及主要问题n 创新能力培
5、养创新能力培养 -几个例子（结合优化模型）几个例子（结合优化模型）第9页，讲稿共60张，创作于星期二CUMCMCUMCM评阅标准评阅标准清晰性：摘要应理解为详细摘要，提纲挈领清晰性：摘要应理解为详细摘要，提纲挈领 表达严谨、简捷，思路清新表达严谨、简捷，思路清新 格式符合规范，严禁暴露身份格式符合规范，严禁暴露身份创造性：特别欣赏独树一帜、标新立异，但要合理创造性：特别欣赏独树一帜、标新立异，但要合理假设的合理性，建模的创造性，假设的合理性，建模的创造性，结果的正确性，表述的清晰性。结果的正确性，表述的清晰性。正确性：正确性：不强调与不强调与“参考答案参考答案”的一致性和结果的精度；的一致性和
6、结果的精度；好方法的结果一般比较好；但不一定是最好的好方法的结果一般比较好；但不一定是最好的合理性：关键假设；不欣赏罗列大量无关紧要的假设合理性：关键假设；不欣赏罗列大量无关紧要的假设 第10页，讲稿共60张，创作于星期二CUMCMCUMCM评阅标准评阅标准:一些常见问题一些常见问题有的论文过于简单，该交代的内容省略了，难以看懂有的论文过于简单，该交代的内容省略了，难以看懂有的队罗列一系列假设或模型，又不作比较、评价，有的队罗列一系列假设或模型，又不作比较、评价，希望碰上希望碰上“参考答案参考答案”或或“评阅思路评阅思路”，弄巧成拙，弄巧成拙数学模型最好数学模型最好明确、合理、简洁：明确、合理
7、、简洁：有些论文不给出明确的模型，只是根据赛题的情况，有些论文不给出明确的模型，只是根据赛题的情况，实际上是用实际上是用“凑凑”的方法给出结果，虽然结果大致是对的方法给出结果，虽然结果大致是对的，没有一般性，不是数学建模的正确思路。的，没有一般性，不是数学建模的正确思路。有的论文参考文献不全，或引用他人结果不作交代有的论文参考文献不全，或引用他人结果不作交代第11页，讲稿共60张，创作于星期二从论文评阅看学生参加竞赛中的问题从论文评阅看学生参加竞赛中的问题n 吃透题意方面不足，没有抓住和解决主要问题；吃透题意方面不足，没有抓住和解决主要问题；n 就事论事，形成数学模型的意识和能力欠缺；就事论事
8、，形成数学模型的意识和能力欠缺；n 对所用方法一知半解，不管具体条件，套用现成的方法，对所用方法一知半解，不管具体条件，套用现成的方法，导致错误；导致错误；n 对结果的分析不够，怎样符合实际考虑不周；对结果的分析不够，怎样符合实际考虑不周；n 写作方面的问题写作方面的问题(摘要、简明、优缺点、参考文献摘要、简明、优缺点、参考文献);n 队员之间合作精神差，孤军奋战；队员之间合作精神差，孤军奋战；n 依赖心理重，甚至违纪（指导教师、依赖心理重，甚至违纪（指导教师、网络）。网络）。第12页，讲稿共60张，创作于星期二简要提纲简要提纲 n 应用数学与数学建模应用数学与数学建模 -建模及建模竞赛的意义
9、建模及建模竞赛的意义n 竞赛评阅标准竞赛评阅标准 -一般原则及主要问题一般原则及主要问题n 创新能力培养创新能力培养 -2007B分析分析第13页，讲稿共60张，创作于星期二14n 优化问题三要素：优化问题三要素：决策变量决策变量；目标函数目标函数；约束条件约束条件约约束束条条件件决策变量决策变量优化问题的一般形式优化问题的一般形式目标函数目标函数n有人统计：有人统计：优化问题占优化问题占CUMCM赛题的一半以上（赛题的一半以上（1/32/3）第14页，讲稿共60张，创作于星期二 建模时需要注意的几个基本问题建模时需要注意的几个基本问题 1、尽量使用实数优化，减少整数约束和整数变量尽量使用实数
10、优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍最小值、四舍五入、取整函数等五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数尽量使用线性模型，减少非线性约束和非线性变量的个数 （如（如x/y 5 改为改为x5y）4、合理设定变量上下界，尽可能给出变量初始值合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当模型中使用的参数数量级要适当 (如小于如小于103)第15页，讲稿共60张，创作
11、于星期二优化建模如何创新？优化建模如何创新？n 方法方法1：大胆创新，别出心裁：大胆创新，别出心裁 -采用有特色的目标函数、约束条件等采用有特色的目标函数、约束条件等 -你用非线性规划，我用线性规划你用非线性规划，我用线性规划 -你用整数你用整数/离散规划，我用连续规划离散规划，我用连续规划/网络优化网络优化 -n 方法方法2：细致入微，滴水不漏：细致入微，滴水不漏 -对目标函数、约束条件处理特别细致对目标函数、约束条件处理特别细致 -有算法设计和分析，不仅仅是简单套用软件有算法设计和分析，不仅仅是简单套用软件 -敏感性分析详细敏感性分析详细/全面全面 -第16页，讲稿共60张，创作于星期二2
12、007B命题背景命题背景 n n奥运相关的题目：奥运相关的题目：(时代特性时代特性,社会关注）社会关注）社会关注）社会关注）uu让运动员及时到达场馆（车辆调度，路径安排等）让运动员及时到达场馆（车辆调度，路径安排等）让运动员及时到达场馆（车辆调度，路径安排等）让运动员及时到达场馆（车辆调度，路径安排等）uu应急管理（紧急疏散，应急调度等）应急管理（紧急疏散，应急调度等）应急管理（紧急疏散，应急调度等）应急管理（紧急疏散，应急调度等）uu赛程安排（单一项目，多个项目）赛程安排（单一项目，多个项目）赛程安排（单一项目，多个项目）赛程安排（单一项目，多个项目）uu成绩排名（如循环赛，体操或跳水等）成
13、绩排名（如循环赛，体操或跳水等）成绩排名（如循环赛，体操或跳水等）成绩排名（如循环赛，体操或跳水等）uu技术类，如技术类，如技术类，如技术类，如“刘翔的运动鞋刘翔的运动鞋刘翔的运动鞋刘翔的运动鞋”n n乘公交，看奥运：原名乘公交，看奥运：原名“自动问路机自动问路机”uu方沛辰（吉大），吴孟达（国防科大）提出方沛辰（吉大），吴孟达（国防科大）提出方沛辰（吉大），吴孟达（国防科大）提出方沛辰（吉大），吴孟达（国防科大）提出uu原拟作乙组题，似乎难度太大原拟作乙组题，似乎难度太大原拟作乙组题，似乎难度太大原拟作乙组题，似乎难度太大第17页，讲稿共60张，创作于星期二命题背景命题背景 n n定位：公交
14、路线选择（查询）模型与算法定位：公交路线选择（查询）模型与算法n n如何给数据？如何给数据？uu抽象数据实际数据？（减小规模，不给地理信息）抽象数据实际数据？（减小规模，不给地理信息）抽象数据实际数据？（减小规模，不给地理信息）抽象数据实际数据？（减小规模，不给地理信息）n n貌似简单，实则不然貌似简单，实则不然uu数据处理（转换）方面有一定难度数据处理（转换）方面有一定难度数据处理（转换）方面有一定难度数据处理（转换）方面有一定难度uu换乘次数多时简单搜索不易（计算复杂度高）换乘次数多时简单搜索不易（计算复杂度高）换乘次数多时简单搜索不易（计算复杂度高）换乘次数多时简单搜索不易（计算复杂度高
15、）uu换乘时间步行时间等需要考虑周全换乘时间步行时间等需要考虑周全换乘时间步行时间等需要考虑周全换乘时间步行时间等需要考虑周全uu标准的最短路算法（如标准的最短路算法（如标准的最短路算法（如标准的最短路算法（如DijkstraDijkstra算法）并不适用算法）并不适用算法）并不适用算法）并不适用第18页，讲稿共60张，创作于星期二 B题：乘公交，看奥运题：乘公交，看奥运 第第29届奥运会届奥运会08年年8月将在北京举行，届时有大量观众月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）
16、出行。北京市的工具（简称公交，包括公汽、地铁等）出行。北京市的公交线路已达公交线路已达800条以上，使得公众的出行更加通畅、便利，条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。备研制开发一个解决公交线路选择问题的自主查询计算机系统。应该应该从实际情况出发考虑，满足查询者的从实际情况出发考虑，满足查询者的各种不同需求。各种不同需求。07-B 题题 解解 题题 分分 析析 为了设计这样一个系统，其为了设计这样一个系统，其核心是核心是线路选择的模
17、型与算法线路选择的模型与算法。第19页，讲稿共60张，创作于星期二07-B 题题 解解 题题 分分 析析请解决如下问题：请解决如下问题：1、仅考虑公汽线路，给出、仅考虑公汽线路，给出任意两公汽站点之间线路任意两公汽站点之间线路选择问题的一般数学模型与算法选择问题的一般数学模型与算法。并根据附录数据，利用。并根据附录数据，利用你们的模型与算法，求出以下你们的模型与算法，求出以下6对起始站对起始站终到站之间的终到站之间的最佳路线（最佳路线（要有清晰的评价说明要有清晰的评价说明）。）。(1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485 (4)、S0008S007
18、3 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间、假设又知道所有站点之间的步行时间,请你请你给出任意两站点之间线路选择问题的数学模型。给出任意两站点之间线路选择问题的数学模型。第20页，讲稿共60张，创作于星期二07-B 题题 解解 题题 分分 析析【附录附录1】基本参数设定基本参数设定相邻公汽站平均行驶时间相邻公汽站平均行驶时间(包括停站时间包括停站时间)：3分钟分钟相邻地铁站平均行驶时间相邻地铁站平均行驶时间(包括停站时间包括停站时间)：2.5分钟分钟公汽换乘
19、公汽平均耗时：公汽换乘公汽平均耗时：5分钟分钟(其中步行时间其中步行时间2分钟分钟)地铁换乘地铁平均耗时：地铁换乘地铁平均耗时：4分钟分钟(其中步行时间其中步行时间2分钟分钟)地铁换乘公汽平均耗时：地铁换乘公汽平均耗时：7分钟分钟(其中步行时间其中步行时间4分钟分钟)公汽换乘地铁平均耗时：公汽换乘地铁平均耗时：6分钟分钟(其中步行时间其中步行时间4分钟分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：其中分段计价的票价为：020站：站：1元；元；2140站：站：2元；元；40站以上：站以上：3元元地铁票价：地铁票
20、价：3元（无论地铁线路间是否换乘）元（无论地铁线路间是否换乘）【附录附录2】公交线路及相关信息公交线路及相关信息 （见数据文件（见数据文件B2007data.rar）第21页，讲稿共60张，创作于星期二线路数据中的问题线路数据中的问题线路数据中的异常或不明确之处，同学可根据自己的线路数据中的异常或不明确之处，同学可根据自己的线路数据中的异常或不明确之处，同学可根据自己的线路数据中的异常或不明确之处，同学可根据自己的理解理解理解理解作出作出作出作出假假假假设设设设和处理，一般不会影响实例的计算结果和处理，一般不会影响实例的计算结果和处理，一般不会影响实例的计算结果和处理，一般不会影响实例的计算结
21、果uu个别线路相邻站点名相同，可去掉其中一点或不作处理等个别线路相邻站点名相同，可去掉其中一点或不作处理等个别线路相邻站点名相同，可去掉其中一点或不作处理等个别线路相邻站点名相同，可去掉其中一点或不作处理等uuL406L406未标明是环线，是否将其当作环线处理均可未标明是环线，是否将其当作环线处理均可未标明是环线，是否将其当作环线处理均可未标明是环线，是否将其当作环线处理均可uuL290L290标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为14771477与与与与14791479，可将所有线路，可将所有线路，可将所有线路，可将所
22、有线路中中中中14771477与与与与14791479统一为统一为统一为统一为14771477后计算。同学也可以按照各自认为合理后计算。同学也可以按照各自认为合理后计算。同学也可以按照各自认为合理后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将的方式处理，包括不当作环线，或将的方式处理，包括不当作环线，或将的方式处理，包括不当作环线，或将14791479改为改为改为改为14771477，或在，或在，或在，或在14791479后增后增后增后增加加加加14771477，等等，等等，等等，等等uu如果在假设中有明确约定，则环线单向或双向发车均应认可（按单如果在假设中有明确约定，则环
23、线单向或双向发车均应认可（按单如果在假设中有明确约定，则环线单向或双向发车均应认可（按单如果在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些）向发车作假设，计算结果可能差些）向发车作假设，计算结果可能差些）向发车作假设，计算结果可能差些）第22页，讲稿共60张，创作于星期二对通过地铁换乘的理解对通过地铁换乘的理解n n“假设同一地铁站对应的任意两个公汽站之间可以通过地铁假设同一地铁站对应的任意两个公汽站之间可以通过地铁假设同一地铁站对应的任意两个公汽站之间可以通过地铁假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘站换乘站换乘站换乘(无需支付地铁费无
24、需支付地铁费)”n n步行：公汽站步行：公汽站地铁站（通道）地铁站（通道）公汽站公汽站公汽站公汽站n n换乘耗时换乘耗时换乘耗时换乘耗时11min11min：步行：步行：步行：步行4+4=8min;等车等车等车等车3minn n第问（只考虑公汽）：可不考虑以上换乘第问（只考虑公汽）：可不考虑以上换乘第问（只考虑公汽）：可不考虑以上换乘第问（只考虑公汽）：可不考虑以上换乘uu有同学也考虑了如上换乘，只是不坐地铁，应该也可以有同学也考虑了如上换乘，只是不坐地铁，应该也可以有同学也考虑了如上换乘，只是不坐地铁，应该也可以有同学也考虑了如上换乘，只是不坐地铁，应该也可以uu此样处理时，第问和第问的难度
25、相近此样处理时，第问和第问的难度相近此样处理时，第问和第问的难度相近此样处理时，第问和第问的难度相近第23页，讲稿共60张，创作于星期二07-B 题题 解解 题题 分分 析析 题目特点题目特点 1、本题根据公交线路查询系统研制的实际需求简本题根据公交线路查询系统研制的实际需求简本题根据公交线路查询系统研制的实际需求简本题根据公交线路查询系统研制的实际需求简 化改编而成；化改编而成；化改编而成；化改编而成；2 2、问题容易理解，相关参考文献较多；、问题容易理解，相关参考文献较多；3 3、相关知识点：、相关知识点：、相关知识点：、相关知识点：（1）图论（最短路径）；）图论（最短路径）；（2）多目标
26、规划。）多目标规划。）多目标规划。）多目标规划。4、题目开放度不够，可发挥余地不多。、题目开放度不够，可发挥余地不多。第24页，讲稿共60张，创作于星期二关于数据的预处理：关于数据的预处理：1 1、对于原始数据中出现的一些异常数据，可根据自己的理解作出假设和处、对于原始数据中出现的一些异常数据，可根据自己的理解作出假设和处、对于原始数据中出现的一些异常数据，可根据自己的理解作出假设和处、对于原始数据中出现的一些异常数据，可根据自己的理解作出假设和处理。如：理。如：理。如：理。如：（1 1）对于个别线路相邻点名相同，可以采取去掉其中）对于个别线路相邻点名相同，可以采取去掉其中）对于个别线路相邻点
27、名相同，可以采取去掉其中）对于个别线路相邻点名相同，可以采取去掉其中1 1点或不作处理等方点或不作处理等方点或不作处理等方点或不作处理等方式，一般不会影响实例计算中线路选择的结果。式，一般不会影响实例计算中线路选择的结果。式，一般不会影响实例计算中线路选择的结果。式，一般不会影响实例计算中线路选择的结果。（2 2）对于）对于）对于）对于L406L406未标明是环行线的问题，无论学生是否将其当作环线处理，一未标明是环行线的问题，无论学生是否将其当作环线处理，一未标明是环行线的问题，无论学生是否将其当作环线处理，一未标明是环行线的问题，无论学生是否将其当作环线处理，一般不会影响到实例的计算结果。般
28、不会影响到实例的计算结果。般不会影响到实例的计算结果。般不会影响到实例的计算结果。（3 3）对于）对于）对于）对于L290L290标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为标明是环线，但首尾站点分别为14771477与与与与14791479的问题，可将所有线的问题，可将所有线的问题，可将所有线的问题，可将所有线路中路中路中路中14771477与与与与14791479统一为统一为统一为统一为14771477后计算。也可以按照各自认为合理的方式处后计算。也可以按照各自认为合理的方式处后计算。也可以按照各自认为合理的方式处后计算。也可以按照各自认为合理的方式
29、处理，包括不当作环线，实例计算用到的是该线路中部的几个站点，一般理，包括不当作环线，实例计算用到的是该线路中部的几个站点，一般理，包括不当作环线，实例计算用到的是该线路中部的几个站点，一般理，包括不当作环线，实例计算用到的是该线路中部的几个站点，一般不会影响实例计算结果。不会影响实例计算结果。不会影响实例计算结果。不会影响实例计算结果。07-B 题题 解解 题题 分分 析析2、关于环行线路，可以假设为单向或双向。、关于环行线路，可以假设为单向或双向。3、线路数据格式需编程进行转换。、线路数据格式需编程进行转换。第25页，讲稿共60张，创作于星期二 模型的目标模型的目标n n多目标优化问题多目标
30、优化问题（至少考虑三方面）（至少考虑三方面）uu换乘次数最少换乘次数最少换乘次数最少换乘次数最少(N)(N)、费用最省、费用最省、费用最省、费用最省(M)(M)、时间最短、时间最短、时间最短、时间最短(T)(T)n n从该问题的实际背景来看，从该问题的实际背景来看，从该问题的实际背景来看，从该问题的实际背景来看，加权不加权不加权不加权不太合适太合适太合适太合适 uu不少同学用层次分析法确定权不少同学用层次分析法确定权不少同学用层次分析法确定权不少同学用层次分析法确定权uu不少同学计算时间的价值（平均收入工作时间）不少同学计算时间的价值（平均收入工作时间）不少同学计算时间的价值（平均收入工作时间
31、）不少同学计算时间的价值（平均收入工作时间）n n不同目标不同目标组合组合组合组合的模型的模型的模型的模型uu三个目标按优先级排序，组合成六个模型三个目标按优先级排序，组合成六个模型三个目标按优先级排序，组合成六个模型三个目标按优先级排序，组合成六个模型uu也可将某些目标作为约束也可将某些目标作为约束也可将某些目标作为约束也可将某些目标作为约束第26页，讲稿共60张，创作于星期二 多数队多数队仅仅采用搜索法（采用搜索法（70-80%?）n n直达；直达；一次换乘；一次换乘；二次换乘；二次换乘；ststs tn n求出所有线路；评价其目标求出所有线路；评价其目标(容易计算容易计算)；选优；选优第
32、27页，讲稿共60张，创作于星期二 多数队多数队仅仅采用搜索法采用搜索法n n总体来看，技术含量较低（基本上是枚举）总体来看，技术含量较低（基本上是枚举）uu几乎没有建模，完全只有算法实现，算法也没什么创新几乎没有建模，完全只有算法实现，算法也没什么创新几乎没有建模，完全只有算法实现，算法也没什么创新几乎没有建模，完全只有算法实现，算法也没什么创新n n一般只考虑不超过两次换乘一般只考虑不超过两次换乘uu不少文章引用参考文献作为依据，实用中似乎够用不少文章引用参考文献作为依据，实用中似乎够用不少文章引用参考文献作为依据，实用中似乎够用不少文章引用参考文献作为依据，实用中似乎够用 uu题目难度大
33、大降低，模型不够题目难度大大降低，模型不够题目难度大大降低，模型不够题目难度大大降低，模型不够一般一般一般一般n n换乘作为了换乘作为了换乘作为了换乘作为了第一目标第一目标第一目标第一目标，或作为一个，或作为一个最重要的约束最重要的约束n n任意次换乘时算法复杂度提高，难以处理任意次换乘时算法复杂度提高，难以处理任意次换乘时算法复杂度提高，难以处理任意次换乘时算法复杂度提高，难以处理uu结果不佳（如：从省时考虑，有些需次换乘）结果不佳（如：从省时考虑，有些需次换乘）结果不佳（如：从省时考虑，有些需次换乘）结果不佳（如：从省时考虑，有些需次换乘）第28页，讲稿共60张，创作于星期二 图论模型与最
34、短路算法图论模型与最短路算法n n用图论做的队也不少，但往往考虑不周用图论做的队也不少，但往往考虑不周uu弧上赋权方式交代不清弧上赋权方式交代不清弧上赋权方式交代不清弧上赋权方式交代不清uu套用套用套用套用DijkstraDijkstra或或或或Floyd-WarshallFloyd-Warshall算法，却不清楚其原理算法，却不清楚其原理算法，却不清楚其原理算法，却不清楚其原理及适用及适用及适用及适用的问题的问题的问题的问题n n需要建立一个带权有向图，节点表示站点，有向弧表需要建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上的权表示前一站示前一站点能够直达后一站点
35、，弧上的权表示前一站点直达后一站点所需付出的代价点直达后一站点所需付出的代价(时间或费用时间或费用时间或费用时间或费用)n n图（网络）如何描述和表示？图（网络）如何描述和表示？图（网络）如何描述和表示？图（网络）如何描述和表示？uu基本要素：节点，有向弧（边），弧上赋权基本要素：节点，有向弧（边），弧上赋权基本要素：节点，有向弧（边），弧上赋权基本要素：节点，有向弧（边），弧上赋权uu邻接矩阵；关联矩阵（数学上处理方便，存储量较大）邻接矩阵；关联矩阵（数学上处理方便，存储量较大）邻接矩阵；关联矩阵（数学上处理方便，存储量较大）邻接矩阵；关联矩阵（数学上处理方便，存储量较大）uu链表（存储量较
36、小，计算机上处理方便）链表（存储量较小，计算机上处理方便）链表（存储量较小，计算机上处理方便）链表（存储量较小，计算机上处理方便）第29页，讲稿共60张，创作于星期二 关联矩阵关联矩阵(Incidence Matrix)表示法表示法在线路选择问题中，当从在线路选择问题中，当从i i可直达可直达j j时，定义弧时，定义弧(i,j)(i,j)；其上；其上的权可为或成本的权可为或成本(时间或费用时间或费用)；多重弧可只保留一条（弧；多重弧可只保留一条（弧上的权可取最小的成本，如时间或费用）上的权可取最小的成本，如时间或费用）G=(V，A)是一个简单有向图；是一个简单有向图；|V|=n，|A|=m 重
37、要重要数学性质：数学性质：关联矩阵是全幺模矩阵关联矩阵是全幺模矩阵图图G=(V，A)的邻接矩阵的邻接矩阵C是如下定义的：是如下定义的：C是一个是一个 的矩阵，即的矩阵，即第30页，讲稿共60张，创作于星期二 邻接矩阵邻接矩阵(Adjacency Matrix)(Adjacency Matrix)表示法表示法图图G=(V，A)的的邻邻接接矩矩阵阵C是是如如下下定定义义的的：C是是一一个个 的的0-1矩阵，即矩阵，即在线路选择问题中，当从在线路选择问题中，当从i i可直达可直达j j时，定义弧时，定义弧(i,j)(i,j)；其；其上的权可为或成本上的权可为或成本(时间或费用时间或费用)G=(V，A
38、)是一个简单有向图；是一个简单有向图；|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次可达矩阵次可达矩阵；第31页，讲稿共60张，创作于星期二链表（邻接表）表示法链表（邻接表）表示法 122345283904602403053036470单向链表(指针数组)A(1)=2,3A(2)=4A(3)=2A(4)=3,5A(5)=3,41234
39、5第32页，讲稿共60张，创作于星期二 Dijkstra Dijkstra算法（标号算法，算法（标号算法，19591959）STEP1.如果S=V,则uj为节点s到节点j的最短路路长(最短路可以通过数组pred所记录的信息反向追踪获得),结束.否则继续.STEP0.(初始化)令S=，=V，；对V 中的顶点j(j s)令初始距离标号 .STEP2.从 中找到距离标号最小距离标号最小的节点i，把它从 删除，加入S.对于所有所有从i出发的弧 ,若 ，则令 转STEP1.特点：特点：1.算法求出从源点算法求出从源点s到所有点的最短路长到所有点的最短路长 2.每每点点给给一一对对标标号号(uj,pred
40、j)，uj是是从从s到到j的的最最短短路长；路长；predj是从是从s到到j的最短路中的最短路中j点的前一点点的前一点第33页，讲稿共60张，创作于星期二Example第34页，讲稿共60张，创作于星期二DijkstraDijkstra算法（标号设定算法）算法（标号设定算法）n适用于正费用网络：适用于正费用网络：“分层分层”设定标号设定标号n永久标号：永久标号：S中的点，中的点，uj是最短路长是最短路长n临时标号；临时标号；其他点，其他点，uj是只通过是只通过S中的点的最短路长中的点的最短路长对对于于稠稠密密网网络络，这这是是求求解解最最短短路路问问题题可可能能达达到到的的最最小小的的复复杂杂
41、度度,因为任何算法都至少必须对每条弧考虑一次因为任何算法都至少必须对每条弧考虑一次.对于稀疏网络，利用各种形式的对于稀疏网络，利用各种形式的堆（堆（HeapHeap），其复杂度可降为，其复杂度可降为 或或 等等算法复杂度算法复杂度O(n2+m)：如链表或邻接矩阵实现：如链表或邻接矩阵实现找最小标号点修改标号找最小标号点修改标号第35页，讲稿共60张，创作于星期二n特点：求所有点对间最短路特点：求所有点对间最短路n基本思想：逐步逼近，迭代求解最短路方程基本思想：逐步逼近，迭代求解最短路方程:O(n3)Floyd-Warshall算法算法（标号修正算法标号修正算法1962)1962)临临时时标标号
42、号 是是不不通通过过k，k+1，,n 节节点点(i,j 除除外外)时时从从节节点点i到到节节点点j的最短路路长的最短路路长.第36页，讲稿共60张，创作于星期二 Floyd-Warshall算法的具体实现算法的具体实现:O(n3)由由于于要要记记录录所所有有节节点点之之间间最最短短路路的的信信息息,所所以以这这里里我我们们要要用用一一个个二二维维数数组组P；可依据可依据P,采用采用“正向追踪正向追踪”的方式得到最短路的方式得到最短路.STEP2：如果：如果k=n,结束结束;否则转否则转STEP1.STEP0:k=0.对于所有节点对于所有节点i和和j:令令 ，,(，若节点，若节点i和和j之间没有
43、弧之间没有弧,认为认为 ).STEP1:k=k+1.对于所有节点对于所有节点i和和j:若若 ,令令 ,;否则令否则令 ,.第37页，讲稿共60张，创作于星期二Floyd-Warshall算法的算法的矩阵迭代法实现：矩阵迭代法实现：O(n4)n令令D为权矩阵为权矩阵(直达最短路长直达最短路长)nDm为正好经过为正好经过m条弧从条弧从i到到j的最短路长的最短路长第38页，讲稿共60张，创作于星期二 问题问题1和和2的一种具体建模方法的一种具体建模方法(赋权赋权)在线路选择问题中，当从在线路选择问题中，当从i i可直达可直达j j时（时（同为公汽或同为公汽或地铁站点地铁站点），定义弧），定义弧(i,
44、j)(i,j)；其上的权为；其上的权为lij表示由表示由i直达直达j付出的代价，可以为时间或费用付出的代价，可以为时间或费用(不包括换乘不包括换乘代价；多条线路可达时只保留最小代价代价；多条线路可达时只保留最小代价)初始等车时间初始等车时间2(3)min也不包括在内，最后结果可加上也不包括在内，最后结果可加上注意：注意：D=D(0)不是对称矩阵不是对称矩阵(“直达矩阵直达矩阵”)dij(0)=dij第39页，讲稿共60张，创作于星期二 问题的一种具体建模方法问题的一种具体建模方法i站点是公汽站点，站点是公汽站点，j站点为地铁站点：站点为地铁站点：（1）若若j站站点点对对应应的的所所有有换换乘乘
45、(公公汽汽)站站点点k，均均不不能能从从i直达直达(不在不在i站点所在公汽线路站点所在公汽线路L上上)，则，则dij(0)=.（2）若若j站站点点对对应应的的换换乘乘站站点点(k),可可从从i站站点点直直达达k，则则费费用用为为dij(0)=dik(0)；对对于于时时间间则则需需要要加加上上k到到j的的步步行行时时间间.(若有多种选择，取最小成本者即可若有多种选择，取最小成本者即可)ikj第40页，讲稿共60张，创作于星期二 问题的一种具体建模方法问题的一种具体建模方法j站点是公汽站点，站点是公汽站点，i站点为地铁站点：站点为地铁站点：（1）若若从从i站站点点对对应应的的任任何何换换乘乘(公公
46、汽汽)站站点点k，均均不不能能直直达达j站站点点，则则dij(0)=.（2）若若从从i站站点点对对应应的的换换乘乘(公公汽汽)站站点点k，能能直直达达j站站点点，则则费费用用为为dij(0)=dkj(0)；对于时间则需要；对于时间则需要加上加上i到到k的步行的步行时间时间.ikj第41页，讲稿共60张，创作于星期二 问题：最小费用或时间问题：最小费用或时间n 定义矩阵算子定义矩阵算子“”如下：设如下：设A、B均为均为n阶方阵，阶方阵，C=A B (考虑考虑换乘代价换乘代价)当考当考虑费虑费用矩用矩阵阵之之间间的运算的运算时时，表示在表示在k的换乘时间的换乘时间 当考当考虑时间虑时间矩矩阵阵之之
47、间间的运算的运算时时，n D(k)=D(k-1)D 表示表示k次换乘的最低代价次换乘的最低代价(费用或时间费用或时间)n 该算法大体相当于求最短路的该算法大体相当于求最短路的Floyd-Warshall算法，但考虑算法，但考虑了换乘因素，可称为改进了换乘因素，可称为改进Floyd-Warshall算法算法n 类似地类似地,通过修改通过修改Dijkstra算法求解也可算法求解也可第42页，讲稿共60张，创作于星期二 问题：最小费用或时间问题：最小费用或时间i,j,ki,j,k表示换乘时间表示换乘时间 ni=j 或或k=i，j时，时，i,j,ki,j,k=0n其他情形：其他情形：若不可换乘若不可换
48、乘(当当i，j为公汽站点而为公汽站点而k为地铁站点，或者为地铁站点，或者i，j为地铁站点而为地铁站点而k为公汽站点时为公汽站点时)，则，则 i,j,ki,j,k=0若可换乘，则若可换乘，则k这只是等待时间，因为步行时这只是等待时间，因为步行时间已在间已在D中考虑了中考虑了ij第43页，讲稿共60张，创作于星期二 第问：已知所有站点间步行时间第问：已知所有站点间步行时间n多数队没有给出一般模型多数队没有给出一般模型,而只考虑最多一次换乘而只考虑最多一次换乘n多数队的想法：假设多数队的想法：假设“起点步行起点步行”，“换乘步行换乘步行”，“终点步行终点步行”三种模式，限定三种模式，限定步行最大时间
49、步行最大时间后搜索后搜索ikj第44页，讲稿共60张，创作于星期二 其他：最短路问题的线性规划模型其他：最短路问题的线性规划模型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
50、，1(0-1规划规划)?第45页，讲稿共60张，创作于星期二 最短路问题的线性规划模型最短路问题的线性规划模型n线性规划模型，应该可以计算到比较大规模的问题线性规划模型，应该可以计算到比较大规模的问题n有些队写出了上述模型，但并未用该模型求解有些队写出了上述模型，但并未用该模型求解n可能需要强大的优化软件，数据输入工作量也较大可能需要强大的优化软件，数据输入工作量也较大n换乘代价不易考虑（网络上的权不易定义，或不具可加性）换乘代价不易考虑（网络上的权不易定义，或不具可加性）n 有些同学提到有些同学提到动态规划动态规划,但要么与这里介绍的最短路算但要么与这里介绍的最短路算法等价法等价,要么处理有