Assignment Problem Solution
Now subtract this smallest element from each element of that column.Having performed the step 1 and step 2, we will be getting at least one zero in each column in the reduced cost table. Now, the assignments are made for the reduced table in following manner.It can also be noticed that in an n x n matrix, always less than ‘n’ lines will cover all the zeros if there is no solution among them. In step 4, if the number of lines drawn are equal to n or the number of rows, then it is the optimum solution if not, then go to step 6. Select the smallest element among all the uncovered elements. Repeat the procedure from step (3) until the number of assignments becomes equal to the number of rows or number of columns.Now, this element is subtracted from all the uncovered elements and added to the element which lies at the intersection of two lines. I do minimization and maximization so we get two observations.Assignment problem is a special type of linear programming problem which deals with the allocation of the various resources to the various activities on one to one basis.
In the first phase, row reductions and column reductions are carried out.
(i) Rows are examined successively, until the row with exactly single (one) zero is found.
Assignment is made to this single zero by putting square □ around it and in the corresponding column, all other zeros are crossed out (x) because these will not be used to make any other assignment in this column. (ii) Step 3 (i) in now performed on the columns as follow:- columns are examined successively till a column with exactly one zero is found.
It does it in such a way that the cost or time involved in the process is minimum and profit or sale is maximum.
Though there problems can be solved by simplex method or by transportation method but assignment model gives a simpler approach for these problems.