Description
Problem 1 (5+5+10=20pts).
Consider the following linear program:
maximize x1 + 3×2 + 3×3 + 8×4
subject to x1 − x2 + x3 ≤ 2
x3 − x4 ≤ 1
2×2 + 3×3 + 4×4 ≤ 10
x1, x2, x3, x4 ≥ 0.
(a) Transform this problem to standard form and find a trivial BFS.
(b) Compute the reduced costs ¯c.
(c) Choose the incoming basis according to Bland’s Rule, compute the step size θ
∗ and and jth
basic direction, then apply the simplex method to update the current BFS to a neighboring
one.
Problem 2 (20pts). Consider the same linear program in Problem 1, please use simplex tableau
to completely solve it. For each step, draw the simplex tableau. Clearly mark what is the current
basis, the current basic solution, and the corresponding objective function value. You can start
from the same trivial BFS found in Problem 1. Also, compare the BFS obtained in Problem 1
and the second tableau obtained in this question. They should be consistent.
Problem 3 (20pts).
Use the two-phase simplex method (implemented by simplex tableau) to completely solve the linear
optimization problem. For each step, draw the simplex tableau. Clearly mark what is the current
basis, the current basic solution, and the corresponding (negative) objective function value.
minimize x1 + 3×2 + x4 − 2×5
subject to x1 + 2×2 + x4 + x5 = 2
x1 + 2×2 − 6×4 + x5 = 2
x1 + 4×2 − 3×3 + x4 = −1
x1, x2, x3, x4, x5 ≥ 0.
Problem 4 (20pts).
Apply the two-phase simplex method (implemented by simplex tableau) to solve the following linear
program. For each step, draw the simplex tableau. Clearly mark what is the current basis, the
current basic solution, and the corresponding (negative) objective function value.
minimize x1 − x2 + 3×3
subject to 2×1 − x2 + 4×3 ≤ −1
x1 − x2 − x3 ≤ 4
x2 − x4 = 0
x1, x2, x3, x4 ≥ 0.
Problem 5 Conditions for a Unique Optimum (10+10=20pts).
Let x
∗ be a basic feasible solution associated with some basic indices B. Prove the following:
a) If the reduced cost of every non-basic variable is positive, then x
∗
is the unique optimal
solution.
Hint: Let y ∈ {x ∈ R
n
: Ax = b, x ≥ 0} be given with y ̸= x
∗
. First, show that there exists
ℓ ∈ N = BC such that yℓ > 0. You can then mimic the proof of the theorem of stopping
criterion based on the reduced costs.
b) If x
∗
is the unique optimal solution and if x
∗
is nondegenerate, then the reduced cost of every
non-basic variable is positive.
Hint: The construction of the simplex method via basic directions can be helpful.