M. Quinn is preparing for a 12 day dog sled race. He owns eight dogs, but the race will allow only five dogs - the four pack dogs and the lead dog. M. Quinn has developed a test to measure the endurance of each dog. The endurance score for each dog and the amount of ALPO each dog requires per day is listed in the table below. M. Quinn wants to select the five dogs that will give the team the maximum endurance score subject to the following constraints.
1. Only 62 ounces of ALPO will be available each day.
2. At least two of the five dogs selected must have lead dog ability
3. Ren and Snippy are very close. Thus if Ren is selected for the team, Snippy must also be selected for the team and vice versa.
4. Snoopy and Snert hate each others guts. Therefore, either Snoopy can be on the team, Snert can be on the team, or neither of them can be on the team. However, both of them can not be on the team.
Formulate the integer LP problem to determine which dogs should be selected in order to maximize endurance rating.
|
Dog
|
Endurance rating
|
Ounces of Alpo/day
|
Lead dog ability
|
|
Bolivar
|
50
|
12
|
Yes
|
|
Pluto
|
90
|
11
|
No
|
|
Ren
|
65
|
10
|
No
|
|
Lassie
|
95
|
15
|
Yes
|
|
Odie
|
60
|
8
|
No
|
|
Snippy
|
65
|
11
|
No
|
|
Snoopy
|
90
|
15
|
Yes
|
|
Snert
|
80
|
18
|
No
|
Which dogs should not be included on the team? __________
What is the total maximum endurance for the team? ________
How many ounces of ALPO will actually be needed each day? _________