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