1. Consider the following all-integer linear program:

Max 2x + y subject to

6x + 4y 22

5x + y 12

x + 2y 8

x, y 0 and both integers

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

1. Solve the ILP for this problem when y is the only integer (x is relaxed). (4 marks)

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

1. 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.1	1.7	1.30
B	0.9	0.95	1.70
C	1.05	0.85	2.0

Max production 250 100 100

Min production 40 80 35

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 $30 for product1, $28 for product 2, and $31 for product 3.

1. Formulate a linear programming model for maximizing total profit contribution. (5 marks)

1. Solve the linear program formulated in part (a) using excel. How many (note that number of products should be considered as integer value only) 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.