Description
- Find all the values of the parameter α such that the following linear program has a finite optimal solution:
maxz = αx1 + 2x2 − x3
subject to
2x1 − x2 + 3x3 ≤ 4
−x1 + x2 − 2x3 ≤ 8 3x1 − 3x3 ≤ 2 x1, x2, x3 ≥ 0
- Solve the following linear program using the simplex algorithm and a suitable auxiliary program:
maxz = 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).
- Solve the following linear program using the simplex algorithm and a suitable auxiliary program:
maxz = 2x1 + 3x2 + 4x3
subject to
−2x2 − 3x3 ≤−5 x1 + x2 + 2x3 ≤ 4 x1 + 2x2 + 3x3 ≤ 7 x1, x2, x3 ≥ 0
- 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?
- 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
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.
- 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 |
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
- Solve the following linear program using the lexicographic method to avoid degeneracy:
maxz = 2x1 + 3x2 + 4x3
subject to
4x1 − x2 ≤ 0
−x1 + x3 ≤ 0 2x2 − 3x3 ≤ 0 x1, x2, x3 ≥ 0
How about Bland’s rule?
- Solve the following linear programming problem by initializing it with an auxiliary program.
maxz = 3x1 + 2x2
subject to
x1 − x2 ≤−1 x1 + x2 ≤ 2 x1, x2 ≥ 0
