Tiffany’s home has four valuable paintings that are up for sale. Four customers
ID: 450080 • 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.
a)Use Hungarian method to determine how to maximize the total revenue received from the sale of the paintings.
b) 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)
Need detailed steps please. Thanks.
Explanation / Answer
Customer Painting 1 Painting 2 Painting 3 Painting 4 1 8 11 - - 2 9 13 12 7 3 9 - 11 - 4 - - 12 9 Step 1 Find the largest number in matrix and subtract the matrix with the largest number Number should be absolute Customer Painting 1 Painting 2 Painting 3 Painting 4 1 5 2 - - 13 is the biggest number 2 4 - 1 6 3 4 - 2 - 4 - - 1 4 Step 2 Find lowest number in each row and subtract with the row elements Customer Painting 1 Painting 2 Painting 3 Painting 4 1 5 2 - - 0 is lowest 2 4 - 1 6 0 is lowest 3 4 - 2 - 0 is lowest 4 - - 1 4 0 is lowest Step 3 Find lowest number in each column and subtract with the row elements Customer Painting 1 Painting 2 Painting 3 Painting 4 1 5 2 - - 2 4 - 1 6 3 4 - 2 - 4 - - 1 4 0 is lowest 0 is lowest 0 is lowest 0 is lowest Step 4 Link all 0 with minimum number of lines. If number of lines is less than number of rows than optimal solution has not been reached. If lines equal number of rows or columns than optimal solution is reached. Since we don’t have any. Check for 3 zeros or more and than for 2 zeros Customer Painting 1 Painting 2 Painting 3 Painting 4 1 5 2 - - 2 4 - 1 6 3 4 - 2 - 4 - - 1 4 Optimal solution is reached Step 5 Consider 0 as minimum opurtunity lost Go row wise to find minimum zero and then do column wise Customer Painting 1 Painting 2 Painting 3 Painting 4 1 5 2 - - 2 4 - 1 6 One Zero is here. So painting 2 goes to Customer 2 3 4 - 2 - Painting 4 goes to customer 3 4 - - 1 4 Painting 1 goes to customer 4 Painting 3 goes to customer 1