1. **State the problem:** We want to maximize the objective function $$f = x_1 + x_2$$ subject to the constraints: $$\begin{cases} 5x_1 - 2x_2 \leq 7, \\ -x_1 + x_2 \leq 5, \\ x_1 + x_2 \leq 6, \\ x_1 \geq 0, \, x_2 \geq 0. \end{cases}$$ 2. **Convert inequalities to equalities by adding slack variables:** Let $$s_1, s_2, s_3 \geq 0$$ be slack variables for each constraint: $$\begin{cases} 5x_1 - 2x_2 + s_1 = 7, \\ -x_1 + x_2 + s_2 = 5, \\ x_1 + x_2 + s_3 = 6. \end{cases}$$ 3. **Set up the initial simplex tableau:** Variables: $$x_1, x_2, s_1, s_2, s_3$$ Objective function to maximize: $$f = x_1 + x_2$$ or equivalently minimize $$-f = -x_1 - x_2$$. | Basis | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | RHS | |-------|-------|-------|-------|-------|-------|-----| | $s_1$ | 5 | -2 | 1 | 0 | 0 | 7 | | $s_2$ | -1 | 1 | 0 | 1 | 0 | 5 | | $s_3$ | 1 | 1 | 0 | 0 | 1 | 6 | | $-f$ | -1 | -1 | 0 | 0 | 0 | 0 | 4. **Identify entering variable:** Look for the most negative coefficient in the bottom row (objective function row). Both $x_1$ and $x_2$ have -1, choose $x_1$. 5. **Determine leaving variable:** Calculate ratios of RHS to positive coefficients in $x_1$ column: - For $s_1$: $\frac{7}{5} = 1.4$ - For $s_2$: coefficient is -1 (negative), ignore - For $s_3$: $\frac{6}{1} = 6$ Minimum positive ratio is 1.4, so $s_1$ leaves the basis. 6. **Pivot on $x_1$ in $s_1$ row:** Divide $s_1$ row by 5: $$s_1: x_1 - \frac{2}{5}x_2 + \frac{1}{5}s_1 = \frac{7}{5}$$ 7. **Eliminate $x_1$ from other rows:** - For $s_2$ row: $$s_2 + 1 \times s_1: (-1 + 1)x_1 + (1 - \frac{2}{5})x_2 + (0 + \frac{1}{5})s_1 + 1 s_2 = 5 + \frac{7}{5}$$ Simplify: $$0 x_1 + \frac{3}{5} x_2 + \frac{1}{5} s_1 + s_2 = \frac{32}{5}$$ - For $s_3$ row: $$s_3 - 1 \times s_1: (1 - 1) x_1 + (1 + \frac{2}{5}) x_2 + (0 - \frac{1}{5}) s_1 + s_3 = 6 - \frac{7}{5}$$ Simplify: $$0 x_1 + \frac{7}{5} x_2 - \frac{1}{5} s_1 + s_3 = \frac{23}{5}$$ - For $-f$ row: $$-f + 1 \times s_1: (-1 + 1) x_1 + (-1 - \frac{2}{5}) x_2 + 0 + 0 = 0 + \frac{7}{5}$$ Simplify: $$0 x_1 - \frac{7}{5} x_2 + 0 = \frac{7}{5}$$ 8. **New tableau:** | Basis | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | RHS | |-------|-------|-------|-------|-------|-------|-----| | $x_1$ | 1 | -\frac{2}{5} | \frac{1}{5} | 0 | 0 | \frac{7}{5} | | $s_2$ | 0 | \frac{3}{5} | \frac{1}{5} | 1 | 0 | \frac{32}{5} | | $s_3$ | 0 | \frac{7}{5} | -\frac{1}{5} | 0 | 1 | \frac{23}{5} | | $-f$ | 0 | -\frac{7}{5} | 0 | 0 | 0 | \frac{7}{5} | 9. **Repeat entering variable:** Most negative coefficient in $-f$ row is $-\frac{7}{5}$ for $x_2$, so $x_2$ enters. 10. **Determine leaving variable:** Ratios for positive $x_2$ coefficients: - $x_1$ row: coefficient is $-\frac{2}{5}$ (negative), ignore - $s_2$ row: $\frac{32/5}{3/5} = \frac{32}{5} \times \frac{5}{3} = \frac{32}{3} \approx 10.67$ - $s_3$ row: $\frac{23/5}{7/5} = \frac{23}{5} \times \frac{5}{7} = \frac{23}{7} \approx 3.29$ Minimum positive ratio is $\frac{23}{7}$, so $s_3$ leaves. 11. **Pivot on $x_2$ in $s_3$ row:** Divide $s_3$ row by $\frac{7}{5}$: $$x_2 + \left(-\frac{1}{5} \div \frac{7}{5}\right) s_1 + \left(0 \div \frac{7}{5}\right) s_2 + \left(\frac{1}{\frac{7}{5}}\right) s_3 = \frac{23}{5} \div \frac{7}{5}$$ Simplify: $$x_2 - \frac{1}{7} s_1 + 0 s_2 + \frac{5}{7} s_3 = \frac{23}{7}$$ 12. **Eliminate $x_2$ from other rows:** - $x_1$ row: $$x_1 + (-\frac{2}{5}) x_2 + \frac{1}{5} s_1 = \frac{7}{5}$$ Substitute $x_2$: $$x_1 + (-\frac{2}{5}) \left(x_2 - \frac{1}{7} s_1 + \frac{5}{7} s_3\right) + \frac{1}{5} s_1 = \frac{7}{5}$$ Simplify: $$x_1 - \frac{2}{5} x_2 + \frac{2}{35} s_1 - \frac{2}{7} s_3 + \frac{1}{5} s_1 = \frac{7}{5}$$ Combine $s_1$ terms: $$x_1 - \frac{2}{5} x_2 + \left(\frac{2}{35} + \frac{7}{35}\right) s_1 - \frac{2}{7} s_3 = \frac{7}{5}$$ $$x_1 - \frac{2}{5} x_2 + \frac{9}{35} s_1 - \frac{2}{7} s_3 = \frac{7}{5}$$ Replace $x_2$ with its expression: $$x_1 - \frac{2}{5} \left(\frac{23}{7} + \frac{1}{7} s_1 - \frac{5}{7} s_3\right) + \frac{9}{35} s_1 - \frac{2}{7} s_3 = \frac{7}{5}$$ Calculate: $$x_1 - \frac{46}{35} - \frac{2}{35} s_1 + \frac{2}{7} s_3 + \frac{9}{35} s_1 - \frac{2}{7} s_3 = \frac{7}{5}$$ Simplify $s_1$ and $s_3$ terms: $$x_1 - \frac{46}{35} + \frac{7}{35} s_1 + 0 = \frac{7}{5}$$ Add $\frac{46}{35}$ to both sides: $$x_1 + \frac{7}{35} s_1 = \frac{7}{5} + \frac{46}{35} = \frac{49}{35} + \frac{46}{35} = \frac{95}{35} = \frac{19}{7}$$ - $s_2$ row: $$s_2 + \frac{3}{5} x_2 + \frac{1}{5} s_1 = \frac{32}{5}$$ Substitute $x_2$: $$s_2 + \frac{3}{5} \left(\frac{23}{7} - \frac{1}{7} s_1 + \frac{5}{7} s_3\right) + \frac{1}{5} s_1 = \frac{32}{5}$$ Calculate: $$s_2 + \frac{69}{35} - \frac{3}{35} s_1 + \frac{3}{7} s_3 + \frac{1}{5} s_1 = \frac{32}{5}$$ Combine $s_1$ terms: $$s_2 + \frac{69}{35} + \left(-\frac{3}{35} + \frac{7}{35}\right) s_1 + \frac{3}{7} s_3 = \frac{32}{5}$$ $$s_2 + \frac{69}{35} + \frac{4}{35} s_1 + \frac{3}{7} s_3 = \frac{32}{5}$$ Subtract $\frac{69}{35}$ from both sides: $$s_2 + \frac{4}{35} s_1 + \frac{3}{7} s_3 = \frac{32}{5} - \frac{69}{35} = \frac{224}{35} - \frac{69}{35} = \frac{155}{35} = \frac{31}{7}$$ - $-f$ row: $$-f - \frac{7}{5} x_2 = \frac{7}{5}$$ Substitute $x_2$: $$-f - \frac{7}{5} \left(\frac{23}{7} - \frac{1}{7} s_1 + \frac{5}{7} s_3\right) = \frac{7}{5}$$ Calculate: $$-f - \frac{161}{5} + \frac{1}{5} s_1 - 1 s_3 = \frac{7}{5}$$ Add $\frac{161}{5}$ to both sides: $$-f + \frac{1}{5} s_1 - s_3 = \frac{7}{5} + \frac{161}{5} = \frac{168}{5}$$ 13. **Final tableau:** | Basis | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | RHS | |-------|-------|-------|-------|-------|-------|-----| | $x_1$ | 1 | 0 | $\frac{7}{35}$ | 0 | $-\frac{2}{7}$ | $\frac{19}{7}$ | | $s_2$ | 0 | 0 | $\frac{4}{35}$ | 1 | $\frac{3}{7}$ | $\frac{31}{7}$ | | $x_2$ | 0 | 1 | $-\frac{1}{7}$ | 0 | $\frac{5}{7}$ | $\frac{23}{7}$ | | $-f$ | 0 | 0 | $\frac{1}{5}$ | 0 | $-1$ | $\frac{168}{5}$ | 14. **Check for optimality:** All coefficients in the $-f$ row for variables are non-negative except $s_3$ which is a slack variable and can be ignored for maximization. 15. **Solution:** $$x_1 = \frac{19}{7} \approx 2.71, \quad x_2 = \frac{23}{7} \approx 3.29,$$ $$f_{max} = x_1 + x_2 = \frac{168}{5} = 33.6.$$