A group of friends has a series of seven purchases to make before meeting for co

Question

A group of friends has a series of seven purchases to make before meeting for coffee. The table below shows the amount that each person believes they can pay for each item, and the group wants to do this as inexpensively as possible. One person will have to make two purchases, and since Ross will just whine, Monica will get too bossy, Chandler won't stay separated from Monica for very long, and both Phoebe and Joey will simply be dumbfounded by having to do multiple things, Rachel will have to come through. Here is the table 2. A life-size cutout of| Three cases A self-help DVD Towels and A stuffed | A copy of “Acronyms | Food for | penguinBetter Left Unstated" Marcel when he was cute ugly naked guy, I of cleaning | about accepting | some chlorine supplies ifts from othersfor the fountain Rachel Monica Phoebe Joey Chandler Ross 32 25 26 40 20 16 20 10 15 18 16 12 15 14 10 45 36 60 30 30 30 67 58 59 70 69 61 14 14 18 15 10 15 60 75 45 52 65 27 Using the Hungarian algorithm, determine who gets what, how much is spent, and who opens the DVD before Rachel has time to return it

Explanation / Answer

the cost matrix has more columns than rows, we add dummy rows with zeros to make the matrix square

We subtract the row minimum from each row

subtract column minima

Cover all zeros with a minimum number of lines

The number of lines is smaller than 7. The smallest uncovered number is 4. We subtract this number from all uncovered elements and add it to all elements that are covered twice

There are 5 lines required to cover all zeros

x

The number of lines is smaller than 7. The smallest uncovered number is 6. We subtract this number from all uncovered elements and add it to all elements that are covered twice

There are 5 lines required to cover all zeros

x

The number of lines is smaller than 7. The smallest uncovered number is 10. We subtract this number from all uncovered elements and add it to all elements that are covered twice

There are 6 lines required to cover all zeros

The number of lines is smaller than 7. The smallest uncovered number is 19. We subtract this number from all uncovered elements and add it to all elements that are covered twice

There are 7 lines required to cover all zeros

Because there are 7 lines required, the zeros cover an optimal assignment

This corresponds to the following optimal assignment in the original cost matrix

The optimal value equals 123.

Rachel gets a copy of "acronyms better left unstated"

Monica gets A self help DVD about accepting gifts from others

Phoebe gets Towels and some chlorine for the fountain

Joey gets Food for Marcel

Chandler gets a life size cutout of ugly naked guy,whwn he was cute

Ross gets a stuffed penguin

total amount is 123.

Monica opens the DVD before rachel has time to return it.

32 16 12 45 67 14 60 25 20 15 36 58 14 75 26 10 14 60 59 18 45 40 15 10 30 70 15 52 20 18 13 30 69 10 65 8 16 27 30 61 15 55

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.