ASSIGNMENT

Transportation Problem

1) 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.

m
The labor cost per hour in producing barley is $8.10, $9.00, and $8.40 in England,

er as
France, and Spain, respectively. The labor cost per hour in producing oats is $6.90, $7.50,

co
and $6.30 in England, France, and Spain, respectively. The problem is to allocate land

eH w
use in each country so as to meet the world food requirement and minimize the total labor

o.
cost.
rs e
ou urc
(a) Formulate this problem as a transportation problem by constructing the appropriate
parameter table.
o

Let England, France, and Spain be the three sources, where their supplies are the millions
aC s

of acres of land that are available for growing these crops. Let Wheat, Barley, and Oats
vi y re

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
ed d

multiplied by the cost per hour. The parameter table is as follows:

ar stu

Unit Cost ($ million)

Destination
sh is

Wheat Barley Oats Supply

Th

England 162 121.5 82.8 70

Source France 93.6 108 75 110

Spain 158.4 100.8 100.8 80

Demand 125 60 75

[Link]
 (b) Draw the network representation of this problem.

The network presentation of this problem is given below:

162
[70] E W [-125]
93.6
158.4

121.5
108
[110] F B [-60]
100.8
75

82.8

m
er as
co
[80] S O [-75]

eH w
100.8

o.
rs e
(c) Obtain an optimal solution. (Use Northwest Corner Method to find the initial solution
ou urc
and MODI to find the optimal solution.)

We can use the Excel Solver to solve this problem and obtain the following solution.
o
aC s

Allocation Quantities
vi y re

Destination

Wheat Barley Oats Totals Supply

ed d
ar stu

England 0 0 70 70 = 70

Source France 110 0 0 110 = 110

sh is

Spain 15 60 5 80 = 80
Th

Totals 125 60 75

= = = Total cost = $25.02 billion

Demand 125 60 75

[Link]
 2) Consider the transportation problem having the following parameter table:

Destination Supply
Source 1 2 3 4 5
1 8 6 3 7 5 20
2 5 M 8 4 7 30
3 6 3 9 6 8 30
4 (Dummy) 0 0 0 0 0 20
Demand 25 25 20 10 20 100

After several iterations of the transportation simplex method, a BF solution is obtained that has
the following basic variables: x13 = 20, x21 = 25, x24 = 5, x32 = 25, x34 = 5, x42 = 0, x43 = 0,
x45 = 20. Continue the transportation simplex method for two more iterations by hand. After
two iterations, state whether the solution is optimal and, if so, why.

m
er as
V1 = 7 V2 = 3 V3= 3 V4= 6 V5= 3 Supply

co
eH w
Destination
Source 1 2 3 4 5

o.
U1= 0 1 8 6 3 7 5
rs e 20 20
ou urc
U2= -2 2 5 M 8 4 7
25 5 30
U3= 0 3 6 3 9 6 8
o

25 5 30
aC s

U4= -3 4 0 0 0 0 0
vi y re

(Dummy) 0 0 20 20
Demand 25 25 20 10 20 100

Total Cost = (25x5) + (25x3) + (0x0) + (20x3) + (0x0) + (5x4) + (5x6) + (19x0)
ed d

= 125 + 75 + 0 + 60 + 0 + 20 + 30 + 0
ar stu

= 310

Improvement Index:
sh is

X11 = 8-0-7 = 1; X12 = 6-0-3 = 3; X14 = 7-0-6 = 1; X15 = 5-0-3 = 2;

X23 = 8-(-2)-3 = 7; X25 = 7-(-2)-3 = 6;
Th

X31 = 6-0-7 = -1; X33 = 9-0-3 = 6; X35 = 8-0-3 = 5;

X41 = 0-(-3)-7 = -4; X44 = 0-(-3)-6 = -3

[Link]
 V1 = 7 V2 = 3 V3= 3 V4= 6 V5= 3 Supply
Destination
Source 1 2 3 4 5
U1= 0 1 8 6 3 7 5
20 20
U2= -2 2 (-1) 5 M 8 (+1) 4 7
25 5 30
U3= 0 3 6 (+1) 3 9 (-1) 6 8
25 5 30
U4= -3 4 (+1) 0 (-1) 0 0 0 0
(Dummy) 0 0 20 20
Demand 25 25 20 10 20 100

Total Cost = 310 – 4(0) = 310

m
er as
co
eH w
V1 = 3 V2 = -1 V3= 3 V4= 2 V5= 3 Supply
Destination

o.
Source 1 2 3 4 5
U1= 0 1 rs e 8 6 3 7 5
ou urc
20 20
U2= 2 2 5 M 8 4 7
25 5 30
o

