Solve the following linear programming problem using Two Phase Method:
Minimize Z = x1 - 2x2 -3x3
Subject to: -2x1 + x2 +3x3 = 2
2x1 + 3x2 + 4x3 =1
where x1, x2, x3 ≥ 0
To solve this linear programming problem using the Two Phase Method, we need to follow these steps:
1. Convert the given problem into standard form by introducing slack, surplus, and artificial variables.
The given problem in standard form is:
Minimize Z = x1 - 2x2 -3x3
Subject to:
-2x1 + x2 + 3x3 + s1 = 2
2x1 + 3x2 + 4x3 + s2 = 1
where x1, x2, x3, s1, s2 ≥ 0
2. Set up the initial simplex tableau:
Cj 1 -2 -3 0 0 0
------------------------------------------------------
| x1 | x2 | x3 | s1 | s2 | RHS |
------------------------------------------------------
x2 | -2 | 1 | 3 | 1 | 0 | 2
x3 | 2 | 3 | 4 | 0 |1 | 1
Zj -1 2 3 0 0 0
3. Perform the Two Phase Method:
- Phase 1: Minimize the sum of artificial variables in the objective function.
- Select entering variable: Choose the variable with the most negative coefficient in the Zj row. In this case, x1 is the entering variable.
- Select leaving variable: Find the minimum ratio of the RHS column to the entering variable's column. The leaving variable is x2.
- Pivot: Perform the pivot operation to make the entering variable's coefficient 1 by dividing the pivot row by -2.
New Tableau:
Cj 1 -2 -3 0 0 0
------------------------------------------------------
| x1 | x2 | x3 | s1 | s2 | RHS |
------------------------------------------------------
x2 | 1 | -0.5 | 1.5 | -0.5 | 0 | 1
x3 | 0 | 4 | 1 | -1 | 1 | 0
Zj -1 1 0.5 1 0 | 2
- Repeat the steps until all artificial variables are eliminated.
New Tableau:
Cj 0 -2 1 3 0 0
------------------------------------------------------
| x1 | x2 | x3 | s1 | s2 | RHS |
------------------------------------------------------
x2 | 1 | -0.5 | 1.5 | -0.5 | 0 | 1
x3 | 0 | 4 | 1 | -1 | 1 | 0
Zj 0 1.5 -0.5 2.5 0 | 2
- Phase 2: Use the final tableau from Phase 1 and minimize the original objective function.
- Update the coefficients in the objective function row based on the Phase 1 result.
New Tableau:
Cj 1 -2 -3 0 0 0
------------------------------------------------------
| x1 | x2 | x3 | s1 | s2 | RHS |
------------------------------------------------------
x2 | 1 | -0.5 | 1.5 | -0.5 | 0 | 1
x3 | 0 | 4 | 1 | -1 | 1 | 0
Zj 0 1.5 -0.5 2.5 0 | 2
- Repeat the steps of finding the entering variable, leaving variable, and performing the pivot operation until there are no negative coefficients in the Zj row.
Final Tableau:
Cj 1 0 -5 2.5 0 0
----------------------------------------------------------
| x1 | x2 | x3 | s1 | s2 | RHS |
----------------------------------------------------------
x1 | 1 | 0.5 | -1 | 0.5 | 0 | 1
x3 | 0 | 2 | 3 | -2 | 1 | 2
Zj 1 1 -9 2 0 | -3
4. Interpret the final tableau:
The optimal solution is Z = -3, which occurs when x1 = 1, x2 = 0, x3 = 2.
Therefore, the min value of Z = -3 occurs when x1 = 1, x2 = 0, x3 = 2.