Maximize $7 x + 2 y$, subject to $\begin{cases} 3 x + 5 y \geq 20 \\ 3 x + y \leq 16 \\ - 2 x + y \leq 1 \\ x \geq 0 \\ y \geq 0 \end{cases}$

The calculator will maximize $7 x + 2 y$, subject to $\begin{cases} 3 x + 5 y \geq 20 \\ 3 x + y \leq 16 \\ - 2 x + y \leq 1 \\ x \geq 0 \\ y \geq 0 \end{cases}$, with steps shown.
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.

Maximize $Z = 7 x + 2 y$, subject to $\begin{cases} 3 x + 5 y \geq 20 \\ 3 x + y \leq 16 \\ - 2 x + y \leq 1 \\ x \geq 0 \\ y \geq 0 \end{cases}.$

Solution

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

$$Z = 7 x + 2 y \to max$\begin{cases} 3 x + 5 y \geq 20 \\ 3 x + y \leq 16 \\ - 2 x + y \leq 1 \\ x, y \geq 0 \end{cases} Add variables (slack or surplus) to turn all the inequalities into equalities: Z = 7 x + 2 y \to max$\begin{cases} 3 x + 5 y - S_{1} = 20 \\ 3 x + y + S_{2} = 16 \\ - 2 x + y + S_{3} = 1 \\ x, y, S_{1}, S_{2}, S_{3} \geq 0 \end{cases}$$

Since we don't have a basis, add an artificial variable:

$$Z = 7 x + 2 y \to max$\begin{cases} 3 x + 5 y - S_{1} + Y_{1} = 20 \\ 3 x + y + S_{2} = 16 \\ - 2 x + y + S_{3} = 1 \\ x, y, S_{1}, S_{2}, S_{3}, Y_{1} \geq 0 \end{cases} Penalize the artificial variable in the objective function: Z = 7 x + 2 y - M Y_{1} \to max$\begin{cases} 3 x + 5 y - S_{1} + Y_{1} = 20 \\ 3 x + y + S_{2} = 16 \\ - 2 x + y + S_{3} = 1 \\ x, y, S_{1}, S_{2}, S_{3}, Y_{1} \geq 0 \end{cases}$$

Write down the simplex tableau:

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $-7$ $-2$ $0$ $0$ $0$ $M$ $0$ $Y_{1}$ $3$ $5$ $-1$ $0$ $0$ $1$ $20$ $S_{2}$ $3$ $1$ $0$ $1$ $0$ $0$ $16$ $S_{3}$ $-2$ $1$ $0$ $0$ $1$ $0$ $1$

Make the Z-row consistent with the rest of the tableau.

Subtract row $2$ multiplied by $M$ from row $1$: $R_{1} = R_{1} - M R_{2}$.

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $- 3 M - 7$ $- 5 M - 2$ $M$ $0$ $0$ $0$ $- 20 M$ $Y_{1}$ $3$ $5$ $-1$ $0$ $0$ $1$ $20$ $S_{2}$ $3$ $1$ $0$ $1$ $0$ $0$ $16$ $S_{3}$ $-2$ $1$ $0$ $0$ $1$ $0$ $1$

The entering variable is $y$, because it has the most negative coefficient $- 5 M - 2$ in the Z-row.

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution Ratio $Z$ $- 3 M - 7$ $- 5 M - 2$ $M$ $0$ $0$ $0$ $- 20 M$ $Y_{1}$ $3$ $5$ $-1$ $0$ $0$ $1$ $20$ $\frac{20}{5} = 4$ $S_{2}$ $3$ $1$ $0$ $1$ $0$ $0$ $16$ $\frac{16}{1} = 16$ $S_{3}$ $-2$ $1$ $0$ $0$ $1$ $0$ $1$ $\frac{1}{1} = 1$

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

Add row $4$ multiplied by $5 M + 2$ to row $1$: $R_{1} = R_{1} + \left(5 M + 2\right) R_{4}$.

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $- 13 M - 11$ $0$ $M$ $0$ $5 M + 2$ $0$ $2 - 15 M$ $Y_{1}$ $3$ $5$ $-1$ $0$ $0$ $1$ $20$ $S_{2}$ $3$ $1$ $0$ $1$ $0$ $0$ $16$ $y$ $-2$ $1$ $0$ $0$ $1$ $0$ $1$

