《王法辉基于gis的数量方法与运用chapter》由会员分享，可在线阅读，更多相关《王法辉基于gis的数量方法与运用chapter（33页珍藏版）》请在金锄头文库上搜索。
1、 1 第十章第十章第十章第十章 线性规划及其在浪费性通勤测算和医疗服务区线性规划及其在浪费性通勤测算和医疗服务区线性规划及其在浪费性通勤测算和医疗服务区线性规划及其在浪费性通勤测算和医疗服务区位优化中的应用位优化中的应用位优化中的应用位优化中的应用 线性规划(Linear Programming或简称LP)是一种优化分析技术，在社会经济分析与规划中 的应用很广。线性规划就是在一组约束条件下，寻找目标函数的最大值或最小值，由于目标 函数和约束条件都是线性函数，故称线性规划。很显然，有关线性规划的问题远不是一个章 节能尽述的，在许多大学的地理系、规划系或其它相关的科系，一般都有一门或几门课程来 讲
2、授线性规划。本章重点讲解线性规划的建模，以及如何利用SAS与ArcGIS这两个软件包来 求解有关的线性规划问题。 本章共分5节。第10.1节复习一下线性规划的基本模型和单纯形解法。第10.2节以城市 交通中浪费性通勤的测算为例，讲解一般线性规划（不涉及整数线性规划）的具体应用。选 用通勤这个主题来讲解线性规划方法的应用，具有重要意义。通勤是城市研究的一个重要主 题，是联系城市居民点和就业地的桥梁，与城市结构和土地利用等理论问题关系密切。同时 ，通勤又反映居民上下班的方便程度，优化通勤与环境保护、设计建造高效能城市等有关公 共政策的制定也有重要的参考价值。查阅目前关于通勤研究的文献，已不单单局限
3、于浪费性 通勤，而是涉及到通勤与城市土地利用之间的关系、城市内部通勤差异的解释、通勤对“空间 错位（spatial mismatch）”和就业便捷性的意义等诸多方面。然而，回顾我们对通勤问题的研 究兴趣，很大程度上要归功于哈米尔顿（Hamilton，1982）早年提出的浪费性通勤问题。第 10.2节以美国俄亥俄州哥伦布都市区为例，讲解浪费性通勤的测算方法，同时演示如何用 SAS来求解一般线性规划问题。 第10.3节介绍整数线性规划。整数线性规划不同于一般线性规划的是，有些决策变量要 求是整数。区位优化（location-allocation）中的一些著名问题，如p-中位问题（p-median
4、problem）、最少服务点问题（location set covering problem 或简称LSCP）和最大服务面问题 （maximum covering location problem 或简称MCLP）等，都是整数线性规划的例子。无论在 社会公众服务部门，还是在私营企业部门，区位优化模型都有十分广泛的用途。第10.4节用 189 2 俄亥俄州凯霍加县医疗服务规划中的一个案例，讲解如何利用ArcGIS进行区位优化分析。 第10.5节为本章总结。 10.1线性规划与单线性规划与单线性规划与单线性规划与单纯形法纯形法纯形法纯形法 10.1.1 线性规划标准型线性规划标准型线性规划标准型线
5、性规划标准型 标准的线性规划问题可以概括为： 求 = n j jjx c 1 的最大值，其中所有n个变量x1，x2，xn为非负（也就是 0 j x ， ,.,2 , 1nj ），而且满足m个约束条件 = n j ijij bxa 1 （其中 ,.,2 , 1mi ）。 上述问题中的 = n j jjx c 1 为目标函数，任务就是寻找满足约束条件的最优解xj （其中 ,.,2 , 1nj ）。 用矩阵形式，线性规划问题可以描述为： 给定 n Rc， m Rb， nm RA，在满足 bAx 和 0x 的约束条件下，求xc T 的最大值。 由于线性规划问题完全由A，b，c三个矩阵参数所决定，因此，
6、可以简洁地概括为（A, b, c）问题。对于不是标准型的线性规划问题，可以通过以下变换规则转变成标准型（Kincaid and Cheney，1991，648页）： 1 求 xc T 的最小值等同于求 xc T 的最大值。 2 约束条件 = n j ijij bxa 1 等同于 = n j ijij bxa 1 。 190 3 3 约束条件 = = n j ijij bxa 1 等同于 = n j ijij bxa 1 , = n j ijij bxa 1 。 4 约束条件 = n j ijij bxa 1 | 等同于 = n j ijij bxa 1 , = n j ijij bxa 1 。
7、 5 如果xj为负数，则用两个非负变量来代替，如 jjj vux= 。 10.1.2 单纯形法单纯形法单纯形法单纯形法（Simplex Algorithm） 单纯形法（Dantzig, 1948）在线性规划问题的求解中广为使用。这里不讨论单纯形法的理 论和证明，只是通过一个简单的实例来直接讲述单纯形法的具体步骤。 让我们看下面这个线性规划问题，已写成标准型。如果线性规划问题不是用标准型表达 的，需要在用单纯形法之前，根据前面所述的规则先将它变为标准型。 求21 54xxz+= 的最大值 约束条件为： 122 21 + xx 2054 21 +xx 153 21 + xx 0, 0 21 xx
8、单纯形法的第一步是将不等式变为等式，具体方法是引入松驰变量 0u ，将约束条件中 的不等式 bAx 转化为等式 buAx=+ 。 对于上面例子，引入三个松驰变量 （ 0, 0, 0 543 xxx ），这样原先的线性规划问 题可以写成下面的形式： 求 54321 00054xxxxxz+= 的最大值 约束条件为: 191 4 12002 54321 =+xxxxx 200054 54321 =+xxxxx 15003 54321 =+xxxxx 0, 0, 0, 0, 0 54321 xxxxx 单纯形法通常写成表格的形式。上述例子可改写为下述表格： 1510031 2001054 12001
9、12 00054 其中最顶上一行是目标函数xc T 的系数，接下来的m行是约束条件。顶行最右上角的空白项 就是待求目标函数z的最大值。这样，单纯形法的通用表格式就是： bIA 0cT 一般情况下，如果线性规划问题有解，其解可以通过单纯形法求得；如果没有 解（如线性规划问题无边界），则在单纯形法的算法过程中就可以发现这个问题。 如果变量x1 、x2取值为0，初始解（x1 = 0, x2 = 0, x3 = 12, x4 = 20, x5 =15）显然满足约束 条件。定义xj值为0的变量为非基变量，而余下的、通常不为0的变量为基变量。单纯形表 格中有n个非基变量和m个基变量，分别对应着初始变量和松
10、驰变量的个数。上述例子中， x1 、 x2 为初始的非基变量 （n = 2）, x3、 x4 、 x5为基变量 （m = 3）。在表中的约束条 件中，每个基变量只出现在一行中，而目标函数都是由非基变量来表示的。 在单纯形法的每一步变换中，我们通过将一个非基变量转变为基变量的方法来逐步增加 目标函数的值，最终达到求解的目的。由于在线性方程组中行变换不会影响方程组的解，因 此，可以通过矩阵变换中的高斯消去法来完成相关的变换。单纯形法的流程如下： 192 5 1 选择目标函数中最大正系数的变量xs为新的基变量，即 0max= is cc 。 2 在每一行中，用本行中bi除以基变量的系数aij。在 0
11、 is a 的行中，选择其中最小的 iji ab/ ，把这个值定为该基变量的解，也就是， /min/ ijikjks ababx= 。如果所 有的ais都小于或等于0，则线性规划无解。 3 以aks为轴项，利用高斯消去法在s列上产生系数为0的项，即保持第k行不变，用 其它的行来减它。 4 如果目标函数（顶行）中的所有系数都小于或等于0，则当前x就是线性规划的解； 否则，继续进行转换。 针对上述例子，以上四个步骤具体操作如下。 在第一步中，由于目标函数中系数最大的正值是5，所以x2成为新的基变量。 在第二步中， a22被选定为轴项（下表中加有下划线），因为20/5在12/1, 20/5, 15/
12、3中 是最小的，基变量的解x2 = 20/5 = 4。 53333. 00013333. 0 402 . 0018 . 0 1200112 00018 . 0 在第三步中，采用高斯消去法产生一个新的表（用其它的行减轴项所在的行）: 13333. 02 . 0001333. 1 402 . 0018 . 0 802 . 0108 . 2 02 . 0006 . 1 参照单纯形法流程的第四步，由于顶行中的系数c1 = 1.6 0，没有达到所有系数都小于或 等于0的要求，因此，继续进行变换。 类似的，x1 成为新的基变量，确定a13为轴项（因为1/1.133 0 ，对每一个(i = 1, 2, ,
13、n) 和每一个 (j = 1, 2, , m) 式中 cij 是表示从居住地i到就业地j的通勤距离或时间，xij表示这个方向上的通勤人数。 目标函数是城市通勤的总量，第一个约束条件定义了从每个居住地到各个就业地的通勤 194 8 人数不能超过该居住地的上班人数，第二个约束条件定义了从不同的居住地到每个就业地 的通勤人数不能超过该就业地总的上班人数。在美国的大都市区内，按就业地统计的总上班 人数一般超过按居住地统计的总上班人数，即 = m j j n i i EP 11 ，也就是说，总体上看来，都 市区内就业岗位多于住在区内的人口，有一部分人住在都市区外、而到都市区内来上班。 10.2.2 Ar
14、cGIS上的数据准备上的数据准备上的数据准备上的数据准备 在光盘中提供的相关数据集有： 1. 图层urbtazpt 包含1990年哥伦布大都区内城市化地区的991个地域单元（TAZ ）; 2. 图层 road 包含研究区的路网。 上述空间数据集来自于美国人口普查局1990年的TIGER文档，参见第一章第1.2节有关 TIGER文档的介绍。哥伦布大都市区包括七个县（Franklin, Union, Delaware, Licking, Fairfield, Pickaway和 Madison），先将这七个县的交通分析区 （Traffic Analysis Zone或称TAZ）的资 料合并，再选取
15、其中城市化地区形成图层urbtazpt。TAZ是美国人口普查局在各都市区规 划委员会的协作下，专门为交通规划设计的一级地域单元。TIGER文档对每个TAZ（象普查 街区census block一样）都明确标注是否已城市化。由于我们关心的是城市内部的通勤问题， 所以，研究区是由都市区内所有城市化的TAZ合并而成的。这里所定义的城市化区，大体相 当于中国的城市建成区，如图10.1所示。参见有关文献（Wang，2001b），其通勤方面的研 究也是用的同一研究区。同样地，路网图层 road也是通过合并研究区内各县道路网络而成 ，为了保持路网的连通性，此图层的地域范围要稍大于都市区城市化的范围。在urb
16、tazpt 图层属性表中，emp项代表每个TAZ作为就业地的上班人数，work项代表每个TAZ作为居 住地的上班人数，同时为便于参考，popu项列出了TAZ中总人口数。这些数据来自于1990 年的CTPP数据集（参见第三章第3.5节的有关论述），从CTPP的第一部分中抽取了居住地 195 9 的上班人数和人口总数，从CTPP的第二部分中抽取了就业地的上班人数。 图层urbtazpt的属性项emp和work定义了每个TAZ区中按居住地（通勤的起点） 和就业地（通勤的终点）而统计的上班人数，对应于上述线性规划模型中的两组变量Pi （i = 1, 2, , n）和 Ej （j = 1, 2, , m）。接下来需要通过路网来计算通勤时间cij。第二章曾讨论 过有关路网距离和时间的概念和量算方法，正好通过这个案例再熟悉一下。读者
