空间分布的测度和时间序列分析

1、上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列第三章第三章 空间分布的测度空间分布的测度和时间序列和时间序列空间分布的测度空间分布的测度时间序列时间序列上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列1 1 空间分布的测度空间分布的测度一、空间分布的类型一、空间分布的类型l点状分布类型点状分布类型：l线状分布类型线状分布类型：l面状分布类型面状分布类型：p离散区域分布类型离散区域分布类型p连续区域分布类型连续区域分布类型上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列1 1

2、 空间分布的测度空间分布的测度二、点状分布的测度l最邻近平均距离的测度最邻近平均距离的测度l对中心位置的测度对中心位置的测度l离散程度的测度离散程度的测度1 地理数据类型及其变换上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列p找出满足找出满足dih dib的距离；的距离；p若有若有p个，按顺序排列：个，按顺序排列：di1 di2 dipp=0,1,2,n-1二、点状分布的测度二、点状分布的测度1 最邻近平均距离l顺序法顺序法1 空间分布的测度i id dibibp测定测定dih，dib;p基准点：基准点：i;上一页下一页退 出返回目录第三章第三章 空间

3、分布的测度和时间序列空间分布的测度和时间序列二、点状分布的测度二、点状分布的测度pn个点依次作为基准点，可得顺序化矩阵：个点依次作为基准点，可得顺序化矩阵：1 空间分布的测度npnnppddddddddd21222211121112n点号12p 顺序号上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列二、点状分布的测度二、点状分布的测度p最邻近平均距离：最邻近平均距离：1 空间分布的测度p第第j级邻近平均距离：级邻近平均距离：Iiidnd1111I I为满足边界条件的最邻近点数的集合，为满足边界条件的最邻近点数的集合，n1为点数。为点数。Iiijjjdnd

4、1p例：例：P30上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列二、点状分布的测度二、点状分布的测度l区域法：（略）区域法：（略）l邻近指数：邻近指数：1 空间分布的测度eddR1Dde21AnD 为理论的随机分布型的最邻近平均距离。为理论的随机分布型的最邻近平均距离。 为点的密度，其中为点的密度，其中A为区域面积，为区域面积，n为区域为区域内点的个数。内点的个数。上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列二、点状分布的测度二、点状分布的测度lR对于点状分布类型的判断：对于点状分布类型的判断：pR=1，随机

5、型分布；，随机型分布；pR1，趋向于离散型的均匀分布。，趋向于离散型的均匀分布。1 空间分布的测度上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列二、点状分布的测度二、点状分布的测度l采用指标采用指标R的优点在于：的优点在于：p可以把要讨论的点的空间分布图式放在一个从可以把要讨论的点的空间分布图式放在一个从凝凝集集的、通过的、通过随机随机的一直到的一直到均匀均匀分布的连续广阔的分布的连续广阔的定量范围之内，此尺度范围为：定量范围之内，此尺度范围为：0-2.149。p对于一个对于一个固定地域固定地域来说，点的空间分布随时间而来说，点的空间分布随时间而变化，

6、亦可通过变化，亦可通过R尺度分析去判断其空间分布比尺度分析去判断其空间分布比原先的是更凝集还是更趋于分散，并且定量的表原先的是更凝集还是更趋于分散，并且定量的表达出其凝集或分散的程度。达出其凝集或分散的程度。pR的数值一般在的数值一般在0.33-1.67之间。之间。1 空间分布的测度上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列邻近指数练习邻近指数练习 我国1953年5万人口以上的城镇数为151个，至1978年发展到302个，见下表。根据计算， 各年5万人口以上城镇的最邻近平均距离如表所示。试计算点状分布的R指标，并作简要的地理解释。83.792711