Subtract row $4$ multiplied by $5$ from row $2$: $R_{2} = R_{2} - 5 R_{4}$.

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $- 13 M - 11$ $0$ $M$ $0$ $5 M + 2$ $0$ $2 - 15 M$ $Y_{1}$ $13$ $0$ $-1$ $0$ $-5$ $1$ $15$ $S_{2}$ $3$ $1$ $0$ $1$ $0$ $0$ $16$ $y$ $-2$ $1$ $0$ $0$ $1$ $0$ $1$

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

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $- 13 M - 11$ $0$ $M$ $0$ $5 M + 2$ $0$ $2 - 15 M$ $Y_{1}$ $13$ $0$ $-1$ $0$ $-5$ $1$ $15$ $S_{2}$ $5$ $0$ $0$ $1$ $-1$ $0$ $15$ $y$ $-2$ $1$ $0$ $0$ $1$ $0$ $1$

The entering variable is $x$, because it has the most negative coefficient $- 13 M - 11$ in the Z-row.

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution Ratio $Z$ $- 13 M - 11$ $0$ $M$ $0$ $5 M + 2$ $0$ $2 - 15 M$ $Y_{1}$ $13$ $0$ $-1$ $0$ $-5$ $1$ $15$ $\frac{15}{13}$ $S_{2}$ $5$ $0$ $0$ $1$ $-1$ $0$ $15$ $\frac{15}{5} = 3$ $y$ $-2$ $1$ $0$ $0$ $1$ $0$ $1$ $\frac{1}{-2}$ (negative denominator, ignore)

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

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

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $- 13 M - 11$ $0$ $M$ $0$ $5 M + 2$ $0$ $2 - 15 M$ $x$ $1$ $0$ $- \frac{1}{13}$ $0$ $- \frac{5}{13}$ $\frac{1}{13}$ $\frac{15}{13}$ $S_{2}$ $5$ $0$ $0$ $1$ $-1$ $0$ $15$ $y$ $-2$ $1$ $0$ $0$ $1$ $0$ $1$

Add row $2$ multiplied by $13 M + 11$ to row $1$: $R_{1} = R_{1} + \left(13 M + 11\right) R_{2}$.

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $0$ $0$ $- \frac{11}{13}$ $0$ $- \frac{29}{13}$ $M + \frac{11}{13}$ $\frac{191}{13}$ $x$ $1$ $0$ $- \frac{1}{13}$ $0$ $- \frac{5}{13}$ $\frac{1}{13}$ $\frac{15}{13}$ $S_{2}$ $5$ $0$ $0$ $1$ $-1$ $0$ $15$ $y$ $-2$ $1$ $0$ $0$ $1$ $0$ $1$

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

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $0$ $0$ $- \frac{11}{13}$ $0$ $- \frac{29}{13}$ $M + \frac{11}{13}$ $\frac{191}{13}$ $x$ $1$ $0$ $- \frac{1}{13}$ $0$ $- \frac{5}{13}$ $\frac{1}{13}$ $\frac{15}{13}$ $S_{2}$ $0$ $0$ $\frac{5}{13}$ $1$ $\frac{12}{13}$ $- \frac{5}{13}$ $\frac{120}{13}$ $y$ $-2$ $1$ $0$ $0$ $1$ $0$ $1$

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

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $0$ $0$ $- \frac{11}{13}$ $0$ $- \frac{29}{13}$ $M + \frac{11}{13}$ $\frac{191}{13}$ $x$ $1$ $0$ $- \frac{1}{13}$ $0$ $- \frac{5}{13}$ $\frac{1}{13}$ $\frac{15}{13}$ $S_{2}$ $0$ $0$ $\frac{5}{13}$ $1$ $\frac{12}{13}$ $- \frac{5}{13}$ $\frac{120}{13}$ $y$ $0$ $1$ $- \frac{2}{13}$ $0$ $\frac{3}{13}$ $\frac{2}{13}$ $\frac{43}{13}$

