Question 1 (LP)

A farmer has 100 acres of land on which she plans to grow wheat and corn.  Each acre of wheat requires 4 hours of labor and $20 of capital, and each acre of corn requires 16 hours of labor and $40 of capital.  The farmer has at most 800 hours of labor and $2400 of capital available. If the profit from an acre of wheat is 80, and from an acre of corn is 100, how many acres of each crop should she plant to maximize her profit?  Formulate a linear program that solves this problem (no need to actually solve it)

Question 2 (LP)

During each 6-hour period of the day,  the Los Angeles Police Department needs at least the number of policeman shown below.  Policeman can be hired to work either 12 consecutive hours or 18 consecutive hours.  Policeman are paid $10 per hour for each of the first 12 hours a day they work, and are paid $15 per hour for the next 6 hours they work in a day.  Formulate a linear program that can be used to minimize the cost of meeting LA’s daily police requirements.

Question 3 (LP)

A firm offering cloud computing services needs to decide how to allocate jobs to available servers optimally. In this particular example there are four jobs to process, and the time required to complete each job is given in Table  1.   Additionally,  the  firm  has three servers available . All servers have different characteristics, and therefore not all servers are suitable to process each job; specifically, Table 2 shows which servers are compatible with each job. A job can be split among two different compatible servers and processed independently. The objective is to minimize the time required to complete all jobs: since all jobs are processed in parallel, this is time used by the server that finishes processing jobs last.

Table 1: Time required to complete each job (in hours)

Table 2: Compatibility of jobs and servers

As an example, if Job 1 is processed completely in server 1, Job 2 is processed com- pletely in Server 2, Job 3 is split evenly between Server 1 and Server 2 and Job 4 is processed completely in Server 3, then:

❼ Server 1 works for a total of 100 + 400 = 300 hours.

❼ Server 2 works for a total of 150 + 400 = 350 hours.

❼ Server 3 works for a total of 200 hours.

❼ The time required to complete all jobs (in parallel) is 350 hours.

Formulate the problem above as an  linear  program.   Clearly  define  your  notation, variables and include a short description of each constraint.

Question 4 (MIP)

Coach Billy Beane and his assistant Peter Brand have been hired by the Lakers.  He is trying to choose the starting lineup for the basketball team.  The team consists of seven players who have been rated (on a scale of 1= poor to 3 = excellent) according to their ball-handling, shooting, rebounding, and defensive abilities. The positions that each player is allowed to play and the player’s abilities are listed below.

The five-player starting lineup must satisfy the following restrictions:

1.  At least 4 members must be able to play guard, at least two members must be able to play forward, and at least 1 member must be able to play center.

2.  The average ball-handling, shooting, and rebounding level of the starting lineup must be at least 2.

3. If player 3 starts, then player 6 cannot start.

4. If player 1 starts, then players 4 and 5 must both start.

5. Either player 2 or player 3 must start.

Given those constraints, Coach Beane wants to maximize the total defensive ability of the starting team.  Formulate a mixed-integer program that will help him choose his starting team.

Figure 1: If we win, on our budget with this team, we’ll change the game.  And that’s what I want, I want it to mean something. –Billy Beane, in Moneyball  (2011)

Question 5 (MIP)

You are tasked with planning which movies to reference in the remainder of this course. You have a list of n movies, and for each movie you have the basic information:  budget, box office gross earnings,  release dates,  gender of the main protagonist,  film  rating, Rotten Tomatoes score, and number of academy awards won.  Finally, making a reference to a movie requires a time investment (for example, seeing the movie). In other words, you have access to the following table.

So far, in the course, movies have been selected in order to maximize the earnings (adjusted by inflation) of the movies referenced, while ensuring a reasonable time com- mitment.  In other words, letting ri  be the earnings of movie i  (adjusted by inflation), letting ti bethe time investment required to reference movie i, and letting T be the total time available to watch movies, the movies selected correspond to the optimal solutions of the optimization problem

max

x

s.t

rixi

tixi ≤ T

x ∈ {0, 1}n.

(earnings)

(time constraint)

In the formulation above, xi  is a decision variable such that xi  = 1 if movie i is selected to reference in class, and xi  = 0 otherwise.

Do the following modifications to the above formulation to ensure better movies are chosen. Clearly define the notation you introduce, as well as additional decision variables (if needed).

1. You have noticed that, so far, all references used involve white males. Modify the above formulation so that at least 30% of the movies used have female leads.

2.  The movies should have some intellectual merit as well.  Modify the formulation so that the average number of awards per movie is at least 2.

3. It may be OK to have some “mature” references, but the class should not become too dark. Modify the formulation so that at most one R rated movie is used.

4.  Since  high-earning  movies  are preferred,  there  is  also  an  implicit bias towards high-budget films. Modify the formulation so that for each movie referenced with a budget over $100M, there should also be a movie with a budget under $10M.