图与网络分析例讲解.doc

图与网络分析例题讲解 例1求救信号的采集问题 紧急呼救电话发挥着极其重要的作用，现在的问题是往往在呼救时当事者大多处于紧张或身体状况不佳的状态，难以清晰表达自己所处位置，给救援工作带来极大的困难，对于有线电话来说，定位相对容易，而对于移动设备由于其可移动性，则确定位置相对比较困难。一种可行的办法是依赖通信基站，按照移动设备接收附近几个基站信号强弱进行定位。区域内的某个点接收到各基站的信号强度组成一个向量，该向量唯一标志区域内的一个点。 采用这种方法定位就需要采集区域内各点的信号强度，派遣一辆装载信号采集设备和GPS的车辆，从研究所出发，依次到达各主要地点采集信号，最后回到研究所提交数据。 考察某大城市的一个特定区域，示意图共5个节点。主要信号采集点在图中已标出（即图中的节点），如何选择一条最短路线，使得信号采集车辆能够顺利地采集信号并返回研究所。图的邻接矩阵为：。 解 该问题实际上就是一个TSP（旅行商问题），要求寻找遍历图中所有节点，并返回起点的最短路。 TSP属于组合优化的范畴，可以采用组合优化的方法求解TSP。 设表示两个城市之间的距离，决策变量是或1（0表示不连接，1表示连接），由组成的邻接矩阵是图的哈密顿圈等价于中每个节点都只有一个入度和一个出度，且去掉任何一个节点将不是圈。此时求解TSP就等价于求解下面0-1规划问题： （1） 对于模型（1）容易用LINGO软件求解，其程序如下： model: sets: city/1..5/:u; !Hamilton路标号; link city,city :distance,x; !邻接矩阵和决策矩阵; endsets data: distance 0 14 12 7 10 14 0 9 13 5 12 9 0 6 8 7 13 6 0 11 10 5 8 11 0; enddata n @size city ; min @sum link:distance*x ; @for city i :u i 1 ; !城市编号非负约束; @for city k : @sum city i |i#ne#k:x i,k 1; !入度为1约束; @sum city j |j#ne#k:x k,j 1; !出度为1约束; @for city j |j#gt#1#and#j#ne#k: u j u k +x k,j -n* 1-x k,j + n-1 *x j,k ; ; !标号约束（除起始点外）; @for link:@bin x ; !0-1约束; @for city k |k#gt#1: u k n- n-2 *x 1,k ; !起点标号约束; u k 1+ n-1 *x k,1 ; ; !终点标号约束; end 例2 装备的合理配置问题 设有套不同型号的装备要配备给个部队，由于各个部队的基础设施、训练特点等条件的差异，不同的装备在不同的部队所产生的效能是不同的，具体的数据如表1所示。试问如何分配这批装备，保证每个部队都有一套设备，并且使总的效能最大？ 表1 装备在不同部队效能表 装备 部队 A B C D E F G H I 1 0.14 0.17 0.23 0.55 0.47 0.26 0.19 0.17 0.12 2 0.37 0.40 0.49 0.09 0.05 0.53 0.42 0.39 0.12 3 0.59 0.62 0.67 0.22 0.17 0.06 0.03 0.02 0.08 4 0.11 0.12 0.16 0.06 0.03 0.19 0.14 0.12 0.46 5 0.12 0.14 0.19 0.24 0.19 0.46 0.37 0.35 0.10 6 0.10 0.12 0.15 0.06 0.03 0.39 0.33 0.30 0.21 7 0.11 0.14 0.18 0.47 0.39 0.06 0.03 0.02 0.25 8 0.63 0.65 0.73 0.07 0.04 0.22 0.17 0.14 0.09 9 0.29 0.30 0.36 0.05 0.03 0.05 0.02 0.01 0.44 解 由题意可以知道，这个问题是属于一标准指派问题，即属于组合优化的范畴，在这里我们来建立组合优化模型，并且相应的方法进行求解。将各部队关于各种装备的效能（表1）数据用矩阵表示，即用表示分配装备给部队产生的效能。用表示决策矩阵，为一个0-1矩阵，即表示将装备分配给部队；表示不将装备分配给部队，则此时可以建立如下的优化规划模型： （2） 模型（2）是一个0-1规划模型，可以用LINGO软件求解，其程序如下： model: set