MA3231-Assignment 3 Solved

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.

a)     Can such a problem have degenerate dictionaries? Explain.

b)    Can such a problem cycle? Explain.

2.    Solve the following linear program using Bland’s rule to resolve degeneracy: maxz = 10x1 − 57x2 − 9x3 − 24x4 subject to

0.5x1 − 5.5x2 − 2.5x3 + 9x4 ≤ 0 0.5x1 − 1.5x2 − 0.5x3 + x4 ≤ 0 x1 ≤ 1 x1,x2,x3,x4 ≥ 0.

3.    Consider the linear program maxz = 3x1 + 5x2

subject to

x1 + 2x2 ≤ 5 x1 ≤ 3 x2 ≤ 2 x1, x2 ≥ 0 Compare the efficiency of the implementation of the simplex algorithm if

a)     You are using the largest positive coefficient for the entering variable (and the lexicographic method for the leaving)

b)    You are using Bland’s rule

4.    Consider the following linear programming problem:

maxz = 2x1 − 3x2 + 2x3 + 12x4

subject to

4x1 + 5x2 + 2x3 ≤ 10

2x1 − x3 + x4 ≤ 30 4x2 + 2x3 + x4 ≤ 20 x1, x2, x3, x4 ≥ 0

Find the dual program to this linear program.

5.    Consider the following dual linear programming problem:

minξ = 3y1 + y2 + 2y3 subject to

2y1 + 3y2 − y3 ≥ 5 −y1 + 4y3 ≥ 10 y1 + 2y2 ≥ 7 3y1 − 2y3 ≥ 7 y1, y2, y3 ≥ 0

a)     Rewrite the problem in standard form.

b)    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 aij, bi, cj for i = 1,...,4 and j = 1,...,4. 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 = x1 + 2x2

subject to

3x1 + x2 ≤ 3 x1, x2 ≥ 0

Compare the efficiency of the implementation of the simplex algorithm if

a)     You are using the largest positive coefficient for the entering variable

b)    You are using Bland’s rule

2.    Consider the following linear programming problem:

maxz = 3x1 + 2x2 + x3

subject to

2x1 + 5x2 + 3x3 ≤ 10 x1 + x3 ≤ 5 3x2 + 2x3 ≤ 8 x1, x2, x3 ≥ 0

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