## 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

_____________________________________________________________________________________________________