Initial Basic Feasible Solution (IBFS) If number of occupied ce

Methods of Initial Solution

1. North West Corner Method (NWCM)

30
Problem 1. National oil company has three refineries and four depots. Transport
requirements are follows and find the IBFS by NWCM. 40

D1 D2 D3
5 7 13
R1

R2 8 6 14

12 10 9
R3
40

Demand 30 0 60 70

20

Supply = Demand = 200===> It is ba

20 30

D2 D3 D4
R1 7 13 10
R2 6 14 13
R3
30 10 9 11
Demand 60 20 70 40
40

40 30 40 40
D2 D3 D4
R2 6 14 13
 R3 10 9 11
30 40
20 0 2030 70 40
40 40

D3 D4
R2 14 13 30
R3 9 11 80
70 40

D3 D4
R3 9 11 80
30
40 40

50 D1 D2 D3
R1 5 7 13
R2 8 6 14
R3 12 10 9
30
Demand 30 60 70

Total Transportation Cost = cost* qu

30

Least Cost Method

Problem
10 2. Find the initial basic solution by least cost metho

M1 M2 M3
40 P1 6 4 9
60
 40
60
P2 20 6 11

P3 7 1 0

7 1 12
P4
Demand 110 30 50 ,0

M1 M2 M4
P1 6 4 1
P2 20 6 3
P4 7 1 6
Demand 110 30 30, 0

M1 M2 Supply
P1 6 4 10
P2 20 6 40
P4 7 1 90, 60
Demand 110 30, 0

M1 Supply
P1 6 10, 0
P2 20 40
P4 7 60
Demand 110, 100

P2 20 40
P4 7 60, 0
Demand 100, 40
Problem 3. Determine the intial solution by least cost and NWCM

D1 D2
19 30
P1

P2 70 30

P3 40 10
Requirement 5 8
umber of occupied cells = m+n-1 (Row +Column - 1)

30 30

four depots. Transportation costs per ton, capacities and

40

D4 Supply For IBFS,

70 40
10
No. of occupied cells = m +n -1
50
13
80
11
40
200
200 Total Transportation Cost=

and = 200===> It is balanced TP

Supply
40 0
50
80

Supply
50
 80

D4 Supply
10 70
13 50
11 80
40 200
200

1770

rtation Cost = cost* quantity

1770

n by least cost method.

M4 Supply
1 40 10
 3 40
14 50 0
90
6
60
30
220
1340

Supply
40, 10
40
90

1340
y least cost and NWCM method
Availabilit
D3 D4 y
7
50 12

40 60 10

60 20 8
7 5
s = m +n -1

n Cost=
Vogel's Approximation Method (VAM)

Problem1. Find the initial basic feasible solution by VAM

Warehouses
I II III Supply
A 40 10
7 8 5 50 10 0
Plants B 40
10 6 4 40 0
C 50 10
20 8 9 60 10
Demand
40 0 50 0 60 50 10 0 150
P1 3 2 1
P2 x 2 1
P3 x 2 5

Problem 2. Find initial solution by using VAM

D1 D2 D3 D4
5 2
S1 19x 30x 50x 12x
7 2
S2 70x 30x 40 60

8 10
S3 40x 70x 20x
8x
Demand 5 0 8 7 14 4 2
P1 21 22 10 8
P2 21 X 10 8
P3 x x 10 8
 Supply = Demand = 150
P1 P2 P3 Therefore the given TP is a balanced

2 3 x Check the condition of IBFS

2 2 2 No. of occupied cells = m +n -1

1 1 1 5 =3+3-1

5=5
So we can say that the obtained sol is an IBFS.
Total TC = 7x40 +5x10 +4x40+8x50+9x10
Total TC= Rs. 980

Supply P1 P2 P3
2
7 2
7 7 38
2
9 2
10 20 20
10
18 10
12 20 50 6 = 3+4-1
34 6=6

Total TC = Rs. 783

= Demand = 150
en TP is a balanced TP

d sol is an IBFS.
 Unbalanced Transportation Problem
Unbalanced Transportation Problem
when supply is not equal to demand,it is called unbalanced TP and we will add a dum

Problem 1.
W1 W2 W3
∈
F1 42 48 38
80 10
F2 40 49 52
90 100
F3 39 38 40

Requirement 80 90 0 110
P1 1 10 2
P2 1 10 2
P3 1x 2
P3 x x 2
Supply ===> rows
Demand===> Columns

