The excel document must be submitted along with the solution (as a separate document).

1) Consider the following all-integer linear program:

Max x + 2y subject to

6x + 4y 20

5x + y 11

x + 2y 9 x,

y 0 and both integers

a) Graph the constraints for this problem. Use dots to indicate all feasible integer solutions.

b) Solve the LP Relaxation of this problem.

c) Find the optimal integer solution (show your work).

2) Martha Manufacturing makes three products. Each product requires manufacturing operations in three departments:

A, B, and C. The labor-hour requirements, by department, are as follows:

Department Product 1 Product 2 Product 3

A 1.5 2.0 1.20

B 1.0 0.75 2.20

C 1.25 0.5 2.0

During the next production period, the labor-hours available are 350 in department A, 350 in department B, and 200 in department C. The profit contributions per unit are $32 for product1, $28 for product 2, and $35 for product 3.

a) Formulate a linear programming model for maximizing total profit contribution.

b) Solve the linear program formulated in part (a) using excel. How much of each product should be produced, and what is the projected total profit contribution?