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
(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
s.t 2x1 + 2x2
- x3 <= 10
- 2x2 + x3 <= 10
-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
+ 2x2 - x3 <= 6
+3x2 - x3 <= -4
x1, x2, x3 >= 0