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.
______________________________________________________________________________________________________________________________