Acknowledgements

I am very grateful to Ron Johnston and Doug Watts for comments on the first draft and to a CATMOG referee for comments on the penultimate draft.

Permission to reproduce Tables 7-12 was kindly given by professor J.M. Henderson and the Harvard University Press.

INTRODUCTION

(i) The conceptual framework

In this booklet the transportation problem of linear programming is introduced. An understanding of the objectives and procedures can be gained using the most elementary algebra and arithmetic. The validity of the procedures can be demonstrated mathematically but this booklet does not attempt such a demonstration.

The central concept of linear programming is that of optimisation. This is a fairly common concept in every day life as most individuals and organisations will, from time to time, ask “what is the best method (the optimal method) by which we can achieve our ends?”. But in every day life the answer will often be “it all depends upon what you mean by 'best'”. The answer to this query will vary : for some individuals the 'best' method means the method which involves achieving a stated target with least effort, least time or least cost. For example a gardener might specify the amount of vegetables he wishes to grow and ask how can I arrange my garden to achieve this with minimum effort. Such people optimise by attempting to minimise a specified quantity. On the other hand some people may start from a different angle: “We have this limited garden plot, how can we choose a mix of vegetables to give us a maximum yield?”. This maximum must again be defined : in terms of food (maximum calories?), in terms of value (maximum cash value of the produce?) or in terms of net value (cash value after costs have been subtract ed). But once such a definition has been made the gardener is clearly a maximiser. Of course in some circumstances the maximisation of one quantity is in effect the minimisation of another, a point to which discussion will return in section III below.

Clearly, in everyday life, most people who ask optimising questions are implicitly assuming certain rules which they will not break. For example a car driver who wants to know the quickest route between two places may (or may not) be tacitly assuming that he will obey speed limits; a less law abiding individual may, on the other hand, be constrained by the top speed of his car. Similarly the man who seeks advice on maximising the food yield of his vegetable garden may be implicitly saying “But I cannot give it more than 10 hours work a weeki”: he is placing a constraint on the type of solution which he will accept. This therefore introduces the concept of optimisation subject to constraints as an everyday concept. The task of linear programming is to define the quantity to be maximised (or minimised) exactly, to state the relevant constraints and then to identify a procedure by which the optimal solution can be identified.

Although some optimising problems are capable of direct mathematical solution many of them are not so soluble. It would of course be possible, although extremely tedious to identify all feasible solutions and then to calculate which is the optimum. By feasible is implied a solution which meets all the constraints specified. The number of feasible solutions is often so large that such a procedure is unsatisfactory. Linear programming provides a fairly rapid trial and error method of search characterised by the following features:

  1. the method starts from a feasible solution and progresses towards an optimal solution,
  2. the method arrives at an optimal solution, and
  3. it is clear when an optimal solution has been reached.

A search procedure of this kind, which involves the same steps repeated many times is known as iteration or iterative solution of the problem. In some cases iteration is the only method of solution: in other cases a direct solution would be possible but iteration proves to be more convenient. Many iterative procedures are ideally suited to computer operations.

(ii) Linear programming defined

The phrase 'linear programming' covers a group of techniques for achieving optimal solutions to allocation problems. One of the results of linear programming studies has been to demonstrate the mathematical similarity of what are at first sight extremely dissimilar problems. This booklet focuses upon one aspect of linear programming only - the so called transportation problem - because its solution has proved to have wide relevance in studies of optimal spatial allocation. It should be noted however that linear programming has also been used to study other types of allocation problem including the optimal allocation of land and labour in agricultural systems. The most widely used method of solution for these problems is the so-called simplex method of linear programming. Several of the references introduce these wider aspects of linear programming (Abler et al. 1971, Vajda 1960).

In addition there is the field known as recursive linear programming. Readers interested in that field and its application to geographic problems like von Thunen's land use model should refer to the work of Day and Tinney (1969).

THE TRANSPORTATION PROBLEM

(i) The basic transportation problem

Consider a situation in which three points of origin (\( A_1, A_2, A_3 \)) have supplies available to meet needs at three destinations (\( N_1, N_2, N_3 \)). The amounts available at each of the origins are specified (\( a_1, a_2, a_3 \)) as also are the amounts needed at each of the destinations (\( n_1, n_2, n_3 \)). Furthermore the costs of moving goods between origins and destinations can be set up as a table of \( m_{ij} \)'s where the subscripts indicate the cell giving the cost of moving from the ith to the jth destination: so, for example, \( m_{32} \) is the cost of moving goods from \( A_3 \) to \( N_2 \). In a real life problem these quantities must be written in specific units: the supplies available and the needs might be in tonnes, or even in thousands of tonnes; the movement costs would then be in cost units per tonne, for example £/tonne. Suppose now an individual operator is seeking to supply these needs from thee suppliers at a minimum cost.

