t

Simplex Method Example: Step-by-Step Tableau

Dr. Awais Khan

Understanding the Simplex Method

The Simplex Method is an iterative algebraic procedure for solving linear programming problems. It starts
at a feasible corner point (usually the origin) and moves along the edges of the feasible region to adjacent corner
points, improving the objective function value at each step until an optimal solution is reached.

Key Variables and Tableau Terms

Before solving, it is essential to understand the components of the Simplex Tableau:

• Basis: The set of variables that currently have a non-zero value in the solution.
• Cj : The coe!cients of the variables in the original objective function.
• CB : The objective function coe!cients for the variables currently in the Basis.
!
• Zj : The amount of profit/cost ”given up” by adding one unit of a variable; calculated as (CB →
column values).
• Cj ↑ Zj (Net Evaluation Row): The net change in the objective function if one unit of that variable
enters the solution.
• Quantity (Qty / b): The current values of the basic variables.

• Ratio: Calculated as (Quantity/Pivot Column value); used to determine the leaving variable by selecting
the minimum non-negative result.
• Slack Variables (sn ): Variables added to ↓ constraints to turn them into equalities, representing unused
resources.

1
 ·
- 76 00

3. 18

x, 7
S

2 #
↑

I
L
[ii]
& Ri
- R2 = R2 -

ERI
R2 =

=
R2-ERI
1 -

