Tiffany\'s home has four valuable paintings that are up for sale. Four customers
ID: 2747322 • Letter: T
Question
Tiffany's home has four valuable paintings that are up for sale. Four customers are bidding for the paintings. The prices that each customer is willing to pay for the paintings she is bidding are given in the table below. Use Hungarian method to determine how to maximize the total revenue received from the sale of the paintings. Formulate it a s an integer program and solve it with a solver to check your solution in part a (you can use only necessary decision variables, i.e. if an assignment is not possible based on the values in the matrix do not include that particular decision variable in the model)Explanation / Answer
The cost matrix for the given problem is as follows:
8 11 0 0
9 13 12 7
9 0 11 0
0 0 12 9
Step 1: from each row find row minimum and subtract it from all the entries in that row,
Result of step 1:
8 11 0 0
2 6 5 0
9 0 11 0
0 0 12 9
Step 2: from each column find column minimum and subtract it from that column entries.
Result of step2:
8 11 0 0
2 6 5 0
9 0 11 0
0 0 12 9
Step 3: we will draw lines across the rows and columns such that all the zeros are covered.
Result of step 3:
As the number of lines drawn is equal to the number of rows thus we are done here.
Now the zero’th positions determine the possible combinations,
Now we have two possible combinations:
Combination1:
Customer1-painting3, customer2-painting4, customer3-painting2, customer4-painting1.
Combination2:
Customer1-painting4, customer2-painting4, customer3-painting4, customer4-painting2.
Thus the maximized revenue after the sales of the painting using Hungarian method is: 7.