Solve by Simplex method: Maximize z = 7x 1 + 5x 2 , subject to x 1 + 2x 2 6 , 4x 1 + 3x 2 12 , x 1, x 2 0 . [6]

Solution by Simplex Method

We are given the linear programming problem (LPP) to maximize: $$z=7x_1+5x_2$$ subject to the constraints: $$\begin{array}{rl}{x}_1+2x_2& \le 6,\\ 4x_1+3x_2& \le 12,\\ x_1,x_2& \ge 0.\end{array}$$

---

Step 1: Convert the Inequalities into Equations

To apply the simplex method, we convert the inequalities into equations by introducing slack variables $s_1$ and $s_2$: $$\begin{array}{rl}{x}_1+2x_2+s_1& =6,\\ 4x_1+3x_2+s_2& =12,\\ x_1,x_2,s_1,s_2& \ge 0.\end{array}$$

The objective function remains: $$z=7x_1+5x_2+0s_1+0s_2.$$

---

Step 2: Write the Initial Simplex Tableau

The initial tableau is constructed as follows:

---

Step 3: Check for Optimality

The optimality condition is that all coefficients in the $z$-row must be non-negative. Here, $-7$ and $-5$ are negative, so the current solution is not optimal.

The entering variable is the one with the most negative coefficient in the $z$-row, which is $x_1$ (since $-7<-5$).

---

Step 4: Determine the Leaving Variable

To find the leaving variable, we compute the ratio test for each positive entry in the $x_1$ column:

$$\text{Ratio}=\frac{\text{RHS}}{\text{Coefficient of }{x}_1}$$

• For $s_1$: $\frac{6}{1}=6$
• For $s_2$: $\frac{12}{4}=3$

The minimum ratio is 3, so $s_2$ is the leaving variable.

---

Step 5: Perform Pivot Operation

We pivot on the element 4 (intersection of $x_1$ row and $s_2$ column). The new tableau is obtained by:

1. Dividing the pivot row by 4: $$\text{New }{s}_2\text{ row}=\frac{4x_1+3x_2+s_2}{4}=x_1+\frac{3}{4}{x}_2+\frac{1}{4}{s}_2=3.$$

2. Eliminating $x_1$ from other rows:

   • For $s_1$ row: $$(x_1+2x_2+s_1)-(x_1+\frac{3}{4}{x}_2+\frac{1}{4}{s}_2)=\frac{5}{4}{x}_2-\frac{1}{4}{s}_2+3.$$
   • For $z$ row: $$(-7x_1-5x_2)-(-4)(x_1+\frac{3}{4}{x}_2+\frac{1}{4}{s}_2)=-3x_2+s_2.$$

The updated tableau is:

---

Step 6: Check Optimality Again

The $z$-row now has $-3$ under $x_2$, which is still negative. Thus, the solution is not yet optimal.

The entering variable is now $x_2$ (since $-3<0$).

---

Step 7: Determine the Leaving Variable (Second Iteration)

Compute the ratio test for the $x_2$ column:

• For $s_1$: $\frac{3}{\frac{5}{4}}=\frac{12}{5}=2.4$
• For $x_1$: $\frac{3}{\frac{3}{4}}=4$

The minimum ratio is 2.4, so $s_1$ is the leaving variable.

---

Step 8: Perform Pivot Operation (Second Iteration)

We pivot on the element $\frac{5}{4}$ (intersection of $x_2$ row and $s_1$ column). The new tableau is obtained by:

1. Dividing the pivot row by $\frac{5}{4}$: $$\text{New }{x}_2\text{ row}=\frac{\frac{5}{4}{x}_2+s_1-\frac{1}{4}{s}_2}{5/4}=x_2+\frac{4}{5}{s}_1-\frac{1}{5}{s}_2=\frac{12}{5}.$$

2. Eliminating $x_2$ from other rows:

   • For $x_1$ row: $$(x_1+\frac{3}{4}{x}_2+\frac{1}{4}{s}_2)-\frac{3}{4}(x_2+\frac{4}{5}{s}_1-\frac{1}{5}{s}_2)=x_1+\frac{3}{5}{s}_1+\frac{2}{5}{s}_2=\frac{9}{5}.$$
   • For $z$ row: $$(-3x_2+s_2)-(-3)(x_2+\frac{4}{5}{s}_1-\frac{1}{5}{s}_2)=\frac{12}{5}{s}_1+\frac{12}{5}{s}_2.$$

The updated tableau is:

---

Step 9: Final Optimality Check

All coefficients in the $z$-row are now non-negative, so the current solution is optimal.

---

Step 10: Extract the Solution

From the final tableau:

• $x_1=\frac{9}{5}=1.8$,
• $x_2=\frac{12}{5}=2.4$,
• $s_1=0$,
• $s_2=0$.

The maximum value of $z$ is: $$z=\frac{126}{5}=\mathrm{25.2.}$$

---

Final Answer

The optimal solution is: $$\boxed{x_1=1.8,x_2=2.4,\text{Maximum }z=25.2}$$