7、973302210151城镇数95.961963160.31195381.021978Rd1(km)年代1 空间分布的测度上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列邻近指数练习邻近指数练习解：1.计算各年的理论随机分布的平均距离。 1953：)(12696000001512121kmAnde 2.计算各年的邻近指数R。 1953：29. 112631.160153eddR90. 0,89. 0,88. 0787363RRR年代城镇数R19531511.2919632100.8819732710.8919783020.901 空间分布的测度上一页下一

8、页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列邻近指数练习邻近指数练习1 空间分布的测度地理解释：l我国我国5万人口以上的城镇万人口以上的城镇1953年的年的R指标为指标为1.29，比，比随机分布更趋分散。随机分布更趋分散。l在在1953-1963年间，城镇发展迅速，由年间，城镇发展迅速，由151个发展到个发展到210个，增长了大约个，增长了大约39%，R63=0.88说明城镇分布已说明城镇分布已略呈凝集型。略呈凝集型。l以后虽然城镇总数虽然继续扩大，但因在此期间边以后虽然城镇总数虽然继续扩大，但因在此期间边远城镇相对发展比较迅速，因此远城镇相对发展比较迅速，因

9、此R指标反而略有增大。指标反而略有增大。上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列二、点状分布的测度二、点状分布的测度2 中心位置及其测度l中项中心中项中心p画东西线画东西线AB；p画南北线画南北线CD；p交点即中心。交点即中心。1 空间分布的测度ABCD上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列二、点状分布的测度二、点状分布的测度2 中心位置及其测度l平均中心（分布重心）平均中心（分布重心）p作作x,y轴；轴；p确定每一点的坐标；确定每一点的坐标；p计算坐标均值。计算坐标均值。1 空间分布的测度y y

10、Ox xniiniiynyxnx111,1niyxPiii, 2 , 1),(),(yxP即为平均中心。即为平均中心。上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列二、点状分布的测度二、点状分布的测度2 中心位置及其测度l区域重心的测度（补充）区域重心的测度（补充）p假设某一个区域由假设某一个区域由n个小区单元构成，其中个小区单元构成，其中,第第i个小区单元的中心坐标为个小区单元的中心坐标为(Xi,Yi)，Mi为该小区单为该小区单元某种属性意义下的元某种属性意义下的“重量重量”，则该属性意义，则该属性意义下的区域重心坐标为下的区域重心坐标为:1 空间分

11、布的测度niiniiiniiniiiMYMyMXMx1111,),(yxP上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列二、点状分布的测度二、点状分布的测度2 中心位置及其测度l区域重心的测度（补充）区域重心的测度（补充）p若属性值若属性值Mi为各小区单元的面积为各小区单元的面积,则空间均值则空间均值P就是区域的就是区域的几何中心几何中心。p当某一空间现象的空间均值显著区别于区域几当某一空间现象的空间均值显著区别于区域几何中心何中心,就指示了这一空间现象的不均衡分布就指示了这一空间现象的不均衡分布,或或称称“重心偏离重心偏离”。p偏离偏离方向方向指示了

12、空间现象的指示了空间现象的“高密度高密度”部位部位,偏偏离的离的距离距离则指示了均衡程度。则指示了均衡程度。1 空间分布的测度上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列二、点状分布的测度二、点状分布的测度2 中心位置及其测度l区域重心的测度（补充）区域重心的测度（补充）p在实际问题的分析中在实际问题的分析中,对于一个较大的行政区域对于一个较大的行政区域:可以将(Xi,Yi)取为各次级行政区域单元,譬如省(市、区)的首府坐标;Mi可以为不同的属性值(譬如,人口、产值等)。1 空间分布的测度上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序

13、列空间分布的测度和时间序列区域重心应用举例区域重心应用举例1 空间分布的测度中国人口重心的迁移l取取Mi为总人口，采用为总人口，采用1978-1997年期间各省年期间各省（市、区）的人口数据，计算出每年的人（市、区）的人口数据，计算出每年的人口重心坐标；口重心坐标；l将其表示在经纬网平面坐标系中，并依次将其表示在经纬网平面坐标系中，并依次将各个坐标点连接起来便可得到将各个坐标点连接起来便可得到20年来中年来中国人口重心的动态演化图。国人口重心的动态演化图。上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列上一页下一页退 出返回目录第三章第三章 空间分布的测

14、度和时间序列空间分布的测度和时间序列区域重心应用举例区域重心应用举例1 空间分布的测度说明问题：l近近20年来年来,中国人口重心一直位于中国人口重心一直位于11329以东以东,3245以南。大大偏离了中国的几以南。大大偏离了中国的几何中心何中心(10350,36)。l在近在近20年内年内,中国人口重心呈现出缓慢稳定中国人口重心呈现出缓慢稳定地向西南方向移动。地向西南方向移动。上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列1 1 空间分布的测度空间分布的测度三、线状分布的测度网络l（一）网络的基本概念（一）网络的基本概念p网络图网络图p与几何学中图形的区

15、别与几何学中图形的区别v1v2v3v4v5v6e1e2e3e4e5v1v2v3v4v5v6e1e2e3e4e5e6（a）图）图（b）图）图无向图无向图G=（V,E）有向图有向图G=（V,A）上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列三、线状分布的测度三、线状分布的测度- -网络网络（二）最短路径问题l1.引例：引例：1 空间分布的测度沿沿v1, v4, v7, v8, v9:4+6+4+2=16 单位单位沿沿v1, v2, v3, v6, v9:2+4+4+4=14 单位单位v1v2v3v4v5v64v7v8v964644442224上一页下一页退

16、 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列三、线状分布的测度三、线状分布的测度- -网络网络一般情况下最短路径问题的叙述：l在有向图在有向图G=(V,A)G=(V,A)中，给定一个始点中，给定一个始点v v1 1和终点和终点v v9 9，对每条弧对每条弧(v(vi i,v,vj j)A)A相应的有一个相应的有一个权权w wijij（称（称G G为为赋权有向图）。赋权有向图）。l最短路径问题，就是要求从始点最短路径问题，就是要求从始点v v1 1到终点到终点v v9 9的的一条路，使其在所有的从一条路，使其在所有的从v v1 1到到v v9 9的路径中，它的路径中

17、，它是是总权总权最小的一条。最小的一条。lV V为点的集合，为点的集合，A A则为弧的集合。则为弧的集合。1 空间分布的测度上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列三、线状分布的测度三、线状分布的测度- -网络网络2.标号法求最短路径（E.W.Dijkstra）l从始点从始点v v1 1开始，给每一个顶点记一个数（称为标号）。开始，给每一个顶点记一个数（称为标号）。l标号分标号分T T和和P P两种：两种：T T标号表示从始点标号表示从始点v v1 1到这一点的最短到这一点的最短路权的上界，称为临时标号；路权的上界，称为临时标号；P P标号表示从

18、标号表示从v v1 1到该点的到该点的最短路权，称为固定标号。最短路权，称为固定标号。l已得到已得到P P标号的点不再改变，凡是没有标上标号的点不再改变，凡是没有标上P P标号的点，标号的点，均标上均标上T T标号。标号。l算法的每一步均把某一点的算法的每一步均把某一点的T T标号改变为标号改变为P P标号。最多标号。最多经过经过n-1n-1步，就可以得到从始点到每一点的最短路径。步，就可以得到从始点到每一点的最短路径。1 空间分布的测度上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列三、线状分布的测度三、线状分布的测度- -网络网络2.标号法求最短路径

19、计算步骤l开始，给开始，给v1标上标上P标号标号P(v1)=0。其余各点标上。其余各点标上T标号，标号，T(vj)=+。 设设vi是刚刚得到是刚刚得到P标号的点，考虑所有这样的点标号的点，考虑所有这样的点vj：使使(vi,vj)A，以及，以及vj的标号是的标号是T标号标号，则修改，则修改vj的的T标标号为号为minT(vj), P(vi)+Wij。 若若G中中没有没有T标号点标号点，则停止，否则，则停止，否则T(vj0)=min T(vj)，vj是是T标号点，则把点标号点，则把点vj0的的T标号修改为标号修改为P标号。转入标号。转入继续。继续。1 空间分布的测度上一页下一页退 出返回目录第三章

20、第三章 空间分布的测度和时间序列空间分布的测度和时间序列三、线状分布的测度三、线状分布的测度- -网络网络例：求图中最短有向路径及其长度开始，开始，P(v1)=0，T(vj)=+，（，（j=2,3,7）。第一步：第一步：S=1,I=1,T=2,3,4,5,6,7(v(v1 1,v,v2 2),(v),(v1 1,v,v3 3),(v),(v1 1,v,v4 4)A)A且且v v2 2、v v3 3、v v4 4是是T T标号点，标号点，则修改其则修改其T T标号为：标号为：1 空间分布的测度v4v6v1v3v7v2v59475113953226990,min)(),(min)(12122WvP

21、vTvT上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列在所有的在所有的T T标号中，标号中，T(vT(v4 4) )最小，于是令最小，于是令P(v4)=2。第二步：第二步： S=2,I=4,T=2,3,5,6,7v v4 4刚得到刚得到P P标号，故考察标号，故考察v v4 4。(v(v4 4,v,v3 3),(v),(v4 4,v,v6 6)A)A且且v v3 3、v v6 6是是T T标号点，则修改其标号点，则修改其T T标号为：标号为：1 空间分布的测度770,min)(),(min)(13133WvPvTvT220,min)(),(min)(1

22、4144WvPvTvT642,7min)(),(min)(43433WvPvTvT532,min)(),(min)(46466WvPvTvT990,min)(),(min)(12122WvPvTvT在所有的在所有的T T标号中，标号中，T(vT(v6 6) )最小，于是令最小，于是令P(v6)=5。上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列第三步：第三步： S=3,I=6,T=2,3,5,7v v6 6刚得到刚得到P P标号，故考察标号，故考察v v6 6。(v(v6 6,v,v2 2),(v),(v6 6,v,v5 5),),(v(v6 6,v,

23、v7 7)A)A且且v v2 2、v v5 5、v v7 7是是T T标号点，则修改为：标号点，则修改为：1 空间分布的测度835,9min)(),(min)(62622WvPvTvT16115,min)(),(min)(65655WvPvTvT在所有的在所有的T T标号中，标号中，T(vT(v3 3) )最小，于是令最小，于是令P(v3)=6。1495,min)(),(min)(67677WvPvTvT上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列第四步：第四步： S=4,I=3,T=2,5,7v v3 3刚得到刚得到P P标号，故考察标号，故考察v

24、 v3 3。(v(v3 3,v,v2 2)A)A且且v v2 2是是T T标号点，则修改为：标号点，则修改为：1 空间分布的测度856,8min)(),(min)(32322WvPvTvT在所有的在所有的T T标号中，标号中，T(vT(v2 2) )最小，于是令最小，于是令P(v2)=8。第五步：第五步： S=5,I=2,T=5,7v v2 2刚得到刚得到P P标号，故考察标号，故考察v v2 2。(v(v2 2,v,v5 5)A)A且且v v5 5是是T T标号点，则修改为：标号点，则修改为：在所有的在所有的T T标号中，标号中，T(vT(v5 5) )最小，于是令最小，于是令P(v5)=1

25、3。1358 ,16min)(),(min)(25255WvPvTvT上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列第六步：第六步： S=6,I=5,T=7v v5 5刚得到刚得到P P标号，故考察标号，故考察v v5 5。(v(v5 5,v,v7 7)A)A且且v v7 7是是T T标号点，则修改为：标号点，则修改为：1 空间分布的测度14613,14min)(),(min)(57577WvPvTvT令令P(v7)=14，计算结束。，计算结束。v1-v7最短路径长度为最短路径长度为14。最短路线的推求最短路线的推求倒推法：倒推法：故最短有向路线为：故

26、最短有向路线为：v1v4 v6 v7。1495,min)(),(min)(67677WvPvTvT532,min)(),(min)(46466WvPvTvT220,min)(),(max)(14144WvPvTvT上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列三、线状分布的测度三、线状分布的测度- -网络网络（三）服务点的最优区位问题l1.服务点的中心（服务点的中心（P46）p求出求出G的距离表：的距离表：1 空间分布的测度020750423075430463630v1v2v3v6v4v5v1v2v3v6v4v502747420525675034342

27、3036754303463630v1v2v3v6v4v5v1v2v3v6v4v5上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列三、线状分布的测度三、线状分布的测度- -网络网络（三）服务点的最优区位问题l2.服务区的中央点（服务区的中央点（P47）p正负荷：正负荷：a(vi)p总运输量的计算：总运输量的计算：1 空间分布的测度3.122645.413.953.61573230)()(1711jjjdvavS上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列三、线状分布的测度三、线状分布的测度- -网络网络（四）运输

28、网络l结点的直通性（结点的直通性（P48）l道路系统的里程（道路系统的里程（P48）l道路系统的运输量（吨千米）（道路系统的运输量（吨千米）（P49）l考虑中转考虑中转运输费用的综合影响（运输费用的综合影响（P49）1 空间分布的测度上一页下一页退 出返回目录（四）、运输网络表示法运输网络是地理研究的重要研究对象。运输网络可以用两种方法表示：形象的图表示法和邻接矩阵表示法。图表示法我们以结点表示经济中心，以结点之间的连线表示反映经济网络的铁路、高速公路等交通运输线路，就构成一张运输网络图。邻接矩阵表示法用邻接矩阵可以表示各结点与道路的关系。它的优点在于便于在计算机上处理。两个结点有边直接相联则

29、取值为1,否则取值0。即邻接矩阵A = (aij)n*n的元素上一页下一页退 出返回目录结点的直通性结点直通性是指从一个结点可以不经中转,直接到达另一个结点的网络便捷性测度。中转与直通是运输网络的重要特征。尽量减少中转，增加运输直达程度是现代运输经济的客观要求，这在区域运输网络和城市公共交通网络中都十分重要。如果一个结点就可以直达其它结点的程度比较高，它在运输网中就处于比较重要的地位，也是较理想的供应中心。假定每一个结点都需要中转，以直通矩阵表示各结点之间的直通程度，则所得到的结果就是上述的邻接矩阵。上一页下一页退 出返回目录最短里程结点和最省运输工作量结点最短里程结点是指一个运输网络中，从一

30、个结点出发到达所有的其它结点，里程之和最小的结点。在各结点具有不同的实际意义时，最短距离不是唯一的经济因素，还需要考虑由于不同结点运出的旅客数或货物量。用“加权”的方法 ，可以把各种网络矩阵综合起来进行分析，把直通性视为一种节约运输工作量的系数或缩短里程的系数。上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列想一想，练一练想一想，练一练某地理区有5个城镇A、B、C、D、E，各城镇的地理位置及正负荷如图所示。现计划在该地区建一工厂，若使产品运往到各城镇的总运输量为最少，问这个工厂建在那个城镇更好？1 空间分布的测度a(A)=1BCEAD4815154212

31、a(B)=2a(C)=3a(D)=4a(E)=5上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列运输网络练习运输网络练习解：1.道路系统的里程ABCDEABCDE0152748636315012546969485442015152712042575701 空间分布的测度上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列运输网络练习运输网络练习2.道路系统的运输量ABCDE总计秩ABCDE01=0 151=15271=27481=48631=63635=315152=30 02=0122=24542=108692=13

32、8695=345484=192544=216424=16804=0154=60155=75273=81123=3603=0423=126573=171575=28505=06186123575044321 空间分布的测度54132上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列标号法求最短路经练习标号法求最短路经练习求从结点V1到各个结点的最短路径。1 空间分布的测度1v3v10v1v4v11v2v8928279911365v53v6963112v7v9110上一页下一页退 出返回目录补充：最大流与最小费用流补充：最大流与最小费用流 最大流问题设有向网络

33、N（V，A），在发点Vs 有一批货，要通过网络上的弧运输到收点Vt 去，受运输条件限制，每条弧aij在单位时间内通过的车辆数不能超过cij 辆，分析：如何组织运输才能使从Vs到Vt 在单位时间内通过的车辆达到最多？最大流问题广泛地应用在交通运输、供水、油管供油、邮电通讯，也可以用在生产安排，管理优化等实际问题上。1. 最大流问题及其求解方法 上一页下一页退 出返回目录最大流与最小费用流最大流与最小费用流 最大流问题设有向网络N（V，A），在发点Vs 有一批货，要通过网络上的弧运输到收点Vt 去，受运输条件限制，每条弧aij在单位时间内通过的车辆数不能超过cij 辆，分析：如何组织运输才能使从V

34、s到Vt 在单位时间内通过的车辆达到最多？最大流问题广泛地应用在交通运输、供水、油管供油、邮电通讯，也可以用在生产安排，管理优化等实际问题上。1. 最大流问题及其求解方法 上一页下一页退 出返回目录例例：如图9.3.1(a)中，有一批物资需要用汽车尽快从发点运到收点，弧（i，j）上所标的数字表示该条道路在单位时间内最多能通过的车辆数（单位：百辆），问如何调运，才能使单位时间里有最多的车辆从调到。23425167563855771132 图图9.3.1(a)3上一页下一页退 出返回目录线线性性规规划划方方法法 点出发的车辆数应该与点到达的车辆数相同，除和以外的各中间点，进的车辆数应该与离去的车辆

35、数应该相同。fxxxxx67571413126765564636575665352546341436353432231325233212xxxxxxxxxxxxxxxxxxxxxxxxij 是通过弧(i，j)的车辆数。上一页下一页退 出返回目录 对所有弧（i，j），应满足约束 满足以上条件的解称为从到的一个可行流，目的：在所有可行流中求出一个方案，使得这个可行流得到的 f 最大。 若从收点到发点连接一条假想弧(7，1)，设它的容量c71=，那么 对点： 对点： 最大流问题的目标 ijijcx 014131271xxxx716757xxxmax71x上一页下一页退 出返回目录 对发点为Vs，收点

36、为Vt的网络N（V，U），当增加一条约束为cts=的假想弧（t，s）后，最大流问题就成为： 容量约束： 平衡条件： 目标函数： ijijcx 0UjjijUijjixx),(),(maxstx上一页下一页退 出返回目录网网络络图图论论方方法法标标号号法法 24163573st565023008102 37007100005 弧的容量的表示弧的容量的表示 每条弧Vij上标上两个数字，靠近i点的是cij，靠近j点的是cji。如表明沿Vij从到的最大通过量是5（百辆），从到的最大通过量是0。将图9.3.1(a)画成9.3.1(b) 的形式。05上一页下一页退 出返回目录0522 求最大流的基本算法

37、对图9.3.1(b)做以下步骤的修改： 步骤步骤1. 从发点s到收点t选定一条路，使这条路通过的所有弧Vij的前面约束量cij都大于0，如果找不到这样的路，说明已经求得最大流，转步骤4。 步骤步骤2. 在选定的路上，找到最小的容许量cij定为P。 步骤步骤3. 对选定的路上每条弧的容量作以下修改，对于与路同向的弧，将cij修改为cij-P，对于与路反向的弧，将cij修改为cij+P。上一页下一页退 出返回目录第一次修改第一次修改：选定，P = c13 = 6。修改后：c13=6-6，c31=0+6，c36=7-6， c63=0+6，c67=7-6，c76=0+6。 图图9.3.29.3.224

38、163573st505023008162 31061160005上一页下一页退 出返回目录 返回步骤1，做第二次修改。 第二次修改第二次修改： 选定， P = c25 = 3。修改后将c12改为2，c25改为0，c57改为5，c21、c52、c75改为3。图图9.3.39.3.324163573st205320305162 31361160005上一页下一页退 出返回目录 回到步骤1，继续做下去： 第三次修改第三次修改： 选定， P = c12 = 2。 图图9.3.49.3.424163573st005500323164 11561160005上一页下一页退 出返回目录 第四次修改：第四次修

39、改： 选定，P = c67 = 1。 图图9.3.59.3.524163573st004500323164 11570161104上一页下一页退 出返回目录 第五次修改第五次修改： 选定,P = c65 = 1。 图图9.3.69.3.624163573st003500322264 11670062203上一页下一页退 出返回目录 在图9.3.6中，仍能找到，使每条弧起点的容量都大于零，P = C35 = 1。注意，这条路经过弧(6，3)，本来在图9.3.1(b)中，从到是无容量可通过的，但经过几次修改，由 变成 ，说明这时从到还可通过1（百辆），而从到，可以通过6（百辆）的容量，实际上只是把

40、计划中从到的通过车辆数进行减少。 0761上一页下一页退 出返回目录 第六次修改第六次修改： 选定， P = c35 =1。 在图9.3.7中，从发点到收点再也不存在连通的起点容量都大于零的弧了。 这样，我们就称图9.3.7为最大流图。 图图9.3.79.3.724163573st002500331064 02770053302上一页下一页退 出返回目录 做出最大流图后，转向步骤4。 步骤步骤4. 将原图各条弧上起点与终点数值减去修改后的图上各点的数值，将得到相反的两个数，将这个数标在弧上，并将从正到负的方向用箭头表示。 例如原来弧(3，6)是 ，现在是 ，相减为5，那边为正，我们就记作 。这

41、样，就得到图9.3.8。 07525上一页下一页退 出返回目录 最大流量如图9.3.8所示。依这样的调动方式，可以从发点s调运14（百辆）汽车到收点t。图图9.3.89.3.824163575 63323530177上一页下一页退 出返回目录最大流算法的讨论一个图成为最大流图的条件是存在饱和路。 饱和路从发点到收点的每一条路上总存在某个起点容量为零的弧。 非饱和路从发点到收点有一条路，它上面每条路的起点容量都大于零。 定理定理1. 一个图是最大流图的充要条件是不存在从s到t的非饱和路。上一页下一页退 出返回目录将网络中的点分成两组，一组包括发点s，称为发集V1，一组包括收点t，称为收集V2，连

42、接V1到V2的所有弧称为截集，截集上各弧在V1旁的容量合称为截集的容量。在将网络分成发集与收集的所有分法中，使截集容量最小的截集成为最小截集。可以证明： 定理定理2. 在网络N中，设f是从发点到收点的一个可行流，f是最大流的充要条件是这时网络的最小截集的容量为零。上一页下一页退 出返回目录定理定理3. 设f是网络N的一个可行流，则这时N的最小截集容量等于网络最大流fmax与f的差，即 称为可行流f的余量。显然，当=0时，就得到了最大流。 定理定理4. 在任一网络中，从vs到vt的最大流的流量等于分离vs，vt的最小截集的容量。 在从vs到vt的运输中，最小截集的弧是网络中的“卡脖子”线路，要获

43、得最大流运输量，必须在最小截集的各弧上达到满载。 ffmax上一页下一页退 出返回目录最大流fmax的大小是确定的，但最大流的路线可以不唯一。 在前例中，若从不同的路来修改图，也可能得到另外一个最大流图（图9.3.9）。 图图9.3.924163575 63323352177上一页下一页退 出返回目录最大流图9.3.8、9.3.9 必有以下性质 对于网络的最小截集上的弧，它们的流量是相同的。 对于由最小截集分开的V1和V2内，它们的流量可能不同，但都是相差一个或几个不饱和回路上的量。 如图9.3.8与图9.3.9，相差: 回路上一个值为2的流量。 上一页下一页退 出返回目录2. 最小费用流及其

44、求解方法最小费用流及其求解方法 最小费用流问题在考虑网络上流量的同时，使得所安排流量的费用或者代价达到最小。上一页下一页退 出返回目录n在前例中，如果单位车辆数通过某条弧要付出一定的代价，其代价图如图9.3.10。 图图9.3.109.3.10425136744331332223222上一页下一页退 出返回目录约束条件(如最大流问题）满足约束条件下，找到一个可行流f的流量 一定时，f的代价最小，即 指单位车辆数通过弧(，)的代价。 fxxxxx6757141312ijijcx 0max0fffmin),(Vjiijijxddijd线线性性规规划划描描述述 6765564636575665352

45、546341436353432231325233212xxxxxxxxxxxxxxxxxxxxxxx上一页下一页退 出返回目录求解最小费用流的步骤 选定一条总的单位费用最小的路，即要给定最小费用的初始可行流，而不是包含边数最小的路。 不断重复求最大流的步骤来进行，当流量达到f0时就可以停止，这时求出的是最小费用流，当然，如果f0=fmax，就可将步骤进行到最后，即没有饱和路存在为止。 网网络络图图论论方方法法标标号号法法 求解最小费用流的步骤和求最大流的步骤几乎完全一致，只是在步骤1的选一条非饱和路时，应选代价和最小的路，即最短路。 上一页下一页退 出返回目录例例：在前例中，如果单位车辆数通过

46、某条弧要付出一定的代价，其代价图如图9.3.10。图图9.3.109.3.10425136744331332223222上一页下一页退 出返回目录修改次数最短路最短路的代价和di最短路的流量xi该路的饱和弧(ij)173285与383492与5101表表9.3.1 9.3.1 最小费用流的求解过程最小费用流的求解过程 这时的总代价为： 1131102938583751iiixdd上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列1 1 空间分布的测度空间分布的测度四、面状分布的测度l（一）空间罗伦兹曲线（一）空间罗伦兹曲线（Lorenz）地区地区12345

47、6789101112 总计钢铁6.68.3 63.2 5.1 11.0 0.13.31.10.70.10.5 100.0食品23.0 24.4 6.04.13.46.07.2 14.03.02.83.62.5 100.0总产值 22.9 17.6 11.7 11.5 4.35.5 10.0 6.02.92.12.53.0 100.0辽宁省工业部门产值的地区分布（辽宁省工业部门产值的地区分布（%）上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列1.罗伦兹曲线的作法l作正方形作正方形1 空间分布的测度20406080 100O O20406080100工业总

48、产值累积百分比（工业总产值累积百分比（% %）选定工业部门产值累积百分比（选定工业部门产值累积百分比（% %）X Xl计算计算R值；值；总产值各部门产值R29.09.226.61R47.06.173.82R上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列l将所得各地区将所得各地区R值按由大到值按由大到小顺序排列。小顺序排列。地区R值35241071812116963.2/11.7=5.411.0/4.3=2.68.3/17.6=0.475.1/11.5=0.440.7/2.1=0.333.3/10=0.336.6/22.9=0.291.1/6.0=0.1

49、80.5/3.0=0.160.1/2.5=0.040.1/5.5=0.020/2.9=0上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列地区R值累积（%）钢铁工业总产值35241071812116963.2/11.7=5.411.0/4.3=2.68.3/17.6=0.475.1/11.5=0.440.7/2.1=0.3399.83.3/10=0.336.6/22.9=0.291.1/6.0=0.180.5/3.0=0.160.1/2.5=0.0499.987.688.391.698.299.3100.00.1/5.5=0.020/2.9=063.274

50、.282.5100.011.716.033.647.245.157.280.186.191.689.197.1100.0钢铁工业按R值大小排列表l计算累积值计算累积值上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列空间罗伦兹曲线分布图20406080100O O20406080100工业总产值累积百分比（工业总产值累积百分比（% %）选定工业部门产值累积百分比（选定工业部门产值累积百分比（% %）ABA：钢铁工业：钢铁工业B：食品工业：食品工业X Xl以累积值作图以累积值作图（11.7,63.2）（16.0,74.2）上一页下一页退 出返回目录第三章第三

51、章 空间分布的测度和时间序列空间分布的测度和时间序列面状分布的测度面状分布的测度2.罗伦兹曲线结构分析lOX表示两种分布完全对应，即某工业部门产值与表示两种分布完全对应，即某工业部门产值与总产值有相同的累积百分率，称为均匀分布。总产值有相同的累积百分率，称为均匀分布。l曲线离开对角线的远近就是两种分布的差异的测度。曲线离开对角线的远近就是两种分布的差异的测度。p曲线曲线A远离对角线，说明本省的钢铁工业比较集远离对角线，说明本省的钢铁工业比较集中，中，3、5、2地区的钢铁产量占全省的地区的钢铁产量占全省的82.5%；p曲线曲线B较接近对角线，说明其分布较均匀。较接近对角线，说明其分布较均匀。1

52、空间分布的测度上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列面状分布的测度面状分布的测度（二）集中化指数RMRCIC C为各工业部门产值累积百分率总和；为各工业部门产值累积百分率总和；R R为工业总产值累积百分率总和；为工业总产值累积百分率总和；M M为最大累积百分率总和。为最大累积百分率总和。 I I的范围：的范围：0-10-1； 当当I=1I=1时，工业部门产值完全集中于一个地区；时，工业部门产值完全集中于一个地区； 当当I=0I=0时，曲线与对角线完全一致。时，曲线与对角线完全一致。1 空间分布的测度上一页下一页退 出返回目录第三章第三章 空间分

53、布的测度和时间序列空间分布的测度和时间序列作图法求集中化指数L2L4L6L8L10O O20406080100工业总产值累积百分比（工业总产值累积百分比（% %）选定工业部门产值累积百分比（选定工业部门产值累积百分比（% %）X XL1L3L5L7L9M2M4M6M8M10M1M3M5M7M9C2C4C6C8C10C1C3C5C7C9上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列面状分布的测度面状分布的测度（二）集中化指数6751009792847767584734191021101CCCCCii5501009080706050403020101021

54、101LLLLRii100010010010010101010110CCCCMi1 空间分布的测度上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列面状分布的测度面状分布的测度（二）集中化指数277.05501000550675RMRCI食品711.05501000550870RMRCI钢铁上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列面状分布的测度面状分布的测度- -基尼系数基尼系数基尼系数l是判断分配平等程度的指标。是判断分配平等程度的指标。1 空间分布的测度O OX XA ABl罗伦兹曲线表示实际收入分配曲线

55、；罗伦兹曲线表示实际收入分配曲线；l对角线表示收入分配绝对平等曲线；对角线表示收入分配绝对平等曲线；l两曲线之间的面积为两曲线之间的面积为A，一半正方形，一半正方形的面积为的面积为B；l基尼系数（罗伦兹系数）为基尼系数（罗伦兹系数）为A/B。上一页下一页退 出返回目录第三章第三章 空间分布的测度和时间序列空间分布的测度和时间序列面状分布的测度面状分布的测度- -基尼系数基尼系数基尼系数的范围：基尼系数的范围：0，1曲线弧度越小，收入分配越趋向于平等，曲线弧度越小，收入分配越趋向于平等，基尼系数也越小；反之越大。基尼系数也越小；反之越大。l0.5：高度不平均。：高度不平均。1 空间分布的测度上一页下一页退 出返回目录第三章第三章 空间