Exercises — The Simplex Method

Chapter 4 · Fully solved exercises on simplex tableaux, pivoting, and optimality

Exercise 1: Complete a Simplex Trace

Problem. Solve the following LP by the simplex method, showing every tableau:

\[ \begin{aligned} \text{maximize} \quad & 4x_1 + 3x_2 \\ \text{subject to} \quad & 2x_1 + x_2 \le 10 \\ & x_1 + 2x_2 \le 10 \\ & x_1, x_2 \ge 0 \end{aligned} \]

Solution. Introduce slack variables \(s_1, s_2 \ge 0\) to convert to standard equality form:

\[ 2x_1 + x_2 + s_1 = 10, \quad x_1 + 2x_2 + s_2 = 10. \]

The initial BFS is \(x_1 = x_2 = 0\), \(s_1 = s_2 = 10\), \(z = 0\), with basis \(\{s_1, s_2\}\).

Initial tableau (reduced costs appear in the \(z\)-row; positive values indicate improving directions):

\[ \begin{array}{c|cccc|c} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\\hline s_1 & 2 & 1 & 1 & 0 & 10 \\ s_2 & 1 & 2 & 0 & 1 & 10 \\\hline z & 4 & 3 & 0 & 0 & 0 \end{array} \]

Pivot 1. The largest reduced cost is \(\bar{c}_{x_1} = 4\), so \(x_1\) enters. Ratio test: \(\frac{10}{2} = 5\) (row \(s_1\)), \(\frac{10}{1} = 10\) (row \(s_2\)). Minimum ratio is 5, so \(s_1\) leaves; the pivot element is \(2\).

Row operations: \(R_1 \leftarrow R_1 / 2\); \(R_2 \leftarrow R_2 - R_1\); \(R_z \leftarrow R_z - 4 R_1\).

Tableau after pivot 1:

\[ \begin{array}{c|cccc|c} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\\hline x_1 & 1 & 1/2 & 1/2 & 0 & 5 \\ s_2 & 0 & 3/2 & -1/2 & 1 & 5 \\\hline z & 0 & 1 & -2 & 0 & 20 \end{array} \]

Pivot 2. Only \(\bar{c}_{x_2} = 1 > 0\), so \(x_2\) enters. Ratio test: \(\frac{5}{1/2} = 10\) (row \(x_1\)), \(\frac{5}{3/2} = \frac{10}{3}\) (row \(s_2\)). Minimum ratio is \(\frac{10}{3}\), so \(s_2\) leaves; the pivot element is \(\frac{3}{2}\).

Row operations: \(R_2 \leftarrow R_2 / (3/2)\); \(R_1 \leftarrow R_1 - \frac{1}{2} R_2\); \(R_z \leftarrow R_z - 1 \cdot R_2\).

Tableau after pivot 2:

\[ \begin{array}{c|cccc|c} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\\hline x_1 & 1 & 0 & 2/3 & -1/3 & 10/3 \\ x_2 & 0 & 1 & -1/3 & 2/3 & 10/3 \\\hline z & 0 & 0 & -5/3 & -2/3 & 70/3 \end{array} \]

All reduced costs are \(\le 0\). Optimal solution: \(x_1^* = x_2^* = \frac{10}{3}\), \(z^* = \frac{70}{3} \approx 23.33\).

---

Exercise 2: Reading Optimality from a Tableau

Problem. The following is claimed to be the optimal simplex tableau for:

\[ \begin{aligned} \text{maximize} \quad & 5x_1 + 4x_2 \\ \text{subject to} \quad & x_1 + 2x_2 \le 8 \\ & 3x_1 + x_2 \le 6 \\ & x_1, x_2 \ge 0 \end{aligned} \]

\[ \begin{array}{c|cccc|c} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\\hline x_2 & 0 & 1 & 2 & -1 & 4 \\ x_1 & 1 & 0 & -1 & 2 & 6 \\\hline z & 0 & 0 & -3 & -2 & 46 \end{array} \]

Answer: (a) What is the optimal solution? (b) What is the basis? (c) Is the solution degenerate?

Solution.

(a) Optimal solution. The basic variables and their values are read directly from the RHS column:

• \(x_2 = 4\) (basic, row 1), \(x_1 = 6\) (basic, row 2).
• Non-basic variables: \(s_1 = 0\), \(s_2 = 0\).
• Objective value: \(z = 5(6) + 4(4) = 30 + 16 = 46\). ✓

We can verify against the \(z\)-row: \(z = 46 - (-3)s_1 - (-2)s_2 = 46\) when \(s_1 = s_2 = 0\). ✓

(b) Basis. The basis is \(\mathcal{B} = \{x_1, x_2\}\). Both original decision variables are basic; both slacks are non-basic at zero. To confirm: the \(x_1\) column is \((0,1)^T\) (unit column in row 2) and the \(x_2\) column is \((1,0)^T\) (unit column in row 1). ✓

