Example 1: Dana and Robbie have just been given 20 minutes and 15 tickets each before leaving Funland. Having done some incidental learning while their father worked on this book, they devoted three of their minutes to generating the data in the table below and solving the problem to maximize their fun.
| Ride | Minutes required | Tickets | Fun value |
|---|---|---|---|
| Paratroopers | 6 | 4 | 8 |
| Teacups | 4 | 3 | 6 |
| Mini Himalayas | 4 | 3 | 5 |
| Whirling chairs | 4 | 2 | 6 |
| Helicopters | 5 | 3 | 3 |
| Merry-go-round | 4 | 2 | 3 |
| Jungle | 5 | 3 | 5 |
Assume that they ride each ride at most once, and solve their problem.
Solution: Let’s use \{0,1\} variables A, B, C, D, E, F, G to indicate whether Dana and Robbie are going to ride each ride separately. We formulate the integer program as follows.
| Maximize: | 8A+6B+5C+6D+3E+3F+5G |
|---|---|
| Subject to: | 6A+4B+4C+4D+5E+4F+5G \le 20-3 |
| 4A+3B+3C+2D+3E+2F+3G \le 15 | |
| A, B, C, D, E, F, G\in \{0,1\} |
Example 2: An analytically minded basketball coach selects his starting lineup according to his ratings of his players, and of course, their position and height. His plan for the next game is to maximize the total shooting ability of the starting team while keeping the average height at 6’5″ or more. He also wants to start at least two guards and a center.
The coach’s data is shown in the table below. Determine his starting 5.
| Player | Height | Position | Shooting |
|---|---|---|---|
| Bob | 6’1″ | Guard | 9 |
| Clyde | 6’6″ | Forward | 8 |
| Michael | 6’4″ | Guard | 9 |
| David | 6’9″ | Center | 7 |
| Scotty | 6’6″ | Forward | 8 |
| Bill | 6’8″ | Center | 8 |
| Dennis | 6’6″ | Forward | 6 |
| Earl | 6’3″ | Guard | 10 |
| Kareem | 6’10” | Center | 6 |
| Sam | 6’1″ | Guard | 8 |
Solution: Let’s use \{0,1\} variables A, B, C, D, E, F, G, H, I, J to indicate separately whether each player is in the starting 5. We formulate the integer program as follows.
| Maximize: | 9A+8B+9C+7D+8E+8F+6G+10H+6I+8J |
|---|---|
| Subject to: | A+B+C+D+E+F+G+H+I+J = 5 |
| A + C + H + J \ge 2 | |
| D + F + I \ge 1 | |
| -4A+B-C+4D+E+3F+G-2H+5I-4J \ge 0 | |
| A, B, C, D, E, F, G, H, I, J\in \{0,1\} |