Linear Programming Examples

Solution Preview

1. A company has 4 projects to be assigned among 3 employees. Find the assignment that minimizes the total time spent by the employees:

Peter Mary Joan
Project 1 2 weeks 3 week 4 weeks
Project 2 3 weeks 2.5 weeks 5 weeks
Project 3 4 weeks 3.5 weeks 3 weeks
Project 4 6 weeks 3 weeks 3.5 weeks

With linear programming problems, the first step is to figure out what the decision variables are. What choices have to be made? In this problem, the company has to decide whether to assign Peter, Mary, or Joan to each project. So, in essence, there are 12 decisions to be made - whether to assign Peter to Project 1, assign Peter to Project 2, ... ... ..., and assign Joan to Project 4.

Since all the decision variables are yes/no decisions (ex: Assign Peter to Project 1? Yes or No), the decision variables are binary (1 for yes, 0 for no).

Now that the decision variables have been found, you need to determine the objective function. What needs to be minimized or maximized? Amount of time spent needs to minimized in this case. If we say that the decision variable of whether or not Peter will do Project 1 is P_1, whether or not Peter will do Project 2 is P_2, and so forth, the objective function will be:

Minimize (P_1)*2 + (P_2)*3 + (P_3)*4 + (P_4)*6 + (M_1)*3 + ... + (J_3)*3 + (J_4)*3.5

To explain further, look at (M_1)*3. M_1 is the decision variable for whether or not Mary will do Project 1. The coefficient of 3 corresponds to the amount of time she would spend on Project 1, which is 3 weeks.

Now that we have figured out the objective function and decision variables, we need constraints. The major constraint we have is that we only want one person to be assigned to each Project. So, for Project 1, the constraint would be:

(P_1) + (M_1) + (J_1) = 1

A similar constraint would be needed for Projects 2, 3, & 4. Finally, you need a constraint that requires each decision variable to be binary, 0 or 1.

Once you program the objective function, constraints, and decision variables into the solver you are using, you can then set the program to solve and the optimal solution will be outputted. In this case, it is optimal for Peter to do Project 1, Mary to do Projects 2 & 4, and Joan to do Project 3. That combination minimizes the time spent.
 
2. A cab company has four cabs. Three customers are requesting the service. Assign the cabs to the customers such that revenue is maximized.

Customer 1 Customer 2 Customer 3
Taxi 1 $300 $250 $280
Taxi 2 ...