Linear Programming

Simplex method — Part 3: The Algebric

Linear Programming Course

Academic Year 2025–2026

[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 1 / 26

What We Learned Last Time
Graphical Solution and Geometric Intuition

In our previous session, we explored:

Graphical Solution Method: Solving 2D linear programs by plotting
constraints and identifying feasible regions
Standard Form: Understanding how to write any LP in canonical form:

maximize cT x
subject to Ax ≤ b
x≥0

Corner Points: Recognizing that optimal solutions occur at vertices of the

feasible region
Simplex Intuition: Understanding that the simplex algorithm moves from
corner point to corner point, improving the objective function at each step

Today, we formalize this intuition and learn the algorithm!

[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 2 / 26

Geometric Intuition of the Simplex
From One Corner to Another

The simplex algorithm exploits a

fundamental property:
Optimal
Start at a corner point
(vertex) of the feasible
region
Iteration 2
At each iteration, move to
an adjacent corner point
Each move improves (or
maintains) the objective
value Iteration 1
Start
Stop when no improvement
is possible

[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 3 / 26

Canonical Form: The Perfect Starting Point

What is Canonical Form?

The canonical form is a specially structured linear program that gives us

an immediate starting point for the simplex algorithm.


Standard
Canonical Form
Form

Original Problem:

max cT x
s.t. Ax ≤ b
x ≥0
[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 4 / 26

Canonical Form: The Requirements

Canonical Form Definition

A linear program is in canonical form if it satisfies:

1. Equality Constraints

All constraints must be equalities (=)

⇒ Use slack variables to convert inequalities: Ax ≤ b → Ax + Is = b

2. Non-Negative Right-Hand Side

All constants bi ≥ 0
⇒ Ensures our initial basic solution is feasible

[Link]
3. Identity Matrix Present
Linear Programming Course Linear Programming Academic Year 2025–2026 5 / 26
Canonical Form: Concrete Example

Step-by-Step Conversion

Let’s transform a linear program into canonical form

Original Problem

Maximize: Z = 3x1 + 2x2

Subject to:

2x1 + x2 ≤ 4
x1 + 2x2 ≤ 3
x1 , x2 ≥ 0

_ Conversion Steps _
[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 6 / 26

Why Canonical Form is Crucial

The Power of Canonical Form

Canonical form provides the essential foundation that makes the simplex
algorithm work efficiently

Benefits Without Canonical Form

Immediate Starting No Clear Starting Point
Point Where to begin optimization?
Slack variables give initial Two-Phase Method
BFS Needed
Systematic Procedure Extra work to find initial BFS
Clear rules for pivot Complex Pivot Rules
operations No standardized procedure
[Link]
Easy Optimality Check Hard to Detect Optimality
Look at Course
Linear Programming objective row Linear Programming No simple stopping
Academic Year condition
2025–2026 7 / 26
Canonical Form: Converting Inequalities to Equalities
Slack Variables

To apply the simplex algorithm, we need to convert the standard form to

canonical form by introducing slack variables.

Given the standard form:

maximize cT x
subject to Ax ≤ b, x≥0

We add slack variables s1 , s2 , . . . , sm (one for each constraint):

maximize c1 x1 + c2 x2 + · · · + cn xn
subject to a11 x1 + a12 x2 + · · · + a1n xn + s1 = b1
a21 x1 + a22 x2 + · · · + a2n xn + s2 = b2
..
.
am1 x1 + am2 x2 + · · · + amn xn + sm = bm
xi ≥ 0, sj ≥ 0
[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 8 / 26

Basic Solutions
Connecting Algebra to Geometry

A basic solution is obtained by setting n variables to zero and solving for the
remaining m variables from the m equations.

Definition: A solution is basic if at most m variables are positive (the rest are
zero). The positive variables are called basic variables; the zero variables are
non-basic variables.

Key Connection to Geometry:

Fundamental Result
Each basic feasible solution corresponds to a corner point of the
feasible region!

Why? Because:
A corner point is where m constraints are active (tight)
m active constraints with n variables give exactly m basic variables
[Link]
The basic solution is the intersection of these constraints
Linear Programming Course Linear Programming Academic Year 2025–2026 9 / 26
Basis: The Set of Basic Variables
From Variables to Indices

Definition: A basis is a set of m variable indices that form a basis for the
solution space.

Example: Suppose we have 3 original variables (x1 , x2 , x3 ) and 2 slack variables

(s1 , s2 ). A basis might be B = {s1 , x2 }.
This means: x1 = 0, x3 = 0 (non-basic)
Solve for: s1 , x2 (basic variables)
If the solution is feasible (all variables ≥ 0), it’s a basic feasible solution

The Simplex Algorithm Strategy:

Algorithm Principle

Move from one basis to another (equivalently, from one corner to an

adjacent corner) by exchanging one basic variable with a non-basic
variable.
[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 10 / 26

The Generic Problem
Standard Notation

We consider the canonical form of the generic LP:

maximize c1 x1 + c2 x2 + · · · + cn xn + 0 · s1 + 0 · s2 + · · · + 0 · sm
subject to a11 x1 + a12 x2 + · · · + a1n xn + s1 = b1
a21 x1 + a22 x2 + · · · + a2n xn + s2 = b2
..
.
am1 x1 + am2 x2 + · · · + amn xn + sm = bm
x, s ≥ 0

Assumptions: bi ≥ 0 for all i (if not, multiply the constraint by −1).

This form is perfect for the simplex tableau!

[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 11 / 26

The Simplex Tableau
Organization and Initial Setup

The simplex tableau is a compact representation of the system:

Basis x1 x2 ··· xn s1 s2 ··· sm RHS

s1 a11 a12 ··· a1n 1 0 ··· 0 b1
s2 a21 a22 ··· a2n 0 1 ··· 0 b2
.. .. .. .. .. .. .. .. .. ..
. . . . . . . . . .
sm am1 am2 ··· amn 0 0 ··· 1 bm
−c1 −c2 ··· −cn 0 0 ··· 0 z =0

Key Features:
Initial Basis: All slack variables; original variables are non-basic (zero)
Last Row: Reduced costs with coefficients −cj ; current objective value z = 0
RHS Column: Current values of basic variables; must all be ≥ 0 [Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 12 / 26

Optimality Test
When Do We Stop?

Step 1: Check Optimality

Optimality Condition

If all reduced costs in the last row are ≤ 0 (all entries are
non-positive), then the current solution is optimal.

Why?
The reduced cost −cj represents the change in objective per unit increase of
variable xj
If all reduced costs are ≤ 0, increasing any non-basic variable decreases the
objective
Therefore, no improvement is possible

Current Solution:
Basic variables = values in RHS column
[Link]

Non-basic variables = 0
Linear Programming Course Linear Programming Academic Year 2025–2026 13 / 26
Entering Variable Selection
Which Non-Basic Variable to Increase?

Step 2: If Not Optimal, Select the Entering Variable

If some reduced cost is positive (say, for variable xj with −cj > 0, i.e., cj < 0 in
the last row but displayed as positive difference):

Selection Rule (Most Positive Reduced Cost):

Entering Variable Rule

Choose the column with the most positive reduced cost.

If multiple columns tie, choose any one arbitrarily.

Rationale: This column has the potential to increase the objective value the most
per unit.

Let’s call this column the pivot column, and the corresponding variable the
entering variable.

Notation: If column j is chosen, we denote it as the entering variable xj (or sj [Link]

it’s a slack variable).
Linear Programming Course Linear Programming Academic Year 2025–2026 14 / 26
Leaving Variable Selection (Minimum Ratio Test)
How Much Can We Increase the Entering Variable?

Step 3: Determine How Much to Increase the Entering Variable

We want to increase the entering variable as much as possible without violating
the constraint x, s ≥ 0.

Minimum Ratio Test (Leaving Variable Rule):

For each row i with positive coefficient aij in the pivot column:

bi
θi =
aij

Leaving Variable Rule

The leaving variable corresponds to the row with the minimum

positive ratio θmin .
This variable will become zero and leave the basis.

This row is called the pivot row, and the element aij at the intersection of pivot
[Link]
row and pivot column is the pivot element.
Linear Programming Course Linear Programming Academic Year 2025–2026 15 / 26
What If No Positive Element Exists?
Unbounded Problem

Case: All aij ≤ 0 in the Pivot Column

Unbounded Solution
If all coefficients in the pivot column are ≤ 0, then the entering
variable can increase indefinitely without violating any constraint.
The LP is unbounded: the objective value can be increased to infinity.

Why?
Increasing the entering variable by ∆ > 0 changes the constraint equations
The constraint values change as: bi − aij · ∆
If aij ≤ 0, the constraint value increases or stays the same
Therefore, all constraints remain satisfied for any ∆ ≥ 0

Conclusion: No finite optimal solution exists. [Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 16 / 26

Pivoting Operation
Updating the Tableau

Step 4: Perform the Pivot

Once the pivot element is identified, we perform row operations to:
1 Divide the pivot row by the pivot element (to make it equal to 1)
2 Eliminate all other entries in the pivot column using row operations

Result:
The entering variable enters the basis
The leaving variable exits the basis
A new tableau is obtained
The objective value improves (or stays the same in case of degeneracy)

Algebraic Operations:
If the pivot element is aij in row k and column j:

Row k
New row k :
aij
New row i : Row i − aij × (New row k) ∀i ̸= k [Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 17 / 26

Complete Simplex Algorithm
Summary

The Simplex Algorithm

Initialization: Start with slack variables as the initial basis.

Iteration:
1 Optimality Test: If all reduced costs ≤ 0, STOP (optimal solution
found).
2 Entering Variable: Choose the column with the most positive
reduced cost. If none exist, STOP.
3 Leaving Variable: Perform the minimum ratio test. If no positive
ratio exists, STOP (unbounded).
4 Pivot: Update the tableau and repeat.
Output: Either an optimal solution, or a declaration that the problem is
unbounded.

[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 18 / 26

Degeneracy
When Multiple Ratios Are Equal

Definition: Degeneracy occurs when:

Multiple rows have the same minimum ratio in the minimum ratio test
The minimum ratio is zero (some RHS entry is zero)
A basic variable takes value zero

What Happens in the Tableau?

In the minimum ratio test, if θmin = 0:
0
θi = =0 (if aij > 0)
aij
The entering variable increases to zero, meaning we don’t move to a different
corner point; we move to a different basis representation of the same corner.

Consequences:
The objective value does not improve (stays the same)
The algorithm may cycle indefinitely if we’re unlucky with variable selection
Perturbation rules or Bland’s rule can prevent cycling
[Link]
Bland’s Rule: Among candidates, choose the one with the smallest index.
Linear Programming Course Linear Programming Academic Year 2025–2026 19 / 26
Detecting Degeneracy in the Tableau
What to Look For

Signs of Degeneracy:
1 Zero RHS: A basic variable has value 0
Basis · · · · · · RHS
s1 ··· 1 ··· 0
2 Tied Minimum Ratios: Multiple rows give the same minimum ratio
b1 10
θ1 = a1j = 2 =5
b2 15
θ2 = a2j = 3 =5 ← Tie!

What to Do:
If degeneracy is detected, expect no improvement in objective at the next
iteration
Use a tie-breaking rule (Bland’s rule) to avoid cycling
The algorithm still converges (with proper tie-breaking)
[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 20 / 26

Numerical Example: Initial Tableau
Setting Up the Problem

Example Problem:

maximize 3x1 + 2x2

subject to x1 + x2 ≤ 4
2x1 + x2 ≤ 7
x1 , x2 ≥ 0

Canonical Form (with slack variables s1 , s2 ):

maximize 3x1 + 2x2 + 0s1 + 0s2

subject to x1 + x2 + s1 = 4
2x1 + x2 + s2 = 7
x1 , x2 , s 1 , s 2 ≥ 0

Initial Basis: {s1 , s2 }; (x1 , x2 ) = (0, 0); z = 0 [Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 21 / 26

Numerical Example: First Tableau
Is the Solution Optimal?

Initial Simplex Tableau:

Basis x1 x2 s1 s2 RHS
s1 1 1 1 0 4
s2 2 1 0 1 7
−3 −2 0 0 z= 0

Optimality Check:
Last row: [−3, −2, 0, 0]
There are negative entries: −3 and −2
NOT OPTIMAL — we can improve!

Next Step: Find the entering variable.

[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 22 / 26

Numerical Example: Select Entering Variable
Most Negative Reduced Cost

Entering Variable Selection:

Look at the last row: [−3, −2, 0, 0]
The most negative entry is −3 (in the x1 column).

Entering Variable: x1 (pivot column is column 1)

Basis x1 x2 s1 s2 RHS
s1 1 1 1 0 4
s2 2 1 0 1 7
−3 −2 0 0 z= 0

[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 23 / 26

Numerical Example: Minimum Ratio Test
Select Leaving Variable

Minimum Ratio Test:

For each row with a positive coefficient in the pivot column (x1 ):

4
Row 1: θ1 = =4
1
7
Row 2: θ2 = = 3.5 ← Minimum
2

Leaving Variable: s2 (pivot row is row 2, because θ2 = 3.5 is smallest)

Pivot Element: a2,1 = 2 (intersection of pivot row and pivot column)

Basis x1 x2 s1 s2 RHS
s1 1 1 1 0 4
s2 2 1 0 1 7
[Link]
−3 −2 0 0 z= 0
Linear Programming Course Linear Programming Academic Year 2025–2026 24 / 26
Numerical Example: Pivot Operation
Row Operations

Pivot Element: a2,1 = 2

Row Operations:
1 Divide pivot row by pivot element:
Row 2  1
= 1, 2 , 0, 12 | 27

New Row 2 =
2
2 Eliminate x1 from Row 1:

New Row 1 = Row 1 − 1 × (New Row 2) = 0, 12 , 1, − 21 | 12

 

3 Eliminate x1 from the objective row:

New Obj Row = Old Obj Row − (−3) × (New Row 2) = 0, − 21 , 0, 32 | z = 21

 
2

[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 25 / 26

Numerical Example: Updated Tableau
After First Pivot

New Simplex Tableau:

[Link]

Linear Programming Course Linear Programming Academic Year 2025–2026 26 / 26