Table 1. The transport problem

Origins \( N_1 \) \( N_2 \) \( N_3 \) Amount
\( A_1 \) \( m_{11} \) \( m_{12} \) \( m_{13} \) \( a_1 \)
\( A_2 \) \( m_{21} \) \( m_{22} \) \( m_{23} \) \( a_2 \)
\( A_3 \) \( m_{31} \) \( m_{32} \) \( m_{33} \) \( a_3 \)
needed (\( n_i \)) \( n_1 \) \( n_2 \) \( n_3 \)

The linear programming problem is to find the optimal (least cost) method of supplying \( N_1 \), \( N_2 \) and \( N_3 \) from \( A_1 \) to \( A_3 \). We are seeking a pattern of flows (\( f_{ij} \)'s) where \( f_{ij} \) is the flow between the ith origin to the jth destination:

Table 2. The unknown flows in the transportation problem

Origins \( N_1 \) \( N_2 \) \( N_3 \) Amount
\( A_1 \) \( f_{11} \) \( f_{12} \) \( f_{13} \) \( a_1 \)
\( A_2 \) \( f_{21} \) \( f_{22} \) \( f_{23} \) \( a_2 \)
\( A_3 \) \( f_{31} \) \( f_{32} \) \( f_{33} \) \( a_3 \)
needed (\( n_i \)) \( n_1 \) \( n_2 \) \( n_3 \)

Clearly for this Table to be 'sensible' the elements (\( f_{ij} \)) in each row should add up to the row total and the column values should add to the column totals. Finally, it is clear that any one \( f_ij \) may be positive or zero, but cannot be negative. These restrictions can be written as constraints on the linear programming problem which can now be specified. We are seeking a set of flows from the ith origin to the jth destination such that: \[ f_{11} + f_{12} + f_{13} = a_1 \\ f_{21} + f_{22} + f_{23} = a_2 \\ f_{31} + f_{32} + f_{33} = a_3 \]

This set of equations can be generalised (and made much more concise) using the following mathematical notation:

\[ \sum_j f_{ij} = a_i \mbox{ for all i} \]

Strictly the form should be \( \sum_{j=1}^{3} f_{ij} \) but \( \sum_j f_{ij} \) is used to simplify the text with the meaning “sum over all the j columns”.

and

\[ f_{11} + f_{21} + f_{31} = n_1 \\ f_{12} + f_{22} + f_{32} = n_2 \\ f_{13} + f_{23} + f_{33} = n_3 \] or

\[ \sum_i f_{ij} = n_j \mbox{ for all j} \]

and

\( a_1 + a_2 + a_3 = n_1 + n_2 + n_3 \) (or mor concisely \( \sum_i a_i = \sum_j n_j \)).

Furthermore the flows cannot be negative:

\[ f_{ij} \geq 0 \] so we now have four constraints.

The total transport cost is given by \[ \sum_i \sum_j f_{ij} m_{ij} \]

It is this grand sum which is to be minimised, subject to the constraints already noted. Clearly there are many possible allocations of the flows between the origins and destinations and to consider all of them in the search of the minimum would be very tedious.

(iii) A simple example

Consider now an example of the transportation problem where the values af the \( a_i \), \( n_j \) and \( m_{ij} \) cells are specified. In the original Catmog, these were entered only for display, here we use R notation

This information can be entered in R as a matric and two vectors:

m <- matrix(c(7, 8, 8, 11, 3, 5, 4, 2, 5), nrow = 3)
m  # the cost matrix 
##      [,1] [,2] [,3]
## [1,]    7   11    4
## [2,]    8    3    2
## [3,]    8    5    5

a <- c(30, 50, 20)
a  # the supply vector (a1 to a3)
## [1] 30 50 20
n <- c(60, 25, 15)
n  # the need vector (n1 to n3)
## [1] 60 25 15

A feasible solution to this problem can be identified as a first step. To do this there are a number of procedures; here we introduce the northwest corner rule. Take the cell \( f_{ij} \) (the “northwest” corner of the table): compare the values of \( a_1 \) and \( n_1 \) and take the lesser value (in this case 30). Now enter this value as \( f_{11} \).

Inspection makes it clear that all supplies, available at A, are now exhausted so \( f_{12} \) and \( f_{13} \) must be zero. Attention is now shifted to the unsatisfied needs of \( n_1 \); this unsatisfied need is for 30 units: the lesser of this and \( a_2 \) is therefore entered in cell $f_{21}, as 30 (as 30 is less than \( a_2 \) which equals 50). At this stage, the (incomplete) table is as follows.

\( N_1 \) \( N_2 \) \( N_3 \) a
\( A_1 \) 30 0 0 30
\( A_2 \) 30 50
\( A_3 \) 0 20
n 60 25 15

Having made up the table thus far attention is paid to the allocation of the 20 units still available at \( A_2 \): these can be allocated to \( N_2 \) (using the 'lesser' criterion again). Readers should continue the procedure untill all cells have values. The result should be:

\( N_1 \) \( N_2 \) \( N_3 \) a
\( A_1 \) 30 0 0 30
\( A_1 \) 30 20 0 50
\( A_1 \) 0 5 15 20
60 25 15

In R, this can be represented as follows:

# entering data, column by column
s1 <- matrix(c(30, 30, 0, 0, 20, 5, 0, 0, 15), nrow = 3)

Finally it is worthwhile to note that this solution is indeed feasible by checking that it meets the four constraints:

\[ f_{ij} \geq 0 \]

\[ \sum_j f_{ij} = a_i \mbox{ for all i} \]

\[ \sum_i f_{ij} = n_j \mbox{ for all j} \]

\[ \sum_i a_i = \sum_j n_j \] Readers should do this for themselves, before running the R code below that tests these assumptions on their own computers.

s1 >= 0  # are all solution 1's cells greater than or equal to 0?
##      [,1] [,2] [,3]
## [1,] TRUE TRUE TRUE
## [2,] TRUE TRUE TRUE
## [3,] TRUE TRUE TRUE

apply(s1, 1, sum) == a
## [1] TRUE TRUE TRUE
# equivalent to rowSums(s1) == a

apply(s1, 2, sum) == n
## [1] TRUE TRUE TRUE
# equivalent to colSums(s1) == a

sum(a)
## [1] 100
sum(n)
## [1] 100

Knowing that the constraints have been met, the next step is to procede to calculate the total costs of transportation, based on the equation in the previous section:

# Cost of each origin-destination flow cell
cbind(as.vector(s1), as.vector(m), as.vector(s1 * m))
##       [,1] [,2] [,3]
##  [1,]   30    7  210
##  [2,]   30    8  240
##  [3,]    0    8    0
##  [4,]    0   11    0
##  [5,]   20    3   60
##  [6,]    5    5   25
##  [7,]    0    4    0
##  [8,]    0    2    0
##  [9,]   15    5   75
sum(s1 * m)
## [1] 610

The next stage is to ask whether this is an optimal solution. This is done by introducing the device of 'shadow prices'. These can be conceived of as being the relative price of the commodity at the various origin and destination locations, relative that is to an arbitrarily chosen 'bench mark' or 'datum level'. For example we might set the datum level as being the value of the commodity at \( A_1 \), arbitrarily set to 0. There is in this case a flow from \( A_1 \) to \( N_1 \): the cost is known to be 7 units. The costs of the goods delivered to \( N_2 \) will thus be the cost at \( A_1 \) plus the cost of movement, in this case 0 + 7. If the cost of goods at \( N_1 \) is 7 it tells us that the cost at \( A_2 \) must have been less than at \( A_1 \): i.e. to make the value at \( N_1 \) equate to 7, after 8 transport cost units the value at \( A_2 \) must be -1. This reasoning is represented algebraically as follow. Each origin has a shadow price \( u_i \) and each destination has a shadow price \( v_j \) such that \( v_j - u_i = m_{ij} \); for all occupied cells in the first solution. For example, the cell \( f_{21} \) is occupied: \( u_2 = -1 \), \( v_1 = 7 \), \( m_{ij} \) = 8. This rule can be used to produce the following patter - which the reader should check by calculation.

m
##      [,1] [,2] [,3]
## [1,]    7   11    4
## [2,]    8    3    2
## [3,]    8    5    5

s1bin <- matrix(as.numeric(s1 > 0), nrow = 3)
s1bin  # binary variable of non-empty cells
##      [,1] [,2] [,3]
## [1,]    1    0    0
## [2,]    1    1    0
## [3,]    0    1    1