MA 3231
Linear Programming
Section E162
Assignment 4
Content: up to Section 4
1. Solve the following linear program using
a) the perturbation (lexicographic) method
b) Bland’s rule
max z = −
3
4
x1 + 150x2 −
1
50x3 + 6x4
subject to
1
4
x1 + 150x2 −
1
25x3 + 9x4 ≤ 0
1
2
x1 − 90x2 −
1
50x3 + 3x4 ≤ 0
x3 ≤ 1
x1, x2, x3, x4 ≥ 0.
2. Consider the following linear programming problem:
max z = 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:
max z = 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
z = 12.4 − 1.2x1 − 0.2x5 − 0.9x6 − 2.8x4
x2 = 6 − x1 − 0.5x6 − 2x4
x3 = 0.4 − 0.2x1 − 0.2x5 + 0.1x6 + 0.2x4
x7 = 11.2 − 1.6x1 + 0.4x5 + 0.3x6 + 1.6x4
(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
max z = 3x1 − x2
subject to
x1 − x2 ≤ 1
−x1 + x2 ≤ −4
x1, x2 ≥ 0
12 points per problems
