The Assignment Problem and the Hungarian Method

The Assignment Problem and the Hungarian Method 1 Example 1: You work as a sales manager for a toy manufacturer, and you currently have three salespeople on the road meeting buyers. Your salespeople are in Austin, TX; Boston, MA; and Chicago, IL. You want them to fly to three other cities: Denver, CO; Edmonton, Alberta; and Fargo, ND. The table below shows the cost of airplane tickets in dollars between these cities. From To Denver Edmonton Fargo Austin 250

400 350 Boston 400 600 350 Chicago 200 400 250 Where should you send each of your salespeople in order to minimize airfare? 2 We can represent the table above as a cost matrix. 250 400 350 400 600 350 200 400 250 3 Let’s look at one possible assignment. 250 400 350 400 600 350 200 400 250 The total cost of this assignment is $250 + $600 +$250 = $1100. 4 Here’s another possible assignment. 250 400 350 400 600 350 200 400 250 The total cost of this assignment is $250 + $350 +$400 = $1000. 5 After checking all six possible assignments we can determine that the optimal one is the following. 250 400 350 400 600 350 200 400 250 The total cost of this assignment is $400 + $350 +$200 = $950. Thus your salespeople should travel from Austin to Edmonton, Boston to Fargo, and Chicago to Denver. 6 Trial and error works well enough for this problem, but suppose you had ten salespeople flying to ten cities? How many trials would this take? There are n! ways of assigning n resources to n tasks. That means that as n gets large, we have too many trials to consider. 7 2 3 4 5 6 7 1 2 3 4 5 6 7 n 8 1 2 3 4 5 6 7 10 20 30 40 n n2 9 1 2 3 4 5 6 7 200 400 600 800 1000 n n2 en 10 1 2 3 4 5 6 7 1000 2000 3000 4000 5000 n n2 en nExclamation 11 Theorem: If a number is added to or subtracted from all of the entries of any one row or column of a cost matrix, then on optimal assignment for the resulting cost matrix is also an optimal assignment for the original cost matrix. 12 The Hungarian Method: The following algorithm applies the above theorem to a given n×n cost matrix to find an optimal assignment. Step 1. Subtract the smallest entry in each row from all the entries of its row. Step 2. Subtract the smallest entry in each column from all the entries of its column. Step 3. Draw lines through appropriate rows and columns so that...

Website: www.math.harvard.edu | Filesize: -
No of Page(s): 31
Download The Assignment Problem and the Hungarian Method.pdf