Answer :
To solve the given linear programming problem (LPP) using the Simplex Method, we need to transform it into a form suitable for applying the simplex algorithm. Here are the steps for solving this LPP:
### 1. Formulate the Problem
First, let's state the given problem in standard form:
Objective: Maximize [tex]\( Z = 5x_1 + 3x_2 \)[/tex]
Subject to the constraints:
[tex]\[ x_1 + x_2 \leq 10 \][/tex]
[tex]\[ 3x_1 + 2x_2 \leq 12 \][/tex]
[tex]\[ x_1 \geq 0 \][/tex]
[tex]\[ x_2 \geq 0 \][/tex]
### 2. Convert Inequalities to Equations
We introduce slack variables [tex]\( S_1 \)[/tex] and [tex]\( S_2 \)[/tex] to convert the inequalities into equalities:
[tex]\[ x_1 + x_2 + S_1 = 10 \][/tex]
[tex]\[ 3x_1 + 2x_2 + S_2 = 12 \][/tex]
So, the problem in terms of [tex]\( x_1 \)[/tex], [tex]\( x_2 \)[/tex], and slack variables [tex]\( S_1 \)[/tex] and [tex]\( S_2 \)[/tex] is:
Objective: Maximize [tex]\( Z = 5x_1 + 3x_2 \)[/tex]
Subject to:
[tex]\[ x_1 + x_2 + S_1 = 10 \][/tex]
[tex]\[ 3x_1 + 2x_2 + S_2 = 12 \][/tex]
[tex]\[ x_1, x_2, S_1, S_2 \geq 0 \][/tex]
### 3. Form the Initial Simplex Tableau
We create an initial simplex tableau for the system:
[tex]\[ \begin{array}{|c|c|c|c|c|c|c|} \hline \text{Basis} & x_1 & x_2 & S_1 & S_2 & \text{RHS} \\ \hline S_1 & 1 & 1 & 1 & 0 & 10 \\ S_2 & 3 & 2 & 0 & 1 & 12 \\ \hline Z & -5 & -3 & 0 & 0 & 0 \\ \hline \end{array} \][/tex]
### 4. Perform the Simplex Algorithm
Iteration 1:
1. Identify the entering variable (most negative in the bottom row): [tex]\( x_1 \)[/tex] (with a coefficient of -5).
2. Identify the leaving variable using the minimum ratio test:
[tex]\[ \frac{10}{1} = 10 \quad \text{(for row 1)} \][/tex]
[tex]\[ \frac{12}{3} = 4 \quad \text{(for row 2)} \][/tex]
[tex]\( S_2 \)[/tex] will leave the basis since it has the smallest ratio.
3. Pivot around [tex]\( x_1 \)[/tex] in row 2:
- Divide row 2 by the pivot element (3) to make the pivot element 1.
- Adjust other rows ensuring the pivot column becomes [tex]\( (0,1) \)[/tex].
New tableau:
[tex]\[ \begin{array}{|c|c|c|c|c|c|c|} \hline \text{Basis} & x_1 & x_2 & S_1 & S_2 & \text{RHS} \\ \hline S_1 & 0 & \frac{1}{3} & 1 & -\frac{1}{3} & 6 \\ x_1 & 1 & \frac{2}{3} & 0 & \frac{1}{3} & 4 \\ \hline Z & 0 & \frac{1}{3} & 0 & \frac{5}{3} & 20 \\ \hline \end{array} \][/tex]
Iteration 2:
1. Identify the entering variable: [tex]\( x_2 \)[/tex] (with a coefficient of [tex]\(\frac{1}{3}\)[/tex]).
2. Identify the leaving variable using the minimum ratio test:
[tex]\[ \frac{6}{\frac{1}{3}} = 18 \quad \text{(for row 1)} \][/tex]
[tex]\[ \frac{4}{\frac{2}{3}} \approx 6 \quad \text{(for row 2)} \][/tex]
[tex]\( S_1 \)[/tex] will leave the basis.
3. Pivot around [tex]\( x_2 \)[/tex] in row 1:
- Divide row 1 by the pivot element ([tex]\(\frac{1}{3}\)[/tex]) to make the pivot element 1.
- Adjust other rows ensuring the pivot column becomes [tex]\( (0,1) \)[/tex].
New tableau:
[tex]\[ \begin{array}{|c|c|c|c|c|c|c|} \hline \text{Basis} & x_1 & x_2 & S_1 & S_2 & \text{RHS} \\ \hline x_2 & 0 & 1 & 3 & -1 & 18 \\ x_1 & 1 & 0 & -2 & 1 & 2 \\ \hline Z & 0 & 0 & -1 & 1 & 20 \\ \hline \end{array} \][/tex]
Since there are no more negative coefficients in the bottom row of the tableau, the simplex algorithm has found the optimal solution.
### 5. Interpret the Solution
From the final simplex tableau, the values of the variables are:
[tex]\[ x_1 = 4 \][/tex]
[tex]\[ x_2 = 0 \][/tex]
Objective Value:
[tex]\[ Z = 5x_1 + 3x_2 = 5(4) + 3(0) = 20 \][/tex]
So, the optimal value of the objective function [tex]\( Z \)[/tex] is 20, attained at [tex]\( x_1 = 4 \)[/tex] and [tex]\( x_2 = 0 \)[/tex].
### 1. Formulate the Problem
First, let's state the given problem in standard form:
Objective: Maximize [tex]\( Z = 5x_1 + 3x_2 \)[/tex]
Subject to the constraints:
[tex]\[ x_1 + x_2 \leq 10 \][/tex]
[tex]\[ 3x_1 + 2x_2 \leq 12 \][/tex]
[tex]\[ x_1 \geq 0 \][/tex]
[tex]\[ x_2 \geq 0 \][/tex]
### 2. Convert Inequalities to Equations
We introduce slack variables [tex]\( S_1 \)[/tex] and [tex]\( S_2 \)[/tex] to convert the inequalities into equalities:
[tex]\[ x_1 + x_2 + S_1 = 10 \][/tex]
[tex]\[ 3x_1 + 2x_2 + S_2 = 12 \][/tex]
So, the problem in terms of [tex]\( x_1 \)[/tex], [tex]\( x_2 \)[/tex], and slack variables [tex]\( S_1 \)[/tex] and [tex]\( S_2 \)[/tex] is:
Objective: Maximize [tex]\( Z = 5x_1 + 3x_2 \)[/tex]
Subject to:
[tex]\[ x_1 + x_2 + S_1 = 10 \][/tex]
[tex]\[ 3x_1 + 2x_2 + S_2 = 12 \][/tex]
[tex]\[ x_1, x_2, S_1, S_2 \geq 0 \][/tex]
### 3. Form the Initial Simplex Tableau
We create an initial simplex tableau for the system:
[tex]\[ \begin{array}{|c|c|c|c|c|c|c|} \hline \text{Basis} & x_1 & x_2 & S_1 & S_2 & \text{RHS} \\ \hline S_1 & 1 & 1 & 1 & 0 & 10 \\ S_2 & 3 & 2 & 0 & 1 & 12 \\ \hline Z & -5 & -3 & 0 & 0 & 0 \\ \hline \end{array} \][/tex]
### 4. Perform the Simplex Algorithm
Iteration 1:
1. Identify the entering variable (most negative in the bottom row): [tex]\( x_1 \)[/tex] (with a coefficient of -5).
2. Identify the leaving variable using the minimum ratio test:
[tex]\[ \frac{10}{1} = 10 \quad \text{(for row 1)} \][/tex]
[tex]\[ \frac{12}{3} = 4 \quad \text{(for row 2)} \][/tex]
[tex]\( S_2 \)[/tex] will leave the basis since it has the smallest ratio.
3. Pivot around [tex]\( x_1 \)[/tex] in row 2:
- Divide row 2 by the pivot element (3) to make the pivot element 1.
- Adjust other rows ensuring the pivot column becomes [tex]\( (0,1) \)[/tex].
New tableau:
[tex]\[ \begin{array}{|c|c|c|c|c|c|c|} \hline \text{Basis} & x_1 & x_2 & S_1 & S_2 & \text{RHS} \\ \hline S_1 & 0 & \frac{1}{3} & 1 & -\frac{1}{3} & 6 \\ x_1 & 1 & \frac{2}{3} & 0 & \frac{1}{3} & 4 \\ \hline Z & 0 & \frac{1}{3} & 0 & \frac{5}{3} & 20 \\ \hline \end{array} \][/tex]
Iteration 2:
1. Identify the entering variable: [tex]\( x_2 \)[/tex] (with a coefficient of [tex]\(\frac{1}{3}\)[/tex]).
2. Identify the leaving variable using the minimum ratio test:
[tex]\[ \frac{6}{\frac{1}{3}} = 18 \quad \text{(for row 1)} \][/tex]
[tex]\[ \frac{4}{\frac{2}{3}} \approx 6 \quad \text{(for row 2)} \][/tex]
[tex]\( S_1 \)[/tex] will leave the basis.
3. Pivot around [tex]\( x_2 \)[/tex] in row 1:
- Divide row 1 by the pivot element ([tex]\(\frac{1}{3}\)[/tex]) to make the pivot element 1.
- Adjust other rows ensuring the pivot column becomes [tex]\( (0,1) \)[/tex].
New tableau:
[tex]\[ \begin{array}{|c|c|c|c|c|c|c|} \hline \text{Basis} & x_1 & x_2 & S_1 & S_2 & \text{RHS} \\ \hline x_2 & 0 & 1 & 3 & -1 & 18 \\ x_1 & 1 & 0 & -2 & 1 & 2 \\ \hline Z & 0 & 0 & -1 & 1 & 20 \\ \hline \end{array} \][/tex]
Since there are no more negative coefficients in the bottom row of the tableau, the simplex algorithm has found the optimal solution.
### 5. Interpret the Solution
From the final simplex tableau, the values of the variables are:
[tex]\[ x_1 = 4 \][/tex]
[tex]\[ x_2 = 0 \][/tex]
Objective Value:
[tex]\[ Z = 5x_1 + 3x_2 = 5(4) + 3(0) = 20 \][/tex]
So, the optimal value of the objective function [tex]\( Z \)[/tex] is 20, attained at [tex]\( x_1 = 4 \)[/tex] and [tex]\( x_2 = 0 \)[/tex].
