Duality Theory 173
(a) Find the optimal solution using the simplex method.
(b) Now consider adding the constraint x
1
+ x
4
= 1 to get the LP
minimize −3x
1
− x
2
subject to x
1
+ x
2
+ x
3
= 2
x
1
+ x
4
= 1
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0.
(c) Solve the new linear program without re-solving the new model from
scratch. (Hint: Use the dual simplex method)
Exercise 4.5
Consider the linear program
maximize 7x
1
+ 17x
2
+ 17x
3
subject to x
1
+ x
2
≤ 8
x
1
+ 4x
2
+ 3x
3
≤ 14
3x
2
+ 4x
3
≤ 9
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0.
(a) What is the optimal solution?
(b) What is the optimal basis?
(c) What are the optimal dual variables?
(d) By how much can the right-hand side of the first constraint be increased
or decreased without changing the optimal basis?
(e) By how much can the objective coefficient of x
1
be increased or