Page 398 Problem 3 By: Ms. Tamara MacEwen Parisay’s comment is in red

Tamara MacEwen

IE 416

Page 398 Problem 3

By: Ms. Tamara MacEwen

Parisay’s comment is in red.
Tom Cruise, Freddy Prinze Jr., Harrison Ford, and Matt LeBlanc are marooned on a desert island with Jennifer Aniston, Courtney Cox, Gwyneth Paltrow, and Julia Roberts. The “compatibility measures” in Table 52 indicate how much happiness each couple would experience if they spent all their time together. The happiness earned by a couple is proportional to the fraction of time they spend together.

Table 52

	JA	CC	GP	JR
TC	7	5	8	2
FP	7	8	9	4
HF	3	5	7	9
ML	5	5	6	7

a) Let Xij be the fraction of time that the ith man spends with the jth woman. The goal of the eight people is to maximize the total happiness of the people on the island. Formulate an LP whose optimal solution will yield the optimal values of the xij’s.

Input


Output

1. 
   Explain why the optimal solution in part (a) will have four xij = 1 and twelve xij = 0. The optimal solution requires that each person spend all his or her time with one person of the opposite sex, so this result is often referred to as the Marriage Theorem.
   

In order to maximize happiness, each man will spend time with the most compatible female that is still available. Each person will stay with the same partner the entire day to maximize happiness. If they were to change partners for a fraction of the day, the new partners would have lower happiness ratings and would cause the happiness rating to be lower than the maximum.

If for a fraction of time we have combination of 4 couples that maximizes happiness, then it can be true for all day. That is why all Xij are zero but 4 couples that are 1 (whole day).

2. 
   Solve the problem using assignment problem
   

Input

Output


Report to Manager:

If Tom Cruise, Freddy Prinze Jr., Harrison Ford, and Matt LeBlanc are marooned on a desert island with Jennifer Aniston, Courtney Cox, Gwyneth Paltrow, and Julia Roberts, the maximum total happiness would be achieved if the following men spent their time with only one woman.

Tom Cruise – Gwyneth Paltrow

Freddy Prinze Jr. – Courtney Cox

Harrison Ford – Julia Roberts

Matt LeBlanc – Jennifer Aniston

This combination would give the maximum compatibility measure of 30.