Simplex Method: Tabular Approach
Problem Setup
Maximize: Z = 6x₁ + 5x₂ (using values from your notes)
Subject to:
- x₁ + x₂ ≤ 5
- 3x₁ + 2x₂ ≤ 12
- x₁, x₂ ≥ 0
Step 1: Convert Inequalities to Equalities (Add Slack Variables)
- x₁ + x₂ + S₁ = 5 (S₁ = unused resource 1)
- 3x₁ + 2x₂ + S₂ = 12 (S₂ = unused resource 2)
Augmented Model:
Z = 6x₁ + 5x₂ + 0S₁ + 0S₂
Initial Simplex Tableau
| Cⱼ | 6 | 5 | 0 | 0 | |
|---|
| Basic Variables | x₁ | x₂ | S₁ | S₂ | RHS |
| 0 S₁ | 1 | 1 | 1 | 0 | 5 |
| 0 S₂ | 3 | 2 | 0 | 1 | 12 |
| Zⱼ | 0 | 0 | 0 | 0 | 0 |
| Cⱼ - Zⱼ | 6 | 5 | 0 | 0 | |
Analysis of Initial Tableau:
- Basic Variables: S₁, S₂ (slack variables)
- Non-Basic Variables: x₁, x₂ (decision variables = 0)
- Current Solution: x₁ = 0, x₂ = 0, S₁ = 5, S₂ = 12
- Current Z value: 0
Iteration 1
Optimality Test:
Cⱼ - Zⱼ row has positive values (6, 5) → Not Optimal
Entering Variable:
Most positive Cⱼ - Zⱼ = 6 → x₁ enters
Leaving Variable (Minimum Ratio Test):
- S₁: 5/1 = 5
- S₂: 12/3 = 4 ← Minimum
S₂ leaves the basis
Pivot Element: 3 (intersection of x₁ column and S₂ row)
Pivot Operations:
- New S₂ row: R₂ → R₂/3
- New S₁ row: R₁ → R₁ - 1×(New R₂)
- New Zⱼ row: Calculate Zⱼ for each column
Tableau After Iteration 1
| Cⱼ | 6 | 5 | 0 | 0 | |
|---|
| Basic Variables | x₁ | x₂ | S₁ | S₂ | RHS |
| 0 S₁ | 0 | 1/3 | 1 | -1/3 | 1 |
| 6 x₁ | 1 | 2/3 | 0 | 1/3 | 4 |
| Zⱼ | 6 | 4 | 0 | 2 | 24 |
| Cⱼ - Zⱼ | 0 | 1 | 0 | -2 | |
Current Solution:
- x₁ = 4, x₂ = 0, S₁ = 1, S₂ = 0
- Z = 24
Iteration 2
Optimality Test:
Cⱼ - Zⱼ has positive value (1) → Not Optimal
Entering Variable:
Only positive Cⱼ - Zⱼ = 1 → x₂ enters
Leaving Variable (Minimum Ratio Test):
- S₁: 1/(1/3) = 3
- x₁: 4/(2/3) = 6
S₁ leaves the basis
Pivot Element: 1/3
Pivot Operations:
- New S₁ row: R₁ → R₁/(1/3) = 3R₁
- New x₁ row: R₂ → R₂ - (2/3)×(New R₁)
- New Zⱼ row: Calculate Zⱼ for each column
Final Tableau
| Cⱼ | 6 | 5 | 0 | 0 | |
|---|
| Basic Variables | x₁ | x₂ | S₁ | S₂ | RHS |
| 5 x₂ | 0 | 1 | 3 | -1 | 3 |
| 6 x₁ | 1 | 0 | -2 | 1 | 2 |
| Zⱼ | 6 | 5 | 3 | 1 | 27 |
| Cⱼ - Zⱼ | 0 | 0 | -3 | -1 | |
Optimality Test:
All Cⱼ - Zⱼ ≤ 0 → OPTIMAL SOLUTION FOUND
Final Solution
Optimal Values:
- x₁ = 2
- x₂ = 3
- S₁ = 0 (resource 1 fully used)
- S₂ = 0 (resource 2 fully used)
- Maximum Z = 27
Physical Interpretation
Basic vs Non-Basic Variables:
- Basic Variables (x₁, x₂): In the final solution, these have positive values
- Non-Basic Variables (S₁, S₂): These equal zero, meaning both resources are fully utilized
Shadow Prices:
From the final Cⱼ - Zⱼ row:
- S₁ has -3: Each additional unit of resource 1 would increase Z by 3
- S₂ has -1: Each additional unit of resource 2 would increase Z by 1
Verification:
- Constraint 1: 2 + 3 = 5 ✓
- Constraint 2: 3(2) + 2(3) = 12 ✓
- Objective: 6(2) + 5(3) = 27 ✓
Key Concepts from Your Notes
- Cⱼ - Zⱼ Test: Positive values indicate the variable can improve the objective
- Minimum Ratio Test: Determines which variable leaves to maintain feasibility
- Pivot Operations: Transform the tableau to represent the new basic solution
- Basic/Non-Basic Classification: Tracks which variables are in the current solution
This tabular method systematically moves from one basic feasible solution to a better one until optimality is achieved.