(c) Degeneracy. A BFS is degenerate if any basic variable equals zero. Here \(x_2 = 4 > 0\) and \(x_1 = 6 > 0\), so the solution is non-degenerate.

The reduced costs for \(s_1\) and \(s_2\) are both negative (\(-3\) and \(-2\)), confirming no improving direction exists. The solution is optimal.

---

Exercise 3: Pivot Operations

Problem. Given the following simplex tableau, a student proposes entering \(x_2\) and pivoting on row 1 (the \(s_1\) row). Verify using the ratio test whether this choice is correct, and then perform the valid pivot.

\[ \begin{array}{c|cccc|c} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\\hline s_1 & 3 & 2 & 1 & 0 & 12 \\ s_2 & 1 & 4 & 0 & 1 & 8 \\\hline z & 6 & 8 & 0 & 0 & 0 \end{array} \]

Solution. The LP is: maximize \(6x_1 + 8x_2\) subject to \(3x_1 + 2x_2 \le 12\), \(x_1 + 4x_2 \le 8\), \(x_1, x_2 \ge 0\).

Entering variable: \(x_2\) has the largest reduced cost \(\bar{c}_{x_2} = 8 > 0\). ✓

Ratio test (only rows with positive coefficient in the \(x_2\) column are candidates):

Row	Basic var	\(x_2\) coeff	RHS	Ratio
1	\(s_1\)	2	12	\(12/2 = 6\)
2	\(s_2\)	4	8	\(8/4 = \mathbf{2}\)

The minimum ratio is 2 (row 2). The student’s choice of row 1 is incorrect — it would violate feasibility (the \(s_2\) constraint would become negative). The correct leaving variable is \(s_2\); the pivot element is \(4\).

Correct pivot: \(x_2\) enters, \(s_2\) leaves. Pivot element = 4.

Row operations:

\[ R_2 \leftarrow R_2 / 4, \quad R_1 \leftarrow R_1 - 2 R_2, \quad R_z \leftarrow R_z - 8 R_2. \]

New \(R_2\): \(\left[\frac{1}{4},\ 1,\ 0,\ \frac{1}{4}\ \Big|\ 2\right]\)

New \(R_1\): \(\left[3 - \frac{2}{4},\ 2-2,\ 1,\ -\frac{2}{4}\ \Big|\ 12-4\right] = \left[\frac{5}{2},\ 0,\ 1,\ -\frac{1}{2}\ \Big|\ 8\right]\)

New \(R_z\): \(\left[6 - \frac{8}{4},\ 0,\ 0,\ -\frac{8}{4}\ \Big|\ 16\right] = \left[4,\ 0,\ 0,\ -2\ \Big|\ 16\right]\)

Tableau after pivot:

\[ \begin{array}{c|cccc|c} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\\hline s_1 & 5/2 & 0 & 1 & -1/2 & 8 \\ x_2 & 1/4 & 1 & 0 & 1/4 & 2 \\\hline z & 4 & 0 & 0 & -2 & 16 \end{array} \]

New BFS: \(x_2 = 2\), \(s_1 = 8\), \(x_1 = s_2 = 0\). Objective \(z = 8(2) = 16\). Still improvable: \(\bar{c}_{x_1} = 4 > 0\), so one more pivot would be needed to reach the optimum.

---

Exercise 4: Phase I — Finding an Initial BFS

Problem. The LP

\[ \begin{aligned} \text{maximize} \quad & x_1 + x_2 \\ \text{subject to} \quad & x_1 + x_2 = 3 \\ & x_1 - x_2 \le 1 \\ & x_1, x_2 \ge 0 \end{aligned} \]

has no obvious starting BFS (the equality constraint cannot be satisfied by slacks alone at the origin). Use the Big-M / Phase I method to find a feasible starting point.

Solution.

Setup. Convert to standard form by adding slack \(s_2 \ge 0\) to the inequality and an artificial variable \(a_1 \ge 0\) to the equality:

\[ x_1 + x_2 + a_1 = 3, \quad x_1 - x_2 + s_2 = 1. \]

The Phase I problem minimises \(a_1\) (equivalently, maximises \(-a_1\)). The initial BFS is \(a_1 = 3\), \(s_2 = 1\), all others zero.

Phase I initial tableau (objective row tracks \(w = -a_1\); express \(a_1\) from row 1 and substitute into \(w\)-row):

\[ \begin{array}{c|ccccc|c} & x_1 & x_2 & a_1 & s_2 & \text{RHS} \\\hline a_1 & 1 & 1 & 1 & 0 & 3 \\ s_2 & 1 & -1 & 0 & 1 & 1 \\\hline w & 1 & 1 & 0 & 0 & -3 \end{array} \]

(\(w\)-row already updated: \(w = -a_1 = x_1 + x_2 - 3\), so rc\((x_1) = 1\), rc\((x_2) = 1\).)