Degeneracy Problem: If No. of occupied cells <

To remove the degeneracy, We will allocate a very small quantity Epsilo

Problem2. Solve the following transportation problem by VAM

D1 D2 D3
25 2 ∈
O1
8 10 7
O2 40
12 9 4
 O3 30
9 11 10
Demand
25 32 40
Penalty 1 1 3

Optimality test : MODI Method

Step1 . Consider all ocuupied cells with its cost and unocuppied cells w

Occupied Cells

8 10 7

* * 4

* 11 *
Vj v1 v2 v3

Cij = Ui +Vj (i= row, j= column)

* * *
For Unoccupied
Cells 5 7 *
9 * 8

8 10 7

Step 4. Cosider all the unoccupied cells with its cost and we will calcula
 * * *
7 2 *
0 * 2
Vj

∆24=𝐶24 −(𝑈2+𝑉4)= 7 -(-3 +6) = 4

∆34=𝐶34 −(𝑈3+𝑉4)⇒8 −(1+6)= 1

Since all delta ij are positive and zero, no need to go for further steps an
the optimum solution and the optimum cost would be Rs. 848.
TP and we will add a dummy row/column with the required quantity and with zero cost.

W4 (Dummy) Capacity P1 P2 P3 P4
160
37 0 160 37 1 1 1
60
51 0 150 90 10 40 9 11 1

43 0 190 100 38 1 1 3

160 60 0 500
6
6x Condition of IBFS
6x 6 = 3+5-1= 7 (Which is not equal)
6x We have allocated a small quantity in next least cost cell to
remove ethe degeneracy
Again, we will check No of occupied cell = m+n-1
7 = 3+5-1 =7

Total TC = 17060

of occupied cells < m+n-1, it is called as degeneracy in TP.

ery small quantity Epsilone(approx =0) to the next unoccupied least cost cell

oblem by VAM

D4 Supply Penalty For IBFS

23
6 50 1

7 40 3 Degeneracy occurs
 8 30 1 To rempove it ,we will allocate epsilone to

23 (O1, D3) or (O2, D4). Let us allocate to (O1, D

1 Now, 6 =6
Total TC=

and unocuppied cells will be represented by dash

25*8+10*2+7
*∈+23*6+4*4
0+11*30

Ui 848

6 u1 8 = u1+v1 Put u1 = 0

* u2 10 = u1+v2 v1 =8, v2 =10,v3= 7, v4 =6

* u3 7 = u1+v3
v4 6 = u1+v4
4 = u2+v3 u2= -3
ow, j= column) 11 = u3+v2 u3 = 1

* 0

3 "-3
7 1

cost and we will calculate opportunity cost

Ui
 *
4
1

o go for further steps and we can consider the solution obtained by VAM is
uld be Rs. 848.
h zero cost.
∈

Supply = 500 not equal to Demand= 440

It is an unbalanced TP

We will add a dummy column with zero cost and 60 units

For IBFS

ast cost cell to

5 not equal to m+n-1

5 3+4-1=6 ∈
ate epsilone to

allocate to (O1, D3)

Rs. 848

Closed Path Loop: Start from an unoccupied cell, take the turn from
1 Balance/unbalance

2 VAM

2 Degeneracy

3 Remove
4 Total TC
l, take the turn from occupied cell and come back to the starting point.
nce/unbalance
Problem 2. Test the optimality of following initial solution obtained by VAM

D1 D2 D3 D4 Supply
S1 19 5 30x 50 12 2 7
S2 70 7 2
30x 40 60 9
S3 40 8x 70 20 10 18
8
Deman5 8 7 14 34

Step 2. Unoccupied cells

D1 D2 D3 D4 Ui
S1
S2
S3
Vj

∆𝒊𝒋=𝑪𝒊𝒋−(𝑼𝒊+𝑽𝒋)

