COMP-360B              Assignment 3          Due: March 24, 2004 5pm

Assignments are to be left in the box near the labs, McConnell 1st floor. Late assignments: -10% per day

This LPs you construct in this assignment should be your own work! You will need lp_solve - see lecture summaries.

1.  Imagine you are the manager of a small company that makes 10 products, each of which requires some combination of 5 resources (which may be material and/or human) which are in limited supply. For each unit of each product you receive a certain profit. Formulate a linear program to maximize your profit. You may invent data, or base it on some (simplified) real situation. Marks will be given for creativity. Your problem should not be so trivial you can solve it by inspection! You should:

(a) Write out the primal and dual problems.
(b) Use lp_solve to find the solution, and give both the primal and dual solutions.
(c) Verify optimality by hand (see section 2.1 and 2.2 of class notes). Can you find any interpretation of the dual variables?

2. You are going to invite 15  friends and  family members to a party in the Laurentians at an inn with 8 double rooms (two people to a room). Each person is willing to share a room with one of a small group of people (say at most 5) and gives a weight between 1 and 10(best) to their preference for each of these people. Formulate the problem of finding a room assignment  which maximizes the total  weight, as an integer linear program and solve it with lp-solve. Again you should construct the data for this problem yourself.
3. (a) Give a certificate for the fact that the following problem is unbounded.
        max    x1 + 3x2 -  x3
s.t             2x1 + 2x2 - x3  <= 10
                 3x1 - 2x2 + x3  <= 10
                    x1  -3x2 + x3 <= 10
                        x1, x2, x3 >= 0
(b) Give a certificate of the infeasibility of the following problem.
max    x1 + 3x2 -  x3
s.t             -2x1 - 2x2 + x3  <= -3
                 3x1 + 2x2 - x3  <= 6
                    x1  +3x2 - x3 <= -4
                        x1, x2, x3 >= 0