Lecture_16_Methods for Initial Basic Feasible Solution

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

2 - Lowest Cost Entry Method (Matrix Minima Method)

Step 1
Determine the smallest cost in the cost matrix of the transportation table. Allocate xij = min (ai, bj) in the cell (i, j)

Step 2
• If xij = ai, cross out the ith row of the table and decrease bj by ai. Go to step 3.
• If xij = bj, cross out the jth column of the table and decrease ai by bj. Go to step 3.
• If xij = ai = bj, cross out the ith row or jth column but not both.
Step 3
Repeat steps 1 and 2 for the resulting reduced transportation table until all the requirements are satisfied. Whenever the minimum cost is not unique, make an arbitrary choice among the minima.