Simplex Method Practice Problems with Solutions (Step by Step)

Six linear programming problems solved step by step with the simplex method: a graphical warm-up, three full tableau solutions, a minimization, an unbounded problem and a problem with infinitely many optimal solutions. Every tableau is shown, so you can check each pivot.

Contents2 sections

The simplex method in five steps

For a problem “maximize $z=c^{\mathsf T}x$ subject to $Ax\le b$ , $x\ge 0$ ” with $b\ge 0$ :

Add a slack variable to each constraint to make it an equation: $a_1x_1+\dots+a_nx_n+s=b$ , $s\ge 0$ .
Write the tableau. The objective row holds $-c$ (we write $z-c^{\mathsf T}x=0$ ). The slack variables form the first basis, which is the corner $x=0$ .
Entering variable: the column with the most negative entry in the $z$ row. If no entry is negative, the current solution is optimal.
Ratio test: for each row with a positive entry in that column, divide the right-hand side by that entry. The smallest ratio picks the leaving row. If no entry is positive, the problem is unbounded.
Pivot: divide the pivot row by the pivot, then clear the rest of the column with row operations. Go back to step 3.

Each pivot moves from one corner of the feasible region to a neighboring corner with a value of $z$ at least as large.

Problem 1

Easy

Solve graphically: maximize $z=2x+3y$ subject to $x+y\le 4$ , $x+3y\le 6$ , $x,y\ge 0$ .

Hint

An optimum of a linear program is always reached at a corner of the feasible region. List the corners.

View Solution

The corners are where the boundary lines meet:

$(0,0)$ : $z=0$
$(4,0)$ on $x+y=4$ : $z=8$
$(0,2)$ on $x+3y=6$ : $z=6$
Intersection of $x+y=4$ and $x+3y=6$ : subtracting gives $2y=2$ , so $(3,1)$ : $z=6+3=9$

The largest value is at $(3,1)$ .

Answer: $x=3,\ y=1,\ z_{\max}=9$

Problem 2

Medium

Use the simplex method: maximize $z=3x+5y$ subject to $x\le 4$ , $2y\le 12$ , $3x+2y\le 18$ , $x,y\ge 0$ .

Hint

Add $s_1, s_2, s_3$ . The first entering variable is $y$ (coefficient $-5$ in the $z$ row).

View Solution

Initial tableau
Basis	$x$	$y$	$s_1$	$s_2$	$s_3$	RHS
$s_1$	1	0	1	0	0	4
$s_2$	0	2	0	1	0	12
$s_3$	3	2	0	0	1	18
$z$	−3	−5	0	0	0	0

Pivot 1. Most negative in the $z$ row: $-5$ , so $y$ enters. Ratios: $s_2\colon 12/2=6$ , $s_3\colon 18/2=9$ (the $s_1$ row has 0 and is skipped). Smallest is 6, so $s_2$ leaves. Pivot on the 2.

After pivot 1 (y enters, s₂ leaves)
Basis	$x$	$y$	$s_1$	$s_2$	$s_3$	RHS
$s_1$	1	0	1	0	0	4
$y$	0	1	0	$\tfrac{1}{2}$	0	6
$s_3$	3	0	0	−1	1	6
$z$	−3	0	0	$\tfrac{5}{2}$	0	30

Pivot 2. Now $x$ enters ( $-3$ ). Ratios: $s_1\colon 4/1=4$ , $s_3\colon 6/3=2$ . So $s_3$ leaves; pivot on the 3.

After pivot 2 (x enters, s₃ leaves): optimal
Basis	$x$	$y$	$s_1$	$s_2$	$s_3$	RHS
$s_1$	0	0	1	$\tfrac{1}{3}$	$-\tfrac{1}{3}$	2
$y$	0	1	0	$\tfrac{1}{2}$	0	6
$x$	1	0	0	$-\tfrac{1}{3}$	$\tfrac{1}{3}$	2
$z$	0	0	0	$\tfrac{3}{2}$	1	36

