Problem 1 (20pts). Consider the following LP:
maximize 500x1 + 250x2 + 600x3
subject to 2x1 + x2 + x3 ≤ 240
3x1 + x2 + 2x3 ≤ 150 x1 + 2x2 + 4x3 ≤ 180 x1,x2,x3 ≥ 0
Use the Simplex method to solve it. For each step, clearly mark what is the current basis, the current basic solution, and the corresponding objective value.
Problem 2 (20pts). Use the Simplex method to solve the following LP (a degenerate case).
minimize −2x1 − 3x2 + x3 + 12x4
subject to −2x1 − 9x2 + x3 + 9x4 + x5 = 0
1/3x1 + x2 − 1/3x3 − 2x4 + x6 = 0 x1,x2,x3,x4,x5,x6 ≥ 0
Problem 3 (20pts). Use the two-phase method to solve completely the following problem:
minimize 2x1 +3x2 +3x3 +x4 −2x5
subject to x1 +3x2 +4x4 +x5 = 2
x1 +2x2 −3x4 +x5 = 2
−x1 −4x2 +3x3 = 1
x1 ,x2 ,x3 ,x4 ,x5 ≥ 0
Problem 4 (20pts). While solving a standard form LP, we arrive at the following simplex tableau (Table 1) with basic variables x3, x4, x5. The entries α, β, γ, δ and η in the tableau are unknown parameters. For each one of the following statements, find the conditions of the parameter values that will make the statement true (sufficient condition is enough).
1. The LP is unbounded (optimal value is −∞).
1
B δ −2 0 0 0 −10
3 −1 η 1 0 0 4
4 α −4 0 1 0 1
5 γ 3 0 0 1 β
Table 1:
2. The current solution is feasible but not optimal.
3. The current solution has the optimal objective value and there are multiple set of basis that achieve the same objective value.
Problem 5 (20pts). Consider a linear optimization problem in the standard form, described in terms of the following initial tableau (Table 2):
B 0 0 0 δ 3 γ ξ 0
2 0 1 0 α 1 0 3 β
3 0 0 1 −2 2 η −1 2
1 1 0 0 0 −1 2 1 3
Table 2:
The entries α, β, γ, δ, η and ξ in the tableau are unknown parameters, and B = {2,3,1}. For each of the following statements, find (sufficient) conditions of the parameter values that will make the statement true.
1. This is an acceptable initial tableau (i.e., the basic variables are feasible for the problem).
2. The first row (in the constraint) indicates that the problem is infeasible.
3. The basic solution is feasible but we have not reached an optimal basic set B.
4. The basic solution is feasible and the first simplex iteration indicates that the problem is unbounded.
5. The basic solution is feasible, x6 is a candidate for entering B, and when we choose x6 as the entering basis, x3 leaves B.
2
