MA 3231 Linear Programming Section E162 Assignment 3

MA 3231
Linear Programming
Section E162
Assignment 3
Content: up to Section 3.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.
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:
max z = 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
max z = 3x1 + 5x2
subject to
x1 + 2x2 ≤ 5
x1 ≤ 3
x2 ≤ 2
x1, x2 ≥ 0
2
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:
max z = 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
3
Problems to be discussed in the Office Hours
1. Consider the linear program
max z = 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:
max z = 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.