Problems related to simplex methods

Question

Problems:

Consider the following linear programming problem:

Maximize           2x₁ + 3x₂ + 5x₃
Subject to         x₁ + 2x₂ + 3x₃  ≤ 8
                          x₁ - 2x₂ + 2x₃  ≤ 6
                         x₁,  x₂,  x₃  ≥  0

1. Write the dual problem

2. Solve the foregoing problem by the simplex method (not the dual -simplex). At each iteration, identify the dual variable values and show which dual constraints are violated.

3. At each iteration, identify the dual basic and nonbasic variables, along with the corresponding 3 x 3 dual basis.

4. Show that at  each iteration of the simplex method, the dual objective is worsened.

5. Verify that at termination, feasible solutions of both problems are at hand, having equal objective values and with complementary slackness holding.

6. The solution to the above maximization problem is (Objective value = 15.5,  x₁ = 7,x₂ = 0.5, x₃ = 0)