1. Solve the following linear program using
a) the perturbation (lexicographic) method
b) Bland’s rule
subject to
2. Consider the following linear programming problem: maxz = x1 + 2x2
subject to
−2x1 − x2 + x3 ≤ 1 x1 + x2 ≤ 2
x1 + x3 ≤ 3 x1, x2, x3 ≥ 0
a) Solve the linear program.
b) Find the dual program.
c) Solve the dual program.
d) Compare the solutions of primal and dual program.
2
3. Consider the following linear programming problem:
maxz = x1 + 2x2 + x3 + x4
subject to
2x1 + x2 + 5x3 + x4 ≤ 8
2x1 + 2x2 + 4x4 ≤ 12 3x1 + x2 + 2x3 ≤ 18 x1, x2, x3, x4 ≥ 0
You know that the final dictionary for this program is given by
(where x5, x6, x7 are slack variables)
a) What will be the optimal solution to the problem if the objective function is changed to
3x1 + 2x2 + x3 + x4
b) What will be the optimal solution to the problem if the objective function is changed to
x1 + 2x2 + 0.5x3 + x4
c) For each of the three objective functions above, find the range of values for which the final dictionary will remain optimal.
4. Use the parametric self-dual simplex method to solve the following problem maxz = 3x1 − x2
subject to
x1 − x2 ≤ 1 −x1 + x2 ≤−4 x1, x2 ≥ 0
12 points per problems