((0) = 2
t(2)
- Ez(1) = 0
=

= o
- (g) =
-

Yy
=
(3 -132')
-
= 113 +6 =
2 =
2
4 -(3) 4 2 z
-
= =
-

=
Example 1: Joshua Emmanuel Tutorial
The Problem
Maximize: Z = 7x1 + 6x2
Subject to:

2x1 + 4x2 → 16
3x1 + 2x2 → 12
x 1 , x2 ↑ 0

Iteration 0: Initial Simplex Tableau

The initial feasible solution is at the origin (0, 0), where x1 , x2 are non-basic variables and s1 , s2 are basic
variables.

Cj 7 6 0 0
Basis CB x1 x2 s1 s2 Quantity Ratio
s1 0 2 4 1 0 16 16/2 = 8
s2 0 3 2 0 1 12 12/3 = 4
Zj 0 0 0 0 0
Cj ↓ Zj 7 6 0 0

Explanation:
• Entering Variable: x1 has the highest positive Cj ↓ Zj (7).
• Leaving Variable: s2 has the minimum ratio (4).
• Pivot Element: 3.

Iteration 1: Improving the Solution

x1 replaces s2 in the basis. Row operations are performed to normalize the pivot row and zero out the pivot
column.

Cj 7 6 0 0
Basis CB x1 x2 s1 s2 Quantity Ratio
s1 0 0 8/3 1 -2/3 8 8 ÷ 8/3 = 3
x1 7 1 2/3 0 1/3 4 4 ÷ 2/3 = 6
Zj 7 14/3 0 7/3 28
Cj ↓ Zj 0 4/3 0 -7/3

Explanation:
• Current Profit is 28. Since 4/3 is positive, the solution is not yet optimal.
• Entering Variable: x2 . Leaving Variable: s1 (Minimum ratio 3).

Iteration 2: Final Optimal Solution

Cj 7 6 0 0
Basis CB x1 x2 s1 s2 Quantity
x2 6 0 1 3/8 -1/4 3
x1 7 1 0 -1/4 1/2 2
Zj 7 6 1/2 2 32
Cj ↓ Zj 0 0 -1/2 -2

Final Result: x1 = 2, x2 = 3, Max Z = 32.

2
Example 2: Reddy Mikks Model (Taha)
The Original Problem
Maximize: z = 5x1 + 4x2
Subject to:

6x1 + 4x2 → 24 (Raw material M1)

x1 + 2x2 → 6 (Raw material M2)
↓x1 + x2 → 1 (Market limit)
x2 → 2 (Demand limit)
x 1 , x2 ↑ 0

Standard Form (Introducing Slack Variables)

To use the Simplex method, we add slack variables s1 , s2 , s3 , s4 to convert the inequalities into equations:

Maximize: z = 5x1 + 4x2 + 0s1 + 0s2 + 0s3 + 0s4

Subject to: 6x1 + 4x2 + s1 = 24
x1 + 2x2 + s2 = 6
↓ x1 + x2 + s 3 = 1
x2 + s 4 = 2
x 1 , x2 , s 1 , s 2 , s 3 , s 4 ↑ 0

Iteration 0: Initial Tableau

Cj 5 4 0 0 0 0
Basis CB x1 x2 s1 s2 s3 s4 Qty Ratio
s1 0 6 4 1 0 0 0 24 24/6 = 4
s2 0 1 2 0 1 0 0 6 6/1 = 6
s3 0 -1 1 0 0 1 0 1 –
s4 0 0 1 0 0 0 1 2 –
Zj 0 0 0 0 0 0 0
Cj ↓ Zj 5 4 0 0 0 0

Decision: x1 enters; s1 leaves. Pivot element is 6.

Iteration 1: Improving Solution

Cj 5 4 0 0 0 0
Basis CB x1 x2 s1 s2 s3 s4 Qty Ratio
x1 5 1 2/3 1/6 0 0 0 4 4 ÷ 2/3 = 6
s2 0 0 4/3 -1/6 1 0 0 2 2 ÷ 4/3 = 1.5
s3 0 0 5/3 1/6 0 1 0 5 5 ÷ 5/3 = 3
s4 0 0 1 0 0 0 1 2 2/1 = 2
Zj 5 10/3 5/6 0 0 0 20
Cj ↓ Zj 0 2/3 -5/6 0 0 0

Decision: x2 enters; s2 leaves. Pivot element is 4/3.

3
Iteration 2: Final Optimal Tableau
Cj 5 4 0 0 0 0
Basis CB x1 x2 s1 s2 s3 s4 Qty
x1 5 1 0 1/4 -1/2 0 0 3
x2 4 0 1 -1/8 3/4 0 0 1.5
s3 0 0 0 3/8 -5/4 1 0 2.5
s4 0 0 0 1/8 -3/4 0 1 0.5
Zj 5 4 3/4 1/2 0 0 21
Cj ↓ Zj 0 0 -3/4 -1/2 0 0

Conclusion: As all Cj ↓ Zj → 0, the optimal solution is reached.

• Optimal Production: x1 = 3, x2 = 1.5.

• Slack Remaining: Raw material M1 and M2 are fully used (s1 = 0, s2 = 0), while the market and
demand limits have cushions of 2.5 and 0.5 respectively.
• Maximum Profit: Z = 21.

4
Problem 2: Direct Minimization
The Problem
Minimize: Z = ↓3x1 + x2
Standard Form:

3x1 + x2 + s1 = 6
↓x1 + 2x2 + s2 = 1
x 1 , x2 , s 1 , s 2 ↑ 0

Iteration 0: Initial Tableau

In direct minimization, we select the entering variable by finding the most negative value in the Cj ↓ Zj row.

Cj -3 1 0 0
Basis CB x1 x2 s1 s2 Qty Ratio
s1 0 3 1 1 0 6 6/3 = 2
s2 0 -1 2 0 1 1 –
Zj 0 0 0 0 0
Cj ↓ Zj -3 1 0 0

Iteration 1: Optimal Tableau

The optimality condition for minimization is reached when all Cj ↓ Zj ↑ 0.

Cj -3 1 0 0
Basis CB x1 x2 s1 s2 Qty
x1 -3 1 1/3 1/3 0 2
s2 0 0 7/3 1/3 1 3
Zj -3 -1 -1 0 -6
Cj ↓ Z j 0 2 1 0

Final Result: Since all Cj ↓ Zj ↑ 0, the solution is optimal.

• Optimal Values: x1 = 2, x2 = 0.

• Minimum Z: -6.