CIT907 ADVANCED OPERATION RESEARCH
106
Saul I. Gass, Arjang A. Assad, An Annotated Timeline of Operations Research: An Informal History. New York, Kluwer Academic Publishers, 2005.
International Federation of Operational Research Societies https://www.ifors.org/
Saul I. Gass (Editor), Arjang A. Assad (2011), Profiles in Operations Research: Pioneers and Innovators. Springer
CIT907 ADVANCED OPERATION RESEARCH
107 3.0 MAIN CONTENT
3.1 Transportation Problems Defined
The typical transportation problem involves a number of sources of supply (e.g. factory) and a number of destinations (e.g. warehouses). A source or supply point is defined as having only outgoing flows. A destination or sink point is defined as having only incoming flows.
The capacities or demands are assumed to be real value as are the cost or profit coefficients.
The usual objective is to minimise the transportation cost of supplying quantities of a commodity from the source to the destination. The major requirement is that, there must be a constant transportation cost per unit. However, there are some situations when a transportation objective is to maximise. This will be discussed later.
3.2 The General Transportation Problem
The general form of a transportation problem for 'm' sources and 'n' destination can be represented as:
A generalised network model A transportation tableau A linear programming mode
. .
Transportation Tableau
Source
Destinati
on Supply
(si ) 1 2 3 ... n
1
c1 1
c1 2
c1
3 … c1n s1
x11 x1 2 x 13 x1n
CIT907 ADVANCED OPERATION RESEARCH
108
2 c21
c2
2 c23 … c2 n s2
x 21 x 22 x 23 x2n
3 c31
c3
2 c33 … c3n s3
x31 x32 x33 x3n
. . . . … . .
. . . . . .
. . . . . .
m
cm
1 cm2
cm
3 … cm n sm
xm1 xm 2 xm3 xm n
Deman d1 d 2 d3 … dn Total
d (di )
The above general transportation tableau has the following characteristics:
The sources are treated as rows and destination as column.
There are (m n) cells in the tableau.
The transportation cost, cij , from source 'i' to destination ' j' is recorded in the top right corner of each cell.
The supply from each source is listed in the last column on the right hand side.
The demand from each destination is recorded at the bottom row.
The xij variable in each cell represents the number of units of products transported from source 'i' to destination ' j' .
The lower right hand corner cell reflects the total supply and the total demand
x
ij 0 for all i,j
m N
si
d j (to indicate that transportation problem is balanced).i 1 j 1
However, it should be noted that for the type of algorithm to be described here; the tabular representation will be used.
3.3 Balanced Transportation Problem
This is when the total supply from all sources exactly equal total demand at all destination.
This type of problem is referred to as a balanced transportation problem. It is rare to observe a balanced transportation problem in reality. However, the analysis of a balanced problem is a good starting point to understand the transportation solution processes. See the table below:
CIT907 ADVANCED OPERATION RESEARCH
109 EXAMPLE 1
Consider the transportation problem with the following unit costs and capacities.
Source Destination Supply
A B C
1 5 1 6 200
2 8 4 3 350
3 7 9 5 170
Demand 200 300 200
From the table above, you will notice that the row total (i.e. supply) is exactly equal to the column total (i.e. demand), which is 720 units.
3.4 Unbalanced Transportation Problem
When the sum of the row requirement is not equal to the sum of the column requirements, the transportation problem is said to be unbalanced. There are two possibilities:
Over Production
If the sum of the row requirement (supply) is greater than the sum of the column requirements (demand), the production at the factories or sources exceeds the demand at the destination, warehouses or sinks and a condition of over production exists.
The transportation problem can be balanced by creating an artificial destination, warehouse or sink where the excess units are sent. This is equivalent to adding one column to the cost and distribution matrices.
This additional column is given a requirement equal to the difference between the sum of rows and column requirements.
For the purpose of this unit, the cost coefficients will be assumed to be all zeros. Their true values depend upon the situation at hand. However, they could have positive values equal to the cost of storing the excess inventory at each destination. For example, consider a problem with the following cost matrix with row and column requirements as an example of over production.
CIT907 ADVANCED OPERATION RESEARCH
110 EXAMPLE 2
Consider the transportation problem with the following unit costs and capacities.
Plant Warehouse Monthly
capacity
A B C
1 20 19 21 12200
2 19 22 18 2800
3 20 20 20 2500
4 21 20 19 2200
Monthly 7300 3500 5600 demand
The over production is 3300 units. With the addition of an artificial column (destination) called “Dummy”, the balanced transportation problem becomes:
Plant Warehouse Monthly
A B C Dummy capacity
1 20 19 21 0 12200
2 19 22 18 0 2800
3 20 20 20 0 2500
4 21 20 19 0 2200
Monthly 7300 3500 5600 3300
demand Under Production
When the sum of row requirements is less than the sum of column requirements, the demand at the destinations (sinks) exceeds the production at the factories (sources) and under production exists. To balance the problem, add an artificial factory (source) with a scheduled production equal to the unsatisfied demand. Again, for the purpose of this unit, the cost coefficients will be assumed to be all zeros. Their true values depend upon the situation at hand. The following is an example of under production with the cost matrix, row and column requirement.
EXAMPLE 3
Consider the transportation problem with the following unit costs and capacities.
Source Destination Supply
A B C D E
X 100 50 90 30 130 30000
Y 90 30 70 50 110 20000
Z 95 30 75 40 120 20000
Demand 10000 12000 15000 17000 25000
CIT907 ADVANCED OPERATION RESEARCH
111
The level of under production is 9000 units. To balance the problem, add an artificial row (factory, supply or source) with a scheduled production of 9000 units. The balanced transportation is:
Source Destination Supply
A B C D E
X 100 50 90 30 130 30000
Y 90 30 70 50 110 20000
Z 95 30 75 40 120 20000
Dummy 0 0 0 0 0 9000
Demand 10000 12000 15000 17000 25000 3.5 Method of Solution
As mentioned in the introduction, linear programming can be used to solve this type of problem. However, more efficient special purpose algorithm has been developed for the transportation application. As in the simplex algorithm, it involves finding an initial feasible solution and the making of step by step improvements until an optimal solution is reached.
Unlike the simplex method, the transportation methods are fairly simple in terms of computation. Here, we will take a look at the
following methods of solution which gives an initial feasible solution to transportation problem.
The methods are:
North-west corner method Least cost first method
Vogel‟s approximation method
While stepping stone method and the modify-improved method (MDI) are iterative techniques for moving from an initial feasible solution to an optimal solution, it must be mentioned however that before any of these methods can be applied, the transportation problem must be a balanced one.
North-west Corner Method
This method advocates that allocation should be made on the basis of geographical location of the cells in the tableau. In particular, the method attaches greater importance to the cell situated at the upper left hand corner of the tableau and makes as much as possible an allocation to the cell with both the supply restriction and demand constraint taking into consideration.
The algorithm for North-west corner methods are:
exhaust the supply (source) capacity at each row before moving down to the next row
exhaust the demand (destination) requirements of each column before moving to the right of the next column
continue in the same manner until all supply has been exhausted and demand requirements have been met.
CIT907 ADVANCED OPERATION RESEARCH
112 EXAMPLE 4
A firm has three factories in Lagos, Ibadan and Benin which make weekly dispatches to four depots located at Kaduna, Kano, Kebbi and Katsina. The transport cost per cost of goods dispatch along route is shown in the table below as well as the weekly quantities available from each factory and the requirement of each depot.
Transport Cost /Create
Storage
Demand
point Supply
capacity Kaduna Kano Kebbi Katsina
Lagos 5 4 5 6 100
Ibadan 3 3 6 6 200
Benin 2 5 7 8 400
Demand 200 100 150 250
How should the product be allocated to the depots? Use the North-west corner method for the initial allocation.
Solution
Using the procedure described above for the North-west corner method, the table below shows the initial allocation:
Storage Demand point Supply capacity
Kaduna Kano Kebbi Katsina
Lagos 4 6 100
5 5 100(1)
Ibadan 3 6 200
3 100(3) 6 100(2)
Benin 2 5 8 400
7 250(5)
150(4)
Demand 200
100
150 250
CIT907 ADVANCED OPERATION RESEARCH
113 Note
The numbers in the table represent deliveries and the numbers in the brackets (1) , (2) etc., represent the order of allocation (distribution). The numbers in the top right corner of each cell represent unit cost of transportation.
Transportation Cost for this Initial Allocation in using North-west Corner Method
Route Unit X Cost = Total
shipped per cost
unit (#)
From To (#)
=
Lagos Kaduna 100 X 5 500
Ibadan Kaduna 100 X 3 = 300
Ibadan Kano 100 X 3 = 300
Benin Kebbi 150 X 7 = 1050
Benin Katsina 250 x 8 = 2000
4150 The total cost from North-west corner method is #4,150 for the initial feasible solution.
Least Cost Method
The method advocates that allocation should be based on minimum cost of transportation rule /criterion. It says that the first allocation must be made to the cell with the most minimum cost of transportation per unit. In other words, we look at the schedule of the transport cell and identify the most minimal.
After identifying the cell with the least transportation cost, next we make maximum allocation to the cell without violating both supply and demand restriction. To demonstrate the use of least cost first method, consider the problem of Example 4.
Storage Demand point Supply capacity Kaduna Kano Kebbi Katsina
Lagos 5 4 5 6 100 100(3)
Ibadan 3 3 6 6 50 100(2) 50(4) 50(5)
Benin 2 5 7 8 400 200(1) 200(6)
Demand 200 0 50 250 The transportation cost for this initial allocation is:
Route Unit x Cost = Total cost
shipped per unit (#)
From To (#)
Benin Kaduna 200 x 2 = 400
CIT907 ADVANCED OPERATION RESEARCH
114
Ibadan Kano 100 x 3 = 300
Lagos Kebbi 100 x 5 = 500
Ibadan Kebbi 50 x 6 = 300
Ibadan Katsina 50 x 6 = 300
Benin Katsina 200 x 8 = 1600
3400
The total cost from least cost first method is #3,400 for the initial
feasible solution.
Note that allocation 5 can be before 4 and vice versa. So, for alternative solution, allocation 5 will be performed before.
Alternative Solution
Storage Demand point Supply Capacity Kaduna Kano Kebbi Katsina
Lagos 5 4 5 6 100 100(3)
Ibadan 3 3 6 6 50 100(2) 100(4)
Benin 2 5 7 8 150 200(1) 50(5) 150(6)
Demand 200 0 500 250 The transportation cost for this initial allocation is:
Route Unit X Cost = Total
shipped per Cost
unit (#)
From To (#)
Benin Kaduna 200 X 2 = 400
Ibadan Kano 100 X 3 = 300
Lagos Kebbi 100 X 5 = 500
Ibadan Katsina 100 X 6 = 600
Benin Kebbi 50 X 7 = 350
Benin Katsina 150 8 = 1200
3350 Vogel‟s Approximation Method
In his consideration, Vogel felt that rather than base allocation on least cost alone, the penalty or opportunity cost one will pay by taking a wrong decision would have been an additional criterion for allocation. Hence, he felt a combination of least cost and opportunity cost would be better for allocation purpose. Thus, he introduced the idea of row and column penalties or opportunity cost. The row or column penalty cost is computed by identifying the two (2) least costs in each row and each column and then find the difference.
CIT907 ADVANCED OPERATION RESEARCH
115
Whatever result that is obtained is taking as penalty for that row or column. If two costs in a row or column are tied for the rank of least cost, the penalty is zero.
The algorithms for Vogel‟s approximation are:
Determine the penalty for each row and column.
After the penalties have been calculated for all rows and columns, locate the greatest; whether a row or a column penalty and place the variable in the cell that has the least cost in the row or column with the greatest penalty. The value of the variable is set equal to the smaller of the row and column requirements corresponding to the variable being brought into the solution. The row or column whose requirement is satisfied is deleted from further consideration and the requirement of the other (row or column) is reduced by the value assigned to the variable entering the solution.
If a row requirement has been satisfied, the column penalties must be recomputed because the element of the cost matrix corresponding to the row deleted is no longer considered in the calculation of column penalties.
If a column requirement has been satisfied, the row penalties must be recomputed because the element of the cost matrix corresponding to the column deleted are no longer considered in the calculation of row penalties.
If a tie develops between two or more row or column penalties, select the least cost cell among these two or more rows and columns. If however, a further tie occurs among the least cost cell, then select arbitrarily (using good judgment) which among the tied cost cell will be used.
Repeat steps I through VI until the solution is completed.
Although, it cannot be proved mathematically that Vogel‟s method yields a near optimal solution frequently, the North-west corner method
and the least cost first method yield an initial solution which is far from optimal.
Application of this method will be demonstrated with the problem of Example 4.
EXAMPLE 6
Storage Demand points Supply Capacity Kaduna Kano Kebbi Katsina
Lagos 5 4 5 6 100
Ibadan 3 3 6 6 200
Benin 2 5 7 8 400
Demand 200 100 150 250 Solution
Cycle 1
CIT907 ADVANCED OPERATION RESEARCH
116
Step 1 Compute the row and column penalties on the cost matrix.
Storage Demand points Row
Penaltie s (200) (100) (150) (250) Kaduna Kano Kebbi Katsina
Lagos 5 4 5 6 1
(100)
Ibadan 3 3 6 6 0
(200)
3
Benin 2 5 7 8
(400)
Column 1 1 1 0 penalties
The greatest penalty is 3 (marked with arrow). This occurs in the 3rd row (i.e. Benin row).
Therefore, the first variable will be entered in the 3rd row of the cell with least cost in this row.
Step 2
With reference to the distribution table of cycle1, we assign a maximum value from row 3 (Benin) to column1(Kaduna). Here, demand is 200
units and supply is 400 units, so that maximum value is 200 units with excess supply of 200 units to be shipped to another destination.
Thus, we have:
Storage Demand points (0) (100) (150) (250) Kaduna Kano Kebbi Katsina
Lagos 5 4 5 6
(100)
Ibadan 3 3 6 6
(200)
Benin (1) 2 5 7 8
(200)
200
Note that Kaduna (i.e. column1) demand has been satisfied. Therefore, it is eliminated from further consideration. Rows1, 2 and 3 penalties must be recomputed.
CIT907 ADVANCED OPERATION RESEARCH
117
Cycle 2 Step 1: Compute new row penalties
Storag
e Demand points Row
penalties (0) (100) (150) (250)
Kaduna Kano Kebbi Katsina
Lagos 5 4 5 6 1
(100)
3
Ibadan 3 3 6 6
(200)
Benin (1) 2 5 7 8 2
(200)
200
Colum
n - 1 1 0
penalties
The greatest penalty is 3 (marked with arrow). This occurs in the 2nd row (i.e. Ibadan). Therefore, the second variable will be entered in the 2nd row of the cell with least cost in this row.
Step 2
With reference to the distribution table of cycle 2 , we have two least costs in the 2nd row (i.e. Ibadan). They are: column1 (Kaduna) and column 2 (Kano). But, the demand at column1 (Kaduna) has been satisfied which now leaves us with column 2 (Kano) only. We now assign a maximum value from Row 2 (Ibadan) to column 2 (Kano). Here, demand is 100 units and supply is 200 units, so the maximum value is 100 units (demand) with excess supply of 100 units to be shipped to another destination. Thus, we have:
Storage Demand points
(0) (0) (150) (250) Kaduna Kano Kebbi Katsina
Lagos 5 4 5 6
(100)
Ibadan 3 (2) 3 6 6
(100)
100
Benin (1) 2 5 7 8
(200)
200
CIT907 ADVANCED OPERATION RESEARCH
118
Cycle 3 Step1: Compute new row penalties Storag
e Demand points Row
penaltie s (0) (0) (150) (250) Kaduna Kano Kebbi Katsina
1
Lagos 5 4 5 6
(100)
Ibadan 3 (2) 3 6 6 0
(100)
100
1
Benin (1) 2 5 7 8
(200)
200
Colum
n - - 1 0 penalties
^
A tie has occurred here; the penalties in column 3 , rows1 and 3 .
We now look at the cells in each of these column and rows altogether and select the cell with the least cost. This occurs in row 1(Lagos) intersection column 3 (Kebbi). Therefore, the third variable will be entered in the 1st row, 3rd column.
Step 2
With reference to the distribution table of cycle 3 , the third variable is entered in the 1st row (Lagos), 3rd column (Kebbi).
The demand here is 150 units and supply is 100 units. We assign 100 units with excess demand of 50 units to be supplied from another source. Thus, we have:
Storage Demand points
(0) (0) (50) (250) Kadun
a Kano Kebbi Katsina
Lagos 5 4 (3)5 6
(0)
100
Ibadan 3 (2)3 6 6
(100)
100
Benin (1) 2 5 7 8
(200)
200
CIT907 ADVANCED OPERATION RESEARCH
119
Note that Lagos (row1) supply has been exhausted. We eliminated this row from further consideration. Columns 3 and 4 penalties must be recomputed.
Cycle 4
Step 1: Compute new column penalties.
Storage Demand points Row
penalties
(0) (0) (50) (250) Kaduna Kano
Kebb
i Katsina
Lagos (0) 5 4 (3) 5 6 -
100
Ibadan 3 (2) 3 6 6 0
(100)
100
Benin (1) 2 5 7 8 1
(200)
200
Column - - 1 2
penalties
^
The greatest penalty is 2 (marked with arrow). This occurs in the 4th column (Katsina).
Therefore, the fourth variable will be entered in the fourth column of the cell with least cost in this column.
Step 2
With reference to the distribution table of cycle 4 , the 4th variable is entered in the 4th column, 2nd row.
The demand here is 250 units and supply is 100 units. We assign 100
units with excess demand of 150 units to be supplied from another source. Thus, we have:
Storage Demand points (0) (0) (50) (150)
Kaduna Kano Kebbi Katsina
Lagos (0) 5 4 (3) 5 6
100
Ibadan 3 (2) 3 6 (4) 6
(0)
100
100
Benin (1) 2 5 7 8
(200)
200
Note that Ibadan (row 2 ) supply has been exhausted.
CIT907 ADVANCED OPERATION RESEARCH
120
We eliminated this row from further consideration. Supply can only be from Benin (row 3 ) at this stage. Demands are from Kebbi (columns 3 ) and Katsina (columns 4 ) only. Based on this, we do not need to calculate penalties anymore. We now allocate to the least cost first.
With reference to the table in step 2 of cycle 4 , we supply from Benin (row 3 ) to Kebbi (columns 3 ) and Katsina (columns 4 ) 50 units and 150 units respectively. Thus, we have the final table which looks like this:
Storage Demand points (0) (0) (0) (0) Kaduna Kano Kebbi Katsina
Lagos 5 4 (3)5 6
(0)
100
Ibadan 3 (2) 3 6 (4) 6
(0)
100
100
Benin (1) 2 5 7 (5) 8
(0)
200
50
150
Transportation cost for this initial allocation is:
Route Unit X Cost = Total
shipped per cost
unit (#)
From To (#)
We Lagos Kebbi 100 X 5 = 500
Ibadan Kano 100 X 3 = 300
Ibadan Katsina 100 X 6 = 600
Benin Kaduna 200 X 2 = 400
Benin Kebbi 50 X 7 = 350
Benin Katsina 150 x 8 = 1200
3,350
should note here that the methods (i.e. North-west corner, Least cost first and Vogel‟s approximation) that we have just discussed are only meant for the initial allocation. They might not give us the optimal allocation. In most cases, they do not. This now lead us to getting the optimal solution. But, before then, we shall discuss degeneracy.
3.6 Degeneracy and the Transportation Problem
The total number of allocation to be made in a transportation problem should be equal to one less than the number of rows added to the number of column i.e. Total number of allocation On the occasions the number of allocations turns out to be less than this (i.e. rows + columns - 1), the condition is known as degeneracy.
Dealing with Degeneracy
If degeneracy occurs in the allocation of a transportation problem, then it is necessary to make one or more zero allocations to routes to bring up the number of allocation to ROWS + COLUMNS - 1.
CIT907 ADVANCED OPERATION RESEARCH
121 3.7 Testing the Solution for Optimality
By optimality test, we want to check the initial feasible solution obtained representing the minimum cost possible. This is done by calculating what is known as „shadow costs‟ (i.e. an imputed cost of not using a particular route) and comparing this with the real transport cost to see whether a change of allocation is desirable. This is done with reference to the initial feasible solution as shown in the table below:
Step 1
Check that number of allocation is ROWS+COLUMN = 1.
Else, treat as degeneracy.
For this solution; Rows = 3 and Column = 4 .
Number of allocation = 3 + 4 -1 = 6, which is the same as the number of allocation made.
Step 2
Calculate a nominal „Sending‟ and „Receiving‟ cost for each occupied cell by making assumption that, the transport cost per unit is capable of being split between Sending and Receiving costs i.e.
S1 D1 8 S2 D2 9 S2 D3 7 S3 D1 13 S3 D3 10 S3 D4 7
Where S 1 , S 2 and S3 represent sending cost from source S 1 , S 2 and S3 and D1 , D2 , D3 and D4 represent receiving cost at destination D1 , D2 , D3 and D4
.
By convention, the first source is assigned the value of zero i.e.
and this value is substituted in the first equation and then all the other values can be obtained thus:
D1 8 , D2 7 , D3 5 , D4 2 .
Source Demand Supply
D1 D2 D3 D4
S 1 8 6
1
0 15 4
4
S 2 12 9 7 8 12
6 6
S3 13
13
1 0
7 14
2 2 10 Demand 6 6 8 10
CIT907 ADVANCED OPERATION RESEARCH
122
Using these values, the shadow cost of the unoccupied cells can be calculated.
The unoccupied cells are: S1D2 , S1D3 , S1D4 ,
S2 D1 , S2 D4 and S3D2 . Therefore:
Cell Shadow cost
S1D2 : S1 D2 0 7 7 S1D3 : S1 D3 0 5 5 S1D4 : S1 D4 0 2 2 S2 D1 : S2 D1 2 8 10 S2 D4 : S2 D4 2 2 4 S3D2 : S3 D2 5 7 12
These computed shadow costs are compared with the actual transport costs (from table...).
Where the ACTUAL costs are less than SHADOW costs, overall costs can be reduced by allocating units into that cell.
By comparison, we mean the difference between Actual cost and Shadow cost. This difference is sometimes referred to as the improvement index i.e.
IMPROVEMENT INDEX ACTUAL COST SHADOW COST.
Cell Actual Shadow Improvement
cost cost index
S1D2 6 7 -1
:
S1D3 10 5 5
:
S1D4 15 2 13
:
S2 D1 12 10 2
:
S2 D4 8 4 4
:
S3D2 13 9 4
The meaning of this is that, if all the improvement indices computed is greater than or equal to zero, an optimal solution has been reached. If not, it is possible to improve the current solution and decrease total transportation costs. In other words, if any of the indices is negative, an improved solution is possible. If however, there are more than one negative improvement index, our strategy would be to choose the route (unused route) with the largest negative index. Situations do arise when the largest negative index is not unique. Now, let us continue with our illustration example. The total cost could be reduced by #1 for every unit that can be transferred into cell S1D2 . As there is a cost reduction that can be made, the solution in the table above is not optimum.
Step 3
CIT907 ADVANCED OPERATION RESEARCH
123
Make the maximum possible allocation of deliveries into the cell with the (largest) negative improvement index using occupied cells i.e.
from step 2 . The number that can be allocated is governed by the need to keep within the row and column totals. This is done as follows:
Source Demand Supply
D1 D2 D3 D4
S 1 ( ) 8 ( ) 6 10
1
5 4 4 S 2 12 ( ) 9 ( ) 7 8 12
6 6 S3 ( ) 13 13 ( ) 10 7 14
10 2 2 Demand 6 6 8 10
This table is a reproduction of the one above with a number of and inserted. These were inserted for the following reasons:
Cell S1D2 : indicates a transfer IN as indicated in step 2 . Cell S1D1 : indicates a transfer OUT to maintain Row S 1 total.
Cell S2 D2 : indicates a transfer OUT to maintain Row column D2 total.
Cell S2 D3 : indicates a transfer IN to maintain Row S 2 total.
Cell S3 D1 : indicates a transfer IN to maintain column D1 total.
Cell S3D3 : indicates a transfer OUT to maintain Row S3 and column D3 balance.
The maximum number that can be transferred into cell S1D2 is the lowest number in the minus cells i.e. cells S1D1 , S2 D2 and S3D3 which is
units.
2 units are transferred in the + and - sequence described above resulting in the following table:
Source Demand Supply
D1 D2 D3 D4
S 1
8 6 10 15
4
2 2
S 2 12 9 7 8 12 4
8
S3 13 13 10 7 14
4
10
Demand 6 6 8 10 The total cost of this solution is:
Cell S1D1
2 units #
8 # 16