No negative entries remain in the $z$ row, so this is optimal. Read the basic variables from the RHS column: $x=2$ , $y=6$ , $s_1=2$ (the first constraint has 2 units of slack), $z=36$ .

Answer: $x=2,\ y=6,\ z_{\max}=36$

Problem 3

Medium

Maximize $z=5x_1+4x_2+3x_3$ subject to

\begin{aligned}2x_1+3x_2+x_3&\le 5\\ 4x_1+x_2+2x_3&\le 11\\ 3x_1+4x_2+2x_3&\le 8\end{aligned}\qquad x_1,x_2,x_3\ge 0.

Hint

After the first pivot, a negative entry appears under $x_3$ even though the $x_1$ and $x_2$ entries are positive. Keep going.

View Solution

Initial tableau
Basis	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$s_3$	RHS
$s_1$	2	3	1	1	0	0	5
$s_2$	4	1	2	0	1	0	11
$s_3$	3	4	2	0	0	1	8
$z$	−5	−4	−3	0	0	0	0

Pivot 1. $x_1$ enters ( $-5$ ). Ratios: $5/2=2.5$ , $11/4=2.75$ , $8/3\approx 2.67$ . The smallest is 2.5, so $s_1$ leaves.

After pivot 1 (x₁ enters, s₁ leaves)
Basis	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$s_3$	RHS
$x_1$	1	$\tfrac{3}{2}$	$\tfrac{1}{2}$	$\tfrac{1}{2}$	0	0	$\tfrac{5}{2}$
$s_2$	0	−5	0	−2	1	0	1
$s_3$	0	$-\tfrac{1}{2}$	$\tfrac{1}{2}$	$-\tfrac{3}{2}$	0	1	$\tfrac{1}{2}$
$z$	0	$\tfrac{7}{2}$	$-\tfrac{1}{2}$	$\tfrac{5}{2}$	0	0	$\tfrac{25}{2}$

Pivot 2. The only negative entry is $-\tfrac12$ under $x_3$ , so $x_3$ enters. Ratios (positive entries only): $x_1$ row $\tfrac52\div\tfrac12=5$ , $s_3$ row $\tfrac12\div\tfrac12=1$ . So $s_3$ leaves.

After pivot 2 (x₃ enters, s₃ leaves): optimal
Basis	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$s_3$	RHS
$x_1$	1	2	0	2	0	−1	2
$s_2$	0	−5	0	−2	1	0	1
$x_3$	0	−1	1	−3	0	2	1
$z$	0	3	0	1	0	1	13

All $z$ -row entries are now $\ge 0$ : optimal. $x_1=2$ , $x_3=1$ , $x_2=0$ (nonbasic), and $z=10+3=13$ . Check the constraints: $4+0+1=5\le 5$ , $8+0+2=10\le 11$ , $6+0+2=8\le 8$ .

Answer: $x_1=2,\ x_2=0,\ x_3=1,\ z_{\max}=13$

Problem 4

Medium

Minimize $w=x-3y$ subject to $x+y\le 4$ , $-x+y\le 2$ , $x,y\ge 0$ .

Hint

Minimizing $w$ is the same as maximizing $z=-w$ .

View Solution

Maximize $z=-x+3y$ instead. The $z$ row holds $-c=(1,-3)$ .

Initial tableau for max z = −x + 3y
Basis	$x$	$y$	$s_1$	$s_2$	RHS
$s_1$	1	1	1	0	4
$s_2$	−1	1	0	1	2
$z$	1	−3	0	0	0

Pivot 1. $y$ enters ( $-3$ ). Ratios: $4/1=4$ , $2/1=2$ . So $s_2$ leaves.

After pivot 1 (y enters, s₂ leaves)
Basis	$x$	$y$	$s_1$	$s_2$	RHS
$s_1$	2	0	1	−1	2
$y$	−1	1	0	1	2
$z$	−2	0	0	3	6

