CSPP 55005 Algorithms — Winter 2013

Homework 4 (assigned January 30, due February 6)

Reading: CLRS chapter 29, Matousek & Gartner, chapters 1, 2–4.

Written assignment: Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in.

"Do" Exercises (not to be handed in):

1. Exercise 29.1-1, page 857.

2. Exercise 29.1-2, page 857.

3. Exercise 29.1-3, page 857.

4. Exercise 29.1-4, page 857.

5. Exercise 29.1-5, page 858.

6. Exercise 29.1-6, page 858.

7. Exercise 29.1-7, page 858.

Problems (to be handed in):

1. Consider the following linear program.
• Plot the feasible region. (3 points)
• Identify the optimal solution. (2 points)

2. Consider the following system of equations:
.
Let x = .
• Write the system as Ax = b and solve it. (5 points)
• Show that the columns of A are linearly independent. (5 points)

Consider a second system of equations:
.
• Write this system as Ax = b. Find three solutions. (3 points)
• Show that the columns of A are not linearly independent. (2 points)

3. A cargo plane can carry a maximum weight of 100 tons and a maximum volume of 60 cubic meters. There are 3 materials to be transported, and the cargo company may choose to carry any amount of each, up to the following maximum available limits.
Material 1 has density 2 tons per cubic meter, maximum available amount 40 cubic meters, and revenue \$1000 per cubic meter.
Material 2 has density 1 ton per cubic meter, maximum available amount 30 cubic meters, and revenue \$1200 per cubic meter.
Material 3 has density 3 tons per cubic meter, maximum available amount 20 cubic meters, and revenue \$12,000 per cubic meter.
• Write a linear program that optimizes revenue within the given constraints.
• Step 1: Define the variables of this problem. (5 points)
• Step 2: Write the constraints. (5 points)
• Step 3: Write the objective function. (5 points)
• Solve your linear program with the linear programming solver lp_solve. (Instructions* for lp_solve given below.) Your solution must include a printout of your lp_solve input file and the numerical answer, i.e., the maximum possible revenue. (10 points)

*Instructions. Techstaff has installed lp-solve on the cs machines for our use. You can run it as "lp_solve". There is documentation in /usr/share/doc/lp-solve. Here is an example.

Consider the following linear program:

maximize x_2 + 2x_3 subject to:
0 ≤ x_1 ≤ 7
5 ≤ x_2 ≤ 10
0 ≤ x_3 ≤ 6
x_1 + x_2 ≤ x_3
Write this in the lp_solve input format by creating the following file, called input.lp (the file can have any name that ends with the .lp extension):
maximize: x2 + 2*x3;
0 <= x1 <= 7;
5 <= x2 <= 10;
0 <= x3 <= 6;
x1 + x2 <= x3;
Then execute the command
lp_solve input.lp
The lp_solver gives the following output:
Value of objective function: 18
Actual values of the variables:
x2           6
x3           6
x1           0
Thus the maximum possible value of the objective function is 18, and setting x_1 = 0, x_2 = 6, x_3 = 6 gives this value.
To find the minimum possible value of the objective function, instead of the maximum, use "minimize" on the first line of the .lp file instead of "maximize". To force a variable x1 to be an integer, add the line
int x1;
in the .lp file.