[理学]2010集训专题三 图论模型.ppt

2010数学建模集训班专题讲座--图论模型的建立与分析;专题;图的表示与锁具问题;图的矩阵表示 ;2) 对有向图 ,其邻接矩阵 ,其中： ;其中：;关联矩阵 ;2) 对有向图 ，其关联矩阵 ,;两点间长度为k的路径数目;1994 年全国大学生数学建模竞赛B 题(锁具装箱) ;求解上述问题的一般方法;图论方法;图论方法;图论方法;图论方法;图论方法;图论方法;最小生成树、TSP和灾区巡视问题;98年全国大学生数学建模竞赛B题最佳灾情巡视路线;98年全国大学生数学建模竞赛B题最佳灾情巡视路线;问题1;分析;问题1的分析与求解--最小生成树法;问题1的分析与求解--最小生成树法;问题1的分析与求解--最小生成树法;问题1的分析与求解--最小生成树法;问题1的分析与求解--最小生成树法;问题1的分析与求解--最小生成树法;问题1的分析与求解--TSP方法;公路边的数字为该路段的公里数.;问题分析：;　 问题1是三个旅行售货员问题;最佳灾情巡视路线的模型的建立与求解;最佳旅行售货员问题是NP—完全问题,采用一种; 问题一 若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线. 此问题是多个售货员的最佳旅行售货员问题.;; 而图中节点数较多，为53个，我们只能去寻求;从O点出发到其它点共有6条干枝，它们的名称;分组2:(①,②),(③,④),(⑤,⑥);分组2的近似解 ;因为该分组的均衡度;;因该分组的均衡度 ;最短路、网络流和运输问题;由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道;钢厂的产量和销价（1单位钢管=1km管道钢管）;（1）制定钢管的订购和运输计划，使总费用最小.;问题1的分析与求解;问题的简化;下面叙述求SA P 矩阵的过程;SA P矩阵;问题的数学描述;问题的求解;线性费用流网络模型一;线性费用流网络模型一;线性费用流网络模型一;最小费用路算法;线性费用流网络模型二;线性费用流网络模型二;线性费用流网络模型二;非线性费用流网络模型;非线性费用流网络模型;非线性费用流网络模型;练习;练习1 求下图的Hamilton回路;某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购买新的？如果继续使用旧的，要付维修费；若要购买一套新的，要付购买费。???确定一个5年计划，使总支出最小。 若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如表1所示;