LLUSTRATION 13

Describe the transportation problem. Use Vogel's approximation method t

Obrain an intialfeasible solution to thefollowingproduct distribution problen.
Transportation Costs
Distribution Centres

Mumbai Bangalore Delhi Chennai Factory

Factory Capacity
30
Kolkata
Ranchi 11 9 7 40

Ahmedabad 8 7 13 50

Centre Demand 35 28 32 25
 reached. The
As C 2 u;+; for all non allocated cells, the optimal solution is
solution is as follows :
No. of Units UnitCost Total Cost
From To
28 5 140
Kolkata Bangalore
2 8 16
Kolkata Chennai
17 5 85
Ranchi Mumbai
23 161
Ranchi Chennai
18 8 144
Ahmedabad Mumbai
32 7 224
Ahmedabad Delhi
G. Total Cost 770
G.Total Units 120
TRATION 14

Solve the following transportation problem, ie., Find the optimal solution,
where theentries are cost coefficients.
Destination
From To
2 3 4
Availability
I5 20 10
Origins 2 12 8 20 50
3 16 14 18 I00
30 40 60 70
Requirement 200
IT#ATIONTABLEAU 5:
D, D,
10 60
18

Summary:
D Dy D DA
10 10
18 20 10
50
12 18 11 20
30 10 60
16 14 18
The total cost incurred is,
10x 10+ ll x50 + 14 x 10 + 18 x 60 = 1870
Step 5: Checkingfor Optimality : The given
allocatedcells n (c; )problem
as number of is non-degenerate (no
=6 degeneracy)
No. of roOws (r) =3, No. of
columns (c) = 4; r+c- l=3 +4-1=6
[: n(o)=r+c- l ]
Now, equations with allocated cells as
We get, cj =u;tVj
W+Vg =0; 4|+Vs 10
ugtvj =0
tdg t Ug = 14; ug t v4 = 18
Assuming =0, we have uy = 5, u=8,
v=-8, Vg =0,Vg =6 and v4= 10
Now checkingc-(4;ty;)20 for non
for G11 15 -(-8+0) = allocated cells,
+23; for c13
for Cg1 12-(-8+5)=15;
for cg2 20-(0+6) =+14
for Cg4 20- 8- (5+0) =+3
(5+10)=+5, and for Cy2
Since all -(4;+ v; ) are positive, the 16-(8+0)=+8.
Hence the minimum cost = Rs. 1870/ obtained solution is optimal.
and allocations are
O, to D,=40 units ;
O to D4= 10units
Oq to Dy = 50 units ; Oz to D
=30 units
O, to D, =10anits and O, to D =
60 units
TRATION 15
Anoil company has got three refineries P QandRandit has to send petrolto four
ferent depots A, B, C and . The cost of shipping 1gallon of petrol at the
refineries aregiven in the table. The requirement of the depots and the available
petrol are also given. Find the minimum cost of shipping afier obtaining an intial
solution by VAM.s Deposit
Refineries Available
D

P 12 15 8 130
150
R 20 9 7 18 170

120 459
Required 90 100 140
JNTU (Mech) 99}
 Operations Research : Theory and
246

as it is filled to its requirement.

Practice
Step 5: Colun1n Cis neglected
ITERATION TABLEAU -3:
Availability Penalty
A
10 2
P
10 12
150
11 11
80
R
30) 11
20
Required 90 100/70

Penalty 2

Step 6: Row Ris neglected

ITERATION TABLEAU -4:
A B Penalty
10
P
10 12 10 2
80 70
11 150
90 70
Penaly

Step 7: Finding the Costs of an Allocaled Cells :

A B C D
P
10 +1I +7 120
= 10
10 12 15 8
80 70 +1
10
R +11 30 140+1i
20 9 18

Initial solution by VAM itself is optimal.

Since the values e -(4yt v;)20.
= 10x 10+ 11x 80 + 11x70 + 9x 9-+8x 120 + 7x14 = Rs.
3960.
Minimum cost Rs. 3960.
Note : This problem yields an alternate optimal sokution.
For hints, Refer illustration- 20 under section 5. 1Ll and try for another solution
RATION 16

