Algorithm Design Techniques

 COMP-360              Assignment 4           Due: Beginning of class, Tues Nov 6

All questions from the class handout, available in class or from Perouz.

Late assignments  -10% per day, including weekends.
Please give late assignments to Perouz (T.A) in McConnell 232
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.3. Write down both the primal and dual LPs. Solve the problem using lp_solve and give both a primal and dual solution.

2.  Handout, problem 7.7. For each of the three outcomes, be sure to include a certificate of correctness.
     Also give an example of each case, complete with a graph of the constraint region and explanation of the outcome.

3.  Handout, problem 7.16. Use lp_solve to solve the problem. Give the dual solution, and verify optimality.
     Can you give any interpretation to the dual variables?
     Hint: Change the right hand side b-vector in one component, and see how the optimum solution varies.