图与网络分析例题讲解.doc
《图与网络分析例题讲解.doc》由会员分享,可在线阅读,更多相关《图与网络分析例题讲解.doc(4页珍藏版)》请在三一办公上搜索。
1、图与网络分析例题讲解例1求救信号的采集问题紧急呼救电话发挥着极其重要的作用,现在的问题是往往在呼救时当事者大多处于紧张或身体状况不佳的状态,难以清晰表达自己所处位置,给救援工作带来极大的困难,对于有线电话来说,定位相对容易,而对于移动设备由于其可移动性,则确定位置相对比较困难。一种可行的办法是依赖通信基站,按照移动设备接收附近几个基站信号强弱进行定位。区域内的某个点接收到各基站的信号强度组成一个向量,该向量唯一标志区域内的一个点。采用这种方法定位就需要采集区域内各点的信号强度,派遣一辆装载信号采集设备和GPS的车辆,从研究所出发,依次到达各主要地点采集信号,最后回到研究所提交数据。考察某大城市
2、的一个特定区域,示意图共5个节点。主要信号采集点在图中已标出(即图中的节点),如何选择一条最短路线,使得信号采集车辆能够顺利地采集信号并返回研究所。图的邻接矩阵为:。解 该问题实际上就是一个TSP(旅行商问题),要求寻找遍历图中所有节点,并返回起点的最短路。TSP属于组合优化的范畴,可以采用组合优化的方法求解TSP。设表示两个城市之间的距离,决策变量是或1(0表示不连接,1表示连接),由组成的邻接矩阵是图的哈密顿圈等价于中每个节点都只有一个入度和一个出度,且去掉任何一个节点将不是圈。此时求解TSP就等价于求解下面0-1规划问题: (1)例2 装备的合理配置问题设有套不同型号的装备要配备给个部队
3、,由于各个部队的基础设施、训练特点等条件的差异,不同的装备在不同的部队所产生的效能是不同的,具体的数据如表1所示。试问如何分配这批装备,保证每个部队都有一套设备,并且使总的效能最大?表1 装备在不同部队效能表 装备部队ABCDEFGHI10.140.170.230.550.470.260.190.170.1220.370.400.490.090.050.530.420.390.1230.590.620.670.220.170.060.030.020.0840.110.120.160.060.030.190.140.120.4650.120.140.190.240.190.460.370.350
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络分析 例题 讲解
链接地址:https://www.31ppt.com/p-4099167.html