Pivot 1. Enter \(x_1\) (rc = 1 > 0). Ratio test: \(3/1 = 3\) (row \(a_1\)), \(1/1 = 1\) (row \(s_2\)). Minimum ratio = 1, so \(s_2\) leaves; pivot element = 1.

Row operations: \(R_2 \leftarrow R_2\) (already unit); \(R_1 \leftarrow R_1 - R_2\); \(R_w \leftarrow R_w - R_2\).

\[ \begin{array}{c|ccccc|c} & x_1 & x_2 & a_1 & s_2 & \text{RHS} \\\hline a_1 & 0 & 2 & 1 & -1 & 2 \\ x_1 & 1 & -1 & 0 & 1 & 1 \\\hline w & 0 & 2 & 0 & -1 & -2 \end{array} \]

Still \(w < 0\) (i.e., \(a_1 > 0\)). Enter \(x_2\) (rc = 2 > 0). Ratio test: \(2/2 = 1\) (row \(a_1\)), row \(x_1\) has coefficient \(-1 < 0\) (skip). Minimum ratio = 1; \(a_1\) leaves; pivot element = 2.

Row operations: \(R_1 \leftarrow R_1 / 2\); \(R_2 \leftarrow R_2 + R_1\); \(R_w \leftarrow R_w - 2 R_1\).

\[ \begin{array}{c|ccccc|c} & x_1 & x_2 & a_1 & s_2 & \text{RHS} \\\hline x_2 & 0 & 1 & 1/2 & -1/2 & 1 \\ x_1 & 1 & 0 & 1/2 & 1/2 & 2 \\\hline w & 0 & 0 & -1 & 0 & 0 \end{array} \]

\(w = 0\) and \(a_1\) is non-basic. Phase I complete. The artificial variable has been driven to zero.

Starting BFS for Phase II: \(x_1 = 2\), \(x_2 = 1\), \(s_2 = 0\).

Feasibility check: \(x_1 + x_2 = 3\) ✓; \(x_1 - x_2 = 1 \le 1\) ✓.

---

Exercise 5: Identify the Error in a Tableau

Problem. A student is solving

\[ \begin{aligned} \text{maximize} \quad & 2x_1 + 3x_2 \\ \text{subject to} \quad & x_1 + x_2 \le 4 \\ & x_1 + 3x_2 \le 6 \\ & x_1, x_2 \ge 0 \end{aligned} \]

and claims the following is the optimal tableau:

\[ \begin{array}{c|cccc|c} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\\hline s_1 & 2/3 & 0 & 1 & -1/3 & 2 \\ x_2 & 1/3 & 1 & 0 & 1/3 & 2 \\\hline z & 1 & 0 & 0 & -1 & 6 \end{array} \]

Find the error (if any). Is this solution actually optimal?

Solution.

Step 1: Identify the current BFS from the tableau.

Basic variables and values: \(x_2 = 2\) (row 2), \(s_1 = 2\) (row 1). Non-basic: \(x_1 = 0\), \(s_2 = 0\).

Claimed objective: \(z = 2(0) + 3(2) = 6\). ✓ (The \(z\)-row value is consistent with the current BFS.)

Step 2: Check the optimality criterion.

The reduced cost of \(x_1\) in the \(z\)-row is \(\bar{c}_{x_1} = 1 > 0\). A positive reduced cost means increasing \(x_1\) would improve the objective. The student has incorrectly concluded optimality — the optimality condition (all \(\bar{c}_j \le 0\) for a maximisation problem) is not satisfied.

The error: The student stopped prematurely. The tableau is valid (the row operations are correct for this BFS), but the \(z\)-row shows \(\bar{c}_{x_1} = 1 > 0\), which signals that \(x_1\) should enter the basis.

Step 3: Perform the missing pivot (\(x_1\) enters).

Ratio test: \(\frac{2}{2/3} = 3\) (row \(s_1\)), \(\frac{2}{1/3} = 6\) (row \(x_2\)). Minimum ratio = 3, \(s_1\) leaves.

Row operations: \(R_1 \leftarrow R_1 / (2/3) = (3/2) R_1\); \(R_2 \leftarrow R_2 - (1/3) R_1\); \(R_z \leftarrow R_z - 1 \cdot R_1\).

\[ \begin{array}{c|cccc|c} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\\hline x_1 & 1 & 0 & 3/2 & -1/2 & 3 \\ x_2 & 0 & 1 & -1/2 & 1/2 & 1 \\\hline z & 0 & 0 & -3/2 & -1/2 & 9 \end{array} \]

All reduced costs \(\le 0\). True optimal solution: \(x_1^* = 3\), \(x_2^* = 1\), \(z^* = 2(3) + 3(1) = 9\).

The student’s answer undervalued the objective by \(9 - 6 = 3\).