[SOLVED] MA3231 Assignment 3

1. Suppose that a linear programming problem has the following property: its initial dictionary is not degenerate and, when solved by the simplex method, there is never a tie for the choice of leaving variable.
   1. Can such a problem have degenerate dictionaries? Explain.
   2. Can such a problem cycle? Explain.
2. Solve the following linear program using Bland’s rule to resolve degeneracy: maxz = 10x₁ − 57x₂ − 9x₃ − 24x₄ subject to

0.5x₁ − 5.5x₂ − 2.5x₃ + 9x₄ ≤ 0 0.5x₁ − 1.5x₂ − 0.5x₃ + x₄ ≤ 0 x₁ ≤ 1 x₁,x₂,x₃,x₄ ≥ 0.

3. Consider the linear program maxz = 3x₁ + 5x₂

subject to

x₁ + 2x₂ ≤ 5 x₁ ≤ 3 x₂ ≤ 2 x₁, x₂ ≥ 0 Compare the efficiency of the implementation of the simplex algorithm if

1. You are using the largest positive coefficient for the entering variable (and the lexicographic method for the leaving)
2. You are using Bland’s rule

4. Consider the following linear programming problem:

maxz = 2x₁ − 3x₂ + 2x₃ + 12x₄

subject to

4x₁ + 5x₂ + 2x₃ ≤ 10

2x₁ − x₃ + x₄ ≤ 30 4x₂ + 2x₃ + x₄ ≤ 20 x₁, x₂, x₃, x₄ ≥ 0

Find the dual program to this linear program.

5. Consider the following dual linear programming problem:

minξ = 3y₁ + y₂ + 2y₃ subject to

2y₁ + 3y₂ − y₃ ≥ 5 −y₁ + 4y₃ ≥ 10 y₁ + 2y₂ ≥ 7 3y₁ − 2y₃ ≥ 7 y₁, y₂, y₃ ≥ 0

1. Rewrite the problem in standard form.
2. What is the primal problem corresponding to this dual linear program.

6. Write a spreadsheet that can solve both, the primal and the dual linear program given the input coefficients a_ij, b_i, c_j for i = 1,…,4 and j = 1,…, Try different values for the coefficients to give an answer to the following questions:
   • If both the primal and the dual problem have optimal solutions, how do they compare?
   • If the primal problem is infeasible, what is happening with the dual problem?
   • If the primal problem is unbounded, what is happening with the dual problem?
   • If the dual problem is infeasible, what is happening with the primal problem?
   • If the dual problem is unbounded, what is happening with the primal problem?

8 points per problems

Problems to be discussed in the Office Hours

1. Consider the linear program

maxz = x₁ + 2x₂

subject to

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

Compare the efficiency of the implementation of the simplex algorithm if

1. You are using the largest positive coefficient for the entering variable
2. You are using Bland’s rule

2. Consider the following linear programming problem:

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

subject to

2x₁ + 5x₂ + 3x₃ ≤ 10 x₁ + x₃ ≤ 5 3x₂ + 2x₃ ≤ 8 x₁, x₂, x₃ ≥ 0

Find the dual program to this linear program. Solve both, the primal and the dual linear program using the simplex algorithm.