The entering variable is $S_{3}$, because it has the most negative coefficient $- \frac{29}{13}$ in the Z-row.

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution Ratio $Z$ $0$ $0$ $- \frac{11}{13}$ $0$ $- \frac{29}{13}$ $M + \frac{11}{13}$ $\frac{191}{13}$ $x$ $1$ $0$ $- \frac{1}{13}$ $0$ $- \frac{5}{13}$ $\frac{1}{13}$ $\frac{15}{13}$ $\frac{\frac{15}{13}}{- \frac{5}{13}}$ (negative denominator, ignore) $S_{2}$ $0$ $0$ $\frac{5}{13}$ $1$ $\frac{12}{13}$ $- \frac{5}{13}$ $\frac{120}{13}$ $\frac{\frac{120}{13}}{\frac{12}{13}} = 10$ $y$ $0$ $1$ $- \frac{2}{13}$ $0$ $\frac{3}{13}$ $\frac{2}{13}$ $\frac{43}{13}$ $\frac{\frac{43}{13}}{\frac{3}{13}} = \frac{43}{3}$

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

Multiply row $2$ by $\frac{13}{12}$: $R_{2} = \frac{13 R_{2}}{12}$.

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $0$ $0$ $- \frac{11}{13}$ $0$ $- \frac{29}{13}$ $M + \frac{11}{13}$ $\frac{191}{13}$ $x$ $1$ $0$ $- \frac{1}{13}$ $0$ $- \frac{5}{13}$ $\frac{1}{13}$ $\frac{15}{13}$ $S_{3}$ $0$ $0$ $\frac{5}{12}$ $\frac{13}{12}$ $1$ $- \frac{5}{12}$ $10$ $y$ $0$ $1$ $- \frac{2}{13}$ $0$ $\frac{3}{13}$ $\frac{2}{13}$ $\frac{43}{13}$

Add row $3$ multiplied by $\frac{29}{13}$ to row $1$: $R_{1} = R_{1} + \frac{29 R_{3}}{13}$.

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $0$ $0$ $\frac{1}{12}$ $\frac{29}{12}$ $0$ $M - \frac{1}{12}$ $37$ $x$ $1$ $0$ $- \frac{1}{13}$ $0$ $- \frac{5}{13}$ $\frac{1}{13}$ $\frac{15}{13}$ $S_{3}$ $0$ $0$ $\frac{5}{12}$ $\frac{13}{12}$ $1$ $- \frac{5}{12}$ $10$ $y$ $0$ $1$ $- \frac{2}{13}$ $0$ $\frac{3}{13}$ $\frac{2}{13}$ $\frac{43}{13}$

Add row $3$ multiplied by $\frac{5}{13}$ to row $2$: $R_{2} = R_{2} + \frac{5 R_{3}}{13}$.

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $0$ $0$ $\frac{1}{12}$ $\frac{29}{12}$ $0$ $M - \frac{1}{12}$ $37$ $x$ $1$ $0$ $\frac{1}{12}$ $\frac{5}{12}$ $0$ $- \frac{1}{12}$ $5$ $S_{3}$ $0$ $0$ $\frac{5}{12}$ $\frac{13}{12}$ $1$ $- \frac{5}{12}$ $10$ $y$ $0$ $1$ $- \frac{2}{13}$ $0$ $\frac{3}{13}$ $\frac{2}{13}$ $\frac{43}{13}$

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

 Basic $x$ $y$ $S_{1}$ $S_{2}$ $S_{3}$ $Y_{1}$ Solution $Z$ $0$ $0$ $\frac{1}{12}$ $\frac{29}{12}$ $0$ $M - \frac{1}{12}$ $37$ $x$ $1$ $0$ $\frac{1}{12}$ $\frac{5}{12}$ $0$ $- \frac{1}{12}$ $5$ $S_{3}$ $0$ $0$ $\frac{5}{12}$ $\frac{13}{12}$ $1$ $- \frac{5}{12}$ $10$ $y$ $0$ $1$ $- \frac{1}{4}$ $- \frac{1}{4}$ $0$ $\frac{1}{4}$ $1$

None of the Z-row coefficients are negative.

The optimum is reached.

The following solution is obtained: $\left(x, y, S_{1}, S_{2}, S_{3}, Y_{1}\right) = \left(5, 1, 0, 0, 10, 0\right)$.

$Z = 37$A is achieved at $\left(x, y\right) = \left(5, 1\right)$A.