Concepts & Steps of Operations Research April 2014 Exam Transportation Problems

Steps –

1. Take Dummy (if required) for balancing the problem & then convert in Regret matrix (if required) if it is a Maximization problem.
2. If there is any Restriction or Prohibition, convert it in M.
3. Find IFS. If the method for IFS is specified in question, use only that method. But if any method is not specified, VAM is preferable. (It will reduce your work when you test for Optimality using MODI).
4. After finding IFS, MODI begins. Find “U & V” values from allocations.
5. Then for empty cells, find Opportunity costs (Delta ∆). If any Delta is/are Positive, solution is not optimal. But if all Delta are Negative or zero, solution is optimal.
6. If any Delta is Positive, start a loop from maximum Positive delta. E. g. if there are two Positive delta (5 and 2), then start loop from 5. Not from 2.
7. Then write next table. Again find new “U, V, and Delta”. Repeat from Step no. 5.

A Transportation problem is Supply and Demand problem. There are some supply centres e. g. plants. And there are some demand centres e. g. warehouses or distribution centres.

Supply at each plant is given. Demand at each warehouse is given. And unit cost of transportation from each Supply centre to each Demand centre is given.

The solution of a Transportation problem is a two step process.

Step 1:                        To find Initial Feasible Solution (IFS). For this we can use any method, say – Vogel’s Approximation method (VAM), Least Cost method (LCM) or North West Corner Rule (NWCR).

But VAM is supposed to be the best method, because it gives IFS which is very near to the Optimal (Final) solution.

Step 2:                        From the IFS, to find the Optimal solution. The IFS may or may not be Optimal. If the IFS is not Optimal, then it can be improved to give a better result. This process of Testing & Improving the IFS is called Modified Distribution Method (MODI).

For IFS, there are many methods, but for Optimal solution there is only one method – MODI.

Note:   Sometimes, in examination problem, IFS is already given (some solution is given). And you are asked, whether it is an Optimal solution. In that case, do not find a new IFS by VAM or any other method. Directly apply MODI method. First, test the given solution. If it is Optimal, OK. If not Optimal, improve it and find actual Optimal solution.

Concepts: 

1. The Transportation problem can be Balanced or Unbalanced problem.

A Balanced problem means total supply is equal to total demand, e. g. if total supply is 400 units and total demand is 400 units then it is balanced.

Where as, an Unbalanced problem means total supply is not equal to total demand. E. g.  if total supply is 400 units and total demand is 350 units, it is not balanced. Then first we need to balance the problem by taking a Dummy. (imaginary quantity). Hence, a Dummy will come on Demand side. Dummy quantity will be 50 (400 – 350 = 50).

2. Dummy:

A Dummy is an imaginary quantity. The purpose of Dummy is to balance the problem. Since the Dummy is imaginary, all unit costs (or unit profits) for Dummy are always zero. Dummy can come as Supply or Demand, depending on problem. If Supply is less, Dummy will come in Supply side. If Demand is less, Dummy will come in Demand side.

3. The Transportation problem can be of Minimization type or Maximization type.

A Minimization Transportation problem involves cost data. The objective of solution is to minimize the total cost.

A Maximization Transportation problem involves sales, revenue or profit data. The objective of solution is maximization of total profit. We need to first convert the Maximization problem in Minimization problem. This conversion is called Regret matrix.  From the original profit values, we find out the highest profit value. From this highest profit, we subtract all profit values. The resulting matrix is Regret matrix. Then we solve it as a normal transportation problem.

Note:

1. But for calculating the final schedule, you must multiply quantity by original profit value. And not by Regret value.
2. In case of Unbalanced Maximization problem, first take Dummy. Dummy profit = 0.

Then convert in Regret matrix. Now, if highest profit in the problem is 21, then Regret for Dummy = 21 – 0 = 21.

4. Prohibited or Restricted problem:

A Prohibited problem is the one in which there are one or more restrictions. E. g. say from Plant ‘A’ it is not possible to transport any quantity to Warehouse ‘Y’. This is a prohibited problem

Then we assign a very high or infinite cost (represented by M) to “Plant A – Warehouse Y” and proceed with solution. Throughout the solution steps, M does not change. Since M is infinity, no quantity or allocation is possible in M.

Even in case of Maximization problem, if there is Restriction, we take profit as M. When we convert to Regret matrix, M remains as M.

The solution of a balanced Transportation Problem of Minimization is divided in two parts –

In part one we find out an initial solution to the given Transportation Problems. This is known as Initial Basic Feasible Solution (I.B.F.S.)

In part two we test the IBFS for optimality           

Part I :-

There are six different methods to find out an IBFS.

1.      North-West Corner Rule (NWCR)

2.      South-East Corner Rule (SECR)

3.      Row Minima Method (RMM)

4.      Column Minima Method (CMM)

