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 1  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.