## 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.