Quantitative Methods and Applications in GIS - Chapter 10

10 Linear Programming and Applications in Examining Wasteful Commuting and Allocating Health Care Providers This chapter introduces linear programming (LP), an important optimization tech-nique in socioeconomic analysis and planning. LP seeks to maximize or minimize an objective function subject to a set of constraints. Both the objective and the constraints are expressed in linear functions. It would certainly take more than one chapter to cover all issues in LP, and many graduate programs in geography, planning, or other fields use a whole course or more to teach LP. This chapter discusses the basic concepts of LP and emphasizes how LP problems are solved in SAS and ArcGIS. Section 10.1 reviews the formulation of LP and the simplex method. The method is applied to examining the issue of wasteful commuting in Section 10.2. Commuting is an important research topic in urban studies for its theoretical linkage to urban structure and land use, as well as its implications in public policy. Themes in the recent literature of commuting have moved beyond the issue of wasteful commuting and cover a diverse set of issues, such as the relation between commuting and urban land use, explanation of intraurban commuting, and implications of commuting patterns in spatial mismatch and job access. However, strong research interests in commuting are, to some degree, attributable to the issue of wasteful commuting raised by Hamilton (1982). A case study in Columbus, OH, is used to illustrate the method of measuring wasteful commuting, and a SAS program is developed to solve the LP in the case study. Section 10.3 introduces integer linear programming (ILP), in which some of the decision variables in a linear programming problem take on only integer values. Some classic location-allocation problems, such as the p-median problem, the loca-tion set covering problem (LSCP), and the maximum covering location problem (MCLP), are used to illustrate the formulation of ILP problems. Applications of these location-allocation problems can be widely seen in both private and public sectors. Section 10.4 uses a hypothetical example of allocating health care providers in Cuyahoga County, Ohio, to illustrate the implementation of a location-allocation problem in ArcGIS. The chapter is concluded in Section 10.5 with a brief summary. 189 © 2006 by Taylor & Francis Group, LLC 190 Quantitative Methods and Applications in GIS 10.1 LINEAR PROGRAMMING (LP) AND THE SIMPLEX ALGORITHM 10.1.1 THE LP STANDARD FORM The linear programming (LP) problem in the standard form can be described as n n follows: find the maximum of cj xj subject to the constraints aij xj £ bi for all j=1 j=1 i ∈{1,2,...,m} and xj ³ 0 for all j ∈{1,2,...,n}. n The function cj xj is the objective function, and a solution xj ( j ∈{1,2,...,n}) j=1 is also called the optimal feasible point. In the matrix form, the problem is stated as follows: Let c ∈Rn , b ∈Rm , and A ∈Rm´n. Find the maximum of cT x subject to the constraints Ax £ b and x ³ 0. Since the problem is fully determined by the data A, b, c, it is referred to as problem (A, b, c).1 Other problems not in the standard form can be converted to it by the following transformations (Kincaid and Cheney, 1991, p. 648): 1. Minimizing cT x is equivalent to maximizing −cT x. n n 2. A constraint aij xj ³ bi is equivalent to − aij xj £ −bi. j=1 j=1 n n n 3. A constraint aij xj = bi is equivalent to aij xj £ bi, − aij xj £ −bi. j=1 j=1 j=1 n n n 4. A constraint |aijxj | £ b is equivalent to aij xj £ bi, − aij xj £ bi. j=1 j=1 j=1 5. If a variable xj can also be negative, it is replaced by the difference of two variables, such as xj = uj − vj . 10.1.2 THE SIMPLEX ALGORITHM The simplex algorithm (Dantzig, 1948) is widely used for solving linear program-ming problems. By skipping the theorems and proofs, we move directly to illustrate the method in an example. Consider a linear programming problem in the standard form: Maximize: Subject to: z = 4x1 + 5x2 2x1 + x2 £12 −4x1 + 5x2 £ 20 © 2006 by Taylor & Francis Group, LLC Linear Programming and Applications in Examining Wasteful Commuting 191 x1 + 3x2 £15 x1 ³ 0,x2 ³ 0 As the problem is not in the standard form, it needs to be converted to the form before the algorithm is applied. The simplex method begins with introducing slack variables u ³ 0 so that the constraints Ax £ b can be converted to an equation form Ax + u = b. For the above problem, three slack variables (x3 ³ 0,x4 ³ 0,x5 ³ 0) are intro-duced. The problem is rewritten as Maximize: Subject to: z = 4x1 + 5x2 + 0x3 + 0x4 + 0x5 2x1 + x2 + x3 + 0x4 + 0x5 = 12 −4x1 + 5x2 + 0x3 + x4 + 0x5 = 20 x1 + 3x2 + 0x3 + 0x4 + x5 = 15 x1 ³ 0,x2 ³ 0,x3 ³ 0,x4 ³ 0,x5 ³ 0 The simplex method is often accomplished by exhibiting the data in a tableau form, such as 4 5 0 0 0 2 1 1 0 0 12 −4 5 0 1 0 20 1 3 0 0 1 15 The top row contains coefficients in the objective function cT x. The next m rows represent the constraints that are reexpressed as a system of linear equations. We leave the element at the top-right corner blank, as the solution to the problem zmax is yet to be determined. The tableau is of a general form cT 0 A I b If the problem has a solution, it is found at a finite stage in the algorithm. If the problem does not have a solution (i.e., an unbounded problem), the fact is discovered in the course of the algorithm. The tableau is modified in successive steps according to certain rules until the solution (or no solution for an unbounded problem) is found. By assigning 0 to the original variables x1 and x2, the initial solution (x1 = 0, x2 = 0, x3 = 12, x4 = 20, x5 = 15) certainly satisfies the constraints of equations. The © 2006 by Taylor & Francis Group, LLC 192 Quantitative Methods and Applications in GIS variables xj that are zero are designated nonbasic variables, and the remaining ones, usually nonzero, are designated basic variables. The tableau has n components of nonbasic variables and m components of basic variables, corresponding to the num-ber of original and slack variables, respectively. In the example, x1 and x2 are the nonbasic variables (n = 2), and x3, x4, and x5 are the basic variables (m = 3). In the matrix that defines the constraints, each basic variable occurs in only one row, and the objective function must be expressed only in terms of nonbasic variables. In each step of the algorithm, we attempt to increase the objective function by converting a nonbasic variable to a basic variable. This is done through Gaussian elimination steps since elementary row operations on the system of equations do not alter the set of solutions. The following summarizes the work on any given tableau: 1. Select the variable x whose coefficient in the objective function is the largest positive number, i.e., cs = max{ci > 0}. This variable becomes the new basic variable. 2. Divide each b by the coefficient of the new basic variable in that row, a , and among those with a > 0 (for any i), select the minimum b / a and assign it to the new basic variable, i.e., xs = bk / akj = min{bi / aij}. If all ais are 0, the problem has no solution. 3. Using pivot element aks, create zeros in column s with Gaussian elimina-tion steps (i.e., keeping the kth row with the pivot element and subtracting it from other rows). 4. If all coefficients in the objective function (the top row) are £ 0, the current x is the solution. We now apply the procedures to the example. In step 1, x2 becomes the new basic variable because 5 (i.e., its coefficient in the objective function) is the largest positive coefficient. In step 2, a22 is identified as the pivot element (highlighted in underscore in the following tableau) because 20/5 is the minimum among {12/1, 20/5, 15/3} and x2 = 20/5 = 4. 0.8 1 0 0 2 1 1 0 −0.8 1 0 0.2 0.3333 1 0 0 0 0 12 0 4 0.3333 5 In step 3, Gaussian eliminations yield a new tableau: 1.6 0 0 −0.2 2.8 0 1 −0.2 −0.8 1 0 0.2 1.1333 0 0 −0.2 0 0 8 0 4 0.3333 1 According to step 4, the process continues as c1 = 1.6 > 0. © 2006 by Taylor & Francis Group, LLC Linear Programming and Applications in Examining Wasteful Commuting 193 Similarly, x1 is the new basic variable, a13 is the pivot element, x1 = 1/1.1333 = 0.8824, and the resulting new tableau is 0 0 0 0 0 0.3571 0 1.25 0 1 0 0 0.0515 0.1050 0.0735 −0.1765 −0.2941 −0.2941 1.9748 0.2941 5.8824 0.2941 0.8824 The process continues and generates a new tableau, such as 0 0 −3.4 0 0 0 3.4 1 0 17 −3.4 0 5.6667 0 3.4 0 −2.9143 −2.8 18.8 6.8 61.2 −1.1333 23.8 By now, all coefficients in the objective function (the top row) are £ 0, and the solution is x1 = 23.8/5.6667 = 4.2 and x2 = 61.2/17 = 3.6. The maximum value of the objective function is zmax = 4*4.2 + 5*3.6 = 34.8. Many software packages (some free) are available for solving LP problems.2 We select the LP procedure in SAS (available in the SAS/OR module) to illustrate the implementation of solving LP problems (see Section 10.2.3). SAS, already introduced in previous chapters, is a powerful package and is particularly convenient for coding large matrices. The LP procedure in SAS solves linear programs, integer programs, and mixed-integer problems. 10.2 CASE STUDY 10A: MEASURING WASTEFUL COMMUTING IN COLUMBUS, OHIO 10.2.1 THE ISSUE OF WASTEFUL COMMUTING AND MODEL FORMULATION The issue of wasteful commuting was first raised by Hamilton (1982). Assuming that residents can freely swap houses, the planning problem is to minimize total commuting given the locations of houses and jobs. Hamilton used the exponential function to capture the distribution patterns of both residents and employment. Since employment is more centralized than population (i.e., the employment density func-tion has a steeper gradient than the population density function), the solution to the problem is that commuters always travel toward the CBD and stop at the nearest employer. See Appendix 10A for details. Hamilton found 87% wasteful commuting in 14 U.S. cities. White (1988) proposed a simple LP model to measure wasteful commuting. White’s study yielded very little wasteful commuting, likely attributable to the large area unit she used (Small and Song, 1992). Using a smaller unit, Small and Song (1992) applied White’s LP approach to Los Angeles and found about 66% wasteful commuting, less than that in Hamilton’s model but still substantial. The following formulation follows White’s LP approach. © 2006 by Taylor & Francis Group, LLC ... - tailieumienphi.vn