U3= 4 3 6 3 9 6 8
aC s

25 5 30
vi y re

U4= -3 4 0 0 0 0 0
(Dummy) 0 0 20 20
Demand 25 25 20 10 20 100
ed d

Improvement Index:
ar stu

X11 = 8-0-3 = 5; X12 = 6-0-(-1) = 7; X14 = 7-0-2 = 5; X15 = 5-0-3 = 2;

X23 = 8-2-3 = 3; X25 = 7-2-3 = 2;
X31 = 6-4-3 = -1; X33 = 9-4-3 = 2; X35 = 8-4-3 = 1;
sh is

X42 = 0-(-3)-1 = 2; X44 = 0-(-3)-2 = 1

Th

[Link]
 V1 = 3 V2 = -1 V3= 3 V4= 2 V5= 3 Supply
Destination
Source 1 2 3 4 5
U1= 0 1 8 6 3 7 5
20 20
U2= 2 2 (-1) 5 M 8 (+1) 4 7
25 5 30
U3= 4 3 6 3 9 (-1) 6 8
(+1) 25 5 30
U4= -3 4 0 0 0 0 0
(Dummy) 0 0 20 20
Demand 25 25 20 10 20 100

m
er as
V1 = 3 V2 = 0 V3= 3 V4= 2 V5= 3 Supply
Destination

co
eH w
Source 1 2 3 4 5
U1= 0 1 8 6 3 7 5

o.
20 20
U2= 2 2 rs e 5 M 8 4 7
ou urc
20 10 30
U3= 3 3 6 3 9 6 8
5 25 30
o

U4= -3 4 0 0 0 0 0
aC s

(Dummy) 0 0 20 20
vi y re

Demand 25 25 20 10 20 100

Total Cost = 310 – 1(5) = 305

ed d

Improvement Index:
ar stu

X11 = 8-0-3 = 5; X12 = 6-0-0 = 6; X14 = 7-0-2 = 5; X15 = 5-0-3 = 2;

X23 = 8-2-3 = 3; X25 = 7-2-3 = 2;
X33 = 9-3-3 = 3; X34 = 6-3-2 = 1; X35 = 8-3-3 = 2;
sh is

X42 = 0-(-3)-0 = 3; X44 = 0-(-3)-2 = 1

Th

OPTIMAL: No NEGATIVE improvement Index

3) A contractor, Susan Meyer, has to haul gravel to three building sites. She can purchase as
much as 18 tons at a gravel pit in the north of the city and 14 tons at one in the south. She
needs 10, 5, and 10 tons at sites 1, 2, and 3, respectively. The purchase price per ton at
each gravel pit and the hauling cost per ton are given in the table below.

Hauling Cost Per Ton at Site Price Per Ton

Pit 1 2 3
North $30 $60 $50 $100
South $60 $30 $40 $120

[Link]
 Susan wishes to determine how much to haul from each pit to each site to minimize the
total cost for purchasing and hauling gravel.

(a) Formulate a linear programming model for this problem. Using the Big M method,
construct the initial simplex tableau ready to apply the simplex method (but do not
actually solve).

Minimize Z = 130X11 + 160X12 + 150X13 + 180X21 + 150X22 + 160X23

Subject to:
X11 + X12 + X13 <= 18
X21 + X22 + X23 <= 14
X11 + X21 >= 10
X12 + X22 >= 5

m
X13 + X23 >= 10

er as
Xij >= 0

co
eH w
o.
Minimize Z = 130X11 + 160X12 + 150X13 + 180X21 + 150X22 + 160X23 + 0S1 +
rs e0S2 + 0S3 + 0S4+ 0S5 +MA3 + MA4 + MA5
ou urc
Subject to:
X11 + X12 + X13 + S1 = 18
X21 + X22 + X23 + S2 = 14
o

X11 + X21 – S3 + A3 = 10
X12 + X22 – S4 + A4 = 5
aC s

X13 + X23 – S5 + A5 = 10
vi y re

Xij >= 0; Si >= 0; Ai >= 0

Maximize –Z + 130X11 + 160X12 + 150X13 + 180X21 + 150X22 + 160X23 + 0S1

ed d

+ 0S2 + 0S3 + 0S4+ 0S5 +MA3 + MA4 + MA5 = 0

ar stu

Subject to:
X11 + X12 + X13 + S1 = 18
X21 + X22 + X23 + S2 = 14
X11 + X21 – S3 + A3 = 10
sh is

X12 + X22 – S4 + A4 = 5
X13 + X23 – S5 + A5 = 10
Th

Xij >= 0; Si >= 0; Ai >= 0

