Question

How could an assignment problem be solved using the transportation approach? What condition will make the solution to this problem difficult?

Please give a typed answer and focus on the second part of the question.

Answer 1

Part 1.)

An assignment problem be solved using the transportation approach by considering each demand node having an unit demand and each supply node having an unit supply.(Therefore, both supply and demand of each node is 1 unit respectively).

Part 2.)

The problem with this approach is that the transportation approach requires m+n-1 allocation to be made, where m and n are the number of supply and demand nodes respectively.

But an assignment problem has exactly n assignment for a n*n problem.

This will lead to a degenerate solution for the transportation problem. That is, we will need to make allocate dummy allocations in remaining locations (n-1 allocations will have infinitesimally small or zero allocation). Only then we can apply stepping stone method to improve the solution.

This huge amount of degeneracy involved makes the transportation approach inefficient to solve an assignment problem.

Thus the condition that makes the solution to this problem difficult is the requirement of m+n-1 allocation at each step of the transportation approach.