Least Cost Method / Matrix Minima Method

Q1.Obtain the initial feasible solution for the following TP using Matrix Minima Method.


                 D1          D2        D3        D4       Supply
O1             1            2            3            4          6
O2             4            3            2            0          8
O3             0            2            2            1         10
Demand     4             6           8             6

Soln:  
STEP I:
Sum up Demand and Supply.
Since Eai=Ebj=24. There exists a feasible solution for TP.

STEP II:
In the Least Cost Method, we have to find out the least value in the given problem and start from there.
In this problem the least value is "0", so start from there,

------------------
1      2      3      4        6
4      3      2      0        8
   4
0      2       2     1       10
------------------
4      6       8      6



-----------------
2        3         4          6
                         6
3         2         0          8
2         2         1          6
------------------
6         8         6

------------
    6
2           3           6
3           2           2
2           2           6
------------
6           8


----------
3        2        2
    0
2         2        6
---------
0         8

Here we have subtracted the demand and supply values , in the previous steps the least values were "0" therefore we did not subtract it .

----
   2
2        2
2        6
---
8

-----
    6
2           6
-----
6

STEP III:
The Solution is given by:

                   6
1             2            3             4
                                 2              6
4              3            2             0
   4               0            6
0               2            2             1


Total Cost = (2 x 6)+(2 x 2)+(0 x 6)+(0 x 4)+(2  x 0)+(2 x 6)
                 = Rs.28

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)