# Linear Programming Section E162 Assignment 2 SOLVED

Original price was: \$35.00.Current price is: \$30.00.

Category:
Rate this product

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 + 2×2 − x3
subject to
2×1 − x2 + 3×3 ≤ 4
−x1 + x2 − 2×3 ≤ 8
3×1 − 3×3 ≤ 2
x1, x2, x3 ≥ 0
2. Solve the following linear program using the simplex algorithm and a suitable auxiliary
program:
max z = x1 + 3×2
subject to
−x1 − x2 ≤ −3
−x1 + x2 ≤ −1
x1 + 2×2 ≤ 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 = 2×1 + 3×2 + 4×3
subject to
−2×2 − 3×3 ≤ −5
x1 + x2 + 2×3 ≤ 4
x1 + 2×2 + 3×3 ≤ 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 −2×2
x1 = 3 −2×2
w2 = 1 +w1 −2×2
Hint: If it could, what was the original problem from whence it came?
5. Consider the following linear programming problem:
max z = 2×1 − 3×2 + 2×3 + 12×4
subject to
4×1 + 5×2 + 2×3 ≤ 10
2×1 − x3 + x4 ≤ 30
4×2 + 2×3 + 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 − 2×2 − 2×4
w1 = − 0.5×1 + 3.5×2 + 2×3 − 4×4
w2 = − 0.5×1 + x2 + 0.5×3 − 0.5×4
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 = 2×1 + 3×2 + 4×3
subject to
4×1 − x2 ≤ 0
−x1 + x3 ≤ 0
2×2 − 3×3 ≤ 0
x1, x2, x3 ≥ 0