Concepts & Steps of Operations Research April 2014 Exam Assignment Problems

Steps –

1. Take Dummy (if required) & then convert in Regret matrix (if required)
2. Do Row minimization and Column minimization.
3. Cover all Zeroes in the Table with Minimum possible lines. (Start from maximum zeroes, either row-wise or column-wise).
4. If optimal, find assignment.
5. If not optimal, write next table, change values & check again with Minimum possible lines.
6. Continue the iterations till optimal solution is reached.

An Assignment problem involves assignment or matching of two things. E. g. matching of workers and jobs or matching of salesmen and areas etc.

The basic principle in Assignment problem is that the matching is on a one to one basis.

i. e. One worker can do only one job or one salesman can operate in only one area.

The method used for solving Assignment problem is called “Hungarian method”.

Concepts:

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

A Balanced problem means the no. of rows and no. of columns in the problem are equal. E. g. if the problem contains 4 workers and 4 jobs, then it is balanced.

Where as, an Unbalanced problem means the no. of rows and no. of columns are not equal. E. g. if the problem contains 4 workers and 3 jobs it is not balanced. Then first we need to balance the problem by taking a Dummy job (imaginary job).

2. Dummy:

A Dummy is an imaginary entity. The purpose of Dummy is to balance the problem. Since the Dummy is imaginary, all values for Dummy are always zero. Dummy can come as row or column, depending on problem.

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

A Minimization Assignment problem involves cost, time or distance data. The objective of solution is to minimize the final answer.

A Maximization Assignment problem involves sales, revenue or profit data. The objective of solution is maximization of the final answer. 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.

4. Prohibited or Restricted problem:

A Prohibited problem is the one in which there are one or more restrictions. E. g. say there are 4 contractors – C1, C2, C3 & C4. And there are 4 roads to be repaired – R1, R2, R3 & R4. But contractor C2 cannot or is not allowed to work on R3. This is a prohibited problem

Then we assign a very high or infinite value (represented by M) to C2-R3 and proceed with solution. Throughout the solution steps, M does not change. Since M is infinity, no assignment is possible in M.

UNIVERSITY THEORY QUESTIONS

1. Multiple optimal solutions in an assignment problem.(Apr 2002) (Apr 2005)

An Assignment problem can have more than one optimal solution, which is called multiple optimal solutions. The meaning of multiple optimal solutions is – The total cost or total profit will remain same for different sets or combinations of allocations. It means we have the flexibility of assigning different allocations while still maintaining Minimum (Optimal) cost or Maximum (Optimal) profit.

We can detect multiple optimal solutions when there are multiple zeroes in any columns or rows in the final (Optimal) table in the Assignment problem.

2. State the algorithm of solving an Assignment problem.(Apr 2002) (Apr 2005)

Algorithm of solving an Assignment problem is as follows –

1] Check if the problem is Balanced or Unbalanced. If no. of rows = no. of columns, problem is balanced. If unbalanced, take Dummy row or column as required. All values for Dummy =0.

2] Check if the problem is of Minimization type (cost) or Maximization type (profit). If Maximization, convert to Minimization by finding Regret matrix.

3] Do row minima. Find minimum value in each row and subtract it from all values in that row.

4] Do column minima. Find minimum value in each column and subtract it from all values in that column.

5] Check for optimality. Draw minimum no. of straight lines to cover all zeroes in the matrix. If Minimum no. of lines= Size of matrix (e. g. 4 x 4, 5 x 5 etc.) then solution is optimal. If not, do iteration.

6] Iteration –   A} Find minimum uncovered value in the matrix.

B} Subtract it from all uncovered values.

C} Add it to all double covered values.

D} Other values remain same.

7] Again check for optimality. Continue procedure till we get optimal solution.

3. Restricted assignment problem, which is an unbalanced problem. (Apr 2003)

A restricted assignment problem is the one in which one or more allocations are prohibited or not possible. For such allocations we assign “M”, which is infinitely high cost. No allocation is given in M.

An unbalanced problem is one in which number of rows is not equal to number of columns. Then we need to introduce dummy row or dummy column as required. All values for dummy are zero.

Hence, in an unbalanced restricted problem, in the first table we will introduce dummy for balancing the problem and “M” to prohibited or restricted allocations.

4. Unbalanced Assignment Problem. (Oct 2003) (Oct 2005)

An unbalanced Assignment problem is the one in which number of rows is not equal to number of columns. Dummy row or column is required as applicable for balancing the problem. All values in Dummy are zero. Then the problem is solved as a normal assignment problem. Step one will be Row minima.

5. Optimality in an Assignment problem. (Oct 2006)

An Assignment problem is optimal when minimum number of lines required to cover all zeroes in the matrix are equal to size of the matrix. Size of the matrix means number of rows or number of columns.

E. g. Size can be 4 x 4 or 5 x 5.

Once optimality is detected then we can do allocations in the matrix. Allocations are done in the zero (0) values.

We test the optimality after doing Row minimization and Column minimization.

6.     Explain ‘Hungarian method’ of solving assignment problem:

Whenever the pay off matrix of any assignment problem is not a square matrix i.e.no. of rows not equal to number of columns the problem is called unbalanced     assignment problem. Hungarian method of solving such problem is as follows :

1.         Insert row or column with all values zero such that pay off matrix become
square matrix.

2.         Row minima : Subtract smallest element of each row from corresponding
element of that row.

3.         Column minima : Subtract smallest element of each column from
corresponding element of that column.

4.         Draw minimum number of vertical and horizontal lines which can cover all
zeros of pay off matrix.

5.         Total number of lines drawn is not equal to size of pay off matrix then select
smallest uncovered number, subtract it from every uncovered number, add it
to point of intersection and no change in other element. Repeat this step till
we get optimum matrix.

6.         This second phase of solution. Select any row or column with single zero and
make allocation cancel out other zeros in corresponding row and column.

7.     Explain regret matrix in assignment problem.

For solving the maximization assignment problem by Hungarian method, given   problem is converted in minimization. Every element of given matrix is subtracted from highest element of given matrix, resultant matrix is called regret matrix. It is also known as opportunity loss matrix.

Regret matrix in assignment problem of maximization type. It is used for     maximization of profit, income, revenue, sales etc.

8.     Explain reduced matrix in assignment problem.

1.     Reduced matrix is a part of Hungarian method of solving assignment problem. If given assignment problem is balanced problem then following two steps are performed.

Step 1 : (Row minima) Subtract smallest element of each row from corresponding elements of that row.

Step 2 : (Column minima) Subtract smallest element of each column from corresponding elements of that column.

Matrix obtained after execution of above steps is called ‘reduced matrix’.