Transportation Problem
We will cover following topics
Transportation Problem
The transportation problem is a special type of linear programming problem, where the objective is to minimize the cost of distributing a product from a number of sources to a number of destinations.
Mathematical Formulation of the problem
If \(x_{ij} (\geq 0)\) is the number of units shipped from \(i^{th}\) source to jth destination, then equivalent LPP model will be
Minimize \(Z = \sum_{i=1}^{m} \sum_{j}^{n} c_{ij} x_{ij}\)
Subject to
\(\sum_{j=1}^n x_{ij} \leq a_i\) for \(i=1, 2 \cdots m\) (Supply)
\(\sum_{j=1}^m x_{ij} \leq b_j\) for \(i=1, 2 \cdots n\) (Demand)
\[x_{ij} \geq 0\]For a feasible solution to exist, it is necessary that total capacity equals total to the requirements. If \(\sum_{i=1}^n a_i = \sum_{j=1}^m b_j\), i.e., if total supply = total demand then it is a balanced transportation problem otherwise it is called unbalanced Transportation problem. There will be \((m + n - 1)\) basic independent variables out of \((m \times n)\) variables.
Underlying Assumptions
1) Only a single type of commodity is being shipped from an origin to a destination.
2) Total supply is equal to the total demand.
\(\sum_{i=1}^n a_i = \sum_{j=1}^m b_j\), \(a_i\) (supply) and \(b_j\) (demand) are all positive integers.
3) The unit transportation cost of the item from all sources to destinations is certainly and preciously known.
4) The objective is to minimize the total cost.
Solution of a Transportation Problem
The transportation peoblem can be solved by first finding the initial basic feasible solution and then by finding the optimal solution.
Initial Basic Solution
The initial basic solution can be found by either of three below methods:
i) North West Corner Rule
ii) Matrix Minima method
iii) Vogel Approximation method (VAM)
Optimal Solution The optimal solution can then be found by Modified Distribution Method (MODI Method)
Optimal Solution
The optimal solution can be found by Modified Distribution Method (MODI Method).
Modified Distribution Method (MODI Method): The modified distribution method, also known as MODI method or \((u - v)\) method provides a minimum cost solution to the transportation problem. In MODI method, only closed path for the unoccupied cell with highest opportunity cost is drawn.
Steps to find an optimal solution usnig Modi Method
1) Determine an initial basic feasible solution using any one of the three methods given below:
a) North West Corner Rule
b) Matrix Minimum Method
c) Vogel Approximation Method
2) Determine the values of dual variables, ui and vj, using ui + vj = cij
3) Compute the opportunity cost using ∆ij= cij – ( ui + vj ).
4) Check the sign of each opportunity cost.
a) If the opportunity costs of all the unoccupied cells are either positive or zero, the given solution is the optimal solution. On the other hand,
b) if one or more unoccupied cell has negative opportunity cost, the given solution is not an optimal solution and further savings in transportation cost are possible.
5) Select the unoccupied cell with the smallest negative opportunity cost as the cell to be included in the next solution.
6) Draw a closed path or loop for the unoccupied cell selected in the previous step. Please note that the right angle turn in this path is permitted only at occupied cells and at the original unoccupied cell.
7) Assign alternate plus and minus signs at the unoccupied cells on the corner points of the closed path with a plus sign at the cell being evaluated.
8) Determine the maximum number of units that should be shipped to this unoccupied cell. The smallest value with a negative position on the closed path indicates the number of units that can be shipped to the entering cell. Now, add this quantity to all the cells on the corner points of the closed path marked with plus signs, and subtract it from those cells marked with minus signs. In this way, an unoccupied cell becomes an occupied cell.
9) Repeat the whole procedure until an optimal solution is obtained.
Degeneracy in Transportation Problem
If the basic feasible solution of a transportation problem with \(m\) origins and \(n\) destinations has fewer than \((m + n – 1)\) positive \(x_{ij}\) (occupied cells), the problem is said to be a degenerate transportation problem.
Degeneracy can occur at two stages:
i) At the initial solution
ii) During the testing of the optimal solution
To resolve degeneracy, we make use of an artificial quantity (d). The quantity d is assigned to that unoccupied cell, which has the minimum transportation cost.
PYQs
Transportation Problems
1) Find the initial basic feasible solution to the following transportation problem by Vogel’s approximation method. Also, find its optimal solution and the minimum transportation cost.
\[\begin{array}{|c|c|c|c|c|}\hline & {D_{1}} & {D_{2}} & {D_{3}} & {D_{4}} & {\text { Supply }} \\ \hline O_{1} & {6} & {4} & {1} & {5} & {14} \\ \hline O_{2} & {8} & {9} & {2} & {7} & {16} \\ \hline O_{3} & {4} & {3} & {6} & {2} & {5} \\ \hline {Demand} & {6} & {10} & {15} & {4} & {} \\ \hline\end{array}\][2014, 20M]
2) By the method of Vogel, determine an initial basic feasible solution for the following transportation problem. Products \(P_{1}\), \(P_{2}\), \(P_{3}\) and \(P_{4}\) have to be sent of destinations \(D_{1}\), \(D_{2}\) and \(D_{3}\). The cost of sending product \(P_{i}\) to destinations \(D_{j}\) is \(C_{i j}\), where the matrix:
\(\left[C_{i
j}\right]=\left[ \begin{array}{cccc}{10} & {0} & {15} & {5} \\ {7} & {3} & {6} & {15} \\ {0} & {11} & {9} & {13}\end{array}\right]\)
The total requirements of destinations \(D_{1}\), \(D_{2}\) and \(D_{3}\) are given by 45, 45, 95 respectively and the availability of the products \(P_{1}\), \(P_{2}\), \(P_{3}\) and \(P_{4}\) are respectively 25, 35, 55 and 70.
[2012, 12M]
3) Determine an optimal transportation programme so that the transportation cost of 340 tons of a certain type of material from three factories to five warehouses \(W_{1}\), \(W_{2}\), \(W_{3}\), \(W_{4}\), \(W_{5}\) is minimized. The five warehouses must receive 40 tons, 50 tons, 70 tons, 70 tons and 90 tons respectively. The availability of the material at \(F_{1}\), \(F_{2}\), \(F_{3}\) is 100 tons, 120 tons, 120 tons respectively. The transportation costs per ton factories to warehouses are given in the table below:
\(\begin{array}{|c|c|c|c|c|}\hline W_{1} & {W_{2}} & {W_{3}} & {W_{4}} & {W_{5}} \\ \hline F_{1} & {4} & {1} & {2} & {6} & {9} \\ {F_{2}} & {6} & {4} & {3} & {5} & {7} \\ {F_{3}} & {5} & {2} & {6} & {4} & {8} \\ \hline\end{array}\)
Use Vogel’s approximation method to obtain the initial basic feasible solution.
[2010, 30M]
4) Solve the following transportation problem by finding the initial solution by matrix minima method.
\(\begin{array}{|c|c|c|c|c|c|c|}\hline & {D_{1}} & {D_{2}} & {D_{3}} & {D_{4}} & {D_{5}} & {D_{6}} & {\text { Availability }} \\ \hline F_{1} & {2} & {1} & {3} & {3} & {2} & {5} & {50} \\ \hline F_{2} & {3} & {2} & {2} & {4} & {3} & {4} & {4} \\ \hline F_{3} & {3} & {5} & {4} & {2} & {4} & {1} & {60} \\ \hline F_{4} & {4} & {2} & {2} & {1} & {2} & {2} & {30} \\ \hline \text { Demand } & {30} & {50} & {20} & {40} & {30} & {10} & {180} \\ \hline\end{array}\)
[2008, 30M]
5) A company has 3 factories \(A\), \(B\) and \(C\) which supply units to warehouses \(X\), \(Y\) and \(Z\). Every month the capacities of the factories per month are 60, 70 and 80 units \(A\), \(B\) and \(C\) respectively. The requirements of \(X\), \(Y\) and \(Z\) are 50, 80 and 80 respectively. The necessary data in terms of unit transportation cost in rupees, factory capacities and warehouse requirements are given below:
\[\begin{array}{|c|c|c|c|c|}\hline {}&{X} & {Y} & {Z} & { } \\ \hline A & {8} & {7} & {5} & {60} \\ \hline B & {6} & {8} & {9} & {70} \\ \hline C & {9} & {6} & {5} & {80} \\ \hline { }&50 & {80} & {80} & {210} \\ \hline\end{array}\][2002, 15M]
6) A manufacturer has distribution centers at Delhi and Chennai. These centers have available 30, 50 and 70 units of his product. His four retail outlets require the following number of units:
\(A,30\); \(B,20\); \(C,60\); \(D,40\). The transportation cost per unit in rupees between each center and outlet is given in the following table:
\(\begin{array}{|c|c|c|}\hline \text { Distribution Centers } & {\text { A }}&{B}&{C}&{D} \\ \hline \text { Delhi } & {10} & {7} & {3} & {6} \\ \hline \text { Kolkata } & {1} & {6} & {7} & {3} \\ \hline \text { Chennai } & {7} & {4} & {5} & {3} \\ \hline\end{array}\)
Determine the minimum transport cost.
[2001, 20M]