5.      Matrix Minima Method (MMM) or Least cost Method (LCM) or Inspection Method.

6.      Vogel’s Approximation Method (VAM) or Vogel’s Method of Penalty.

Steps for Vogel’s Approximation Method :

1.      Calculate penalty for each row and each column. Penalty is the difference between the least cost and the next least cost in each row and each column.

2.      Identify the row or the column with the maximum penalty.

3       In the identified row or column, select the cell with the least cost and allocate maximum possible number of units as per the RIM conditions.

4.      Eliminate the Row or Column which is fully exhausted and recalculate the penalties.

5.      Repeat Step-2 to Step-4 until all the Rows and Columns are exhausted.

Part II :-

Test for optimality –

There are two pre conditions for an optimal solution –

1.      Number of occupied cells should be equal to m + n – 1 [i.e. Total of number of row + total of number of columns – 1]

2.      They should be at independent position.

If the above two conditions are satisfied we apply the modified distribution method [MODI’s algorithm] or the UV Method.

Closed Loop –

1.      A closed loop consist of horizontal and vertical lines starting from and ending on an unoccupied cell.

2.      All the vertex or the corner points should be occupied cells except the starting vertex.

3.      For any given Transportation Problem we can form only one loop for an unoccupied cell.

Degeneracy in the solution of a Transportation :

When the number of occupied cells in the solution of a Transportation Problem becomes less than m + n – 1 [where m = number of row and n = number of columns], the solution is known as a degenerate solution. [i.e. it cannot generate an optimum solution].

To resolve the degeneracy, we transfer Epsilon i.e.         quantity, In any of the non occupied cells in such a way that the occupied cells should be in an independent position i.e. occupied cells should not form a closed loop. Epsilon is a negligible quantity.

Explain unbalanced transportation problem.

(i)  When supply capacity of sources and requirement (demand) of destinations do not match a transportation problem is said to be unbalanced. An unbalanced problem can not be processed. (ii) To eliminate imbalance, a dummy source or destination is created and shortfall in terms of supply or demand is allocated to dummy.

Explain Prohibited transportation problem.

Ans.    ‘Allocations to minimum cost route’ is the principle which prevents allocation to prohibited routes when we designate “M’ (maximum cost) to the prohibited route. In many practical solutions, some of the routes in a transportation are prohibited due to certain operational problems such as flood situation, road conditions, government restrictions can be handled for solving transportation problem by converting these operational problems in to the mathematical problem by assigning a very high cost of transportation to these prohibitive routes to ensure that these routes will not be included in the final optimal solution.

Explain Compare transportation problem and Assignment problem. 

Ans.   

Explain Independent cells in a Transportation Problem. 

Ans.    (i) Independent cells are those which do not form a closed loop with other occupied cells. (ii) An infinitesimally allocation i.e. epsilon is added  to an empty independent cell which carries lowest transportation cost to eliminate degeneracy.

Explain Looping in Transportation problem.

Ans.    (i) Looping is determining a track for shifting allocated inventory to new cells for modifying the distribution pattern. (ii) Determining the looping track and shifting of inventory is done as per rules of MODI method.

Explain Degeneracy in a Transportation problem.

Ans.    When number of allocations is less then (m + n – 1), an infinitely small allocation called epsilon is added to eliminate the degeneracy. This epsilon is added to an empty cell in the degenerate matrix which is independent with minimum cost. If number of allocations is greater then (m + n – 1) we would notice a closed loop in the matrix which enables us to remove degeneracy.

Explain Sensitivity Analysis in a Transportation Problem.

Ans.    When a solution is obtained its ability to remain optimal when external environment changes is tested in sensitivity analysis. The obtained solution is subjected to sensitivity analysis to determine its sensitivity it changes.

Explain Test for Optimality in Transportation Problem.

Ans.    Optimally test in a transmission problem is carried out on a non-degenerate initial feasible solution to ascertain if the IFS obtained is optimal. Optimally test in a TP is carried out by determining the opportunity costs of all empty cells in a transportation matrix. Nature of the opportunity cost indicates the optimality. There is no other set of transportation route that will reduce the total transportation cost.

UNIVERSITY THEORY QUESTIONS

How to solve Unbalanced Transportation problem of maximization type?(Apr 2002) (Apr 2005)

Transportation is a minimization model. First, we should balance the problem by taking dummy where necessary (i. e. either on Supply side or Demand side). After balancing the problem, we should convert the problem in Minimization by converting it into Regret matrix.

To find Regret matrix, find maximum profit value in the original matrix. From this maximum profit value, subtract all profit values in the matrix. The resulting matrix is Regret matrix.

Explain least cost method to obtain initial feasible solution for a transportation problem. Is this method better than NWCR? Why?(Apr 2002)

