1) Consider the following all-integer linear program:

Max 2x + y subject to

6x + 4y 20

5x + y 11

x + 2y 8

x, y 0 and both integers

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

b) Solve the LP Relaxation of this problem. (5 marks)

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

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.3	1.9	1.30
B	1.0	0.75	2.20
C	1.25	0.5	2.0

During the next production period, the labor-hours available are 330 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. (4 marks)

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? (5 marks)

Note that you must submit your excel document as a separate document (no pictures or pdfs are allowed) in order to get credit for this question.