Learn & Review: LPP | Simple Steps | Solved Problem in Operations Research by kauserwise

Summary of Solving LPP using the Simplex Method

This video explains how to solve a Linear Programming Problem (LPP) using the Simplex method, focusing on a maximization problem.

1. Problem Formulation

• Objective Function: Maximize $Z = 12x_1 + 16x_2$
• Constraints:
  • $10x_1 + 20x_2 \le 120$
  • $8x_1 + 8x_2 \le 80$
  • $x_1, x_2 \ge 0$

2. Introducing Slack Variables

To convert the inequalities into equalities, slack variables ($S_1$ and $S_2$) are introduced.

• $10x_1 + 20x_2 + S_1 = 120$
• $8x_1 + 8x_2 + S_2 = 80$
• $x_1, x_2, S_1, S_2 \ge 0$

The objective function is also modified to include the slack variables with zero coefficients: Maximize $Z = 12x_1 + 16x_2 + 0S_1 + 0S_2$

3. Initial Simplex Table

The initial simplex table is constructed with the following components:

• Cj: Coefficients of the objective function ($12, 16, 0, 0$ for $x_1, x_2, S_1, S_2$).
• Basic Variables (BV): Initially, the slack variables ($S_1, S_2$) are the basic variables.
• Cbi: Coefficients of the basic variables in the objective function ($0, 0$ for $S_1, S_2$).
• Solution (b): The right-hand side values of the constraints ($120, 80$).
• Coefficients of Variables: The coefficients of $x_1, x_2, S_1, S_2$ from the constraint equations.

Initial Simplex Table Structure:

| Cj | | 12 | 16 | 0 | 0 | | | :---- | :---- | :-- | :-- | :-- | :-- | :---- | | Cbi | BV | x1 | x2 | S1 | S2 | Ratio | | 0 | S1 | 10 | 20 | 1 | 0 | 120 | | 0 | S2 | 8 | 8 | 0 | 1 | 80 | | | Zj | 0 | 0 | 0 | 0 | | | | Cj-Zj | 12 | 16 | 0 | 0 | |

4. Calculating Zj and Cj-Zj

• Zj: Calculated by multiplying the Cbi values with the corresponding column coefficients and summing them up.
  • $Zj(x_1) = (0 \times 10) + (0 \times 8) = 0$
  • $Zj(x_2) = (0 \times 20) + (0 \times 8) = 0$
  • $Zj(S_1) = (0 \times 1) + (0 \times 0) = 0$
  • $Zj(S_2) = (0 \times 0) + (0 \times 1) = 0$
• Cj-Zj: The difference between the Cj and Zj values.
  • $Cj-Zj(x_1) = 12 - 0 = 12$
  • $Cj-Zj(x_2) = 16 - 0 = 16$
  • $Cj-Zj(S_1) = 0 - 0 = 0$
  • $Cj-Zj(S_2) = 0 - 0 = 0$

5. Optimality Condition and Iterations

• Optimality Condition (Maximization): All $Cj-Zj$ values must be less than or equal to zero.
• Since there are positive values ($12$ and $16$), optimality is not reached.

First Iteration:

1. Identify Key Column: Select the column with the highest positive $Cj-Zj$ value. Here, it's $16$ for $x_2$. This is the key column.
2. Calculate Ratios: Divide the 'Solution' column values by the corresponding values in the key column.
   • Row 1: $120 / 20 = 6$
   • Row 2: $80 / 8 = 10$
3. Identify Key Row: Select the row with the minimum non-negative ratio. Here, it's $6$ for Row 1. This is the key row.
4. Identify Key Element: The element at the intersection of the key column and key row is the key element ($20$).
5. Identify Entering and Leaving Variables:
   • Entering Variable: The variable corresponding to the key column ($x_2$).
   • Leaving Variable: The basic variable corresponding to the key row ($S_1$).

First Iteration Simplex Table:

• The key row is divided by the key element to get the new values for the entering variable ($x_2$).
• For other rows, a formula is used: New Value = Old Value - (Corresponding Key Column Value * Corresponding Key Row Value / Key Element).
• $Zj$ and $Cj-Zj$ are recalculated.

| Cj | | 12 | 16 | 0 | 0 | | | :---- | :---- | :-- | :-- | :--- | :-- | :---- | | Cbi | BV | x1 | x2 | S1 | S2 | Ratio | | 16 | x2 | 1/2 | 1 | 1/20 | 0 | 6 | | 0 | S2 | 4 | 0 | -1/5 | 1 | 32 | | | Zj | 8 | 16 | 4/5 | 0 | | | | Cj-Zj | 4 | 0 | -4/5 | 0 | |

• Optimality is still not reached as there is a positive $Cj-Zj$ value ($4$ for $x_1$).

Second Iteration:

1. Identify Key Column: The highest positive $Cj-Zj$ is $4$ for $x_1$.
2. Calculate Ratios:
   • Row 1: $(1/2) / 6 = 12$ (Note: The video calculates this as $6 / (1/2) = 12$)
   • Row 2: $4 / 32 = 8$ (Note: The video calculates this as $32 / 4 = 8$)
3. Identify Key Row: The minimum ratio is $8$ for Row 2.
4. Identify Key Element: The element at the intersection is $4$.
5. Identify Entering and Leaving Variables:
   • Entering Variable: $x_1$.
   • Leaving Variable: $S_2$.

Second Iteration Simplex Table:

• The key row (Row 2) is updated by dividing by the key element ($4$).
• The other row (Row 1) is updated using the formula.
• $Zj$ and $Cj-Zj$ are recalculated.

| Cj | | 12 | 16 | 0 | 0 | | | :---- | :---- | :-- | :-- | :--- | :--- | :---- | | Cbi | BV | x1 | x2 | S1 | S2 | Ratio | | 16 | x2 | 0 | 1 | 1/10 | -1/8 | 2 | | 12 | x1 | 1 | 0 | -1/10| 1/4 | 8 | | | Zj | 12 | 16 | 2/5 | 1 | | | | Cj-Zj | 0 | 0 | -2/5 | -1 | |

6. Reaching Optimality

• All $Cj-Zj$ values are now less than or equal to zero ($0, 0, -2/5, -1$).
• Optimality is reached.

7. Optimal Solution

• Basic Variables: $x_2 = 2$, $x_1 = 8$.
• Optimal Value of Z: $Z = 128$.

The optimal solution is $x_1 = 8$, $x_2 = 2$, and the maximum value of the objective function is $Z = 128$.