In least cost method, we start giving allocations from the minimum cost in the matrix. It means that cell for which cost is minimum is given allocation first. Then allocation is given in next minimum cost and so on. It means lower cost cells are given priority over higher cost cells.

Where as in NWCR, there is no priority to lower cost cells. We start giving allocation from 1^st North West corner, then next North West corner and so on. Hence, generally, the Initial solution obtained by LCM is lower than that by NWCR.

Hence, LCM solution is nearer to the optimal solution as compared to NWCR solution. Hence, LCM is a better method than NWCR.

Prohibited transportation problem. (Apr 2003) (Oct 2005)

In a transportation problem if it is not possible transport any quantity from a Supply centre to a particular Demand centre due to some constraints, it is called Prohibited transportation problem. For the prohibited cell, the unit cost of transportation is put as “M”, which is infinitely high cost.

Since M is infinity, till the end of the solution, M remains as M. It does not change. No allocation can come in that cell.

Compare Transportation problem with Assignment problem (Apr. 2003) (Apr 2004) (Oct 2004) 

Independent cells in a Transportation problem.  (Oct 2003)

Independent cells in Transportation problems mean the cells which do not form a closed loop with Occupied cells (Allocations.) When the Transportation problem is Degenerate (No. of allocations are less than “Row + Columns – 1”), we need Epsilon Є. The Epsilon should be placed in independent cell so that there is no closed loop between Epsilon and other allocations.

Looping in a Transportation problem.  (Apr 2004) 

In transportation problem we get a loop when solution is not optimal. We find delta value (opportunity cost) for each unoccupied cell. Delta = C – (U + V). If any delta is negative, solution is not optimal. In next table there is scope for reducing the cost. Hence, we draw a loop from maximum negative delta. The loop can be a four corner loop or a six corner loop.

Signs at the corner of the loop are: positive (+) sign at starting point and then alternate negative (-) and positive (+) sign at other corners. From this we get new values for the next transportation matrix. Only values at the corner of the loop change. Other values in the matrix remain same.

Restricted transportation problem.  (Oct 2004) 

A transportation problem is called restricted or prohibited when transportation is not possible from a particular source to a particular destination. Cost for that cell may or may not be given in the problem.

We take the cost for the prohibited cell as “M”, which is infinitely high cost. No allocation is possible in the restricted cell.

Various method of finding the Basic Feasible Solution in Transportation problem.  (Oct 2004)

A} Methods based on position of the cells-

1. NWCR North West Corner Rule – Starting the allocations from top left corner (North West corner).

2. SECR South East Corner Rule – Starting the allocations from bottom right corner (South East corner).

These methods are ineffective because they are based on position. They do not take transportation cost into account. Hence, answer found by these methods will give higher cost which is much more than optimal cost.

B} Methods based on cost –

3. LCM Least cost method – In LCM we start allocations from the cell with minimum cost. Then we go to next minimum cost and so on.

4. VAM Vogel’s approximation method – In VAM we calculate penalties for each row and column. Penalty is the difference between two lowest costs in the row or column. We start giving allocations from maximum penalty.

These methods are very effective because they take costs into account. The preference is given to those cells which have lower costs. Hence, the answer is close to the optimal solution.

Degeneracy in a transportation problem. (Apr 2006)

In a transportation problem, degeneracy occurs when the number of Allocations are less than (Rows +Columns – 1), where –

M= number of rows

N=number of columns

This is also called as Rim condition. If rim condition is satisfied, the solution is not degenerate.

But if number of allocations are less than (m + n – 1), then the solution is degenerate. To remove degeneracy, we need to take Epsilon Є which is an imaginary allocation almost equal to zero.

Interpret the meaning of u, v, and delta in MODI method. (Apr 2006)

In MODI (Modified distribution) method, we find u and v values. U and v are cost components on the supply and demand side. We calculate the value of u and v from the allocations.

Formula:          c = u + v OR [ u = c – v and v = c –u ]

From u and v values, we calculate delta (opportunity costs or cell evaluation) for empty cells.

Formula:          Delta = (u +v) – C

If all opportunity costs are either negative or zero, then there is no scope for any further reduction in cost. Hence, the present solution is optimal. But if any opportunity costs are Positive, it indicates possible decrease in cost. The present solution is not optimal.

In that case, we construct a closed loop from maximum Positive delta (opportunity cost). Then we write the next table and again check for opportunity costs.

Sensitivity analysis in transportation problem. (Oct 2006)

Sensitivity analysis in transportation problem can be done with the help of delta (opportunity costs) for empty cells. Delta indicates the change in cost per unit (increase or decrease) if that cell is included in the solution.

Hence, if in an optimal solution, delta for an empty cell is +4 & the unit transportation cost for that cell is 10. Then it means a reduction of at least 4 Rs. is required in the cost if that cell is to enter the solution. Hence, the new cost will be. 10 – 4 = Rs. 6.