∆𝟏𝟐=
∆𝟏𝟑=
∆𝟐𝟏=
∆𝟐𝟐=
∆𝟑𝟏=
∆𝟑𝟑=
Now, we will select the smallest allocation between the negative corner of the loop (From solution obtai
Now Make a new table and keep all the values as it is (VAM table) except the corners of the loop

D1 D2 D3 D4
 S1 19 5 30 50 12 2
S2 70 30 2 40 7 60
S3 6 12
40 8x 70 20
V1 V2 V3 V4
Smalllest allocation was 2 , between negative corners. Subtract this 2 at
negative corners and addd it to positive corners

Now, (S2, D4) will be considered as unoccupied cell

Again calculate U and V, then delta and check whether all delta are positive and
tained by VAM Step1. For occupied cells

D1 D2 D3 D4 Ui
S1
S2
S3
Vj

𝑪𝒊𝒋=(𝑼𝒊+𝑽𝒋)
𝑪

of the loop (From solution obtained by VAM)

t the corners of the loop
 2 U1=0

U2
12
U3

Subtract this 2 at
orners

delta are positive and zero with this new table

Stepping Stone Method
1. Trace the loop from each of the unoccupied cell one by one, assign
sign to each corner(+ and - in alternate order) and check the net changes in the

Problem 2. Test the optimality using stepping stone method of the followi

D1 D2 D3 D4 Supply
S1 19 5 30 50 12 2 7
S2 7 7 2
70 30 40 60 9
S3 10
40 8 8 70 20 18
Deman5 8 7 14 34

1. No.of occupied cells = m+n-1

6 =3+4-1
2. Total TC = Rs. 748
For optimality test by stepping stone method, we will trace loop with each
and we will check whether there is any net change in the cost

19 30 50 12
7
70 30 40 60

40 8 70 20

the table obtained by VAM, and we will select the smallest allocat
it will be subtracted from negative corner allocation and added to
 will remain same.

D1 D2 D3 D4
S1 19 5 30 50 12 2
S2 2 7
70 30 40 60
S3 6 12
40 8 70 20

Degeneracy
total Cost= 747
Again check the net change in the cost

Maximization Case in TP

Check the given TP is maximizing (e. g profit, revenue, production, sales etc)or mi
subtract all the values (except supply and demand ) with largest value in
 −
changes in the cost

hod of the following initial solution obtained by VAM

Step3. Trace a loop from the cell (S1, D2)
D1 D2 D3 D4
S1 19 30 (+) 50 12 (-)
S2 7
70 30 40 60
S3 40 8 (-) 70 20 (+)

Net cost change =+3

e loop with each unoccupied cell one by one

19 30 50 12 30
7
70 30 40 60 -60

40 8 70 20 20
-8
Net -18

smallest allocation between the negative corner of the loop (S2, D2)
n and added to the positive corner of the loop, rest of the allocation
 19 5 30 50 12 2
70 30 2 40 7 60
6 12
40 8 70 20

n, sales etc)or minimizing type, if maximizing type, convert it into minimizing matrix
largest value in the whole table
 Step4.
Cost
Cell change

(S1,D2) 30
(S1, D4) -12
(S3, D2) -8
(S3, D4) 20
Net cost change =+30
 12

mizing matrix
Steps in Transportation Problem

1. Check balanced or unbalanced, if unbalanced , make it balance.

2. Check the given TP is maximizing or minimizing type, if maximizing type, convert
3. Find initial solution by VAM/LCM/NWCM
4. Check the degeneracy (No. of occupied cells < row +column-1)of initial solution
5. If no degeneracy (No. of occupied cells = row +column-1), proceed for step 6.
6. Calculate total transporation cost
7. Test the optimality of above obtained solution (VAM/LCM/NWCM) using MODI or
8. If any delta is negative, again try to improve the solution by tracing the loop (MO
9. After getting the improved solution by MODI or stepping stone (No negative delta
again check degeneracy for this new table and calculate total TC.
ance.
ximizing type, convert it into minimizing matrix

mn-1)of initial solution , if exist, remove it and go to step 6.

proceed for step 6.

NWCM) using MODI or Stepping Stone method

tracing the loop (MODI method)
one (No negative delta or net change in cost)
TC.
After applying MODI method, the improved solution is obtained as follows

F1 F2 F3 Ui
W1 8 50 7 5 50 U1=0
W2 6 100 4 50 8 U2= -2
W3 7 5 6 150 U3=1
V1= 8 V2= 6 V3 = 5

∆𝟏𝟐= 1
∆𝟐𝟑= 5,

∆𝟑𝟏= -2

∆𝟑𝟐= -2
ed as follows

F1 F2 F3
W1 − 7 −
W2 − − 8
W3 7 5 −

F1 F2 F3
W1 8 7 5 100 U1
W2 6 150 4 𝜖 8 U2
W3 7 5 50 6 100 U3

V1 V2 V3
No. of occupied cells 4
m+n-1 3+3-1 5
there is a degeneracy
To remove it, we will allocate epsilone to (W2, F2)
Total TC = Rs. 2250