Assignment problem
HAM (HUNGARIAN METHOD ) OR MIN CASE
The Hungarian
mathematician D. Konig developed simpler & more efficient method of solving
assignment problem which is known as Hungarian techniques or method.
Steps
to follow
1) Prepare cost matrix, if it is not square matrix it means problem is unbalanced, so to convert it
into balanced matrix add a dummy row with zero.
2) Starting with this smallest the first row, locate the
smallest cost element in each row of the cost table. Now subtract this smallest
element from each element in that row. As a result there shall be at least one
zero in each row of this new table.
3) In the reduced cost table obtained in step 2, consider each
column and locate the smallest element in it .subtract the smallest element in
each column from every element of that column.
4) Make the assignment for the reduced matrix obtained from
step no 2 & 3 in the following way.
·
Examine the rows successively,
until a row with exactly one zero is found make an assignment to this single
zero by putting square around it and cross out all other zeros appearing in the
corresponding column as they will not be used to male any other assignment in
that column. Proceed in this manner until all rows have been examined.
·
Examine the columns successively,
until a column with exactly one zero is found make an assignment to this single
zero by putting square around it and cross out all other zeros appearing in the
corresponding column as they will not be used to male any other assignment in
that row. proceed in this manner until all columns have been examined.
·
Repeat step 4(i) and 4(ii) until
all zeros in the rows and columns are either marked or crossed out. If the no. of
assignment made are equal to no. of rows / columns. Then it is an optimum
solution and there is exactly one assignment in each row and in each column.
5) Draw the minimum number of horizontal and vertical lines
necessary to cover all the zeros in the reduced matrix obtained from step 4 in
the following way
· Mark all rows that do not have any
assignment
· Mark all columns that have zero in
marked rows [step 5(a)]
· Market all rows that have assignment
in marked columns. [step 5(b)]
· Repeat step 5(a) and 5(b) until no
more rows and columns can be marked
· Draw straight lines through all
unmarked rows and marked columns
6) If the number of lines drawn are equal to 'n' that is equal
to number of rows or columns then it is an optimum solution, otherwise go to
step 7
7) Select the smallest element among all the uncovered
elements. Subtract this smallest element from all the uncovered elements and
add it to the element which lies at the intersection of two lines. Then we
obtain another reduced matrix for fresh assignment
8) Go to step 4 an repeat the procedure until the number of assignment
become equal to the number of rows and columns. In such a case we shall observe
that every row and column has an assignment. Then the current solution is the
optimum solution
MAX CASE
In some cases, the element of assignment problem may represent
revenue or profit instead of cost, so that the objective will be to maximize
total revenue or profit. The problem of MAX can also be solved by using HAM
method that we can use for solving the MIN problem.in this the MAX problem will
be converted into MIN problem by selecting the largest element among all the
profit matrix and then subtract it from all the elements in the matrix
including itself. The apply HAM(Discussed above)
Profit
= sale revenue – production cost
UNBALANCED ASSIGNMENT
PROBLEM
If the cost matrix of assignment problem is not a square
matrix i.e. number of rows not equal to number of columns , then the assignment
problem is called Unbalanced assignment problem. In such case add a dummy row
or column depending on need with zero cost to convert it in to a square matrix then
apply HAM
No comments:
Post a Comment