The Hindu Business Line : Assignment technique in transportation problems

Compared to the simplex method, assignment and transportation techniques are special purpose algorithms which are useful for solving some types of linear programming problems. The assignment problem itself is a special case of the transportation problem.

Usually for the initial allocation in the case of a transportation problem, methods such as north-west corner rule, Vogel’s approximation method and least cost entry method are used. For the purpose of optimality the MODI check is carried out finally.

A specific condition is that the number of allocations should always equal m+n-1, where m=number of rows and n=number of columns.

An interesting feature of the transportation problem arises in the case of initial allocation through the assignment technique. Consider a situation where the data constitute selling price, cost of production and shipping costs. If the objective is to maximise it can be shown that each data can be construed separately as a transportation problem — that is, maximise selling price, minimize cost of production and minimise transportation costs.

If the selling price and the cost of production are uniform to each column and row respectively, and the transportation costs are different it can be further shown that the solution obtained for the allocation of the transportation cost individually will also be the solution for the selling price as well as the cost of production, taken independently or collectively, that is, selling price minus cost of production.

This is because of the fact that application of the assignment technique in case of selling price minus cost of production results in a constant difference and ultimately will lead to zero in the case of each cell. If all the cells are zero there are any number of solutions.

A problem to solve

A company has four factories situated in four different locations in the country and four sales agencies located in four other locations. The cost of production (rupees per unit), the sales price (rupees per unit) and shipping costs (rupees per unit) in the cells of the matrix, and monthly capacities and monthly requirements are given in Table 1. Find the monthly production and distribution schedule, which will maximise profit.

In this problem, the usual procedure is to compute the profit for each of the sales agency corresponding to the factory.

For example, for Factory A and sales agency 1, the profit will be Rs 20 -(10+7) = Rs 3. By applying Vogel’s approximation method and MODI check, the optimal solution (Chart 2) is obtained. It may be noticed that a minimum of two iterations are necessary to arrive at the optimal solution.

assignment technique

As already stated, the optimal allocation is found only with respect to the transportation cost. Applying the assignment technique, the final cost matrix is obtained (Chart 3).

After the column operation, it can be noticed that element zero is found in six places. Out of which, cells R1C2, R2C4, R3C1, R3C3 and R4C4 can be allocated with the quantity 10, 15, 8, 12 and 7 respectively. To satisfy the total condition of m+n-1, it is necessary to allocate in two more cells, with the next least cost.

In this case the least cost is one which could be found in cells R4C2 and R4C3 which requires to be allocated. The balance quantity of two as well as six will be allocated in these cells.

This solution will obviously be optimal since the allocation happens to be through the element zero and the next least cost one, which is normally the basic property of any assignment model.

As already seen, the solution is optimal, with the transportation cost being Rs 245.

Simple accounting equation suggests that the net profit equals selling price minus cost. This aspect can be seen in the above problem. Since the selling price remains constant for each sales agency individually, the cost of production constant for each factory, the total sales equals Rs 1,270 (Rs 20 x 8 + 22 x 12 + 25 x 18 + 18 x 22) and the cost of production equals Rs 870 (Rs 10 x 10 + 15 x 15 + 20 x 16 + 15 x 15). The transportation cost is Rs 245 and the net profit equals Rs 155, which was the solution obtained initially.

Application of assignment technique results in the elimination of a constant figure from each of the rows as well as columns. This could be used as a general case for all transportation problems.

A major advantage is that the initial allocation can be easily carried out in the cells having zero as the element. If all the m+n-1 allocations are possible through zero element it can be easily concluded that such a solution is always optimal. However such a situation is quite rare. In any case after allocating the resources in the zero cell, if the balance allocation is carried out in the next least cost apart from zero, one can still be towards the optimal solution. Almost all transportation problems whether balanced or unbalanced can be solved by using the assignment method and, in majority of the cases, the solution is obtained in lesser number of iterations.

More Stories on : Transport | Management

Article E-Mail :: Comment :: Syndication :: Printer Friendly Page

Stories in this Section
Labour cases: No place for misplaced compassion

Neglected man can deny son property: apex court

Assignment technique in transportation problems

Patients’ patience

Wanted, women directors

Just Do IT

Number Crunch

Medical allowance not exempt from tax

Be fact-based

The British vs Bhagat Singh

The phi of rabbits, markets, hockey