Algorithm Design Techniques
COMP-360
Assignment 3
Due: 5pm Friday November 4, 2005
Under construction.
Please leave your assignment in the box marked
COMP360, 1st floor McConnell.
Late assignments -10% per day, including
weekends. Hand in late assignments to the T.A.
Each student should submit a different solution for problems 1 and 2.
1. You are going into the
business of selling speciality coffee blends. You plan to sell at least
5 brands, such as: Morning wakeup, Insomniacs delight, ... etc. You
have coffee beans from at least 5 different countries. Some of these
beans are strong, some light, some aromatic etc. Each of your brands is
a blend of some or all of these beans. Make up some data for this
problem (ie. profit for each brand, the blend for each brand, the
ammount of each bean available) and maximize your profit by solving the
linear program using lp_solve. ( See Announcements
). Get lp_solve to tell you the values of the dual variables for the
optimum solution.
Note: Try to choose the data values so the problem is not trivial to
solve by inspection.
2. For the problem you developed in problem 1, write down the dual
LP. Get lp_solve to solve the dual LP directly. Verify that the
solution obtained gives a proof of optimality for the LP in problem 1.
Ask lp_solve to give the "dual" variables for the optimum solution in
this case also. What are these variables in terms of problem 1?
3. Consider an LP in standard
form: max cx , Ax <= b , x >= 0.
Suppose that there is one row in the A matrix for
which all entries are positive. Can the LP be unbounded?
Give a proof or counterexample.
4. Show that the dual of the dual
of an LP in standard form is the original LP.
Verify the claim for the LP you created in problem 1.