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.

Comma-separated.

If the calculator did not compute something or you have identified an error, or you have a suggestion/feedback, please write it in the comments below.

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}$$$SolutionRatio
$$$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}$$$SolutionRatio
$$$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.