运筹学课件第8章-图与网络分析.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 图与网络模型Graph Theory距离矩阵摹乘法 矩阵摹乘运算法： dk = W ? dk-1 , ( k = 2 , 3 , … ) 当 dk = dk-1 , ( k= 2, 3, … ) 则计算停止， dk 中的元素即为各点到 vr 的最短距离。 图与网络模型Graph Theory网络中心和重心问题 一、基本概念 网络最短距离矩阵 D = ( dij )n×n dij——表示vi到vj的最短距离 （ 1 ）网络的中心 令： d( vi )= max ? dij ? , i = 1, 2, … , n 若 max ? d( vi ) ? = d( vk ) 1≤i≤n 1≤j≤n 则称点 vk 为网络的中心。 图与网络模型Graph Theory网络中心和重心问题 （ 2 ）网络的重心 设 gi 为点 vi 的权重（ i = 1, 2, …, n ）， 令： h ( vj ) = ∑ gidij , j = 1, 2, … , n i=1 n 若 max ? h( vj ) ? = h( vr ) 1≤j≤n 则称点 vr 为网络的重心。 图与网络模型Graph Theory网络中心和重心问题 二、应用 例—— 某地 7 个村镇之间的现有交通道路如下图，边旁数值为各村镇之间道路的长度，点旁数值为各村镇的小学生人数。现拟在某一村镇建一商店和小学，试问： （1）商店应该建在何村，能使各村都离它较近？ （2）小学应该建在何村，能使各村小学生总的行走路程最短？ 图与网络模型Graph Theory网络中心和重心问题 v1 v3 v4 v5 v6 v7 v2 7 4 6 4 3 5 7 1 2 3 2 4 2 30 40 45 35 25 20 50 距离 人数 图与网络模型Graph Theory网络中心和重心问题 （1）中心问题 网络最短距离矩阵如下： vj vi D = ( dij ) d( vi )= max ? dij ? 1 2 3 4 5 6 7 1 0 3 4 5 7 8 10 10 2 3 0 3 2 4 5 7 7 3 4 3 0 5 5 6 8 8 4 5 2 5 0 2 3 5 5 ( min ) 5 7 4 5 2 0 1 3 7 6 8 5 6 3 1 0 2 8 7 10 7 8 5 3 2 0 10 j 结论： 商店应该建在 v4 村。 图与网络模型Graph Theory网络中心和重心问题 （2）重心问题 vj vi gidij 1 2 3 4 5 6 7 1 0 120 160 200 280 320 400 2 75 0 75 50 100 125 175 3 180 135 0 225 225 270 360 4 150 60 150 0 60 90 150 5 140 80 100 40 0 20 60 6 280 175 210 105 35 0 70 7 500 350 400 250 150 100 0 h ( vj ) 1325 920 1095 870 850 (min) 925 1215 结论： 小学应该建在 v5 村。 第四节 最大流问题 如下是一运输网络，弧上的数字表示每条弧上的容量，问：该网络的最大流量是多少？ vs v2 v1 v3 v4 vt 4 3 2 3 1 2 2 3 4 图与网络模型Graph Theory网络流问题 定义1：定一个有向图D=(V,E),在V中有一个发点vs和一收点vt，其余的点为中间点。对于每一条弧(vi,vj),对应有一个c(vi,vj)?0,(cij)称为弧的容量。这样的有向图称为容量网络。记为D=(V,E,C)。 1、网络流——义在弧集合E上的一个函数f={f(vi,vj)}，称f(vi,vj)为弧(vi,vj)上的流量，简记fij 。 2、可行流—— 3、最大流—— 4、增广链—— 5、最小截集—— 2、可行流与最大流 定义2 满足下列条件的流称为可行流： 1) 0? fij?cij 2)平衡条件：中间点 ? fij = ? fji (v