Lecture_15_Methods for Initial Basic Feasible Solution

15.1 Methods for Initial Basic Feasible Solution
Some simple methods to obtain the initial basic feasible solution are
1. North-West Corner Rule
2. Lowest Cost Entry Method (Matrix Minima Method)
3. Vogel’s Approximation Method (Unit Cost Penalty Method)
North-West Corner Rule
Step 1
? The first assignment is made in the cell occupying the upper left-hand (north-west) corner
of the table.
? The maximum possible amount is allocated here i.e. x11 = min (a1, b1). This value of x11
is then entered in the cell (1,1) of the transportation table.
Step 2
i. If b1 > a1, move vertically downwards to the second row and make the second allocation
of amount x21 = min (a2, b1 - x11) in the cell (2, 1).
ii. If b1 < a1, move horizontally right side to the second column and make the second
allocation of amount x12 = min (a1 - x11, b2) in the cell (1, 2).
iii. If b1 = a1, there is tie for the second allocation. One can make a second allocation of
magnitude x12 = min (a1 - a1, b2) in the cell (1, 2) or x21 = min (a2, b1 - b1) in the cell (2, 1)
Step 3
Start from the new north-west corner of the transportation table and repeat steps 1 and 2 until all
the requirements are satisfied.
1-
Find the initial basic feasible solution by using North-West Corner Rule
1.
W?
F
?
W1
W2
W3
W4
Factory
Capacity
F1 19 30 50 10 7
F2 70 30 40 60 9
F3 40 8 70 20 18
Warehouse
Requirement 5 8 7 14 34
1
Methods for Initial Basic Feasible Solution
Lecture 15
Transportation problem :
( North - West corner rule and matrix minimum method )
Solution
W1 W2 W3 W5 Availability
F1 5 2 (19) (30) 7 2 0
F2 6 (30) 3 (40) 9 3 0
F3 4 (70) 14 (20) 18 14 0
Requirement
5
0
8
6
0
7
4
0
14
0
Initial Basic Feasible Solution
x11 = 5, x12 = 2, x22 = 6, x23 = 3, x33 = 4, x34 = 14
The transportation cost is 5 (19) + 2 (30) + 6 (30) + 3 (40) + 4 (70) + 14 (20) = Rs. 1015
2.
D1 D2 D3 D4 Supply
O1 1 5 3 3 34
O2 3 3 1 2 15
O3 0 2 2 3 12
O4 2 7 2 4 19
Demand 21 25 17 17 80
Solution
D1 D2 D3 D4 Supply
21 13
O1 (1) (5) 34 13 0
12 3
O2 (3) (1) 15 3 0
12
O3 (2) 12 0
2 17
O4 (2) (4) 19 17
Demand
21
0
25
12
0
17
14
2
0
17
0
The transportation cost is 21 (1) + 13 (5) + 12 (3) + 3 (1) + 12 (2) + 2 (2) + 17 (4) = Rs. 221
2
Initial Basic Feasible Solution
x11 = 21, x12 = 13, x22 = 12, x23 = 3, x33 = 12, x43 = 2, x44 = 17
The transportation cost is 21 (1) + 13 (5) + 12 (3) + 3 (1) + 12 (2) + 2 (2) + 17 (4) = Rs. 221
3.
From To Supply
2 11 10 3 7 4
1 4 7 2 1 8
3 1 4 8 12 9
Solution
From To Supply
3 1
(2) (11) 4 1 0
2 4 2
(4) (7) (2) 8 6 2 0
3 6
(8) (12) 9 6 0
Demand
3
0
3
2
0
4
0
5
3
0
6
0
Initial Basic Feasible Solution
x11 = 3, x12 = 1, x22 = 2, x23 = 4, x24 = 2, x34 = 3, x35 = 6
The transportation cost is 3 (2) + 1 (11) + 2 (4) + 4 (7) + 2 (2) + 3 (8) + 6 (12) = Rs. 153
Demand 3 3 4 5 6