[SOLVED] MA3231 Assignment 4

1. Solve the following linear program using
   1. the perturbation (lexicographic) method
   2. Bland’s rule

subject to

2. Consider the following linear programming problem: maxz = x₁ + 2x₂

subject to

−2x₁ − x₂ + x₃ ≤ 1 x₁ + x₂ ≤ 2

x₁ + x₃ ≤ 3 x₁, x₂, x₃ ≥ 0

1. Solve the linear program.
2. Find the dual program.
3. Solve the dual program.
4. Compare the solutions of primal and dual program.

2

3. Consider the following linear programming problem:

maxz = x₁ + 2x₂ + x₃ + x₄

subject to

2x₁ + x₂ + 5x₃ + x₄ ≤ 8

2x₁ + 2x₂ + 4x₄ ≤ 12 3x₁ + x₂ + 2x₃ ≤ 18 x₁, x₂, x₃, x₄ ≥ 0

You know that the final dictionary for this program is given by

(where x₅, x₆, x₇ are slack variables)

1. What will be the optimal solution to the problem if the objective function is changed to

3x₁ + 2x₂ + x₃ + x₄

1. What will be the optimal solution to the problem if the objective function is changed to

x₁ + 2x₂ + 0.5x₃ + x₄

1. 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 = 3x₁ − x₂

subject to

x₁ − x₂ ≤ 1 −x₁ + x₂ ≤−4 x₁, x₂ ≥ 0