图论和网络分析算法与Matlab实现（Graph_and_Network_Analysis).ppt

* 模型计算方法 (1)?? 对地图网格加密，形成图。 (2)???计算网格的距离，用费用作为权值。 (3) 求赋权图两点间的最短距离。 * 参考答案 * 1998年全国大学生数学建模竞赛 灾情巡视路线，下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 * 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 　 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。　 若巡视组数已定(如三组)，要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。　 * 乡村分布图 * 点的行遍性问题 1、图论---哈密尔顿问题（是否存在经过所有点一次的圈） 2、组合优化--旅行商问题（赋权图经过所有顶点至少一次） 非完全图的多旅行商问题 两点间的最短路长度作为两点间的权，构造完全图。 两边权之和不小于第三边的权==》 完全图的最优哈密尔顿圈《==》原图的最优旅行商问题。 完全图---增广完全图==?求最优哈密尔顿圈 近似算法或分组后直接有哪些信誉好的足球投注网站 注意 （1）?? 两点间的最短路长度可用Dijkstra算法 （2）?? 多旅行商问题===》最优哈密尔顿圈 * 线性规划模型 * 问题解答： 1、分三组（路）巡视，试设计总路程最短且 各组尽可能均衡的巡视路线。 目标函数： min(C1+C2+C3) 限制条件：min(C3 - C1) 或 者 ：min(C1) 2、假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线。 * 目标函数： min(H1+H2+H3) 花费时间：Hi=2mi+ni+Ci/V 限制条件：min(max(Hi)) 总时间69小时===》至少4组，4组的路线可以找到。 3、在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 单独巡视的最短时间=最远距离　 （1）每组时间不超过最远距离时间 （2）巡视组足够少，22组 4、? 若巡视组数已定(如三组)，要求尽快完成巡视，讨论T，t和 V改变对最佳巡视路线的影响。 讨论花费时间函数：Hi=2mi+ni+Ci/V 注意：多旅行商问题===》单旅行商问题（LINGO） * 2005年全国大学生数学建模竞赛DVD在线租赁 随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音像制品的在线租赁就是一种可行的服务。这项服务充分发挥了网络的诸多优势，包括传播范围广泛、直达核心消费群、强烈的互动性、感官性强、成本相对低廉等，为顾客提供更为周到的服务。 考虑如下的在线DVD租赁问题。顾客缴纳一定数量的月费成为会员，订购DVD租赁服务。会员对哪些DVD有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张DVD，这些DVD是基于其偏爱程度排序的。网站会根据手头现有的DVD数量和会员的订单进行分发。每个会员每个月租赁次数不得超过2次，每次获得3张DVD。会员看完3张DVD之后，只需要将DVD放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。请考虑以下问题： * 1) 网站正准备购买一些新的DVD，通过问卷调查1000个会员，得到了愿意观看这些DVD的人数（表1给出了其中5种DVD的数据）。此外，历史数据显示，60%的会员每月租赁DVD两次，而另外的40%只租一次。假设网站现有10万个会员，对表1中的每种DVD来说，应该至少准备多少张，才能保证希望看到该DVD的会员中至少50%在一个月内能够看到该DVD？如果要求保证在三个月内至少95%的会员能够看到该DVD呢？ 2）? 表2中列出了网站手上100种DVD的现有张数和当前需要处理的1000位会员的在线订单（表2的数据格式示例如下表2，具体数据请下），如何对这些DVD进行分配，才能使会员获得最大的满意度？