Solve the Transportation Problen whose unit cost matrix, supply and demand
aregiven below:
D1 D2 D3 DË Ds Supply
10 5 45

4 3 8 6 13 90

9 8 6 7 5 96

O4 12 13 10 6 3 75

I2 105
Os 4

Demand 120 80 50 75 85
|JNTU(Mech) 98/sl
TransportationProblem 251

D D D, D
+0 45 0
10
07 90

10 96 9
7 0*
+6 75 0 75 0
10
105 |+1| +2 105 -2
6 12 0

190 80 50 75 88

7 6 4 5

Wt0: Wt=5; My t vy = 4
lug t Ug =6
Mg t Uy = 7
D, Dg D D D, D6
+1 +6 45 +8 +2
45
7 10 11
10 80 +7 +9 +5
90 -3
4 8 6
5 50 30 10 1 96 2
9 8 6 5
+5 +7 +6 +1 75 +9
75
12 13 10 6 0
105 +3 +3 +11 +4
105
5 4 5 6 12
120 80 50 75 85
7 6 4 5

From the above tableau G-(4;+ u;) 20 i:e., Non-negative for all
non-allocated cells, the opimal solution is obtained as follows,
Cell Unit cost Allocated units Total cost
(Rs.) (Rs.)
225
(0,,D,) 5 45
40
(0,, D,) 10
240
(0, D) 80
45
(O3,D,)
300
(O,,D,) 6 50
2 Operations Research: Theory and Practice
30 210
(0,. D,) 7
50
(O,.D,) 5 10
0
(0,. D,)
(0, D,) 3 75 225

(0,,D,) 5 105 525

Grand Total Rs. 1860/

The total minimum ransporation cost(optimum) is Rs. 1860/- and one unitin
the supply of origin -3 is not transported to any destination (unutilized resource).
Note : The above TP ields multiple optimal solutions uhich will be explained in later sections.
may try. Students
RLUSTRATION 17

Findthe optimalsolutionto the Transportation Problem given below:

Warehouses
W W W W Supply
F 4 25 45 6
Factor F 65 25 35 $5
35 3 65 15 16
Demand
13 30 (tota)

NTU (CSE)97]
254
IBES TABLEAU:
W W, W, W
2
Supply
Pracie
4 6
F 25 45 5
14
8
25 35 55
65
7 9
16
F 65 15
35
Demand 4 7 6 13
Initial basic feasible solution = 14x4 + 3 x7.+6 x 35 +2x5+2x 55.+9x
n(C) =n (r) + n(c)-1 ie.,,6=4+3-
& 1, Hence 1 15 =542
no
Optimisation :
W, W
degeneracy
W; W,
4 +32 +60 2
F 14
=0
25 45 5
+} -18 6 2
F 65 dg =50
25 35 55
+70 l7 +70
Fs 35 65
iy = 10
15
U= 14 Vg =- 15
Wtv = 14;
ug t vg 35; hg t Vy 55
ug t Ug 3;
W +32 +42
4
Wy W3 WA
+19 14
25 45 +18 6
65 25 +52
35 55
5 8
F 35 ky =32
3
65
4 15 16
6
13
lUg = 10
Uj = 14

