计量地理学(9-10章)ppt.ppt

第9章 随机型决策分析方法 随机型决策分析方法，是处理随机 型决策问题的分析技术。 由于许多地理问题与地理数据具有 随机性特征，所以许多地理决策问题属 于随机型决策问题。 因此，随机型决策分析方法是地理 学中必不可少的方法。 本章主要内容 随机型决策问题 风险型决策方法 非确定型决策方法 第一节 随机型决策问题 决策的基本概念 随机型决策问题 一般来说，凡是根据预定的目标做出 的任何行动决定，都可以称之为决策。 几个关于决策的概念: n决策问题 在实际生产或生活问题中，对于一 个需要处理的事件，面临几种客观条件 ，又有几种可供选择的方案，这就构成 了一个决策问题。 一、决策的基本概念 n行动方案 在决策问题中，那些可供选择的方案 就称之为行动方案，简称方案或策略，有 时也称为方案变量或决策变量。 n状态概率 指在决策问题中，每一种自然状态出 现的概率。 n自然状态 在决策问题中，决策者所面临的每一 种客观条件就称之为一个自然状态，简 称状态或条件，有时也称为状态变量。 n益损值 指每一种行动方案在各种自然状态 下所获得的报酬或者需要付出的损失（ 成本、代价）。 n最佳决策方案 就是依照某种决策准则，使决策目 标取最优值（譬如，收益最大值或者成 本最小值）的那个（些）行动方案。 例1:根据自然条件，某农场可以选择种 植的农作物有4种：水稻、小麦、大豆、 燕麦。该农场 所在地区每一年可能发生 的天气类型有5种：极旱年、旱年、平年 、湿润年、极湿年。表9.1.1给出了每一 种天气类型发生的概率，以及在每一种天 气类型条件下种植各种农作物所获得的收 益。该农场 究竟应该种植哪一种农作物 ？ 表9.1.1 每一种天气类型发生的概率及 种植各种农作物的收益 该例所描述的就是一个决策问题。在 这一个决策问题中，各种天气类型就是自 然状态，共有5种状态，即“极旱年”、“ 旱年”、“平年”、“湿润年”、“极湿 年”，各状态发生的概率，即状态概率分 别为0.1,0.2,0.4,0.2,0.1；各农作物种类 就是行动方案，共有4种方案，即“水稻” 、“小麦”、“大豆”、“燕麦”；在每 一种状态下，各方案的益损值就是在每一 种天气类型下各种农作物的收益值。 二、 随机型决策问题 (一)决策问题的基本类型 根据人们对决策问题的自然状态 的 认识程度，可以把决策问题划分为两种基 本类型，即确定型决策问题 和 随机型决 策问题。 n确定型决策问题 指决策者已经完全确切地知道将发生 什么样的自然状态，从而可以在既定的状 态下选择最佳行动方案。 也就是说，对于确定型决策问题而言 ，只存在一个唯一确定的自然状态。 对于确定型决策问题，在实际工作中 ，决策者所面临的方案数目可能是很大的 ，最佳决策方案的选择往往需要采用各种 规划方法（如线性规划、目标规划等）才 能实现。 n随机型决策问题 指决策者所面临的各种自然状态将是随机 出现的。 随机型决策问题，必须具备以下几个条件 ： 存在着决策者希望达到的明确目标； 存在着不依决策者的主观意志为转移 的两个以上的自然状态； 存在着两个以上的可供选择的行动方 案； 不同行动方案在不同自然状态下的益 损值可以计算出来。 随机型决策问题可进一步分为风险型 决策问题和非确定型决策问题。 风险型决策问题：每一种自然状态发 生的概率是已知的或者可以预先估计的。 非确定型决策问题：各种自然状态发 生的概率也是未知的和无法预先估计的。 (二)决策问题的分类及特点 图9.1.1 第2节 风险型决策方法 最大可能法 期望值决策法及其矩阵运算 树型决策法 灵敏度分析法 效用分析法 许多地理问题,常常需要在自然、经济、 技术、市场等各种因素共存的环境下做出决策 。而在这些因素中，有许多是决策者所不能控 制和完全了解的。对于这样一类地理决策问题 的研究，风险型决策方法是必不可少的方法。 对于风险型决策问题，其常用的决策方 法主要有最大可能法、期望值法、灵敏度分析 法、效用分析法等。 在对实际问题进行决策时，可以采用各种 不同方法分别进行计算、比较，然后通过综合 分析，选择最佳的决策方案，这样，往往能够 减少决策的风险性。 一、最大可能法 (一)最大可能法 在解决风险型决策问题时，选择一个概 率最大的自然状态，把它看成是将要发生的 唯一确定的状态，而把其他概率较小的自然 状态忽略，这样就可以通过比较各行动方案 在那个最大概率的自然状态下的益损值进行 决策。这种决策方法就是最大可能法。 n应用条件 在一组自然状态中，某一自然状态出 现的概率比其他自然状态出现的概率大很 多，而且各行动方案在各自然状态下的益 损值差别不是很大。 实质 在“将大概率事件看成必然事件，小概 率事件看成不可能事件“的假设条件下， 将风险型决策问题转化成确定型决策问题 的一种决策方法。 例1：用最大可能法对第9章第1节中的例1 所描述的风险型决策问题求解。 表9.1.1 每一种天气类型发生的概率及 种植各种农作物的收益 解:由表可知，“极旱年“、“旱年“、“平年“、“ 湿润年“、“极湿年“5种自然状态发生的概率 分别为0.1、0.2、0.4、0.2、0.1，显然，“平 年“状态的概率最大。按照最大可能法，可 以将“平年“状态的发生看成是必然事件。而 在“平年“状态下，各行动方案的收益分别是 ：水稻为18千元/hm2，小麦为17千元/hm2， 大豆为23千元/hm2，燕麦为17千元/hm2，显 然，大豆的收益最大。所以，该农场应该选 择种植大豆为最佳决策方案。 二、期望值决策法及其矩阵运算 n期望值决策法 对于一个离散型的随机变量X，它的数学期望 为 式中:xi(n=1，2，n)为随机变量x的各个取值 ；Pi为x=xi的概率，即Pi = P(xi)。 随机变量x的期望值代表了它在概率意义下的平 均值。 期望值决策法，就是计算各方案的期望益损值， 并以它为依据，选择平均收益最大或者平均损失最小 的方案作为最佳决策方案。 n期望值决策法的计算、分析过程 把每一个行动方案看成是一个随机 变量，而它在不同自然状态下的益损值就 是该随机变量的取值； 把每一个行动方案在不同的自然状 态下的益损值与其对应的状态概率相乘， 再相加，计算该行动方案在概率意义下的 平均益损值； 选择平均收益最大或平均损失最小 的行动方案作为最佳决策方案。 例2：试用期望值决策法对表9.1.1所描述 的风险型决策问题求解。 表9.1.1 每一种天气类型发生的概率及 种植各种农作物的收益 解：(1) 方案：水稻B1，小麦B2，大豆B3， 燕麦B4； 状态：极旱年1 、旱年2 、平年3 、 湿润年4 、极湿年5； 方案Bi在状态j下的收益值aij看做该随 机变量的取值。 (2)计算各个行动方案的期望收益值 E(B1)1000.1+1260.2+1800.4+ 2000.2+2200.1=169.2(千元/hm2) E(B2)2500.1+2100.2+1700.4+ 1200.2+800.1=167(千元/hm2) E(B3)1200.1+1700.2+2300.4+ 1700.2+1100.1=183(千元/hm2) E(B4)1180.1+1300.2+1700.4+ 1900.2+2100.1=164.8(千元/hm2) 表9.2.1 风险型决策问题的期望值计算 (3)选择最佳决策方案。 因为E(B3)maxE(Bi)183（千元/hm2 ） 所以，种植大豆为最佳决策方案。 n期望值决策法的矩阵运算 假设某风险型决策问题，有m个方案B1 ，B2，Bm；有n个状态1，2，,n， 各状态的概率分别为P1,P2,Pn。如果在状 态j下采取方案Bi的益损值为aij（i=1， 2,m；j=1,2,n）,则方案Bi的期望益损值 为 如果引入下述向量 , , 及矩阵 则矩阵运算形式为 例2：试用期望值决策法对第9章第1节中的 例1所描述的风险型决策问题求解。 在上例中，显然有 由于E(B3)=maxE(Bi)=183(千元/hm2)， 所以该农场应该选择种植大豆为最佳决策方 案。 运用矩阵运算法则,经乘积运算可得 1 . 0 2 . 0 4 . 0 2 . 0 1 . 0 三、树型决策法 树型决策法,是研究风险型决策问 题经常采取的决策方法。 决策树,是树型决策法的基本结构 模型,它由决策点、方案分枝、状态结 点、概率分枝和结果点等要素构成 。 决策树结构示意图 在图中，小方框代表决策点，由决策点引出的 各分支线段代表各个方案，称之为方案分枝；方 案分枝末端的圆圈叫做状态结点；由状态结点引 出的各分枝线段代表各种状态发生的概率，叫做 概率分枝；概率分枝末端的小三角代表结果点。 n树型决策法的决策原则 树型决策法的决策依据是各个方案的期望益 损值，决策的原则一般是选择期望收益值最大或 期望损失（成本或代价）值最小的方案作为最佳 决策方案。 n树型决策法进行风险型决策分析的逻辑顺序 树根树杆树枝，最后向树梢逐渐展开。 各个方案的期望值的计算过程恰好与分析问题 的逻辑顺序相反，它一般是从每一个树梢开始，经 树枝、树杆、逐渐向树根进行。 （1）画出决策树。把一个具体的决策问 题，由决策点逐渐展开为方案分支、状态结 点，以及概率分支、结果点等。 （2）计算期望益损值。在决策树中，由 树梢开始，经树枝、树杆、逐渐向树根，依 次计算各个方案的期望益损值。 （3）剪枝。将各个方案的期望益损值分 别标注在其对应的状态结点上，进行比较优 选，将优胜者填入决策点，用“|“号剪掉舍 弃方案，保留被选取的最优方案。 n用树型决策法的一般步骤 (1)所谓单级风险型决策，是指在整个 决策过程中，只需要做出一次决策方案的 选择，就可以完成决策任务。实例见例3。 (2)所谓多级风险型决策，是指在整个 决策过程中，需要做出多次决策方案的选 择，才能完成决策任务。实例见例4。 n单级风险型决策与多级风险型决策 例3：某企业为了生产一种新产品，有3个方案可供决 策者选择：一是改造原有生产线；二是从国外引进生产 线；三是与国内其他企业协作生产。该种产品的市场需 求状况大致有高、中、低3种可能，据估计，其发生的 概率分别是0.3、0.5、0.2。表9.2.2给出了各种市场需 求状况下每一个方案的效益值。试问该企业究竟应该选 择哪一种方案？ 表9.2.2 某企业在采用不同方案生产某种新产品的效益值 解：该问题是一个典型的单级风险型决策问题，现 在用树型决策法求解这一问题。 (1) 画出该问题的决策树 (图9.2.2所示)。 图9.2.2 单级风险型决策问题的决策树 (2)计算各方案的期望效益值。 状态结点V1的期望效益值为 EV12000.3+1000.5+200.2=114（万元） 状态结点V2的期望效益值为 EV22200.3+1200.5+600.2138（万元） 状态结点V3的期望效益值为 EV31800.3+1000.5+800.2120（万元） (3) 剪枝。因为EV2 EV1, EV2 EV3， 所以，剪掉状态结点V1和V3所对应的方案 分枝，保留状态结点V2所对应的方案分枝 。即该问题的最优决策方案应该是从国外 引进生产线。 例4:某企业，由于生产工艺较落后，产品成本 高，在价格保持中等水平的情况下无利可图， 在价格低落时就要亏损，只有在价格较高时才 能盈利。鉴于这种情况，企业管理者有意改进 其生产工艺，即用新的工艺代替原来旧的生产 工艺。 现在，取得新的生产工艺有两种途径：一 是自行研制，但其成功的概率是0.6；二是购 买专利，估计谈判成功的概率是0.8。 如果自行研制成功或者谈判成功，生产规 模都将考虑两种方案：一是产量不变；二是增 加产量。 如果自行研制或谈判都失败，则仍采用原 工艺进行生产，并保持原生产规模不变。 据市场预测，该企业的产品今后跌价的概 率是0.1，价格保持中等水平的概率是0.5，涨 价的概率是0.4。 表9.2.3给出了各方案在不同价格状态下的 效益值。 试问，对于这一问题，该企业应该如何决策 ？ 解：这个问题是一个典型的多级（二级）风 险型决策问题，下面仍然用树型决策法解决 该问题。 (1)画出决策树（图9.2.3）。 表9.2.3 某企业各种生产方案下的效益值(单位：万元) 方 案 效 益 价格状态（概率） (2) 计算期望效益值，并进行剪枝： 状态结点V7的期望效益值为 EV7(-200)0.1+500.5+1500.465（ 万元）； 状态结点V8的期望效益值为 EV8(-300)0.1+500.5+2500.495（万 元）。 由于EV8EV7，所以，剪掉状态结点V7对 应的方案分枝，并将EV8的数据填入决策点 V4，即令EV4EV895（万元）。 状态结点V3的期望效益值为 EV3(-100)0.1+00.5+1000.430（万元 ）。 所以，状态结点V1的期望效益值为 EV1=300.2+950.8=82(万元)。 状态结点V9的期望效益值为 EV9(-200)0.1+00.5+2000.460（ 万元）； 状态结点V10的期望效益值为 EV10(-300)0.1+(-250)0.5+6000.4 85（万元）。 由于EV10EV9，所以，剪掉状态结点V9对 应的方案分枝，将EV10的数据填入决策点V5。 即令EV5EV1085（万元）。 状态结点V6的期望效益值为 EV6(-100)0.1+00.5+1000.430（万元 ）， 所以，状态结点V2期望效益值为 EV2=300.4+850.6=63(万元)。 由于EV1EV2, 所以，剪掉状态结点V2 对应的方案分枝将EV1的数据填入决策点EV ，即令 EVEV182（万元）。 综合以上期望效益值计算与剪枝过程可 知，该问题的决策方案应该是：首先采用购 买专利方案进行工艺改造，当购买专利改造 工艺成功后，再采用扩大生产规模（即增加 产量）方案进行生产。 四、灵敏度分析法 对于风险型决策问题，其各个方案的 期望益损值是在对状态概率预测的基础上 求得的。由于状态概率的预测会受到许多 不可控因素的影响，因而基于状态概率预 测结果的期望益损值也不可能同实际完全 一致，会产生一定的误差。 这样，就必须对可能产生的数据变动 是否会影响最佳决策方案的选择进行分析 ，这就是灵敏度分析。 n灵敏度分析 例5：某企业拟扩大产品产量，现有两种方案可供选 择：一是新建生产线；二是改造生产线。该企业管 理者经过研究，运用期望值决策法编制出决策分析 表（表9.2.4）。由于市场情况极其复杂，它受许多 不可控因素的影响，因而销售状态的概率可能会发 生变化。试针对这种情况，进行灵敏度分析。 表9.2.4 某企业扩大产品产量决策分析表 解:(1)以最大期望效益值为准则确定最佳方 案。 E(A1)maxE(A1),E(A2)=290万元， 所以，新建生产线（B1）为最佳方案。 (2)灵敏度分析。当考虑市场销售状态中 适销的概率由0.7变为0.3时，则两个方案的 期望效益值的变化为 E(B1)10万元， E(B2)20万元。 所以，在0.7与0.3之间一定存在一点P， 当适销状态的概率等于P时，新建生产线方案 与改造原生产线方案的期望效益值相等。P称 为转移概率 500P+(1-P)(-200)=300P+(1-P)(-100) P0.33 所以，当P0.33时，新建生产线（B1） 为最佳方案； 当P0.33时，改造原生产线方 案（B2）为最佳方案。 五、效用分析法 决策是由决策者自己做出的，决策者个 人的主观因素不能不对决策过程产生影响。如 果完全采用期望益损值作为决策准则，就会把 决策过程变成机械地计算期望益损值的过程， 而排除了决策者的作用，这当然是不科学的。 面对同一决策问题，不同的决策者对相同 的利益和损失的反应不同。即便是对于相同的 决策者，在不同的时期和情况下，这种反应也 不相同。这就是决策者的主观价值概念，即效 用值概念。 n画出效用曲线 将效用理论应用于决策过程的主要步骤: 以益损值为横坐标，以效用值为纵坐 标。规定：益损值的最大效用值为1，益 损值的最小效用值为0，其余数值可以采 用向决策者逐一提问的方式确定。 曲线A是保守型决策者的效用曲线， 不求大利，尽量避免风险，谨慎小心；曲 线C是风险型决策者的效用曲线，谋求大 利，不惧风险；曲线B是中间型决策者的 效用曲线。 n按效用值进行决策 找出每一个行动方案在不同状态下的益 损值的效用值； 计算各个行动方案的期望效用值； 选择期望效用值最大的方案作为最佳决策 方案。 可见，效用分析法对于方案的选择，不但 考虑了决策问题的客观情况，还考虑了决策者 的主观价值，即效用值，是一种更符合实际的 决策分析方法。效用函数（曲线），是对决策 问题进行效用分析的关键。 第3节 非确定型决策方法 乐观法 悲观法 折衷法 等可能性法 后悔值法 对于非确定型决策问题，不但状态 的 发生是随机的，而且各状态发生的概率也 是未知的和无法事先确定的。 对于这类问题的决策，主要取决于决 策者的素质、经验和决策风格 等，没有一 个完全固定的模式可循，对于同一个决策 问题，不同的决策者可能会采用不同的处 理方法。 几种比较常用的分析和处理非确定型 决策问题的方法如下： 一、乐观法 乐观法，又叫最大最大准则法，其 决策原则是“大中取大”。 乐观法的特点是，决策者持最乐观 的态度，决策时不放弃任何一个获得最 好结果的机会，愿意以承担一定风险的 代价去获得最大的利益。 假定某非确定型决策问题有m个方案B1，B2， Bm；有n个状态1，2，n。如果方案Bi（i=1，2， ，m）在状态j（j1，2，n）下的效益值为V（ Bi，j），则乐观法的决策步骤如下： 计算每一个方案在各状态下的最大效益值 V（Bi，j）； 计算各方案在各状态下的最大效益值的最大值 V（Bi，j）； 选择最佳决策方案。如果 V（Bi*，j*） V（Bi，j） 则Bi*为最佳决策方案。 例1：对于第9章第1节例1所描述的风险型决策问题 ，假设各天气状态发生的概率未知且无法预先估计 ，则这一问题就变成了表9.3.1所描述的非确定型决 策问题。试用乐观法对该非确定型决策问题求解。 表9.3.1 非确定型决策问题 解：（1） 计算每一个方案在各状态下的 最大收益值 =22（千元/hm2） =25（千元/hm2） =23（千元/hm2） =21（千元/hm2） （2）计算各方案在各状态下的最大效 益值的最大值 （3）选择最佳决策方案。因为 所以种小麦（B2）为最佳决策方案。 25（千元/hm2） 二、悲观法 悲观法，又叫最大最小准则法或瓦尔 德（Wold Becisia）准则法，其决策原则是 “小中取大”。 特点是决策者持最悲观的态度，他总 是把事情估计得很不利。 计算每一个方案在各状态下的最小效益 值 V（Bi，j）； 计算各方案在各状态下的最小效益值的 最大值 V（Bi，j）； 选择最佳决策方案。 如果V（Bi*，j*） V（Bi，j） 则：Bi*为最佳决策方案。 应用悲观法进行决策的步骤如下： 例2：试用悲观法对下表所描述的非确定型决策问题求解。 解：（1）计算每一个方案在各状态下的最小效益值 =10（千元/hm2） =8（千元/hm2） =11（千元/hm2） （2） 计算各方案在各状态下的最小效 益值的最大值 11.8（千元/hm2） 11.8（千元/hm2） （3）选择最佳决策方案。因为 所以种燕麦（B4）为最佳决策方案。 三、折衷法 乐观法按照最好的可能性选择决策方案， 悲观法按照最坏的可能性选择决策方案。 两者缺点：损失的信息过多，决策结果有 很大的片面性。 特点是既不非常乐观，也不非常悲观，而 是通过一个系数（01）表示决策者对客观 条件估计的乐观程度。 采用折衷法进行决策，在一定程度上可以 克服以上缺点。 计算每一个方案在各状态下的最大效益值 计算每一个方案在各状态下的最小效益值 计算每一个方案的折衷效益值 计算各方案的折衷效益值的最大值 ； 选择最佳决策方案。如果 ,则Bi*为 最佳决策方案。 应用折衷法进行决策的步骤： 例3：试用折衷法对下表所描述的非确定 型决策问题求解。 解：（1） 计算每一个方案在各状态下的最大 效益值 21（千元/hm2） 22（千元/hm2） =25（千元/hm2） =23（千元/hm2） （2）计算每一个方案在各状态下的最小效益值 11.8（千元/hm2） =10（千元/hm2） =8（千元/hm2） 11（千元/hm2） （3）计算每一个方案的折衷效益值（譬如取0.5） 0.521+0.511.816.4（千元/hm2） 0.522+0.51016（千元/hm2） 0.525+0.5816.5（千元/hm2） 0.523+0.51117（千元/hm2） （4）计算各方案的折衷效益值的最大值 17（千元/hm2） （5）选择最佳决策方案。由于 所以种大豆（B3）为最佳决策方案。 ， 四、等可能性法 等可能性法指在非确定型决策问题中，由于 状态发生的概率未知，所以假设各个状态发生的 概率是相等的。基于这种假设的决策方法称为等 可能性法 。 等可能性法求解非确定型决策问题的做法： 假设各个状态发生的概率相等，即P1P2 Pn； 计算各个方案的期望益损值，通过比较各 个方案的期望益损值，选择最佳决策方案。 例4：试用等可能性法对于下表所描述的 非确定型决策问题求解。 解：（1）假设“极旱年”，“旱年”，“平年”，“湿润 年”， “极湿年”各天气类型发生的概率相等 P1P2P3P4P51/5 （2）计算各方案的期望效益值 10+ 12.6+ 18+ 20+ 2216.52（千元/hm2） 25+ 21+ 17+ 12+ 816.6（千元/hm2） 12+ 17+ 23+ 17+ 1116（千元/hm2） 11.8+ 13+ 17+ 19+ 2116.36（千元/hm2） （3）选择最佳决策方案。因为 所以种小麦（B2）为最佳决策方案。 =16.6（千元/hm2） 五、后悔值法 对于一个实际的非确定型决策问题，当某一状 态出现后，就能很容易地知道哪个方案的效益最大 或损失最小。如果决策者在决策后感到后悔，遗憾 当时没有选准效益最大或损失最小的方案。为了避 免事后遗憾太大，可以采用后悔值法进行决策。 后悔值指某状态下的最大效益值与各方案的效 益值之差。 后悔值法决策的主要依据是后悔值。后悔值法 也称最小最大后增值法。 计算每一个状态下各方案的最大效益值 对于每一个状态下的各方案，计算其后悔值 对于每一个方案，计算其最大后悔值 ； 计算各方案的最大后悔值的最小值 ； 选择最佳决策方案。如果 ， 则Bi*为最佳决策方案。 应用后悔值法进行决策的步骤： 例5：试用后悔值法对下表所描述的非 确定型决策问题求解。 解：（1） 计算每一个状态下各方案的最 大效益值 25（千元/hm2） 21（千元/hm2） 23（千元/hm2） 20（千元/hm2） 22（千元/hm2） （2）对于每一个状态下的各方案，计 算其后悔值 V1125-1015（千元/hm2）； V2125-250（千元/hm2）； V3125-1213（千元/hm2）； V4125-11.813.2（千元/hm2）； V1221-12.68.4（千元/hm2）； V2221-210（千元/hm2）； V3221-174（千元/hm2）； V4221-138（千元/hm2）； V1323-185（千元/hm2）； V2323-176（千元/hm2）； V3323-230（千元/hm2）； V4323-176（千元/hm2）； V1420-200（千元/hm2）； V2420-128（千元/hm2）； V3420-173（千元/hm2）； V4420-191（千元/hm2）； V1522-220（千元/hm2）； V2522-814（千元/hm2）； V3522-1111（千元/hm2）； V4522-211（千元/hm2）。 （3）对于每一个方案，计算其最大后悔值 15（千元/hm2） 14（千元/hm2） 13（千元/hm2） 13.2（千元/hm2） (4) 计算各方案的最大后悔值的最小值 (5)选择最佳决策方案。因为 种大豆（B3）为最佳决策方案。 13（千元/hm2） ， 第10章 地理网络分析 对于许多现实的地理问题，譬如，城镇体 系问题、城市地域结构问题、交通问题、商业 网点布局问题、物流问题、管道运输问题、供 电与通讯线路问题等等，都可以运用网络分析 方法进行研究。 网络分析，是运筹学的一个重要分支，它 主要运用图论方法研究各类网络的结构及其优 化问题。 网络分析方法是计量地理学必不可少的重 要方法之一。 本章主要内容 地理网络的图论描述 最短路径与选址问题 最大流与最小费用流 第1节 地理网络的图论描述 地理网络的图论描述 地理网络的测度 通俗意义上的“图”，主要是指各种各样的地 图、遥感影像图，或者是由各种符号、文字代表的 示意图，或者是由各种地理数据绘制而成的曲线图 、直方图等等。 图论中的“图”，是一个数学概念，这种“图 ”能从数学本质上揭示地理实体与地理事物空间分 布格局，地理要素之间的相互联系以及它们在地域 空间上的运动形式、地理事件发生的先后顺序等 。 （1）图： 设V是一个由n个点vi (i=1，2， n)所组成的集合，即V=v1，v2，vn，E是一 个由m条线ei（i=1，2，m）所组成的集合， 即E=e1，e2，em，而且E中任意一条线，都 是以V中的点为端点；任意两条线除了端点外没有 其他的公共点。 一、地理网络的图论描述 （一）图的定义 那么，把V与E结合在一起就构成了一个图G ，记作G（V，E）。 （3）边：E中每一条线称为图G 的边（或弧） ；若一条边e连接u，v两个顶点，则记为e（u，v ）。 （2）顶点： V中的每一个点vi（i=1，2， ，n）称为图G的顶点。 （4）在图G（V，E）中，V不允许是空集， 但E可以是空集。 （5）从以上定义可以看出，图包含两个方面的 基本要素： 点集（或称顶点集）；边集（或称弧集 ）。 例：在如图10.1.1所示的图中，顶点集为 Vv1，v2 ，v3，v4，v5，v6，v7，v8，边集为Ee1，e2，e3， e4，e5，e6，e7，e8，e9，e10，e11 。 图10.1.1 （6）在现实地理系统中，对于地理位置、地理实 体、地理区域以及它们之间的相互联系，可以经过一 定的简化与抽象，将它们描述为图论意义下的地理网 络，即图。 地理位置、地理实体、地理区域，譬如，山顶、 河流汇聚点、车站、码头、村庄、城镇等点。 它们之间的相互联系，譬如，构造线、河流、交 通线、供电与通讯线路、人口流、物质流、资金流、 信息流、技术流等点与点的连线。 一个由基本流域单元组成的复杂的流域地貌系统 ，如果舍弃各种复杂的地貌形态，各条河流线， 河流分岔或汇聚处点，流域地貌系统水系的 基本结局（树）。 列昂纳德欧拉7桥问题 东普鲁士的哥尼斯堡城（现在的加里宁格勒 ）是建在两条河流的汇合处以及河中的两个小岛 上的，共有7座小桥将两个小岛及小岛与城市的其 他部分连接起来，那么，哥尼斯堡人从其住所出 发，能否恰好只经过每座小桥一次而返回原处？ 图论研究结果告诉我们，其答案是否定的。 （7）需要说明的是：图的定义只关注点之间是否连 通，而不关注点之间的连结方式。对于任何一个图，他 的画法并不唯一。 （二）图的一些相关概念 （1）无向图与有向图： 无向图图的每条边都没有给定方向， 即（u，v）（v，u）； 有向图图的每条边都给定了方向， 即（u，v）（v，u）。 一般将有向图的边集记为A，无向图的边集记 为E。这样，G=（V，A）就表示有向图，而G=（V ，E）则表示无向图。 有向图 （2）赋权图：如果图G（V，E）中的每 一条边（vi，vj）都相应地赋有一个数值wij， 则称G为赋权图，其中wij称为边（vi，vj）的权 值。 除了可以给图的边赋权外，也可以给图的 顶点赋权。这就是说，对于图G中的每一顶点 vj，也可以赋予一个载荷a(vj)。 （3）关联边：若e（u，v），则称u和v是 边e的端点，e是u和v的关联边。 （4）环：若e的两个端点相同，即uv，则称为 环。 （5）多重边：若连接两个端点的边多于一条以上 ，则称为多重边。 （6）多重图：含有多重边的图，称为多重图。 （7）简单图：无环、无多重边的图，称为简单图 。 （8）点与次。以点v为端点的边的个数称为点v的 次，记为d(v)。 次等于1的点称为悬挂点；与悬挂点关联的边称 为悬挂边。 次为零的点称为孤立点。次为奇数的点称为奇 点；次为偶数的点称为偶点。 （9）连通图。在图G中，若任何两点之间至少存 在一条路（对于有向图，则不考虑边的方向），则称 G为连通图，否则称为不连通图。 （10）路（链）：若图G（V，E）中，若顶 点与边交替出现的序列（对于有向图来说，要求 排在每一条边之前和之后的顶点分别是这条边的 起点和终点） Pvi1，ei1，vi2，ei2，eik-1，vik 满足 eit = (vit，vi，t+1) (t=1,2,k-1) 则称P为一条从vi1到vik的路（或链），简记为 Pvi1，vi2，vik。 （11）回路：若一条路的起点与终点相同，即 vi1=vik，则称它为回路。 （12）树：不含回路的连通的无向图称为树。 （13）基础图：从一个有向图D（V，A） 中去掉所有边上的箭头所得到的无向图，就称为 D的基础图，记之为G（D）。 （14）截：如果从图中移去边的一个集合将 增加亚图的数目时，被移去的边的集合就称为截 。 （15）子图：设G（V， E）是一个无向图 ，V1与E1分别是V与E的子集，即V1 V， E1 E。如果对于任意eiE1，其两个端点都属 于V1，则称G1（V1，E1）是图G的一个子图。 （16）支撑子图：设G1（V1，E1）是图G（V ，E）的一个子图，如果V1 V，则称G1是G 的支撑 子图。 （17）支撑树：设G（V，E）是一个无向图， 如果T（V1，E1）是G的支撑子图，并且T是树，则 称T是G 的一个支撑树。 （18）树的重量：一个树的所有边的权值之和称 为该树的重量。 （19）最小支撑树：在一个图的所有支撑树中， 重量最小的那个叫做该图的最小支撑树。 二、地理网络的测度 许多现实的地理问题，只要经过一定的简化和抽 象，就可以将它们描述为图论意义下的地理网络，点 和线的排布格局，并可以进一步定量化地测度它们的 拓扑结构，以及连通性和复杂性。 树状型 地理网络 平面网络（二维的）非平面网络（非二维的） 道路型 环状型 细胞型 图10.1.5 地理网络的拓扑分类 目前关于地理网络的拓扑研究，最多、最常 见的是基于平面图描述的二维平面网络。 所谓平面图，被规定为：各连线之间不能交 叉，而且每一条连线除顶点以外，不能再有其他 的公共点（牛文元，1987）。 以下的讨论，除非特别申明外，都限于二维 平面网络。 （一）关联矩阵与邻接矩阵 n关联矩阵 测度网络图中顶点与边的关联关系。 假设网络图G（V，E）的顶点集为V=v1，v2 ，vn，边集为E=e1，e2，em，则该网络图 的关联矩阵就是一个nm矩阵，可表示为 式中：gij为顶点vi与边ej相关联的次数。 v3 v1 v2 v4v5 e1 e2 e3 e4 e5 e6 e7 该图的关联矩阵为 例： n邻接矩阵 测度网络图中各顶点之间的连通性程度。 假设图G（V，E）的顶点集为V=v1，v2， ，vn，则邻接矩阵是一个n阶方阵，可表示为 式中：aij表示连接顶点vi与vj的边的数目。 该图的邻接矩阵为 v3 v1 v2 v4v5 e1 e2 e3 e4 e5 e6 e7 例： （二）有关测度指标 对于任何一个网络图，都存在着3种共同的 基础指标： 连线（边或弧）数目m； 结点（顶点）数目n； 网络中亚图的数目p。 由它们可以产生如下几个更为一般性的测度 指标： 指数、 回路数k、 指数、指数。 也称为线点率，是网络内每一个结点的平均 连线数目 =0，表示无网络存在；网络的复杂性增加， 则值也增大。 没有孤立点存在的网络，连线数目为n- p,则 指数为 n指数 如果地理网络不包含次级亚图 ，即P1， 则其最低限度连接的 指数值为 。 n回路数k 回路是一种闭合路径,它的始点同时也是终点 。 若网络内存在回路，则连线的数目就必须超 过n-p（最低限度连接网络的连接数目）。 回路数k为实际连线数目减去最低限度连接的 连线数目，即 n 指数 指数指实际回路数与网络内可能存在的最大 回路数之间的比率。 网络内可能存在的最大回路数目为连线的最大 可能数目减去最低限度连接的连线数目，即 所以， 指数为 指数也可以用百分率表示 对于非平面网络，其 指数为 指数的变化范围，一般介于0，1区间， 0意味着网络中不存在回路； 1，说明网络中 已达到最大限度的回路数目。 n指数 指数指网络内连线的实际数目与连线可能存 在的最大数目之间的比率，对于平面网络，其 计算公式为 指数也可以用百分比表示 指数是测度网络连通性的一种指标，其数 值变化范围为0，1。 0，表示网络内无连线，只有孤立点存在 ；1，则表示网络内每一个结点都存在与其他 它所有结点相连的连线。 对于非平面网络，指数的计算公式为 表10.1.1 几种简单网络图的有关测度指标 第2节 最短路径与选址问题 最短路径问题 选址问题 对于许多地理问题，当它们被抽 象为图论意义下的网络图时，问题的核 心就变成了网络图上的优化计算问题。 其中，最为常见的是关于路径和顶点的 优选计算问题。 在路径的优选计算问题中，最常见 的是最短路径问题；而在顶点的优选计 算问题中，最为常见的是中心点和中位 点选址问题。 n“纯距离”意义上的最短路径 例如，需要运送一批物资从一个城市到另 一个城市，选择什么样的运输路线距离最短？ n“经济距离”意义上的最短路径 例如，某公司在10大港口C1，C2， C10设有货栈，从Ci到Cj之间的直接航运价格， 是由市场动态决定的。如果两个港口之间无直 接通航路线，则通过第三个港口转运。那么， 各个港口之间最廉价的货运线路是什么？ 一、最短路径问题 （一）最短路径的含义 n “时间”意义上的最短路径 例如，某家经营公司有一批货物急需从一个 城市运往另一个城市，那么，在由公路、铁路、 河流航运、航空运输等4种运输方式和各个运输线 路所构成的交通网络中，究竟选择怎样的运输路 线最节省时间？ 以上3类问题，都可以抽象为同一类问题， 即赋权图上的最短路径问题。 不同意义下的距离都可以被抽象为网络图中 边的权值。 权这种权值既可以代表“纯距离 ”， 又可以代表“经济距离 ”，也可以代表“时间 距离 ”。 （二）最短路径的算法 n标号法 1959年E.W.Dijkstar 提出的标号法是最短路径 问题最好的求解方法 。 n标号法优点 不仅可以求出起点到终点的最短路径及其长度 ，而且可以求出起点到其他任何一个顶点的最短路 径及其长度；同时适用于求解有向图或无向图上的 最短路径问题。. n标号法的基本思想 设G是一个赋权有向图，即对于图中的每一条边， 都赋予了一个权值。在图G中指定两个顶点，确定为起 点和终点，不妨设v1为起点，vk为终点。 首先从v1开始，给每一个顶点标一个数，称为标 号。这些标号，又进一步区分为T标号和P标号两种类 型。其中，每一个顶点的T标号表示从起点v1到该点的 最短路径长度的上界，这种标号为临时标号；P标号表 示从v1到该点的最短路长度，这种标号为固定标号。 在最短路径计算过程中，对于已经得到P标号的顶 点，不再改变其标号；对于凡是没有标上P标号的顶点 ，先给它一个T标号；算法的每一步就是把顶点的T标 号逐步修改，将其变为P标号。 那么，最多经过k-1步，就可以求得到从起点v1到 每一个顶点的最短路径及其长度。 n标号法具体计算步骤 如果刚刚得到P标号的点是vi，那么，对于 所有这样的点 将其T标号修改为：minT(vj)，P(vi)+wij。 若G中没有T标号，则停止。否则，把点 的T标号修改为P标号，然后再转入。 其中， 满足 开始，先给v1标上P标号P(v1) 0，其余各 点标上T标号T(vj)+（j1）。 例1：在图10.2.1所示的赋权有向图中，每一个顶点vi （i=1，2，n）代表一个城镇；每一条边代表相 应两个城镇之间的交通线，其长度用边旁的数字表 示。试求城镇v1到v7之间的最短路径。 图10.2.1 赋权有向交通网络图 解：首先给v1标上P标号P(v1)=0，表示从v1到v1的最 短路径为零。其他点(v2，v3，v7)标上T标号T(vj) +（j2，3，7）。 第1步： v1是刚得到P标号的点。因为(v1，v2) ，(v1，v3)，(v1，v4)E，而且v2，v3，v4是T标号，所 以修改这3个点的T标号为 T(v2)minT(v2)，P(v1)+w12min +，0+22 T(v3)minT(v3)，P(v1)+w13 min +，0+55 T(v4)minT(v4)，P(v1)+w14 min +，0+33 在所有T标号中，T(V2)2最小，于是令P(V2)2。 第2步： v2是刚得到P标号的点。因为(v2，v3)， (v2，v6)E，而且v3, v6是T标号，故修改v3和v6的T标 号为 T(v3)minT(v3)，P(v2)+w23min5，2+24 T(v6)minT(v6)，P(v2)+w26min+，2+79 在所有的T标号中，T(v4)3最小，于是令P(v4)3。 第3步： v4是刚得到P标号的点。因为(v4，v5)E， 而且v5是T标号，故修改v5的T标号为 T(v5)minT(v5)，P(v4)+w45min+，3+58 在所有的T标号中，T(v3)4最小，故令P(v3)4。 第4步： v3是刚得到P标号的点。因为(v3，v5)， (v3，v6)E，而且v5和v6为T标号，故修改v5和v6的T标 号为 T(v5)minT(v5)，P(v3)+w35min8，4+37 T(v6)minT(v6)，P(v3)+w36min9，4+59 在所有的T标号中，T(v5)7最小，故令 P(v5)7。 第5步： v5是刚得到P标号的点。因为(v5，v6) ，(v5 ，v7)E，而且v6和v7都是T标号，故修改它们 的T标号为 T(v6)minT(v6)，P(v5)+w56min9，7+1= 8 T(v7)minT(v7)，P(v5)+w57min+，7+7=14 在所有T标号中，T(v6)8最小，于是令： P(v6)8。 第6步： v6是刚得到P标号的点。因为(v6，v7)E ，而且v7为T标号，故修改它的T标号为 T(v7)minT(v7)，P(v6)+w67min14，8+5=13 目前只有v7是T标号，故令：P(v7)13。 从城镇v1到v7之间的最短路径为(v1，v2，v3，v5，v6 ，v7)，最短路径长度为13。 二、选址问题 选址问题，是现代地理学研究的主要问题之一 。选址问题涉及人类生产、生活、文化、娱乐等各 个方面。 选址问题的数学模型取决于两个方面的条件 ： 可供选址的范围、条件；怎样判定选址的质量。 本节的讨论仅限于选址的范围是一个地理网络 ，而且选址位置位于网络图的某一个或几个顶点上 。 对这样的选址问题，根据其选址的质量判据， 可以将其归纳为求网络图的中心点与中位点两类问 题。 （一）中心点选址问题 例：某县要在其所辖的6个乡镇之一修建一 个消防站，为6个乡镇服务，要求消防站至 最远乡镇的距离达到最小。 n中心点选址问题的质量判据 使最佳选址位置所在的顶点的最大服务 距离为最小。 中心点选址问题适宜于医院、消防站点 等一类服务设施的布局问题。 设G（V，E）是一个无向简单连通赋权图，连 接两个顶点的边的权值代表它们之间的距离，对于每 一个顶点vi，它与各个顶点之间的最短路径长度为di1 ，di2，din。这些距离中的最大数称为顶点vi的最 大服务距离，记为e(vi)。 那么，中心点选址问题，就是求网络图G的中心 点 ，使得 n中心点选址问题的数学描述 例2：假设某县下属的6个乡镇及其之间公路联系如 图所示。每一顶点代表一个乡镇；每一条边代表连 接两个乡镇之间的公路，每一条边旁的数字代表该 条公路的长度。现在要设立一个消防站，为全县的 6个乡镇服务。试问该消防站应该设在哪一个乡镇 （顶点）？ 图10.2.2 解：第1步：用标号法求出每一个顶点vi至其他 各个顶点vj的最短路径长度dij（i，j 1，2， ，6），并将它们写成如下的距离矩阵 第2步：求每一个顶点的最大服务距离。显然，它们 分别是矩阵D中各行的最大值，即： e(v1)6，e(v2)7， e(v3)6，e(v4)7，e(v5)6，e(v6)7。 第3步：判定。因为e(v1)e(v3)e(v5)mine(vi)6 ，所以v1，v3，v5都是中心点。也就是说，消防站设在 v1，v3，v5中任何一个顶点上都是可行的。 n中位点选址问题的质量判据 使最佳选址位置所在的顶点到网络图中 其他各个顶点的最短路径距离的总和（或者 以各个顶点的载荷加权求和）达到最小。 （二）中位点选址问题 n