[Solved] MA3231 Assignment 4

1. Solve the following linear program using
   1. the perturbation (lexicographic) method
   2. Blands 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