The Simplex Method in Linear Programming
Tabular Form with Examples
Eng: Youssef A. Mehanna
April 4, 2025
Eng: Youssef A. Mehanna Simplex Method April 4, 2025 1 / 10
Example 1: Problem Statement
Maximize
z = 7x1 + 6x2
Constraints
2x1 + 4x2 ≤ 16
3x1 + 2x2 ≤ 12
x1 , x2 ≥ 0
Eng: Youssef A. Mehanna Simplex Method April 4, 2025 2 / 10
Simplex Method Steps
1 Convert objective function and constraints to Standard form
Introduce slack variables
Add slack variables to all equations
2 Build Simplex Method Tabular Form
3 Solve using the Simplex Method algorithm
Eng: Youssef A. Mehanna Simplex Method April 4, 2025 3 / 10
Step 1: Standard Form
Introduce Slack Variables
There are two equations, so we have 2 Slack Variables
2x1 + 4x2 ≤ 16 ⇒ Add x3
3x1 + 2x2 ≤ 12 ⇒ Add x4
Add Slack Variables to All Equations
Max : z = 7x1 + 6x2 + 0x3 + 0x4
2x1 + 4x2 + x3 = 16
3x1 + 2x2 + x4 = 12
x1 , x2 , x3 , x4 ≥ 0
Eng: Youssef A. Mehanna Simplex Method April 4, 2025 4 / 10
Step 2: Build Initial Simplex Tableau
Ci : Coefficients from objective function
Xb : Basic variables (initially slack variables)
θ: Ratio variable for pivot selection
CB : Coefficients of basic variables
Ci
7 6 0 0
Xb CB b x1 x2 x3 x4 θ
x3 0 16 2 4 1 0
x4 0 12 3 2 0 1
Ci − Zi 7 6 0 0
Eng: Youssef A. Mehanna Simplex Method April 4, 2025 5 / 10
Step 3: Solving the Simplex Tableau (First Iteration)
1 Pick pivot column with the greatest positive value in Ci − Zi row
(In this case, x1 column with value 7)
2 Calculate the ratio θ for each row: θ = bi /pivot column value
3 Choose pivot row with the smallest positive θ value
Ci
7 6 0 0
Xb CB b x1 x2 x3 x4 θ
x3 0 16 2 4 1 0 16/2 = 8
x4 0 12 3 2 0 1 12/3 = 4
Ci − Zi 7 6 0 0
Pivot element is 3 (intersection of pivot column x1 and pivot row x4 )
Eng: Youssef A. Mehanna Simplex Method April 4, 2025 6 / 10
First Iteration - Resulting Tableau
1 Replace x4 with x1 in the basic variables
2 Update the pivot row: divide all elements by the pivot value (3)
3 Eliminate x1 from other rows: Row1 = Row1 − 2 × Row2
4 Calculate new Ci − Zi values
Ci
7 6 0 0
Xb CB b x1 x2 x3 x4 θ
8
x3 0 8 0 3 1 − 23
2 1
x1 7 4 1 3 0 3
4
Ci − Zi 0 3 0 − 73
Zmax = CBT · b = (0, 7) · (8, 4) = 28
Eng: Youssef A. Mehanna Simplex Method April 4, 2025 7 / 10
Second Iteration
4
1 New pivot column is x2 (largest positive Ci − Zi value: 3)
8 4
2 Calculate θ ratios: 8 = 3 and 2 =6
3 3
3 Pivot row is the first row (smallest θ value)
8
4 Pivot element is 3
Ci
7 6 0 0
Xb CB b x1 x2 x3 x4 θ
8
x3 0 8 0 3 1 − 32 3
2 1
x1 7 4 1 3 0 3 6
4
Ci − Zi 0 3 0 − 37
Eng: Youssef A. Mehanna Simplex Method April 4, 2025 8 / 10
Second Iteration - Resulting Tableau
1 Replace x3 with x2 in the basic variables
8
2 Update pivot row: divide all elements by 3
3 Eliminate x2 from other rows
4 Calculate new Ci − Zi values
Ci
7 6 0 0
Xb CB b x1 x2 x3 x4
3
x2 6 3 0 1 8 − 14
x1 7 2 1 0 − 14 1
2
Ci − Zi 0 0 − 21 −2
Zmax = CBT · b = (6, 7) · (3, 2) = 32
Eng: Youssef A. Mehanna Simplex Method April 4, 2025 9 / 10
Final Solution
Optimal Solution
Since all values in the Ci − Zi row are ≤ 0, we have reached an optimal
solution:
x1 = 2
x2 = 3
x3 = 0
x4 = 0
Maximum value: Zmax = 32
Verification
Z = 7x1 + 6x2 = 7(2) + 6(3) = 14 + 18 = 32
Eng: Youssef A. Mehanna Simplex Method April 4, 2025 10 / 10