Pivot 2. $x$ enters ( $-2$ ). Only the $s_1$ row has a positive entry: $2/2=1$ . So $s_1$ leaves.

After pivot 2 (x enters, s₁ leaves): optimal
Basis	$x$	$y$	$s_1$	$s_2$	RHS
$x$	1	0	$\tfrac{1}{2}$	$-\tfrac{1}{2}$	1
$y$	0	1	$\tfrac{1}{2}$	$\tfrac{1}{2}$	3
$z$	0	0	1	2	8

Optimal: $x=1$ , $y=3$ , $z_{\max}=8$ . Since $w=-z$ , the minimum of $w$ is $-8$ . Check: $1-3\cdot 3=-8$ .

Answer: $x=1,\ y=3,\ w_{\min}=-8$

Problem 5

Hard

Maximize $z=x+y$ subject to $x-y\le 1$ , $-2x+y\le 2$ , $x,y\ge 0$ . What does the simplex method report?

Hint

Do one pivot, then look closely at the column of the entering variable.

View Solution

First pivot: $x$ and $y$ both have $-1$ ; take $x$ . Only the first row has a positive entry, so $s_1$ leaves.

After pivot 1 (x enters, s₁ leaves)
Basis	$x$	$y$	$s_1$	$s_2$	RHS
$x$	1	−1	1	0	1
$s_2$	0	−1	2	1	4
$z$	0	−2	1	0	1

Now $y$ enters ( $-2$ ), but every entry in the $y$ column is negative: no row limits how far $y$ can grow. The ratio test finds nothing, so the problem is unbounded.

Concretely, with $y=t\ge 0$ the tableau gives $x=1+t$ , $s_2=4+t$ , all feasible, and $z=1+2t\to\infty$ .

Answer: unbounded, no maximum

Problem 6

Hard

Maximize $z=2x+4y$ subject to $x+2y\le 8$ , $x\le 6$ , $x,y\ge 0$ . Is the optimal solution unique?

Hint

In the final tableau, look at the $z$ -row entry of a nonbasic variable.

View Solution

$y$ enters ( $-4$ ); the only positive entry is in the first row, ratio $8/2=4$ , so $s_1$ leaves.

After pivot 1 (y enters, s₁ leaves): optimal
Basis	$x$	$y$	$s_1$	$s_2$	RHS
$y$	$\tfrac{1}{2}$	1	$\tfrac{1}{2}$	0	4
$s_2$	1	0	0	1	6
$z$	0	0	2	0	16

The $z$ row has no negative entry, so $z_{\max}=16$ at $x=0,\ y=4$ . But the nonbasic variable $x$ has a zero in the $z$ row: bringing it in does not change $z$ . Pivoting $x$ in (ratios $4\div\tfrac12=8$ and $6\div 1=6$ , so $s_2$ leaves) gives the corner $x=6,\ y=1$ , also with $z=16$ .

The reason is visible in the data: $z=2x+4y=2(x+2y)$ , parallel to the first constraint. Every point of the segment from $(0,4)$ to $(6,1)$ is optimal.

Answer: $z_{\max}=16$ , infinitely many optimal points

Frequently asked questions

What if a constraint is “ $\ge$ ” or an equation?

Then the slack variables do not give a starting corner. Add artificial variables and use the Big M method or the two-phase method, which first finds a feasible corner and then optimizes.

What does a tie in the ratio test mean?

A tie means the next corner is degenerate (a basic variable becomes 0). Pick either row; in rare cases the method can cycle, which a rule such as Bland’s rule (always choose the lowest-index variable) prevents.

Is the simplex method the same as solving graphically?

It follows the same idea, moving from corner to corner, but works with any number of variables, where drawing is impossible.

The simplex method in five steps

Problem 1

Problem 2

Problem 3

Problem 4

Problem 5

Problem 6

Frequently asked questions

What if a constraint is “≥\ge≥” or an equation?

What does a tie in the ratio test mean?

Is the simplex method the same as solving graphically?

What if a constraint is “ $\ge$ ” or an equation?