Algorithm Design Techniques
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
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?