18.310 Assignment 10 Due
Monday November 22, 2004
1. Here is a linear program, with variables x1
to x4 and constraints as follows
3x1
– 2x2 + x3 +
x4 ≤ 3
x1 + 2x2 – 2x3 +
2x4 ≤ 3
3x1
– x2 + 3x3 – x4 ≤ 1
Each xj is non-negative and we
want to maximize x1 + x2 + x3 + x4.
Set up a tableau for this program (with 8 columns, one
for each s one for each x and one for –b) and perform enough pivots to find
the solution, using the simplex algorithm. Read off the solution. (The values
of the original x variables and of the objective function at the point at
which all c’s become negative.)
2. Write down the dual linear program to this one and
deduce the solution to the dual problem from your solution above. (this
is the value of the y’s and of the dual objective function at its solution
point.)
3. Here is another Linear Program. Our variables are
as before except that x4 need not be positive. The constraints
are now
3x1
– 2x2 +
x3 +
x4 ≤ 0
x1 + 2x2 – 2x3 + x4 ≤ 0
-3x1
– x2 + 3x3 + x4 ≤ 0
x1
+ x2 + x3 = 1
Maximize x4.
Write down the dual to this LP.
Treat x1 as
a slack variable for the last equality (by using it to eliminate x1
everywhere else). Also perform a pivot on the first equation and the variable
x4 (ignoring the signs of the b’s). If
some of your b’s other than the one for which b4 is a slack are now negative,
add a new variable so that the origin in all 5 variables is feasible.
Perform pivots to find the solution to this, and deduce
the solution of the dual.
4. State and indicate a proof
of the duality theorem of linear programming.
5. Explain with an example what you do when the origin
is not a feasible point for your constraints to make it one.