Lesson 7: Maximum assignments and more than one optimum
A maximum assignment for sales regions
SkillMaximum assignment
Worked example
A company has four sales representatives — Alex (), Bella (), Chen () and Dina () — for four regions. The table shows each rep's expected weekly sales in a region, in thousands of dollars. Use the Hungarian algorithm to allocate one region to each rep so that total expected sales are as large as possible.
Step 1: Convert to a minimum problem
The largest entry is 24. Subtract every entry from 24:
Each new entry is how far that pairing falls short of 24, so the smallest total shortfall gives the largest total sales.
Step 2: Row reduction
Subtract 2, 1, 0 and 0:
Step 3: Column reduction
Subtract 2 from column 1 and 4 from column 4:
Step 4: Cover the zeros
Rows and and column 2 cover every zero: 3 lines, fewer than 4, so adjust.
Step 5: Adjust
The smallest uncovered entry is 4 (at ). Subtract 4 from the uncovered entries (rows and , columns 1, 3 and 4) and add 4 at the crossings and :
Step 6: Assign
4 lines are now needed. has one zero: – 2. then takes 3 (its other zero). 's zeros are in columns 1 and 3, so – 1, and – 4.
Step 7: Total from the original table
, that is $83 000 per week.
Answer
Alex – Region 3, Bella – Region 1, Chen – Region 4, Dina – Region 2, for maximum expected sales of $83 000 per week.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Subtract every entry from the largest entry.
Apply the Hungarian algorithm for a minimum.
Total the assignment from the original table.
Watch out for
Totalling the converted table (which gives the total shortfall, not the sales).
Forgetting to convert: minimising the sales table itself finds the smallest total, $57 000.