| |
A mathematical tool for seeking optimal solutions to location problems, devised to identify optimal configurations for whole systems in terms of an objective function to be maximized (i.e. a goal to be achieved), subject to constraints. The methods of solution are iterative, converging on the optimum by a series of adjustments from an initial, feasible, solution.
The first task is to define the objective function. In economic studies this is usually stated in monetary terms — such as maximizing revenue or minimizing costs — but other quantities may be defined, such as minimizing the total distance travelled to schools from their homes by pupils, minimizing the average distance from a fire station to any potential site of a fire, or maximizing the food output from a farm.
The second step involves setting the constraints. These may be either equalities, such as the number of pupils allocated to each school is equal to the number of places there, or inequalities, such as the number of pupils allocated to a school shall be equal to, or less than, the number of places there. It is assumed that the production functions involved are linear: e.g. that the total amount of travel by the pupils is a function of the number of pupils and the distance travelled.
{img src=show_image.php?name=bkhumgeofig37.gif }
linear programming The graphical solution to a simple linear programming problem, showing the effect of constraints, the convex set of feasible solutions lying within the convex hull AXB\' and the optional solution at X
Simple linear programming problems can be solved graphically. A farmer, for example, may wish to maximize the cash return from two crops A and B (the objective function), subject to the constraints of the amount of land and labour available. The possible combinations of the two crops are plotted on the first graph in the figure, where the axes indicate the amounts of Aand B grown: they can vary through monoculture (i.e. only crop A is grown), through various mixes of A and B, to a further monoculture (i.e. only crop B is grown). The amount of land available means that all solutions above and to the right of the line joining A and B are not feasible, whereas any solution below and to the left is sub-optimal, since it does not use up all of the available land. The middle graph in the figure shows a similar analysis using the constraint of available labour. Superimposition of the two graphs (in the lower part of the figure) reveals that some solutions are infeasible because of land constraints whereas others result from labour supply constraints. The maximum yield is achieved with the combination of A and B at X (i.e. XA of crop A and XB of crop B). The line AXB′ is known as the convex hull and the area below it as the convex set: all solutions within the set are feasible; all those on the hull employ all of the land and labour resources.
More complex problems, with more than two constraints, have more sides to the hull, which means that solutions have to be found in multi-dimensional space, which is not possible graphically: they have to be approached either by using a simplex algorithm or by recasting the problem as a transportation problem.
Solution of such problems also produces what are known as shadow prices. The farmer might, for example, decide to reduce production of crop A below the optimum indicated, but there will be opportunity costs in so doing: income will be lost because of such sub-optimal behaviour (i.e. rent will be lost).
Linear programming was originally devised as an approach to solving management problems in, for example, resource allocation but has proved valuable in a wide range of geographical applications such as the planning of agricultural, transport, industrial and warehouse location, the delimitation of school districts and the siting of health-care facilities. Occasionally, linear programming has been used to evaluate the efficiency of actual location decisions — whether the pattern is the most efficient possible — usually with disappointing results: close matches are rarely found, suggesting that the objective functions and constraints applied by decision-makers are too complex to be modelled in this way. (AMH)
Suggested Reading Abler, R.F., Adams, J.S. and Gould, P.R. 1971: Spatial organization: the geographer\'s view of the world. Englewood Cliffs, NJ: Prentice Hall. Killen, J.E. 1979: Linear programming: the simplex method with geographical applications. Norwich: GeoBooks, CATMOG 24. Vajda, S. 1960: An introduction to linear programming and the theory of games. London: Methuen and New York: John Wiley. |
|
