## Algorithm Design Techniques

COMP-360              Assignment 3              Due: Mon Nov 13, 5pm

Late assignments  -10% per day, including weekends. Put assignments in the box, McConnell 1st floor.
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. (Network Flows) Text, P. 421, problem 14.

2. (Network Flows). Text, P. 423, problem 17.

3. (LP)  To support the sailing club, you plan to open a drink stand which serves mixed drinks (alcoholic or non as you wish).
You plan to have 6 kinds of different drinks which you will prepare in bulk in advance, each using some combination of up to 6 ingredients.
For each ingredient, you have a certain amount of stock on hand. Furthermore you know the selling price of each drink.
Your goal is to earn as much as possible for the club.
Construct a reasonable set of data for this problem, formulate it as an LP, and solve it using lpsolve.
Write down the dual problem, and give the dual solution. Can you interpret the dual problem in any way?

4. (LP) A ship arrives with 15 containers weighing  7, 9, 11, 12, 14, 17, 19, 21, 26, 28, 33 ,41, 43, 52, 63 tons each.
You have to load the containers onto trucks, each of which can hold at most 100 tons. Your goal is to minimize the number of trucks used.
Formulate this as an integer linear program and solve it using lpsolve. Also solve the problem as a linear program and get the dual solution.
Can you see how to get the primal and dual LP solutions by hand?