# Simplex Method Calculator

## Solve optimization problems using the simplex method

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.**