Tom Cruise, Freddy Prinze Jr., Harrison Ford, and Matt LeBlanc are marooned on a desert island with Jennifer Aniston, Courteney Cox, Gwyneth Paltrow, and Julia Roberts. The “compatibility measures” in Table indicate how much happiness each couple would experience if they spent all their time together.
|
JA
|
CC
|
GP
|
JR
|
TC
|
7
|
5
|
8
|
2
|
FP
|
7
|
8
|
9
|
4
|
HF
|
3
|
5
|
7
|
9
|
ML
|
5
|
5
|
6
|
7
|
The happiness earned by a couple is proportional to the fraction of time they spend together. For example, if Freddie and Gwyneth spend half their time together, they earn happiness of
.
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.
b 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.
c Determine the marriage partner for each person.
d Do you think the Proportionality Assumption of linear programming is valid in this situation?