Algorithm Design Techniques
COMP-360
Assignment 3
Due: Tues, March 18 in class
2008.3.12
Clarifications to question 3 highlighted in red.
Some questions from the LP handout, available in hidden
folder or from Anil.
Instructions for lp_solve contained on Announcement
page.
Late assignments -10% per day, including
weekends.
If you work closely with someone else, indicate the person's name(s)
on your homework.
The final write-up of each assignment must, however, be your own work.
1. Handout, problem
7.2. Also solve the problem using
lp_solve and give both a primal and dual solution, and verify
optimality.
2.
Handout, problem 7.8. Also solve the problem using
lp_solve and give both a primal and dual solution, and verify
optimality.
3. Formulate and solve (using lp_solve) one
of the problems below. Preferably use real data, but if not, make up
something reasonable. Also give the dual solution, and verify
optimality.
(a) Diet problem. Choose at least 6 of your favourite foods and at
least 4 minimum daily requirements of various vitamins etc., as well as
a maximum calorie level, and upper bound requirements on each food.
Find a minimum cost diet subject to these constraints.
or
(b) Casino night bar. Look up at least 6 cocktail recipes that each use
some combination of 4 or more
types of liquor. Give a price to
each cocktail, and suppose you have a fixed amount of each liquor
available. Figure out which drinks to mix to maximize your revenue
(assuming you sell everything you make.)
4. For the problem below
give either a feasible non-negative
solution, or prove that none exists.
3x1 + 2x2 -x3 +3x4 +2x5 <=7
x1 -2x2 +2x3 <= -6
-2x1 +3x2 -2x3 -3x4 <= 10
-x1 +3x4 -2x5 <= -2
-3x1 -4x3 +2x5 <= 4
_____________________________________________________________________________________________________