W+v 14 ;
t v4= 5
ug t U= 25;
uy t Ug = 35
ug t Uy = 3;
hgtv4 = 15
: Optimal solution
= 4x 14+2 x
25 +3 x5+6x
35+ 2x5+ 1lx 15 = 506
Transportation
255
5.6 Degeneracy in Transportation Problem
AAtransportation problemis said to be degenerate if its initial
the condition that the number of allocated
(occupied)
cells n (C) is
solution violates
of
equalto sum number of rows n (r) and number of greater than or
columns (c) minus one. In other
n
words if n(C) <n () +n (c) - 1, the TP is degenerate.
It becomess difficult while computing optimal solution ifthe
Therefore the degeneracy is to be first removed betore going to TP has degeneracy.
How to Resolve Degeneracy : computation of IBFS.
Degeneracy in TP can be resoBved by allocating a minute quantity e (read as
epsilon) to an appropriate cell. This [ is assumed so negligible quantity such that
a+[=a -=aand[0 (also +¬= , E-E= 0).
Where a is any quantity.
Thus [ is a very minute and negligible no zero quantity that
uwhen added or subtracled any number of times. does not aller any value
eg.:e is likeone Rupee tip given to worker for
loadingunloadingin
where some lakhs or some thousands are spent in transporting abusines
the goods:Thus e does
not affect that total ransportation cost.
The degeneracy may be experienced in the initial stage of
the subsequent iterations. optimisation or at
In general the
finding IBES itself by degeneracy
can be identified in transportation problem while
the following points.
1. If the partial surn of availability is equal to partial sum of
is a chance of getting degeneracy. requirements, there
2. In any method (of NWCM, VAM, LCEM etc.), if a row and a
column are
simuitaneously satisfied/exhausted and hence both deleted for next iteration,
then degeneracy will occur while optimising.
S.6.l Degeneracy in the Initial Solution
ILLUSTRATION 18
Determine the Optimum basic feasible solution to the following Transporation
problem.
To
B C Available
50 30 220
From 2 90 45 170 3
4
3 250 200 50
Required 4 2 2
(ECE)99/CCC|
JNTU(Mech.) 99/CCC,
 Operations Research: Theory and
256

Solution:
Practica
Stop : The given Transportation problem (TP) is in the standard from (ie.,
directBly.
minimizaion case). Hence we can proceed
Step 2 nthe given 1P, the sum of availability (8) is equal to the sum of required (8),
Therefore it is balanced.
Sp 3: heparation of BES by North West Corner Method.
To
Available

50 30 220
From 3
90 45 170
4
250 200 50
Required 4
Step 4: Optimization :The number of allocated cells say (n) =
cokumns -Isay r+ ~l= 3+9-]=5 4; No. of rows + No. of
As
the cell (1, n<r+c-1, there is a
B) such that [ 0 anddegeneracy.
a *Hence assuming eas an allocation at
Then, the costs u; and v; are +g=4-ga.
A computed.
4;t;=Gj for allocated cells
50 30 M= (assumed) dj+v = 50
920
#] +Ug = 30
90 45 wg= 40
170 hg tv = 90
250 ug = 170 kg t Uy = 200
200 50
; 50 h + vg = 50
Uy 30 y--120
(As we have five
equal to zero. Hence uequations and six variables, we have to
=0 is assumed)
Now, calculating the value of ci- assume one of these as
optimality, we get (4,t;) for non-allocated cells, to check the
B

50:.3 t+340
80 920
25
908 f 4
+250
+30 170 40
250 200
4 50 170
50 30
" The degeneracy can be -120
sum of availability of lst detected in initial(1 stages
Also, when cell (2, A) is &2nd row i.e., + 3) is while
equalandfinding
allocated with Sunits both row to partialIBFS, since the
rerequired
partial
ofA i.e., 4.
column get satisfied.
nsportation Problem 257

As ci- (4;t u,)<0for cell (2, B), we revise it by transfering someunits given
by least figure among thecorners marked by ve on the loop i.e. e here and then the
above stepisrepeated.
A
+25 +865
0
50 30 220
3 +275
40
90 45 170
+5 195
250 200 50
4 2 -2
Required
50 -145

Asthe values ofe;-(u;+v; )20(non negative) for all non-allocated cells, the
obtained.
optimal basic feasible solution is
The solution is,
Unit Cost No, of Units Total Cost
From To
50 1 50
1 A
90 270
A
45 45¬
B
200 400
B
50 100
4
Total 8+& 320+ 45 [

Rs.)
Hence the total tranportation cost is 320 units (or

S.62 Degeneracy in the Subsequent Iterations

ILLUSTRATION 19
Optimise the following TP
DË Dg Ds Supply
120
S; 5 6
80
15 10 12
80
S 10
150 80 50

Solution :
With usual steps (as explained) the initial solution for the above TP
(minimisation &balanced) by North-west corner method is given below.
 iITERATION TABLEAU 1:
D D Dg SuppBy
120 120
S, 5 6
8
30 50 80
15 12
30 50 80
Ss 10
150 80 50

Since the number of occupied cells n(C) is 5and No. of rows n(r) + No.
columns ie., n(c) - l is 3+3-1 =5, there is no degeneracy. Thus ;
computed with usual set of rules, Also, values C- (4;t v) for unoccupiedandcellsu; anare
calcaulted. The loop is identified for most negative.
TERATION TABLEAU 2:
D, D, D, Supply
120 +2 +2
S 120
5 6
30 50+
80
15t 10 19
30 50
80 tég =6
10
Demand 150 80 50 280

iTERATION TABLEAU3:
D D2
120
Dy Supply
S
5 120
80
Ss 15 80
10 12
30
S_ 50
80
10
Demand 150 80 50 280
In IT -3 we notice
n (r)+ n(c)-l=5. degeneracy*
Thus n(Ci) since
<n()+ n(c)- 1.occupied cells are only four whie
(Se, Do)Therefore
we have to resolve
such that
ate=a-&=a and degeneracy
e*0 and
first, by allocating e to(S, D)
Note : Here degeneracy occured since
both cells have proceed with usual rules.
been transferred. turned out to be
* The
of chance of occuring
unoccupied when 30 units ha°t
availability
DË and Ds (150 of SÊ &degeneracy
+ 50). Ss (120 + can be
80) is predicted in the
equal to partialDeginning
sum of
since partialsumof
requirement
sportation Problem
259
ITERATIONTABLEAU4:
D, D¡ Ds Supply
120
S 120 0
6
+il 80
80 -4
15 10 19
30. 50
80
S 10
-5

Demand 150 80 50 280

14 15

TERATION TABLEAU5:
D, DD, Supply
70 -9 50
120 0
5 6
+11 80 +10
80 -4
15 10 12
80 +9
80 -5
9 10
Demand 150 80 50 280
8 14 6

TERATION TABLEAU6:
D, D Dy Supply
70 50
S,| 120 0
8 6
+2 80+1 80 +5
Sp 15 10 12
80 +9 +9
80 -5
3 9 10
Demand 150 80 50 280
8 5 6

Since Cif lcells, the optimal solution is

arrived.
(uyt u) for all
Ihe optimal cost calculations are the unoccupied
shown below.
Cells From To
Total Cost
No. of Units Units Cost
70 560
D,
S 58
D 300
50 6
D,
 Opera
260
10 800
80
S D, 240
80
S D 1900 + 5e
280
= 1900
G. Total
cost =
the total transportation 1900 units.
Since value of eis negligible,

5.7 Special
ThereCases in special
are some TP cases in TP and are listed below. [We may hae;
combination of two or more of these specialities)
1. Maximisation cases
2. Unbalanced cases

3. Multiple or alternate optimal solution case

4. Restricted transportation case
5. Conditional T.P.
6. Trans-shipment problem.
Of the above the first two cases have been explained in the earlier illustration:
incuding them as first two steps ofIBFS of the T.P. However, these cases are explained
again in combination with restricted and conditional transportation
illustration - 21 and 22 to follow. The third case has been explained inproblems unde
11& 12. However, the alternate optimal illustration 10,
solution illustration - 12 is shown here
in
5.7.1Multiple Optimal Solution or
LLUSTRATION 20
Alternate Optimal Solution
The optimal solution of TP given in
illustrate the alternate optimal solution.illustration - 10or 12 is considered here
Solution :
After arriving the optimal solution by MODI or
identify alternate optimal solution as follows
D, D
steppings stone method, we noN
D, D
o, 20 Tio +4 Supply
30 0
4
0 30 10
50 1
20 +4
+9
5 20
Demand 20 40 30
2 100
 25
ortation Problem
As
I calculations of u; &u; find C-(4;+ v)for non-allocated cells.
allare + ve we obtain optimal solution equal to 180.
Since Ci - (u; +y) value for (0,. D) cell is zero (or C =#; +v). this ceu
good as any allocated cell (whose Cij ; +v) and thus can enter the basis (allocation).
We take up this celland construct a loop as shown in the above table. From the l00P
(O; D-( D) ’ (O,, Dg)’ (0,, D)., we transfer the units from
(O D) Or (Oz, D) and the maximum possible units to transfer is only 10. Therefore
we choose the direction from (0,, D, to (0,, D). Thus the revised matrix is given
below.

(Add 10 to (O, D), subtract 10 to (O,, Da), Add 10 to (Oz, D) arnd subtract 10
to (0j, D). Thus (0,, Ds) becomes occupied i.e., basic while (O,, Da) becomes
unoccupied i.e., non basic.]
Note : This resembles thesame Z;- Cj= 0aues in simplex table. Comparefor your better undersianding
DË D Dy D4 SuppBy
20 10 +4 30
1 4
+1 20 20 10 50
1
+3 20 +4 +9 20
4 2 5 9

30 10 100
Demand 20 40
2

the above table the values of C;f -tu; +u) >0 for all unoccupied cells.
From
thence it is optimal solution.
below.
The cost calculation are given
Total Cost
To Units Cost No. of Units
Cells From
20 20
D 10
10
Ds
Cys 20 60

20 40

Cgg 1 10 10
DA
Cg4 D
9 20 40

180
Grand Total transportation cost
 Operations Research : Theory and
270

Practice Problems
Praciea
Obrain IBFS by NWCMfor the following transportation problemsswhose unit cost
availabilhties and requirements are given in thei matrices, and
of ransportation,
then optimize
(JNTU (CSE)- 2000/S) 5
D, D D, D,
padras LS&
D, Ds
Source
Destination
Supply
S, 9 12 4
Supph5
6 5
7 6
4
4 8 5 5 6 10 14 6
Demand 10 S, 7 5 7 10

2. Ss 2 8 10 2 4
Cosuer Demand S 4 5 7 6 4
Party B |Supply There is degeneracy in this problem
6 4 6
4
pelhi (stat)-73)
12 1 4 5
2 6 5
Supply
A2 10 7
Demand 6 10 15 B 4

3. 12 9
[AS -89, 00- NRA -92]
Demand 3
D, DÍ D, D4
5 6
6
SuppBy
4 1 5 14 7.
O 8 2 7 16
4 6
DË D¡ D D, Supply
2 5 A
Demand
11 13 17
6 10 15 4 14 250
B
16 18 14 10 S00
4. CI 21 24
(LAS- 89. AU - B.Tech -90) 13 10 400
II III
IV Demand 200 225 275
19 15 20
Supply
200
250 950

17 14 12
13 600
18 18
12 700
Demand 300 300 400 500
ortation Problem 271

8. (ou-B.Tech (Mech) -91, JNTU - (FDE) -92, 0U - MBA -Sep. 99]

D, D D, D, Supply
S, 19 80 50 10
S 70 30 40 60

S 40 70 20 18
Demand 7 14 34

Answer : 19x5+30 x2 + 30x6+ 40 x 3+70 x 4 +20 x 14= 1015

9. Find the optimum solution to the following transportation problem in which
the cells contain the ransportation cost in rupees :
W, Available
Wy Ws W;
7 6 4 5 9 40
8 5 6 30
6 20

f 5 7 7 6 10

Required 30 30 15 20

Answer : 7 x30 +6x 10 +5x 20 +6x 10 +9x5+6x 15 +8 x5+6x5= 695

10. Find IBFS by matrix mínium method to the following TP, each cells value
being the unit profit, and find the corresponding profit. Also compare your
results by any other method. [oU- MBA 90]
D D Dg D4 D Avail.
34 55 47 24 32 250
4I 28 32 46 51 150
20 31 35 47 50 175
53 35 26 28 39 125

Req 130 280 110 60 120 700

Answer : 34 x 130 +55 x 120+ 28x150+31 x 10+ 35 x 110
+47x 155 + 28 x 5 + 39 x 120 =26785
11. Find IBFS to the following TP using WwC, VAM and LCEM, each cell value
being cost, and find cost. [OU- MBA 91]
D, D, D, D4 D, Avail.
O, 17 12 20 300
16 10 15 14 180
18 19 11 12 145
13
04 15 14 16 15 130
Req 200 250 150 80 120
Aneuer: 17 x 200 +1lx 100
+9x 150+ 10x 30 + 9x 120 + 11 x
25+ 16x 55 = 8385
 273
Operations Research :Theory and Practice Transportation Problem profit
transportation problem. Fiven theMBAunit
-May 95]
12. Find the initial basic feasible solution to the following to the following
16. Find the IBFSVogel's
[oU-
cost matrix T.Pusing VAM given the approximation method.
fou- MBA - Sep 2001, May 92 Matrix. Using B C Supply
Factory
D, D D, D. Supply Fl 10 8
F, 20 25 10 7
28 81 300 10 7
Fo
9 7
32 28 32 41 180 F 11
14 10
Fs 18 $5 24 32 10 FA 12
Demand 10 Vogel's
Demand 150 40 180 170
transportation problem using
for the followingwith the result of NWC.
13. Solve the following transportation problem using matrix minimum methods 17. Find an IBFS method. Compare [oU-MBA Apr. 98, Sep. 99, May
95]
each cell vahue being the ünit profit. [ou - MBA - Sep. 2000] approximation
D, D D, D4 D; Supply D, D4 Avail.
D, D
F 1 4 4 |60 100 50
F 190 300 500
2 3 35 300 400 600 100
Fa 700 200150
4 |40 100 600
5 Fs 400
70 140
Demand 45 20 18 30 135 50 80
22 Req
at Nizamabad and
company has two centers specifications,
14. Acompany has four factories situated in different locations and five ware houses manufacturing but at
unit) is given below 18. A garment where it manufactures special skirts of same
in different itites. The matrix of transportationcost (Rs. per(units) of the ware Hyderabad of 2500 skirts at cost of
and the requirement centre has a Hvderabad it can produce 2100 skirts
with capacity (unities) as factories (OU- MBA - Apr. 94] varying costs. Nizamabad whilethat at
houses. production as Rs. 23/- per skirt
boutiques are willing to purchase
these skirts with the
Four as 39,
Req. @Rs. 25/- requirements as 1800, 2300, 550 and 1750 and ofer the prices
per skirt.
Ware
House
I III IV
(Units) maximum cost (in rupees) of the shipping one skirt from
37, 40 and 36 respectively. The that from
150 boutigques is 6, 8, 11 and 9 whiledistribution
4 6
Nizamabad center to the four
respectively. Determine the optimal
B 9 5 8 50 Hyderabad is 12, 6, 8 and 5 manufacturer. [1GNOU (NCA) DEC 97, JULY
99]
oo o
7 40 arrangement for the garment
5 matrixas folows,
can be formulated intoa TP
C
D 5 8 6 3 60 Hint: The above information Cap. Mig. Cost
6 8 200 Boutiques
7
2 23
36- 23 -9= 2500
Capacity 80 120 100 37- 23-8= 40-23 -ll=
100 Nizamabad 39- 23 -6= 4
Ünits 6 6
2100 25
@Rs. 23/ 10
solution by matrix method. 40- 25-8= 36- 25-5=
Find initial basic feasible the following ransportation
problem Hyderabad 39- 25 -12 = 37- 25-6= 6
the initial basic feasible solution to entry methqdu - MBA - Feb. 93, Sep. 99] @Rs. 25 6
1750 4600
15. Find matrix, using least cost 1800 2300 550 6400
given the unit cost Supply
Req
Ds D4 D; 40
36
D; D 37
70 50 Sales Price 39
(production) capacity 18OO and
20 28
55
proceed with reating a dummy rowisofnon-standard, hence proceeu y
25 100 [Then that the given problem
36 40 44 zero as cellcots. Noticeor subtracting from highest.]
Og 48 48 150 assigning negative sign
22 45
55
O, 35 80
50 40
100 70
Demand