Let's solve the linear programming problem using the simplex method step-by-step.
We are given the objective function:
[tex]\[ \operatorname{Max} Z = 3x_1 + 5x_2 \][/tex]
subject to the constraints:
[tex]\[
\begin{aligned}
1. &\ x_2 \leq 6 \\
2. &\ 3x_1 + 2x_2 \leq 18 \\
3. &\ x_1, x_2 \geq 0
\end{aligned}
\][/tex]
### Step 1: Convert Inequalities to Equalities
We introduce slack variables [tex]\(s_1\)[/tex] and [tex]\(s_2\)[/tex] to convert the inequalities into equalities:
1. [tex]\(x_2 + s_1 = 6\)[/tex]
2. [tex]\(3x_1 + 2x_2 + s_2 = 18\)[/tex]
Where [tex]\(s_1, s_2 \geq 0\)[/tex].
### Step 2: Set Up the Initial Simplex Tableau
[tex]\[
\begin{array}{c|cccc|c}
& x_1 & x_2 & s_1 & s_2 & \text{RHS} \\
\hline
\text{Constraint 1} & 0 & 1 & 1 & 0 & 6 \\
\text{Constraint 2} & 3 & 2 & 0 & 1 & 18 \\
\hline
\text{Objective Function} & -3 & -5 & 0 & 0 & 0 \\
\end{array}
\][/tex]
### Step 3: Perform Simplex Algorithm Iterations
#### Iteration 1:
Identify the entering variable (most negative in the objective row):
- Entering variable: [tex]\(x_2\)[/tex] (coefficient -5)
Identify the leaving variable (minimum ratio test):
- Ratios: [tex]\(\frac{6}{1} = 6\)[/tex], [tex]\(\frac{18}{2} = 9\)[/tex]
- Leaving variable: [tex]\(s_1\)[/tex]
Pivot on the element in the [tex]\(x_2\)[/tex] column and [tex]\(s_1\)[/tex] row.
Update the tableau:
[tex]\[
\begin{array}{c|cccc|c}
& x_1 & x_2 & s_1 & s_2 & \text{RHS} \\
\hline
\text{Row 1 (New Basis)} & 0 & 1 & 1 & 0 & 6 \\
\text{Row 2} & 3 & 2 & 0 & 1 & 18 \\
\hline
\text{Objective Function} & -3 & 0 & 5 & 0 & 30 \\
\end{array}
\][/tex]
#### Iteration 2:
Identify the entering variable (most negative in the objective row):
- Entering variable: [tex]\(x_1\)[/tex] (coefficient -3)
Identify the leaving variable (minimum ratio test):
- Ratios: [tex]\(\frac{18}{3} = 6\)[/tex]
Pivot on the element in the [tex]\(x_1\)[/tex] column and the second row:
Update the tableau:
[tex]\[
\begin{array}{c|cccc|c}
& x_1 & x_2 & s_1 & s_2 & \text{RHS} \\
\hline
\text{Row 1} & 0 & 1 & 1 & 0 & 6 \\
\text{Row 2 (New Basis)} & 1 & 2/3 & 0 & 1/3 & 6 \\
\hline
\text{Objective Function} & 0 & 1 & 5 & 1 & 36 \\
\end{array}
\][/tex]
The objective row has no more negative coefficients, which means we have reached the optimal solution.
### Step 4: Extract the Solution
From the final tableau:
- [tex]\(x_1 = 2\)[/tex]
- [tex]\(x_2 = 6\)[/tex]
The maximum value of [tex]\(Z\)[/tex] is:
[tex]\[ Z = 3(2) + 5(6) = 6 + 30 = 36 \][/tex]
### Conclusion
The optimal solution is:
[tex]\[ x_1 = 2, \quad x_2 = 6 \][/tex]
The maximum value of the objective function is:
[tex]\[ Z = 36 \][/tex]
