MA 3231 Linear Programming Section E162 Assignment 2

MA 3231
Linear Programming
Section E162
Assignment 2
Content: up to Section 2.12
1. Find all the values of the parameter α such that the following linear program has a
finite optimal solution:
max z = αx1 + 2x2 − x3
subject to
2x1 − x2 + 3x3 ≤ 4
−x1 + x2 − 2x3 ≤ 8
3x1 − 3x3 ≤ 2
x1, x2, x3 ≥ 0
2. Solve the following linear program using the simplex algorithm and a suitable auxiliary
program:
max z = x1 + 3x2
subject to
−x1 − x2 ≤ −3
−x1 + x2 ≤ −1
x1 + 2x2 ≤ 2
x1, x2 ≥ 0
Draw the region of feasible solution to this problem and indicate the solution you get at
each step of the simplex algorithm (only for the original problem, i.e., Phase II).
2
3. Solve the following linear program using the simplex algorithm and a suitable auxiliary
program:
max z = 2x1 + 3x2 + 4x3
subject to
−2x2 − 3x3 ≤ −5
x1 + x2 + 2x3 ≤ 4
x1 + 2x2 + 3x3 ≤ 7
x1, x2, x3 ≥ 0
4. Show that the following dictionary cannot be the optimal dictionary for any linear
programming problem in which w1 and w2 are the initial slack variables:
z = 4 −w1 −2x2
x1 = 3 −2x2
w2 = 1 +w1 −2x2
Hint: If it could, what was the original problem from whence it came?
5. 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
Solve it numerically using the built-in simplex algorithm of a spreadsheet program (such
as MS Excel). Please just submit the .xlsx file as submission comment to your
homework on Canvas.
6. Reconsider the degenerate dictionary of Lecture 2.8 that led to the cycling issue:
z = x1 − 2x2 − 2x4
w1 = − 0.5x1 + 3.5x2 + 2x3 − 4x4
w2 = − 0.5x1 + x2 + 0.5x3 − 0.5x4
w3 = 1 − x1
3
Write down the corresponding linear programming problem and find the optimal
solution by using
a) the lexicographic method (comment on the choice of the entering variable).
b) Bland’s rule
8 points per problems
Problems to be discussed in the Office Hours
1. Solve the following linear program using the lexicographic method to avoid degeneracy:
max z = 2x1 + 3x2 + 4x3
subject to
4x1 − x2 ≤ 0
−x1 + x3 ≤ 0
2x2 − 3x3 ≤ 0
x1, x2, x3 ≥ 0
How about Bland’s rule?
2. Solve the following linear programming problem by initializing it with an auxiliary
program.
max z = 3x1 + 2x2
subject to
x1 − x2 ≤ −1
x1 + x2 ≤ 2
x1, x2 ≥ 0