This problem consists of allocating some resources to some operating patterns in such a way that the costs of the assignments are minimized, each resource is assigned exactly once. Hungarian algorithm is used to solve the problem.
This tutorial assumes that the given problem will be in a square matrix form and that the values given in the matrix are COSTS. If the original problem is given in terms of profits, the user will have to multiply the profit numbers by -1 and then use the tutorial.
:[font = subsection; inactive; ]
Example1
:[font = text; inactive; ]
This section steps you through an example problem. The following subsections are arranged logically so that you can perceive the operations performed to arrive at an optimum solution. Please note that there may typically be many more alternate optimum solutions.
:[font = subsubsection; inactive; ]
Loading the Function Definitions
:[font = input; ]
<<hungarian.m
:[font = subsubsection; inactive; ]
Initialization
:[font = input; startGroup; ]
initialization
:[font = print; inactive; endGroup; ]
INITIALIZATION DONE
:[font = subsubsection; inactive; ]
Data Input Process
:[font = input; startGroup; ]
inputphase
:[font = print; inactive; endGroup; ]
2 10 9
15 4 14
13 14 16
:[font = subsubsection; inactive; ]
Row Reduction by the minimum of the row elements
:[font = input; startGroup; ]
rowreduction
:[font = print; inactive; endGroup; ]
0 8 7
11 0 10
0 1 3
:[font = subsubsection; inactive; ]
Column Reduction by the minimum of the column elements
:[font = input; startGroup; ]
columnreduction
:[font = print; inactive; endGroup; ]
0 8 4
11 0 7
0 1 0
:[font = subsubsection; inactive; ]
Checking for all the zeroes that the matrix has at this point
:[font = input; startGroup; ]
zerocheck
:[font = print; inactive; endGroup; ]
11
22
31
33
:[font = subsubsection; inactive; ]
What kind of solution do we have now?
:[font = input; startGroup; ]
whatdoithink
:[font = print; inactive; endGroup; ]
POSSIBLE OPTIMUM goto OPTIMAL function
:[font = subsubsection; inactive; ]
Check for Optimum solution and find the SOLUTION
:[font = input; startGroup; ]
optimal
:[font = print; inactive; endGroup; ]
OPTIMAL
11
22
33
:[font = subsection; inactive; ]
Example2
:[font = subsubsection; inactive; ]
Loading the Function Definitions
:[font = input; ]
<<hungarian.m
:[font = subsubsection; inactive; ]
Initialization
:[font = input; startGroup; ]
initialization
:[font = print; inactive; endGroup; ]
INITIALIZATION DONE
:[font = subsubsection; inactive; ]
Data Input Process
:[font = input; startGroup; ]
inputphase
:[font = print; inactive; endGroup; ]
2 10 9 7
15 4 14 8
13 14 16 11
4 15 13 19
:[font = subsubsection; inactive; ]
Row Reduction by the minimum of the row elements
:[font = input; startGroup; ]
rowreduction
:[font = print; inactive; endGroup; ]
0 8 7 5
11 0 10 4
2 3 5 0
0 11 9 15
:[font = subsubsection; inactive; ]
Column Reduction by the minimum of the column elements
:[font = input; startGroup; ]
columnreduction
:[font = print; inactive; endGroup; ]
0 8 2 5
11 0 5 4
2 3 0 0
0 11 4 15
:[font = subsubsection; inactive; ]
Checking for all the zeroes that the matrix has at this point
:[font = input; startGroup; ]
zerocheck
:[font = print; inactive; endGroup; ]
11
22
33
34
41
:[font = subsubsection; inactive; ]
What kind of solution do we have now?
:[font = input; startGroup; ]
whatdoithink
:[font = print; inactive; endGroup; ]
POSSIBLE OPTIMUM goto OPTIMAL function
:[font = subsubsection; inactive; ]
Check for Optimum solution and find the optimal solution
This tutorial allows you to solve any assignment problem you have, of any order. You will have to start the program by first clicking the INITIALIZATION cell. This clears out all the previous results stored. Then you should click the DATA INPUT cell. First, you will be asked to give the order of the matrix. i.e. 3,4,5 etc.
Then, click the ROW REDUCTION, COLUMN REDUCTION, ZEROCHECK, WHATDOITHINK cells in that order. Depending on the message given by the last function, you will want to go either to OPTIMAL or NONOPTIMAL cell. If you are directed to OPTIMAL and OPTIMAL says "optimal", you will get the final solution and you are done. But, if you get the message "Non optimal still...go to NONOPTIMAL", then click NONOPTIMAL, ZEROCHECK, OPTIMAL in that order. Repeat the 3 function process until you are done. The Tutorial has appropriate messages at every point and so, please rest assured that you WILL get the solution even if you do not clearly comprehend what was just said in these two paragraphs.
Whenever the tutorial says click the command etc., you are expected to place the cursor anywhere in that command line and press "Enter" ...not "Return" . Good Luck!
:[font = subsubsection; inactive; ]
STEP1 : LOAD THE DEFINITIONS
:[font = text; inactive; ]
This is an essential step before solving any problem using this tutorial. This step loads the necessary function definitions stored elsewhere.
:[font = input; ]
<<hungarian.m
:[font = subsubsection; inactive; ]
STEP2 : INITIALIZATION
:[font = text; inactive; ]
This step lets you clear out all the previous definitions and results and start afresh. This will have to be performed every time you would like to solve a new problem or if you would like to re-solve the problem that has been just solved.
:[font = input; ]
initialization
:[font = subsubsection; inactive; ]
STEP3 : DATA INPUT
:[font = text; inactive; ]
This step when performed, opens a dialog box for you to input the order of the matrix and the cost elements of the matrix. You will have to press "Return" and not "Enter" after each input. The cost elements should be entered row by row. i.e. If you have matrix of order 2, then you will enter the elements in the following order:
row 1 & Column 1
row 1 & Column 2
row 2 & Column 1
row 2 & Column 2
If you make a mistake in inputting the numbers, go back to INITIALIZATION and perform that and the following steps once again. You don't have to LOAD the definitions again, though.
:[font = input; ]
inputphase
:[font = subsubsection; inactive; ]
STEP4 : ROW REDUCTION
:[font = text; inactive; ]
This step finds the minimum element in each row and subtracts that number from each element of the respective row.These are nothing but valid matrix row operations which point at a possible minimum cost optimum solution.
:[font = input; ]
rowreduction
:[font = subsubsection; inactive; ]
STEP5 : COLUMN REDUCTION
:[font = text; inactive; ]
This step finds the minimum element in each column and subtracts that number from each element of the respective column.These are nothing but valid matrix column operations which point at a possible minimum cost optimum solution.
:[font = input; ]
columnreduction
:[font = subsubsection; inactive; ]
STEP6 : CHECKING FOR ZEROES
:[font = text; inactive; ]
This step when performed, enumerates all the zeroes in the matrix resulting from the row and column operations in steps 4 and 5. The rest of the tutorial involves manipulating zeroes to see if we have an optimum solution or to tell us what to do if we still have a nonoptimum solution.
:[font = input; ]
zerocheck
:[font = subsubsection; inactive; ]
STEP7 : WHERE DO WE GO NEXT?
:[font = text; inactive; ]
This step is designed to aid you to know where to go next. When performed, you will get a message. If you get, "Possible Optimum go to OPTIMAL function" then click the input command in STEP8. If you get, "Non Optimal yet..go to NONOPTIMAL function", then click the input command in STEP9. You will be directed further by those steps till you arrive at a final OPTIMAL solution.
:[font = input; ]
whatdoithink
:[font = subsubsection; inactive; ]
STEP8 : CHECKING FOR OPTIMUM SOLUTION
:[font = text; inactive; ]
This step checks for an optimum solution and if it finds one comes back and tells you
"OPTIMAL" followed by the solution in terms of the row and column numbers. If it tells you "nonoptimal still...go to NONOPTIMAL", then you should click the command in STEP9.
:[font = input; ]
optimal
:[font = subsubsection; inactive; ]
STEP9 : MODIFICATION OF THE MATRIX
:[font = text; inactive; ]
This step modifies the matrix from the STEP5 according to the HUNGARIAN Algorithm. At the end of the process, you will see the resulting matrix. You will have to click the command in STEP6 again followed by STEP7. Just follow the directions from there on in an iterative fashion until you arrive at an optimum solution.
:[font = input; ]
nonoptimal
:[font = subsubsection; inactive; ]
FINAL STEP
:[font = text; inactive; ]
At this point, you will have an OPTIMUM solution in your hands. If you want to save the calculations for yourself, then choose "SAVE AS" in the "WINDOW" menu and give the file a new name of your choice.
If you just want to quit without saving anything, then just choose "QUIT" in the main menu OR close the window by clicking on X and clicking NO in the dialog box that appears.