Assignment Model In Linear Programming

Approach to solution:

4. Hungarian Method / Flood's technique / Assignment algorithm: (opportunity cost method)(cont.):

Step 4.(modified): Total opportunity cost matrix can be got by simplify doing row operation on Column opportunity matrix or column operation on row opportunity cost matrix. (Doing row operation on column opportunity matrix means: Deduct the smallest element in the row from all other elements in the row in column opportunity matrix and vice versa). The property of total opportunity cost matrix is that it will have at least one zero in every row and column. All the cells, which have zero as the opportunity cost, are eligible for assignment.

Step 5.Once we get the total opportunity cost matrix, cover all the zeros by MINIMUM NUMBER OF HORIZONTAL AND VERTICAL LINES.

Step 6.If the lines thus drawn are equal to the number of rows or columns (because of square matrix).

Step 7.To make assignment: Search for a single zero either row wise or column wise. If you start row wise, proceed row by row in search of single zero. Once you find a single zero; assign that cell by enclosing the element of the cell by a square. Once all the rows are over, then start column wise and once you find single zero assign that cell and enclose the element of

the one cell in a square. Once the assignment is made, then all the zeros in the row and column corresponding to the assigned cell should be cancelled. Continue this procedure until all assignments are made. Sometimes we may not find single zero and find more than one zero in a row or column. It indicates, that the problem has an alternate solution. We can write alternate solutions. (The situation is known as a TIE in assignment problem).

Step 8.If the lines drawn are less than the number of rows or columns, then we cannot make assignment. Hence the following procedure is to be followed: The cells covered by the lines are known as Covered cells. The cells, which are not covered by lines, are known as uncovered cells. The cells at the intersection of horizontal line and vertical lines are known as Crossed cells.

1.       Identify the smallest element in the uncovered cells.

a)      Subtract this element from the elements of all other uncovered cells.

b)      Add this element to the elements of the crossed cells.

c)       Do not alter the elements of covered cells.

2.       Once again cover all the zeros by minimum number of horizontal and vertical lines.

3.       Once the lines drawn are equal to the number of rows or columns, assignment can be made as said in step (6).

4.       If the lines are not equal to number of rows or columns, repeat the steps 7 (a) and 7 (b) until we get the number of horizontal and vertical lines drawn are equal to the number of rows or columns and make allocations as explained in step (6).

Note:

For maximization same procedure is adopted, once we convert the maximization problem into minimization problem by multiplying the matrix by (-1) or by subtracting all the elements of the matrix from highest element in the matrix. Once we do this, the entries in the matrix gives us relative costs, hence the problem becomes Minimisation problem. Once we get the optimal assignment, the total value of the original pay off measure can be found by adding the individual original entries for those cells to which assignment have been made.