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

_____________________________________________________________________________________________________