A Transportation Problem World Food Engineering Essay

✅ Paper Type: Free Essay	✅ Subject: Engineering
✅ Wordcount: 2196 words	✅ Published: 1st Jan 2015

Reference this

Share this: Facebook Twitter Reddit LinkedIn WhatsApp

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

110

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

France

93.6

108

110

Spain

158.4

100.8

Demand

125

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

110

Spain

158.4

100.8

Demand

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

Spain

158.4

100.8

Demand

Step 3:

Allocate At [2][2] = 55

Wheat

Barley

Oats

Supply

England

162(70)

121.5

82.8

France

93.6(55)

108(55)

Spain

158.4

100.8

Demand

Step 4:

Allocate At [3][2] = 5

Wheat

Barley

Oats

Supply

England

162(70)

121

82.8

France

93.6(55)

108(55)

Spain

158.4

100.8(5)

100.8

Demand

Step 5:

Allocate At [3][3] = 75

Wheat

Barley

Oats

Supply

England

162(70)

121.5

82.8

France

93.6(55)

108(55)

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.

Get Help With Your Essay

If you need assistance with writing your essay, our professional essay writing service is here to help!
Find out more about our Essay Writing Service

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