# Linear Programming Examples

Solve the linear programming models using either lp_solve (recommended, see linear programming tutorial) or excel solver (Google for details).

Include mathematical models.

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

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 $195 $228 $318

Taxi 3 $198 $193 $308

Taxi 4 $150 $325 $240

3. ACME construction build homes in Albany, GA. The company has $300,000 dollars to be invested next month. Table below show potential construction sites, cost of buildings and Expected profits:

Location Building cost Expected Profit

Clifton 60,000 5,000

Auburn 50,000 6,000

Adams 82,000 10,000

Amberly 103,000 12,000

Norwood 50,000 8,000

Covington 41,000 3,000

Roselawn 80,000 9,000

Eden 69,000 10,000

a. Find the set of projects that maximizes profits.

4. (From a previous final) A company has 3 million dollars for new projects in a manufacturing facility. Move over, there is limited space (1500 ft2) and only 15 employees to be assigned to the projects. Below is a summary of ten projects recommended by the plant manager:

Project Projected Revenue [$M] Required Investment Required Employees Required Space

1 0.65 0.5 7 248

2 0.48 0.4 3 215

3 0.84 0.7 2 261

4 0.48 0.7 7 272

5 0.55 0.5 6 342

6 0.66 0.4 8 235

7 0.44 0.6 3 298

8 0.66 0.7 5 444

9 0.84 0.7 2 439

10 0.36 0.3 5 366

Select the set of projects that maximizes company's revenue.

#### 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 ...

#### Solution Summary

This post covers four example linear programming problems (specifically, binary programming). Step-by-step instructions are provided, and Excel solver is used to solve each problem.