Linear Programming Problem Solution Using
Simplex Method
Problem Statement
Maximize Z = 3X₁ + 2X₂ + 5X₃
Subject to:
X₁ + 2X₂ + X₃ ≤ 430
3X₁ + 2X₃ ≤ 460
X₁ + 4X₂ ≤ 420
X₁, X₂, X₃ ≥ 0
Solution Process
Step 1: Convert to Standard Form
Adding slack variables S₁, S₂, S₃:
Maximize Z = 3X₁ + 2X₂ + 5X₃ + 0S₁ + 0S₂ + 0S₃
X₁ + 2X₂ + X₃ + S₁ = 430
3X₁ + 0X₂ + 2X₃ + S₂ = 460
X₁ + 4X₂ + 0X₃ + S₃ = 420
Step 2: Initial Simplex Tableau
X₁ X₂ X₃ S₁ S₂ S₃ RHS
S₁ 1.0 2.0 1.0 1.0 0.0 0.0 430.0
S₂ 3.0 0.0 2.0 0.0 1.0 0.0 460.0
S₃ 1.0 4.0 0.0 0.0 0.0 1.0 420.0
Z -3.0 -2.0 -5.0 0.0 0.0 0.0 0.0
Step 3: Simplex Iterations
Iteration 1:
Entering variable: X₃ (most negative coefficient: -5)
Leaving variable: S₂ (minimum ratio: 460/2 = 230)
Iteration 2:
Entering variable: X₂ (most negative coefficient: -2)
Leaving variable: S₁ (minimum ratio: 200/2 = 100)
Iteration 3:
All coefficients in Z row are non-negative → Optimal solution found
Step 4: Final Optimal Solution
Decision Variables:
X₁ = 0 units
X₂ = 100 units
X₃ = 230 units
Maximum Objective Value:
Z = 1,350
Slack Variables:
S₁ = 0 (Constraint 1 is binding)
S₂ = 0 (Constraint 2 is binding)
S₃ = 20 (Constraint 3 has 20 units of slack)
Verification
Constraint 1: 0 + 2(100) + 230 = 430 ≤ 430 ✓
Constraint 2: 3(0) + 2(230) = 460 ≤ 460 ✓
Constraint 3: 0 + 4(100) = 400 ≤ 420 ✓
Objective Function: 3(0) + 2(100) + 5(230) = 1,350
Business Interpretation
The optimal production strategy involves producing 0 units of Product 1, 100 units of
Product 2, and 230 units of Product 3
This allocation maximizes profit at 1,350 units
Constraints 1 and 2 are fully utilized (binding constraints)
Constraint 3 has excess capacity of 20 units
Product 3 (X₃) contributes most to profit due to its highest coefficient (5) in the objective
function