Special Cases in Simplex Method: Degeneracy, Unbounded, Multiple and Infeasible Solutions

Most textbook problems end with one clean optimal solution. Real problems and exam questions do not always behave that way. There are four special cases you need to recognise in a simplex tableau: degeneracy, alternative (multiple) optimal solutions, unbounded solutions and infeasible problems. Each one leaves a clear signal in the tableau. This guide shows that signal with a small solved example for each case.

All examples are maximization problems with ≤ constraints, solved with slack variables s1 and s2. You can paste any of them into the simplex method calculator with steps to see the same tableaus.

1. Degeneracy

Signal: a tie in the minimum ratio test, or a basic variable equal to zero.

Example. Maximize Z = 3x1 + 9x2 subject to x1 + 4x2 ≤ 8 and x1 + 2x2 ≤ 4.

In the first tableau x2 enters (Cj − Zj = 9). The ratio test gives 8 / 4 = 2 for row s1 and 4 / 2 = 2 for row s2: a tie. We pick s1 to leave, and the next tableau is:

Basis	x1	x2	s1	s2	RHS
x2	1/4	1	1/4	0	2
s2	1/2	0	−1/2	1	0
Cj − Zj	3/4	0	−9/4	0	Z = 18

The basic variable s2 is 0. That is a degenerate solution. x1 still has a positive Cj − Zj of 3/4, so it enters. The ratio for row s2 is 0 / (1/2) = 0, so s2 leaves, but x1 enters at the value 0:

Basis	x1	x2	s1	s2	RHS
x2	0	1	1/2	−1/2	2
x1	1	0	−1	2	0
Cj − Zj	0	0	−3/2	−3/2	Z = 18

The tableau is now optimal: x1 = 0, x2 = 2, Z = 18. The objective did not improve in the last iteration; it stayed at 18. That is the hallmark of degeneracy: the basis changes but the solution point does not move.

Why it matters: in rare cases degeneracy makes the simplex method cycle through the same bases forever. Textbook problems almost never cycle, and rules such as Bland’s rule (always pick the lowest-index variable when there is a choice) prevent it completely.

2. Alternative (Multiple) Optimal Solutions

Signal: in the optimal tableau, a non-basic variable has Cj − Zj = 0.

Example. Maximize Z = 2x1 + 4x2 subject to x1 + 2x2 ≤ 5 and x1 + x2 ≤ 4.

x2 enters first (Cj − Zj = 4), and the ratio test (5/2 against 4) removes s1. After one pivot:

Basis	x1	x2	s1	s2	RHS
x2	1/2	1	1/2	0	5/2
s2	1/2	0	−1/2	1	3/2
Cj − Zj	0	0	−2	0	Z = 10

No Cj − Zj is positive, so the solution x1 = 0, x2 = 5/2, Z = 10 is optimal. But x1 is non-basic and its Cj − Zj is 0. Bringing x1 into the basis would not change Z. Pivoting on it (ratio test: 5 for row x2, 3 for row s2, so s2 leaves) gives a second optimal corner, x1 = 3, x2 = 1, with the same Z = 2(3) + 4(1) = 10.

Geometrically, the objective line 2x1 + 4x2 is parallel to the constraint x1 + 2x2 = 5, so every point on that edge between the two corners is optimal. Exam answers usually ask you to state both corner solutions and say that the problem has infinitely many optimal solutions.

3. Unbounded Solution

Signal: a variable has a Cj − Zj that would improve the objective, but every entry in its column is zero or negative, so the ratio test has no valid row.

Example. Maximize Z = 2x1 + x2 subject to x1 − x2 ≤ 10 and 2x1 ≤ 40.

The first two iterations proceed normally. x1 enters and s1 leaves (ratios 10 and 20), then x2 enters and s2 leaves. The tableau after two pivots is:

Basis	x1	x2	s1	s2	RHS
x1	1	0	0	1/2	20
x2	0	1	−1	1/2	10
Cj − Zj	0	0	1	−3/2	Z = 50

s1 has Cj − Zj = 1, so increasing it would increase Z. But the s1 column contains 0 and −1, with no positive entry. Nothing limits how far s1 can grow, so Z can increase without limit. The problem is unbounded.

In practice an unbounded result almost always means a constraint is missing from the model, for example a forgotten capacity or demand limit.

4. Infeasible Problem

Signal: when artificial variables are used (Big M or the two-phase method), the final optimal tableau still has an artificial variable in the basis with a positive value. In the two-phase method, Phase 1 ends with W greater than 0.

Example. Maximize Z = 3x1 + 2x2 subject to 2x1 + x2 ≤ 2 and 3x1 + 4x2 ≥ 12.

The ≥ constraint needs a surplus variable and an artificial variable. The simplex method cannot drive that artificial variable to zero, because no point satisfies both constraints. You can confirm this directly: the first constraint limits the region to the triangle with corners (0, 0), (1, 0) and (0, 2). On those corners, 3x1 + 4x2 equals 0, 3 and 8, so the largest value it can reach is 8. It can never reach 12, so the constraints contradict each other and the problem has no feasible solution.

Infeasibility usually points to a modelling error, such as a requirement that is larger than the available capacity or an inequality written the wrong way round.

Quick Reference

Special case	What you see in the tableau	Meaning
Degeneracy	Tie in the ratio test, or a basic variable equal to 0	Basis changes but Z may not improve
Multiple optimal solutions	Optimal tableau with Cj − Zj = 0 for a non-basic variable	Infinitely many optimal points with the same Z
Unbounded solution	Improving column with no positive entries	Z can grow without limit
Infeasible problem	Artificial variable still positive at the end	No point satisfies all constraints

Detecting Special Cases Automatically

When you solve these problems by hand, the signals are easy to miss in a large tableau. The simplex method calculator reports unbounded and infeasible problems with a clear message, and shows every tableau, so you can spot a tie in the ratio test, a zero basic variable or a zero Cj − Zj yourself. For problems with ≥ or = constraints, use the non-standard simplex method calculator, which adds the surplus and artificial variables for you.