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):
-
Exercise 29.1-1, page 857.
-
Exercise 29.1-2, page 857.
-
Exercise 29.1-3, page 857.
-
Exercise 29.1-4, page 857.
-
Exercise 29.1-5, page 858.
-
Exercise 29.1-6, page 858.
-
Exercise 29.1-7, page 858.
Problems (to be handed in):
-
Consider the following linear program.
-
-
Plot the feasible region. (3 points)
-
Identify the optimal solution. (2 points)
-
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)
-
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.
Gerry Brady and Janos Simon
Wednesday January 30 17:39:01 CST 2013