Simplex Method Calculator

The calculator will solve the given optimization problem using the simplex algorithm. It will add slack, surplus and artificial variables, if needed. In case of artificial variables, the Big M method or the two-phase method is used to determine the starting solution. Steps are available.

Your Input

Maximize $Z = 3 x_{1} + 4 x_{2}$ , subject to $\begin{cases} x_{1} + 2 x_{2} \leq 8 \\ x_{1} + x_{2} \leq 6 \\ x_{1} \geq 0 \\ x_{2} \geq 0 \end{cases}$ .

Solution

The problem in the canonical form can be written as follows:

Z = 3 x_{1} + 4 x_{2} \to max

\begin{cases} x_{1} + 2 x_{2} \leq 8 \\ x_{1} + x_{2} \leq 6 \\ x_{1}, x_{2} \geq 0 \end{cases}

Add variables (slack or surplus) to turn all the inequalities into equalities:

Z = 3 x_{1} + 4 x_{2} \to max

\begin{cases} x_{1} + 2 x_{2} + S_{1} = 8 \\ x_{1} + x_{2} + S_{2} = 6 \\ x_{1}, x_{2}, S_{1}, S_{2} \geq 0 \end{cases}

Write down the simplex tableau:

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Solution
$Z$	$-3$	$-4$	$0$	$0$	$0$
$S_{1}$	$1$	$2$	$1$	$0$	$8$
$S_{2}$	$1$	$1$	$0$	$1$	$6$

The entering variable is $x_{2}$ , because it has the most negative coefficient $-4$ in the Z-row.

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Solution	Ratio
$Z$	$-3$	$-4$	$0$	$0$	$0$
$S_{1}$	$1$	$2$	$1$	$0$	$8$	$\frac{8}{2} = 4$
$S_{2}$	$1$	$1$	$0$	$1$	$6$	$\frac{6}{1} = 6$

The leaving variable is $S_{1}$ , because it has the smallest ratio.

Divide row $1$ by $2$ : $R_{1} = \frac{R_{1}}{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Solution
$Z$	$-3$	$-4$	$0$	$0$	$0$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$S_{2}$	$1$	$1$	$0$	$1$	$6$

Add row $2$ multiplied by $4$ to row $1$ : $R_{1} = R_{1} + 4 R_{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Solution
$Z$	$-1$	$0$	$2$	$0$	$16$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$S_{2}$	$1$	$1$	$0$	$1$	$6$

Subtract row $2$ from row $3$ : $R_{3} = R_{3} - R_{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Solution
$Z$	$-1$	$0$	$2$	$0$	$16$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$S_{2}$	$\frac{1}{2}$	$0$	$- \frac{1}{2}$	$1$	$2$

The entering variable is $x_{1}$ , because it has the most negative coefficient $-1$ in the Z-row.

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Solution	Ratio
$Z$	$-1$	$0$	$2$	$0$	$16$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$	$\frac{4}{\frac{1}{2}} = 8$
$S_{2}$	$\frac{1}{2}$	$0$	$- \frac{1}{2}$	$1$	$2$	$\frac{2}{\frac{1}{2}} = 4$

The leaving variable is $S_{2}$ , because it has the smallest ratio.

Multiply row $2$ by $2$ : $R_{2} = 2 R_{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Solution
$Z$	$-1$	$0$	$2$	$0$	$16$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$x_{1}$	$1$	$0$	$-1$	$2$	$4$

Add row $3$ to row $1$ : $R_{1} = R_{1} + R_{3}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Solution
$Z$	$0$	$0$	$1$	$2$	$20$
$x_{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$4$
$x_{1}$	$1$	$0$	$-1$	$2$	$4$

Subtract row $3$ multiplied by $\frac{1}{2}$ from row $2$ : $R_{2} = R_{2} - \frac{R_{3}}{2}$ .

Basic	$x_{1}$	$x_{2}$	$S_{1}$	$S_{2}$	Solution
$Z$	$0$	$0$	$1$	$2$	$20$
$x_{2}$	$0$	$1$	$1$	$-1$	$2$
$x_{1}$	$1$	$0$	$-1$	$2$	$4$

None of the Z-row coefficients are negative.

The optimum is reached.

The following solution is obtained: $\left(x_{1}, x_{2}, S_{1}, S_{2}\right) = \left(4, 2, 0, 0\right)$ .

Answer

$Z = 20$ A is achieved at $\left(x_{1}, x_{2}\right) = \left(4, 2\right)$ A.

Simplex Method Calculator

Solve optimization problems using the simplex method

Your Input

Solution

Answer