[Link]
 Transformed Objective Function:

X11 X12 X13 X21 X22 X23 S1 S2 S3 S4 S5 A3 A4 A5 RHS

OLD
130 160 150 180 150 160 0 0 0 0 0 M M M 0
-Z
Const
-M -M M -M -10M
3 * -M
Const
-M -M M -M -5M
4 * -M
Const
-M -M M -M -10M
5 * -M
NEW 130- 160- 150- 180- 150- 160-
0 0 M M M 0 0 0 -25M
-Z M M M M M M

m
er as
Initial Tableau:

co
eH w
X11 X12 X13 X21 X22 X23 S1 S2 S3 S4 S5 A3 A4 A5 RHS

o.
130- 160- 150- 180- 150- 160-
-Z
M M M rs e
M M M
0 0 M M M 0 0 0 -25M
ou urc
S1 1 1 1 1 18
S2 1 1 1 1 14
A3 1 1 -1 1 10
o

A4 1 1 -1 1 5
aC s

A5 1 1 -1 1 10
vi y re

(b) Now formulate this problem as a transportation problem by constructing the

appropriate parameter table. Compare the size of this table (and the corresponding
ed d

transportation simplex tableau) used by the transportation simplex method with the
ar stu

size of the simplex tableau from part (a) that would be needed by the simplex method.

From/To Site 1 Site 2 Site 3 Dummy Supply

sh is

North 130 160 150 0 18

South 180 150 160 0 14
Th

Demand 10 5 10 7 32

[Link]
 (c) Susan Meyer notices that she can supply sites 1 and 2 completely from the north pit
and site 3 completely from the south pit. Use the optimality test (but no iterations) of
the transportation simplex method to check whether the corresponding BF solution is
optimal.

V1 = 130 V2 = 160 V3 = 160 V4 = 0

From/To Site 1 Site 2 Site 3 Dummy Supply
U1= 0 North 10 130 5 160 150 3 0 18
U2 = 0 South 180 150 10 160 4 0 14
Demand 10 5 10 7 32

Impovement Index
X13 = 150 – 0 – 160 = -10
X21 = 180 – 0 – 130 = 50

m
X22 = 150 – 0 – 160 = -10

er as
co
NOT OPTIMAL because the Improvement index values of the unused cells have still

eH w
negative values.

o.
rs e
ou urc
(d) Starting with the northwest corner rule, interactively apply the transportation simplex
method to solve the problem as formulated in part (b).
o

Northwest Corner Method:

aC s
vi y re

From/To Site 1 Site 2 Site 3 Dummy Supply

North 10 130 5 160 3 150 0 18
South 180 150 7 160 7 0 14
Demand 10 5 10 7 32
ed d
ar stu

Total Cost = (10x130) + (5x160) + (3x150) + (7x160) + (7x0) = 3670

Inprovement Index:
sh is

X14 = 0-0+160-150 = 10;

X21 = 180-130+150-160 = 40;
Th

X22 = 150-160+150-160 = -20

From/To Site 1 Site 2 Site 3 Dummy Supply

North 10 130 160 8 150 0 18
South 180 5 150 2 160 7 0 14
Demand 10 5 10 7 32

Total Cost = 3670 – 20(5) = 3570

[Link]
 Improvement Index:
X12 = 160-150+160-150 = 20;
X14 = 0 -150+160-0 = 10
X21 = 180-130+150-160 = 40

OPTIMAL SOLUTION: No negative Improvement Index

(e) As usual, let cij denote the unit cost associated with source i and destination j as given
in the parameter table constructed in part (b). For the optimal solution obtained in part
(d), suppose that the value of cij for each basic variable xij is fixed at the value given
in the parameter table, but that the value of cij for each nonbasic variable xij possibly
can be altered through bargaining because the site manager wants to pick up the
business. Use sensitivity analysis to determine the allowable range to stay optimal
for each of the latter cij, and explain how this information is useful to the contractor.

m
er as
From/To Site 1 Site 2 Site 3 Dummy Supply

co
North 10 130 160 8 150 0 18

eH w
South 180 5 150 2 160 7 0 14

o.
Demand 10 5 10 7 32
rs e
ou urc
X12:
X12 – 150 + 160 – 150 >= 0
X12 >= 140
o
aC s

Minimum = 140;
vi y re

Maximum = infinity;

X21:
X21 – 130 + 150 - 160 >= 0
ed d

X21 >= 140

ar stu

Minimum = 140;
Maximum = infinity
sh is

The above values will make the optimal solution be the same. If the cost is below these
Th

allowable range, the contractor can choose these sites as possible destinations.

[Link]

Powered by TCPDF ([Link])