North West Corner Rule (NWCR)

Q1.Obtain the Initial Basic Feasible Solution to a TP , whose cost and requirements are given:

Origin/Destination       D1         D2              D3          Supply
 O1                              2            7                4              5
 O2                              3            3                1              8
 O3                              5            4                7              7
 O4                              1            6                2             14
Demand                       7            9                18           34

Soln:
STEP I: 
Sum up Demand and Supply ,

Eai=Ebj=34, The given TP is a balanced one and there exists a feasible solution to TP.

STEP II:

-----------------
    5
2         7       4         5
3         3       1         8      
5         4        7        7        
1         6        2        14    
-----------------              
7         9         18

  In this step select the North West corner cell and check its demand and supply, among these two which has the minimum value put it at the top of the NWC  cell. and cancel it . If the supply is the minimum value cancel row other wise cancel column..

----------------
    2
3      3        1       8    
5      4        7        7  
1      6        2        14
--------------
2       9        18

 As in the previous step we have minimum supply we have to reduce the value in   demand , (7-5=2)this becomes the new demand value for the next one.   

----------    
   6              
3        1     6  
4        7      7
6        2      14
---------
9      18

------------
     3
4          7        7
6          2        14
----------
3        18

----
   4
7       4
2      14
---
18

-----
    14
2        14
-----
14

Both demand and supply are the same for a balanced TP.

STEP III:

The solution is given by:

   5
2          7        4

   2          6
3          3         1

               3          4      
5           4         7        

                          14
1           6         2

Finally for the given problem allocate their respective demand and supply based on  the places where they get strike out.This is IBFS

Total Cost =(2 x 5)+(3 x 2) + (3 x 6)+( 4 x 3)+(7 x 4)+(2 x 14)
                 = 10+ 6+18+12+28+28
                  =Rs.102

Transportation Problem (TP)

• Feasible Solution: Any set of non-negative allocation which satisfies row and column sum is called a feasible solution.
• Basic Feasible Solution(BFS): A feasible solution is called BFS if the number of non-negative allocation is equal to m+n-1, where m- number of rows , n- number of columns
• Non Degenerated Basic Feasible Solution: Any feasible solution of a TP containing m origins and n destinations are said to be Non Degenerated, if it contains m+n-1 occupied cells and each allocation is in independent positions.
• Allocations are said to be independent if it is impossible to form a closed path.
• Closed Path: It means by allowing horizontal and vertical lines and all the corner cells are occupied.

• Degenerated Basic Feasible Solution:If a BFS contains less than m+n-1 non-negative allocations it is said to be degenerated.

OPTIMAL SOLUTION:

It is a feasible solution which minimizes the total cost.

The solution of a TP can be obtained in two stages namely

1. Initial solution
2. Optimal solution

Initial solution can be obtained by any one of the following methods

• North West Corner Rule(NWCR)
• Least Cost Method (LCM) or Matrix Minima Method
• Vogel's Approximation Method (VAM)