**18.310 Assignment 10 ****Due
Monday November 22, 2004**

_{1}
to x_{4} and constraints as follows

3x_{1
}– 2x_{2} + x_{3}_{ }+
x_{4} ≤ 3

x_{1}_{ }+ 2x_{2} – 2x_{3 }+
2x_{4} ≤ 3

3x_{1
}– x_{2} + 3x_{3 }– x_{4} ≤ 1

_{j} is non-negative and we
want to maximize x_{1} + x_{2} + x_{3} + x_{4}.

_{4} need not be positive. The constraints
are now

3x_{1
}– 2x_{2} +
x_{3}_{ }+
x_{4} ≤ 0

x_{1}_{ }+ 2x_{2} – 2x_{3 }+ x_{4} ≤ 0

-3x_{1
}– x_{2} + 3x_{3 }+ x_{4} ≤ 0

x_{1
}+ x_{2} + x_{3 } = 1

_{4}.
Write down the dual to this LP.

_{1 } as
a slack variable for the last equality (by using it to eliminate x_{1}
everywhere else). Also perform a pivot on the first equation and the variable
x_{4 }(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.