A Transportation Problem World Food Engineering Essay
Suppose that England, France, and Spain produce all the wheat, barley, and oats in the world. The world demand for wheat requires 125 million acres of land devoted to wheat production. Similarly, 60 million acres of land are required for barley and 75 million acres of land for oats. The total amount of land available for these purposes in England, France, and Spain is 70 million acres, 110 million acres, and 80 million acres, respectively. The number of hours of labor needed in England, France and Spain to produce an acre of wheat is 18, 13, and 16, respectively. The number of hours of labor needed in England, France, and Spain to produce an acre of barley is 15, 12, and 12, respectively. The number of hours of labor needed in England, France, and Spain to produce an acre of oats is 12, 10, and 16, respectively. The labor cost per hour in producing wheat is $9.00, $7.20, and $9.90 in England, France, and Spain, respectively. The labor cost per hour in producing barley is $8.10, $9.00, and $8.40 in England, France, and Spain respectively. The labor cost per hour in producing oats is $6.90, $7.50, and $6.30 in England, France, and Spain, respectively. The problem is to allocate land use in each country so as to meet the world food requirement and minimize the total labor cost.
BASIC TERMINOLOGY
Transportation Problem:
Transportation problems are one of the types of the Linear Programming Problem in which the object is to transport the various quantities of a single homogeneous commodity to different destinations in such a way that the total transportation cost is minimum.
Feasible Solution:
The non negative value of Xij, where i= 1,2,3…..m and j = 1,2,3…..n which satisfies the constraints of supply and demand.
Basic Feasible Solution:
If the number of positive allocation is (m+n-1) then it is a basic feasible solution.
Balanced Transportation Problem:
A transportation problem in which the total supply from all sources is equal to the total demand in all the destinations is a balanced transportation problem.
Optimal solution:
A feasible solution is said to me optimal solution if it minimizes the total transportation cost.
Methods for finding initial basic feasible solution:
Northwest Corner Rule
Least Cost entry method
Vogel’s Approximation method
Methods for making improvements:
Modified Distribution Methods. (MODI)
Stepping Stone
Steps to find Basic Feasible Solution by North West Corner Rule Method:
Starting with the first cell at the north – west corner of the matrix, allocate maximum possible quantity.
Address the supply and demand numbers in the representation rows and column allocations.
Continue the procedure until the total available quantity is fully allocated to the cell as required.
(a) Formulate this problem as a transportation problem by constructing the appropriate parameter table.
Let England, France, and Spain be the three sources, where their supplies are the millions of acres of land that are available for growing these crops. Let Wheat, Barley, and Oats be the three destinations, where their demands are the millions of acres of land that are needed to fulfill the world demand for these respective crops. The unit cost (in millions of dollars) is the labor cost per million acres, so the number of hours of labor needed is multiplied by the cost per hour.
The network presentation of this problem is given below.
The parameter table is given as:
Unit cost ($ millions)
Destination
Wheat Barley Oats
Supply
England
Source France
Spain
162 121.5 82.8
93.6 108 75
158.4 100.8 100.8
70
110
80
Demand
125 60 75
260
(b) Reconsider the problem in the preceding example. Starting with the northwest corner rule, Find basic feasible solution.
Supply constraints: 3
Demand constraints: 3
As the total demand is equal to the total supply, therefore it is a balanced transportation problem.
The Problem Table is:
Wheat
Barley
Oats
Supply
England
162
121.5
82.8
70
France
93.6
108
75
110
Spain
158.4
100.8
100.8
80
Demand
125
60
75
Step 1:
Using the Northwest corner rule, first we look at the northwest or the top left corner of the table i.e. [1][1]. Here, we can see that the demand is of 125 and the supply is of 70. Therefore, we complete the demand of 70 which is available and Allocate At [1][1] = 70.
Now, supply of 70 is exhausted and can be written as 0, whereas the demand is fulfilled by only 70 so remaining 55 is left.
Wheat
Barley
Oats
Supply
England
162(70)
121.5
82.8
France
93.6
108
75
110
Spain
158.4
100.8
100.8
80
Demand
55
60
75
Step 2:
Similarly, we now see the next northwest corner or the top left corner of the table, which is, [2][1]. Here, the demand is of 55 and the supply of 110. Therefore we can fulfill the demand of 55 and Allocate At [2][1] = 55. Now the demand in the first column is completed and we can write zero whereas supply is left with 55.
We can repeat the above steps till the complete demand and supply is met.
Wheat
Barley
Oats
Supply
England
162(70)
121.5
82.8
France
93.6(55)
108
75
55
Spain
158.4
100.8
100.8
80
Demand
60
75
Step 3:
Allocate At [2][2] = 55
Wheat
Barley
Oats
Supply
England
162(70)
121.5
82.8
France
93.6(55)
108(55)
75
Spain
158.4
100.8
100.8
80
Demand
5
75
Step 4:
Allocate At [3][2] = 5
Wheat
Barley
Oats
Supply
England
162(70)
121
82.8
France
93.6(55)
108(55)
75
Spain
158.4
100.8(5)
100.8
75
Demand
75
Step 5:
Allocate At [3][3] = 75
Wheat
Barley
Oats
Supply
England
162(70)
121.5
82.8
France
93.6(55)
108(55)
75
Spain
158.4
100.8(5)
100.88(75)
Demand
Final Allocation Table is:
The total supply constraint + total demand constraint – 1 = 3 + 3 – 1 = 5
Therefore, the solution is feasible.
Total transportation cost = 162 x 70 + 93.6 x 55 +108 x 55 + 100.8 x 5 + 100.8 x 75
= 11340 + 5148 + 5940 + 504 + 7560
= 30492
The cost minimized total transportation = 30492
(c) Obtain an optimal solution.
Optimality Test:
Since cij – ui – vj = 0 if xij is a basic variable,
cij = ui + vj for each (i, j) such that xij is basic.
Because the number of unknowns (the ui and vj) exceed the number of these equations by one, we can set one unknown equal to an arbitrary value, say 0. These equations can then be solved as outlined below.
x21: 93.6 = u2 + v1. Set u2 = 0, so v1 = 93.6,
x22: 108 = u2 + v2. v2 = 108.
x11: 162 = u1 + v1. Know v1 = 93.6, so u1 = 68.4.
x32: 100.8 = u3 + v2. Know v2 = 108, so u3 = -7.2.
x33: 100.8 = u3 + v3. Know u3 = -7.2, so v3 = 108.
Since cij – ui – vj represents the rate at which the objective function will change as a non basic variable xij is increased, we now can check whether increasing any non basic variable will decrease the total cost Z.
Non basic variable
cij – ui – vj
x12
121.5 – 68.4 – 108 = -54.9
x13
82.8 – 68.4 – 108 = -93.6
x23
75 – 0 – 108 = -33
x31
158.4 -(-7.2) – 93.6 = 72
Because some of these (cij – uij – vj) values are negative, the initial BF solution is not optimal.
Iteration 1:
We select the non basic variable x13 to be the entering basic variable because it has the largest negative value of (cij – ui – vj).
When x13 is increased from 0 by any particular amount, a chain reaction is set off that requires alternately decreasing and increasing current basic variables by the same amount in order to continue satisfying the supply and demand constraints. This chain reaction is depicted in the next figure, where the + sign inside a box in cell (1, 3) indicates that the entering basic variable is being increased there and the + or – sign next to other circles indicate that a basic variable is being increased or decreased there.
Each donor cell (indicated by a minus sign) decreases its allocation by exactly the same amount as the entering basic variable and each recipient cell (indicated by a plus sign) is increased. The entering basic variable will be increased as far as possible until the allocation for one of the donor cells drops all the way down to 0. Since the original allocations for the donor cells are
x11 = 70, x22 = 55, x33 = 75,
x22 will be the one that drops to 0 as x13 is increased (by 55). Therefore, x22 is the leaving basic variable.
Since each of the basic variables is being increased or decreased by 55, the values of the basic variables in the new BF solution are
x11 = 15, x13 = 55, x21 = 110, x32 = 60, x33 = 20.
Optimality Test after Iteration 1:
Since Source 1 now has two basic variables (tied for the maximum number), let us set u1 = 0 this time. The cij = ui + vj equations then would be solved as follows.
x11: 162 = u1 + v1. Set u1 = 0, so v1 = 162,
x13: 82.8 = u1 + v3. v3 = 82.8.
x21: 93.6 = u2 + v1. Know v1 = 162, so u2 = -68.4.
x33: 100.8 = u3 + v3. Know v3 = 82.8, so u3 = 18.
x32: 100.8 = u3 + v2. Know u3 = 18, so v2 = 82.8.
We next calculate (cij – ui – vj) for the non basic variables.
Nonbasic variable
cij – ui – vj
x12
121.5 – 0 – 82.8 = 38.7
x22
108 – (-68.4) – 82.8 = 93.6
x23
75 – (-68.4) – 82.8 = 60.6
x31
158.4 – 18 – 162 = -21.6
We still have one negative value of (cij – ui – vj), so the current BF solution is not optimal.
Iteration 2:
Since x31 is the one non basic variable with a negative value of (cij – ui – vj), x31 becomes the entering basic variable.
The resulting chain reaction is depicted next.
The donor cells have allocations of x11 = 15 and x33 = 20. Because 15 < 20, the leaving basic variable is x11.
Since the basic variables x21 and x32 were not part of this chain reaction, their values do not change. However, x31 and x13 increase by 15 while x11 and x33 decrease by 15. Therefore, the values of the basic variables in the new BF solution are
x13 = 70, x21 = 110, x31 = 15, x32 = 60, x33 = 5
Optimality Test after Iteration 2:
Because Source 3 now has the largest number of basic variables, we set u3 = 0 this time. The resulting calculations are shown below.
x31: 158.4 = u3 + v1. Set u3 = 0, so v1 = 158.4,
x32: 100.8 = u3 + v2. v2 = 100.8.
x33: 100.8 = u3 + v3. v3 = 100.8.
x13: 82.8 = u1 + v3. Know v3 = 100.8, so u1 = -18.
x21: 93.6 = u2 + v1. Know v1 = 158.4, so u2 = -64.8.
Nonbasic variable
cij – ui – vj
x11
162 – (-18) – 158.4 = 21.6
x12
121.5 – (-18) – 100.8 = 38.7
x22
108 – (-68.4) – 100.8 = 72
x23
75 – (-64.8) – 100.8 = 39
Since all of these values of (cij – ui – vj) are nonnegative, the current BF solution is optimal.
Thus, the optimal allocation of land to crops is
70
million acres in England for oats,
110
million acres in France for wheat,
15
million acres in Spain for wheat,
60
million acres in Spain for barley,
5
Million acres in Spain for oats.
The total cost of this grand enterprise would be