Transportation Problem

Matrix Minimum Method

Matrix minimum (Least cost) method is a method for computing a basic feasible solution of a transportation problem, where the basic variables are chosen according to the unit cost of transportation. This method is very useful because it reduces the computation and the time required to determine the optimal solution. The following steps summarize the approach.

Steps

1. Identify the box having minimum unit transportation cost (c_ij).
2. If the minimum cost is not unique, then you are at liberty to choose any cell.
3. Choose the value of the corresponding x_ij as much as possible subject to the capacity and requirement constraints.
4. Repeat steps 1-3 until all restrictions are satisfied.

Example 1

Consider the transportation problem presented in the following table:

Solution.

We observe that c₂₁ =2, which is the minimum transportation cost. So x₂₁ = 20. The demand for the first column is satisfied. The allocation is shown in the following table.

Table 1

Factory	Retail Shop				Supply
	1	2	3	4
1	3	5	7	6	50
2		5	8	2	75  55
3	3	6	9	2	25
Demand	20	20	50	60

Now we observe that c₂₄ =2, which is the minimum transportation cost, so x₂₄ = 55. The supply for the second row is exhausted.

Table 2

Factory	Retail Shop				Supply
	1	2	3	4
1	3	5	7	6	50
2		5	8		75
3	3	6	9	2	25
Demand	20	20	50	60 5

Proceeding in this way, we observe that x₃₄ = 5, x₁₂ = 20, x₁₃ = 30, x₃₃ = 20. The resulting feasible solution is shown in the following table.

Final Table

Factory	Retail Shop				Supply
	1	2	3	4
1	3			6	50
2		5	8		75
3	3	6			25
Demand	20	20	50	60

Number of basic variables = m + n –1 = 3 + 4 – 1 = 6.

Initial basic feasible solution

The total transportation cost associated with this solution is calculated as given below:
20 X 2 + 20 X 5 + 30 X 7 + 55 X 2 + 20 X 9 + 5 X 2 = 650.