Simplex Method

288. Simplex Method

288.0.1. Matrix Notation

288.0.0.1. Linear Algebra Review

288.0.0.2. Gaussian Elimination

288.0.0.3. Inverse

288.0.0.4. Linear Dependence and Independence

288.0.0.5. Extreme Points

288.0.0.6. Slack and Suplus

288.0.0.7. Standard Form

288.0.0.8. Simplex Method

\begin{aligned} 𝑥 + 𝑦 = 5 \\ 2 & 𝑥 - 𝑦 = 4 \end{aligned}

Row View

Solution: Intersection of $𝑛$ lines or (hyper)planes

Column View

Solution: Combination of LHS column vectors to form the RHS vector

𝑥 [\begin{matrix} 1 \\ 2 \end{matrix}] + 𝑦 [\begin{matrix} 1 \\ - 1 \end{matrix}] = [\begin{matrix} 5 \\ 4 \end{matrix}]

A linear system is singular if there is no unique solution

Row view: the $𝑛$ (hyper)planes do not intersect at exactly one point
Column view: the $𝑛$ vectors do not span a complete $𝑛$ -dimensional space

Given a system $𝐴 𝑥 = 𝑏$ , or augmented matrix $[\begin{matrix} 𝐴 & 𝑏 \end{matrix}]$ , use the following 3 rules:

Row Swapping: $𝑅_{𝑖} ⟷ 𝑅_{𝑗}$
Row Scaling: $𝑘 \cdot 𝑅_{𝑖} ⟶ 𝑅_{𝑖}$
Row Replacement: $𝑅_{𝑖} - 𝑘 \cdot 𝑅_{𝑗} ⟶ 𝑅_{𝑖}$

To solve the system:

Transform the augmented matrix into row echelon form (REF) using these operations:
- The first nonzero entry (pivot) in each row is to the right of the pivot in the row above
- All entries below a pivot are zero
- Rows of all zeros (if any) are at the bottom
Back-substitute starting from the last nonzero row to find the solution

Example

Non-singular Case

System of equations

\begin{aligned} 2 & 𝑦 = 4 \\ 1 & 𝑥 & + 1 & 𝑦 = 3 \end{aligned}

Augmented matrix

[\begin{matrix} 0 & 2 & 4 \\ 1 & 1 & 3 \end{matrix}]

Swapping ( $𝑅_{1} ⟷ 𝑅_{2}$ )

[\begin{matrix} 1 & 1 & 3 \\ 0 & 2 & 4 \end{matrix}]

Scaling ( $\frac{1}{2} 𝑅_{2} ⟶ 𝑅_{2}$ )

Row Echelon Form (REF)

[\begin{matrix} 1 & 1 & 3 \\ 0 & 1 & 2 \end{matrix}]

Replacement ( $𝑅_{1} - 𝑅_{2} ⟶ 𝑅_{1}$ )

Reduced Row Echelon Form (RREF)

[\begin{matrix} 1 & 0 & 1 \\ 0 & 1 & 2 \end{matrix}]

Result

𝑥 = 1, 𝑦 = 2

Example

Singular Case

System of equations

\begin{aligned} 𝑥 + & 𝑦 = 2 \\ 2 & 𝑥 + 2 & 𝑦 = 4 \end{aligned}

Augmented matrix

[\begin{matrix} 1 & 1 & 2 \\ 2 & 2 & 4 \end{matrix}]

Replacement ( $𝑅_{2} - 2 𝑅_{1} ⟶ 𝑅_{2}$ )

[\begin{matrix} 1 & 1 & 2 \\ 0 & 0 & 0 \end{matrix}]

Infinitely many solutions E.g.

$𝑥 = 0, 𝑦 = 2$
$𝑥 = 1, 𝑦 = 1$
$𝑥 = 2, 𝑦 = 0$
etc.

Rows are linearly dependent

The coefficient matrix

𝐴 = [\begin{matrix} 1 & 1 \\ 2 & 2 \end{matrix}]

$𝐴$ has determinant 0, so it’s not invertible

𝐴^{- 1} 𝐴 = 𝐼 \land 𝐴 𝐴^{- 1} 𝐴 = 𝐼

$𝐴^{- 1}$ is unique

Finding $𝐴^{- 1}$ : Gauss-Jordan Elimination

A square matrix is nonsingular iff it is invertible

[\begin{matrix} 𝐴 & 𝐼 \end{matrix}] ⟶ [\begin{matrix} 𝐼 & 𝐴^{- 1} \end{matrix}]

Example

𝐴 = [\begin{matrix} 1 & 2 \\ 2 & 1 \end{matrix}]

[\begin{matrix} 𝐴 & 𝐼 \end{matrix}] = [\begin{matrix} 1 & 2 & 1 & 0 \\ 2 & 1 & 0 & 1 \end{matrix}]

Replacement ( $𝑅_{2} - 2 𝑅_{1} ⟶ 𝑅_{2}$ )

[\begin{matrix} 1 & 2 & 1 & 0 \\ 0 & - 3 & - 2 & 1 \end{matrix}]

Scale ( $- \frac{1}{3} 𝑅_{2} ⟶ 𝑅_{2}$ )

[\begin{matrix} 1 & 2 & 1 & 0 \\ 0 & 1 & \frac{2}{3} & - \frac{1}{3} \end{matrix}]

Replacement ( $𝑅_{1} - 2 𝑅_{2} ⟶ 𝑅_{1}$ )

[\begin{matrix} 1 & 0 & - \frac{1}{3} & \frac{2}{3} \\ 0 & 1 & \frac{2}{3} & - \frac{1}{3} \end{matrix}]

Result

𝐴^{- 1} = [\begin{matrix} - \frac{1}{3} & \frac{2}{3} \\ \frac{2}{3} & - \frac{1}{3} \end{matrix}]

A set of $𝑚$ $𝑛$ -dimensional vectors $𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑚}$ are linearly dependent if there exists a non-zero vector $𝑤 \in ℝ^{𝑚}$ such that:

𝑤_{1} 𝑥_{1} + 𝑤_{2} 𝑥_{2} + \dots + 𝑤_{𝑚} 𝑥_{𝑚} = 0

That is, at least one of the vectors can be written as a linear combination of the others.

Example

Dependent

Let:

𝑥_{1} = [\begin{matrix} 1 \\ 2 \end{matrix}], 𝑥_{2} = [\begin{matrix} 2 \\ 4 \end{matrix}]

Augmented:

[\begin{matrix} 1 & 2 & 0 \\ 2 & 4 & 0 \end{matrix}]

Elimination ( $𝑅_{2} - 2 𝑅_{1} ⟶ 𝑅_{2}$ )

[\begin{matrix} 1 & 2 & 0 \\ 0 & 0 & 0 \end{matrix}]

Independent

Let:

𝑥_{1} = [\begin{matrix} 1 \\ 2 \end{matrix}], 𝑥_{2} = [\begin{matrix} 3 \\ 1 \end{matrix}]

Augmented:

[\begin{matrix} 1 & 3 & 0 \\ 2 & 1 & 0 \end{matrix}]

Elimination ( $𝑅_{2} - 2 𝑅_{1} ⟶ 𝑅_{2}$ )

[\begin{matrix} 1 & 2 & 0 \\ 0 & - 5 & 0 \end{matrix}]

Back-substitute

$- 5 𝑤_{2} = 0 \Rightarrow 𝑤_{2} = 0$
$𝑤_{1} + 3 𝑤_{2} = 0 \Rightarrow 𝑤_{1} = 0$

Only solution is $𝑤_{1} = 𝑤_{2} = 0$

In Gaussian elimination, a row of all zeros

Homogeneous System (RHS = 0)

[\begin{matrix} 1 & 2 & 0 \\ 0 & 0 & 0 \end{matrix}]

\begin{matrix} 𝑥_{1} + 2 𝑥_{2} = 0 \\ 0 = 0 \end{matrix}

✅ Represents a redundant equation (i.e., no new information) dependent set of vectors
✅ Does not affect consistency: the system is always consistent
✅ The system has fewer pivots than variables, hence infinitely many solutions

Inconsistent System (Nonzero RHS)

[\begin{matrix} 1 & 2 & 3 \\ 0 & 0 & 5 \end{matrix}]

\begin{matrix} 𝑥_{1} + 2 𝑥_{2} = 3 \\ 0 = 5 \end{matrix}

❌ The second row leads to a contradiction
❌ The system is inconsistent (no solution)

Given that $𝑥$ , $𝑥_{1}$ , and $𝑥_{2}$ are points in the set $𝑆$ :

If you can find two different points $𝑥_{1}$ and $𝑥_{2}$ in $𝑆$ such that $𝑥$ lies somewhere strictly between them on the straight line connecting $𝑥_{1}$ and $𝑥_{2}$ , then $𝑥$ is not an extreme point
If no such pair of points exists—meaning you cannot place $𝑥$ anywhere strictly between two other points in $𝑆$ on a straight line—then $𝑥$ is an extreme point

Formal Definition

For a set $𝑆 \in ℝ^{𝑛}$ , a point $𝑥$ is an extreme point if there does not exist a three-tuple $(𝑥_{1}, 𝑥_{2}, 𝜆)$ such that $𝑥_{1} \in 𝑆$ , $𝑥_{2} \in 𝑆$ , $𝜆 \in (0, 1)$ , and

𝑥 = 𝜆 𝑥_{1} + (1 - 𝜆) 𝑥_{2}

A point $𝑥$ in set $𝑆 \subseteq ℝ^{𝑛}$ is extreme if it cannot be written as a strict convex combination of two different points $𝑥_{1}, 𝑥_{2} \in 𝑆$ .

Convex Combination

Let $𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑘} \in ℝ^{𝑛}$ . A convex combination of these vectors is any point of the form:

𝑥 = 𝜆_{1} 𝑥_{1} + 𝜆_{2} 𝑥_{2} + \dots + 𝜆_{𝑘} 𝑥_{𝑘}

where:

$𝜆_{𝑖} \geq 0 \forall 𝑖$
$\sum_{𝑖 = 1}^{𝑘} 𝜆_{𝑖} = 1$

$𝑥$ lies strictly between $𝑥_{1}$ and $𝑥_{2}$ on the line segment connecting them, not equal to either one

1. Slack

Unused capacity

Example

Given a constraint:

𝑥_{1} + 𝑥_{2} \leq 5

The total must not exceed 5. To convert this into an equation, we add a slack variable $𝑠 \geq 0$ :

𝑥_{1} + 𝑥_{2} + 𝑠 = 5

If $𝑥_{1} + 𝑥_{2} = 3$ , then $𝑠 = 2$
If $𝑥_{1} + 𝑥_{2} = 5$ , then $𝑠 = 0$

2. Excess (surplus)

Excess above the required amount

Example

Given a constraint:

𝑥_{1} + 𝑥_{2} \geq 5

The total must be at least 5. To convert this into an equation, we subtract a excess variable $𝑠 \geq 5$ :

𝑥_{1} + 𝑥_{2} - 𝑒 = 5

If $𝑥_{1} + 𝑥_{2} = 7$ , then $𝑒 = 2$
If $𝑥_{1} + 𝑥_{2} = 5$ , then $𝑒 = 0$

Objective Function
Max	✅	$max 𝑧 = 𝑐^{𝑇} 𝑥$
Min $⟶$ Max	$- 𝑧$	$\begin{matrix} min 𝑧 = 𝑐^{𝑇} 𝒙 \\ ⟺ \\ max 𝑧 = - 𝑐^{𝑇} 𝒙 \end{matrix}$
Constraint Forms
$\leq$	Slack	$\begin{matrix} 𝑎_{1} 𝑥_{1} + 𝑎_{2} 𝑥_{2} \leq 𝑏 \\ 𝑎_{1} 𝑥_{1} + 𝑎_{2} 𝑥_{2} + 𝑠 = 𝑏 \end{matrix}$
$\geq$	Excess + Artificial	$\begin{matrix} 𝑎_{1} 𝑥_{1} + 𝑎_{2} 𝑥_{2} \geq 𝑏 \\ 𝑎_{1} 𝑥_{1} + 𝑎_{2} 𝑥_{2} - 𝑒 + 𝑎 = 𝑏 \end{matrix}$
$=$	Artificial	$\begin{matrix} 𝑎_{1} 𝑥_{1} + 𝑎_{2} 𝑥_{2} = 𝑏 \\ 𝑎_{1} 𝑥_{1} + 𝑎_{2} 𝑥_{2} + 𝑎 = 𝑏 \end{matrix}$
Negative $𝑏$	Multiply by −1	$\begin{matrix} 𝑎_{1} 𝑥_{1} + 𝑎_{2} 𝑥_{2} \leq - 𝑏 \\ - 𝑎_{1} 𝑥_{1} - 𝑎_{2} 𝑥_{2} \geq 𝑏 \end{matrix}$
Variable Bounds
Non-negativity		$𝑥_{𝑖}, 𝑠_{𝑖}, 𝑎_{𝑖} \geq 0 \forall 𝑖$
Lower Bound ≠ 0	Substitution	$\begin{matrix} 𝑥_{1} \geq 5 \\ 𝑦_{1} = 𝑥_{1} - 5 \\ 𝑥_{1} = 𝑦_{1} + 5 \\ 𝑦_{1} \geq 0 \end{matrix}$
Unrestricted Variables	Replace with difference	$\begin{matrix} 𝑥_{𝑗} unrestricted \\ 𝑥_{𝑗} = 𝑥_{𝑗}' - 𝑥_{𝑗} ″ \\ 𝑥_{𝑗}', 𝑥_{𝑗} ″ \geq 0 \end{matrix}$
Variable Roles
Basic Variables	Usually non-zero	Part of the current solution (solved from the constraints)
Non-Basic Variables	Always zero	Temporarily set to 0 so basic variables can be solved
Simplex



Selection: Entering variable Pivot column selection	For maximization problems: Select the column with the most negative value in the objective row This corresponds to the variable that will increase the objective function the most For minimization problems: Select the column with the most positive value in the objective row This corresponds to the variable that will decrease the objective function the most
Selection: Leaving variable Pivot row	Calculate ratios for each row (except the objective row) For each row: $𝑏_{𝑖} / 𝑝_{𝑖}$ Only consider rows where the pivot column element $𝑝_{𝑖} > 0$ Ignore rows where the pivot column element $𝑝_{𝑖} \leq 0$ Select the minimum ratio: The row with the smallest non-negative ratio becomes the pivot row The basic variable in this row is the leaving variable (exits the basis)

Example

\begin{aligned} max & 𝑧 = 3 𝑥_{1} + 2 𝑥_{2} \\ 𝑠 . 𝑡 . & 𝑥_{1} + 𝑥_{2} \leq 4 \\ 𝑥_{1} \leq 2 \\ 𝑥_{2} \leq 3 \\ 𝑥_{1}, 𝑥_{2} \geq 0 \end{aligned}

Step 1: Convert to Standard Form

\begin{aligned} max & 𝑧 = 3 𝑥_{1} + 2 𝑥_{2} \\ 𝑠 . 𝑡 . & 𝑥_{1} + 𝑥_{2} + 𝑠_{1} = 4 \\ 𝑥_{1} + 𝑠_{2} = 2 \\ 𝑥_{2} + 𝑠_{3} = 3 \\ 𝑥_{1}, 𝑥_{2}, 𝑠_{1}, 𝑠_{2}, 𝑠_{3} \geq 0 \end{aligned}

Objective

𝑧 - 3 𝑥_{1} - 2 𝑥_{2} = 0

Step 2: Initial Tableau

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	1	1	1	0	0	4
$𝑠_{2}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	−3	−2	0	0	0	0

Basic Variables: $𝑠_{1} = 4$ , $𝑠_{2} = 2$ , $𝑠_{3} = 3$
Non-basic variables: $𝑥_{1} = 0$ , $𝑥_{2} = 0$
- $𝑉_{0} = (0, 0)$
- Objective: $𝑧 = 3 𝑥_{1} + 2 𝑥_{2} = 3 (0) + 2 (0) = 0$

Step 3: Choose entering variable

Look at the bottom row ( $𝑧$ ):
- Coefficients of $𝑥_{1} = - 3$ , $𝑥_{2} = - 2$
Most negative: $𝑥_{1}$ $⟶$ Enter the basis

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	1	1	1	0	0	4
$𝑠_{2}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	−3	−2	0	0	0	0

Step 4: Determine leaving variable

Look at ratios of $𝑏 / 𝑥_{1}$ :

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$	$𝑏 / 𝑥_{1}$
$𝑠_{1}$	1	1	1	0	0	4	$4 / 1 = 4$
$𝑠_{2}$	1	0	0	1	0	2	$2 / 1 = 2$
$𝑠_{3}$	0	1	0	0	1	3	$3 / 0 = \infty$
$𝑧$	−3	−2	0	0	0	0

Minimum Ratio
- $𝑠_{2}$ leaves, $𝑥_{1}$ enters

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	1	1	1	0	0	4
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	−3	−2	0	3	0	0

Step 5: Pivot on row 2, column $𝑥_{1}$

Now eliminate $𝑥_{1}$ from other rows:

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	1	1	1	0	0	4
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	−3	−2	0	3	0	0

$𝑅_{𝑠_{1}} ≔ 𝑅_{𝑠_{1}} - 𝑅_{𝑥_{1}}$

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	1	1	1	0	0	4
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	−3	−2	0	3	0	0

𝑅_{𝑠_{1}} ≔ 𝑅_{𝑠_{1}} - 𝑅_{𝑥_{1}} ⟹ \begin{cases} 𝑥_{1} & : & 1 - 1 = 0 \\ 𝑥_{2} & : & 1 - 0 = 1 \\ 𝑠_{1} & : & 1 - 0 = 1 \\ 𝑠_{2} & : & 0 - 1 = - 1 \\ 𝑠_{3} & : & 0 - 0 = 0 \\ 𝑏 & : & 4 - 2 = 2 \end{cases}

Update $𝑅_{𝑠_{1}}$

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	0	1	1	−1	0	2
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	−3	−2	0	3	0	0

$𝑅_{𝑧} ≔ 𝑅_{𝑧} - 3 𝑅_{𝑥_{1}}$

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	0	1	1	−1	0	2
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	−3	−2	0	3	0	0

𝑅_{𝑧} ≔ 𝑅_{𝑧} - 3 𝑅_{𝑥_{1}} ⟹ \begin{cases} 𝑥_{1} & : & - 3 + 3 (1) = 0 \\ 𝑥_{2} & : & - 2 + 3 (0) = - 2 \\ 𝑠_{1} & : & 0 + 3 (0) = 0 \\ 𝑠_{2} & : & 0 + 3 (1) = 3 \\ 𝑠_{3} & : & 0 + 3 (0) = 0 \\ 𝑏 & : & 0 + 3 (2) = 6 \end{cases}

Update $𝑅_{𝑧}$

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	0	1	1	−1	0	2
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	0	−2	0	3	0	6

Basic Variables: $𝑥_{1} = 2$ , $𝑠_{1} = 2$ , $𝑠_{3} = 3$
Non-basic variables: $𝑥_{2} = 0$
- $𝑉_{1} = (2, 0)$
- Objective: $𝑧 = 3 𝑥_{1} + 2 𝑥_{2} = 3 (2) + 2 (0) = 6$

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	0	1	1	−1	0	2
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	0	−2	0	3	0	6

Step 3: Choose entering variable

Look at the bottom row ( $𝑧$ ):
- Coefficients of $𝑥_{2} = - 2$
Most negative: $𝑥_{2}$ $⟶$ Enter the basis

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	0	1	1	−1	0	2
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	0	−2	0	3	0	6

Step 4: Determine leaving variable

Look at ratios of $𝑏 / 𝑥_{2}$ :

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$	$𝑏 / 𝑥_{2}$
$𝑠_{1}$	0	1	1	−1	0	2	$2 / 1 = 2$
$𝑥_{1}$	1	0	0	1	0	2	$2 / 0 = \infty$
$𝑠_{3}$	0	1	0	0	1	3	$3 / 1 = 3$
$𝑧$	0	−2	0	3	0	6

$𝑠_{1}$ leaves, $𝑥_{2}$ enters

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑥_{2}$	0	1	1	−1	0	2
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	0	−2	0	3	0	6

Step 5: Pivot on row 1, column $𝑥_{2}$

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑥_{2}$	0	1	1	−1	0	2
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	0	−2	0	3	0	6

Now eliminate $𝑥_{2}$ from other rows:

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑥_{2}$	0	1	1	−1	0	2
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	0	−2	0	3	0	6

$𝑅_{𝑠_{3}} ≔ 𝑅_{𝑠_{3}} - 𝑅_{𝑥_{2}}$

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑥_{2}$	0	1	1	−1	0	2
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	1	0	0	1	3
$𝑧$	0	−2	0	3	0	6

𝑅_{𝑠_{3}} ≔ 𝑅_{𝑠_{3}} - 𝑅_{𝑥_{2}} ⟹ \begin{cases} 𝑥_{1} & : & 0 - 0 = 0 \\ 𝑥_{2} & : & 1 - 1 = 0 \\ 𝑠_{1} & : & 0 - 1 = - 1 \\ 𝑠_{2} & : & 0 - (- 1) = 1 \\ 𝑠_{3} & : & 1 - 0 = 1 \\ 𝑏 & : & 3 - 2 = 1 \end{cases}

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑥_{2}$	0	1	1	−1	0	2
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	0	−1	1	1	1
$𝑧$	0	−2	0	3	0	6

$𝑅_{𝑧} = 𝑅_{𝑧} - (- 2) 𝑅_{𝑥_{2}} = 𝑅_{𝑧} + 2 𝑅_{𝑥_{2}}$

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑥_{2}$	0	1	1	−1	0	2
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	0	−1	1	1	1
$𝑧$	0	−2	0	3	0	6

𝑅_{𝑧} = 𝑅_{𝑧} + 2 𝑅_{𝑥_{2}} ⟹ \begin{cases} 𝑥_{1} & : & 0 + 2 (0) = 0 \\ 𝑥_{2} & : & - 2 + 2 (1) = 0 \\ 𝑠_{1} & : & 0 + 2 (1) = 2 \\ 𝑠_{2} & : & 3 + 2 (- 1) = 1 \\ 𝑠_{3} & : & 0 + 2 (0) = 0 \\ 𝑏 & : & 6 + 2 (2) = 10 \end{cases}

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑥_{2}$	0	1	1	−1	0	2
$𝑥_{1}$	1	0	0	1	0	2
$𝑠_{3}$	0	0	−1	1	1	1
$𝑧$	0	0	2	1	0	10

Basic Variables: $𝑥_{1} = 2$ , $𝑥_{2} = 2$ , $𝑠_{3} = 1$
Non-basic variables: $𝑠_{1} = 0$ , $𝑠_{2} = 0$
- $𝑉_{2} = (2, 2)$
- Objective: $𝑧 = 3 𝑥_{1} + 2 𝑥_{2} = 3 (2) + 2 (2) = 10$

Example

Problem

\begin{aligned} min & 𝑧 = 𝑥_{1} + 2 𝑥_{2} \\ 𝑠 . 𝑡 . & 𝑥_{1} + 𝑥_{2} \leq 1 & (slack) \\ 2 𝑥_{1} - 𝑥_{2} \geq 2 & (surplus + artificial) \\ - 𝑥_{1} + 3 𝑥_{2} \leq - 1 & (negative 𝑏) \\ 𝑥_{1} - 𝑥_{2} = 1 & (artificial) \\ 𝑥_{1} \geq 0 \\ 𝑥_{2} & (unrestricted) \end{aligned}

Standard Form

Step 1: Handle Unrestricted Variable $𝑥_{2}$

Since $𝑥_{2}$ is unrestricted:

\begin{matrix} 𝑥_{2} = 𝑥_{2}^{'} - 𝑥_{2}^{″} \\ 𝑥_{2}^{'}, 𝑥_{2}^{″} \geq 0 \end{matrix}

Rewrite the objective:

\begin{aligned} 𝑧 & = 𝑥_{1} + 2 (𝑥_{2}^{'} - 𝑥_{2}^{″}) \\ = 𝑥_{1} + 2 𝑥_{2}^{'} - 2 𝑥_{2}^{″} \end{aligned}

Step 2: Slack Constraint ( $\leq$ )

𝑥_{1} + 𝑥_{2} \leq 1

Rewrite with $𝑥_{2}^{'} - 𝑥_{2}^{″}$ :

𝑥_{1} + (𝑥_{2}^{'} - 𝑥_{2}^{″}) \leq 1

Add slack variable:

\begin{matrix} 𝑥_{1} + 𝑥_{2}^{'} - 𝑥_{2}^{″} + 𝑠_{1} = 1 \\ 𝑠_{1} \geq 0 \end{matrix}

Step 3: Surplus + Artificial Constraint ( $\geq$ )

2 𝑥_{1} - 𝑥_{2} \geq 2

Rewrite with $𝑥_{2}^{'} - 𝑥_{2}^{″}$ :

2 𝑥_{1} - (𝑥_{2}^{'} - 𝑥_{2}^{″}) \geq 2 ⟹ 2 𝑥_{1} - 𝑥_{2}^{'} + 𝑥_{2}^{″} \geq 2

Convert to equality by subtracting a surplus variable and adding an artificial variable:

\begin{matrix} 2 𝑥_{1} - 𝑥_{2}^{'} + 𝑥_{2}^{″} - 𝑠_{2} + 𝑎_{1} = 2 \\ 𝑠_{2}, 𝑎_{1} \geq 0 \end{matrix}

Step 4: Negative RHS Constraint

- 𝑥_{1} + 3 𝑥_{2} \leq - 1

Rewrite with $𝑥_{2}^{'} - 𝑥_{2}^{″}$ :

- 𝑥_{1} + 3 (𝑥_{2}^{'} - 𝑥_{2}^{″}) \leq - 1 ⟹ - 𝑥_{1} + 3 𝑥_{2}^{'} - 3 𝑥_{2}^{″} \leq - 1

Multiply both sides by $- 1$ to get a positive RHS and flip inequality:

𝑥_{1} - 3 𝑥_{2}^{'} + 3 𝑥_{2}^{″} \geq 1

Convert to equality by subtracting a surplus variable and adding an artificial variable:

\begin{matrix} 𝑥_{1} - 3 𝑥_{2}^{'} + 3 𝑥_{2}^{″} - 𝑠_{3} + 𝑎_{2} = 1 \\ 𝑠_{3}, 𝑎_{2} \geq 0 \end{matrix}

Step 5: Artificial Equality Constraint ( $=$ )

𝑥_{1} - 𝑥_{2} = 1

Rewrite with $𝑥_{2}^{'} - 𝑥_{2}^{″}$ :

𝑥_{1} - (𝑥_{2}^{'} - 𝑥_{2}^{″}) = 1 ⟹ 𝑥_{1} - 𝑥_{2}^{'} + 𝑥_{2}^{″} = 1

Add an artificial variable:

\begin{matrix} 𝑥_{1} - 𝑥_{2}^{'} + 𝑥_{2}^{″} + 𝑎_{3} = 1 \\ 𝑎_{3} \geq 0 \end{matrix}

Final Standard Form

\begin{aligned} min & 𝑧 = 𝑥_{1} + 2 𝑥_{2}^{'} - 2 𝑥_{2}^{″} \\ 𝑠 . 𝑡 . & 𝑥_{1} + 𝑥_{2}^{'} - 𝑥_{2}^{″} + 𝑠_{1} = 1 \\ 2 𝑥_{1} - 𝑥_{2}^{'} + 𝑥_{2}^{″} - 𝑠_{2} + 𝑎_{1} = 2 \\ 𝑥_{1} - 3 𝑥_{2}^{'} + 3 𝑥_{2}^{″} - 𝑠_{3} + 𝑎_{2} = 1 \\ 𝑥_{1} - 𝑥_{2}^{'} + 𝑥_{2}^{″} + 𝑎_{3} = 1 \\ 𝑥_{1}, 𝑥_{2}^{'}, 𝑥_{2}^{″}, 𝑠_{1}, 𝑠_{2}, 𝑠_{3}, 𝑎_{1}, 𝑎_{2}, 𝑎_{3} \geq 0 \end{aligned}

Phase I

Objective

\begin{aligned} min & 𝑤 = 𝑎_{1} + 𝑎_{2} + 𝑎_{3} \\ 𝑠 . 𝑡 . & 𝑥_{1} + 𝑥_{2}^{'} - 𝑥_{2}^{″} + 𝑠_{1} = 1 & (slack) \\ 2 𝑥_{1} - 𝑥_{2}^{'} + 𝑥_{2}^{″} - 𝑠_{2} + 𝑎_{1} = 2 & (surplus + artificial) \\ 𝑥_{1} - 3 𝑥_{2}^{'} + 3 𝑥_{2}^{″} - 𝑠_{3} + 𝑎_{2} = 1 & (negative 𝑏) \\ 𝑥_{1} - 𝑥_{2}^{'} + 𝑥_{2}^{″} + 𝑎_{3} = 1 & (artificial) \\ 𝑥_{1}, 𝑥_{2}^{'}, 𝑥_{2}^{″}, 𝑠_{1}, 𝑠_{2}, 𝑠_{3}, 𝑎_{1}, 𝑎_{2}, 𝑎_{3} \geq 0 & (unrestricted) \end{aligned}

Deriving Phase I Objective Row $𝑅_{𝑤}$

Objective function before substitution

𝑤 = 𝑎_{1} + 𝑎_{2} + 𝑎_{3}

Express each artificial variable in terms of other variables from their constraints

$𝑅_{𝑎_{1}}$

\begin{matrix} 2 𝑥_{1} - 𝑥_{2}^{'} + 𝑥_{2}^{″} - 𝑠_{2} + 𝑎_{1} = 2 \\ 𝑎_{1} = - 2 𝑥_{1} + 𝑥_{2}^{'} - 𝑥_{2}^{″} + 𝑠_{2} + 2 \end{matrix}

$𝑅_{𝑎_{2}}$

\begin{matrix} 𝑥_{1} - 3 𝑥_{2}^{'} + 3 𝑥_{2}^{″} - 𝑠_{3} + 𝑎_{2} = 1 \\ 𝑎_{2} = - 𝑥_{1} + 3 𝑥_{2}^{'} - 3 𝑥_{2}^{″} + 𝑠_{3} + 1 \end{matrix}

$𝑅_{𝑎_{3}}$

\begin{matrix} 𝑥_{1} - 𝑥_{2}^{'} + 𝑥_{2}^{″} + 𝑎_{3} = 1 \\ 𝑎_{3} = - 𝑥_{1} + 𝑥_{2}^{'} - 𝑥_{2}^{″} + 1 \end{matrix}

Substitute into $𝑤$ :

\begin{aligned} 𝑤 & = 𝑎_{1} + 𝑎_{2} + 𝑎_{3} \\ = (- 2 𝑥_{1} + 𝑥_{2}^{'} - 𝑥_{2}^{″} + 𝑠_{2} + 2) + (- 𝑥_{1} + 3 𝑥_{2}^{'} - 3 𝑥_{2}^{″} + 𝑠_{3} + 1) + (- 𝑥_{1} + 𝑥_{2}^{'} - 𝑥_{2}^{″} + 1) \\ = (- 2 𝑥_{1} - 𝑥_{1} - 𝑥_{1}) + (𝑥_{2}^{'} + 3 𝑥_{2}^{'} + 𝑥_{2}^{'}) + (- 𝑥_{2}^{″} - 3 𝑥_{2}^{″} - 𝑥_{2}^{″}) + (𝑠_{2} + 𝑠_{3}) + (2 + 1 + 1) \\ = - 4 𝑥_{1} + 5 𝑥_{2}^{'} - 5 𝑥_{2}^{″} + 𝑠_{2} + 𝑠_{3} + 4 \end{aligned}

Rewrite as a constraint (bring all variables to the left):

\begin{matrix} 𝑤 + 4 𝑥_{1} - 5 𝑥_{2}^{'} + 5 𝑥_{2}^{″} - 𝑠_{2} - 𝑠_{3} = 4 \\ 𝑤 = - 4 𝑥_{1} + 5 𝑥_{2}^{'} - 5 𝑥_{2}^{″} + 𝑠_{2} + 𝑠_{3} + 4 \end{matrix}

So in tableau row $𝑅_{𝑤}$ :

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	1	1	−1	1	0	0	0	0	0	1
$𝑎_{1}$	2	−1	1	0	−1	0	1	0	0	2
$𝑎_{2}$	1	−3	3	0	0	−1	0	1	0	1
$𝑎_{3}$	1	−1	1	0	0	0	0	0	1	1
$𝑤$	4	−5	5	0	−1	−1	0	0	0	4

Perform First Pivot

1. Pivot Column

Look at the $𝑤$ row (objective row) for the most negative coefficient:

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	1	1	−1	1	0	0	0	0	0	1
$𝑎_{1}$	2	−1	1	0	−1	0	1	0	0	2
$𝑎_{2}$	1	−3	3	0	0	−1	0	1	0	1
$𝑎_{3}$	1	−1	1	0	0	0	0	0	1	1
$𝑤$	4	−5	5	0	−1	−1	0	0	0	4

The most negative is $- 5$ $⟶$ pivot column is $𝑥_{2}^{'}$

2. Ratio

Compute ratios ( $𝑏 / 𝑥_{2}^{'}$ ) for rows with positive pivot entries:

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$	$𝑏 / 𝑥_{2}^{'}$
$𝑠_{1}$	1	1	−1	1	0	0	0	0	0	1	1
$𝑎_{1}$	2	−1	1	0	−1	0	1	0	0	2	❌
$𝑎_{2}$	1	−3	3	0	0	−1	0	1	0	1	❌
$𝑎_{3}$	1	−1	1	0	0	0	0	0	1	1	❌
$𝑤$	4	−5	5	0	−1	−1	0	0	0	4

Minimum ratio is $1$ , so we pivot on row $𝑠_{1}$ :

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$	$𝑏 / 𝑥_{2}^{'}$
$𝑠_{1}$	1	1	−1	1	0	0	0	0	0	1	1
$𝑎_{1}$	2	−1	1	0	−1	0	1	0	0	2	❌
$𝑎_{2}$	1	−3	3	0	0	−1	0	1	0	1	❌
$𝑎_{3}$	1	−1	1	0	0	0	0	0	1	1	❌
$𝑤$	4	−5	5	0	−1	−1	0	0	0	4

3. Pivot $𝑠_{1} ⟶ 𝑥_{2}^{'}$

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑥_{2}^{'}$	1	1	−1	1	0	0	0	0	0	1
$𝑎_{1}$	2	−1	1	0	−1	0	1	0	0	2
$𝑎_{2}$	1	−3	3	0	0	−1	0	1	0	1
$𝑎_{3}$	1	−1	1	0	0	0	0	0	1	1
$𝑤$	4	−5	5	0	−1	−1	0	0	0	4

4. Gauss-Jordan Elimination

Example

Step 3: Pivot $𝑎_{1} ⟶ 𝑥_{1}$

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	1	1	−1	1	0	0	0	0	0	5
$𝑥_{1}$	3	−1	1	0	−1	0	1	0	0	4
$𝑎_{2}$	1	−2	2	0	0	−1	0	1	0	6
$𝑎_{3}$	1	−1	1	0	0	0	0	0	1	2
$𝑤$	−5	4	−4	0	1	1	0	0	0	12

Gauss-Jordan Elimination

𝑅_{𝑥_{1}} = \frac{1}{3} 𝑅_{𝑥_{1}}

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	1	1	−1	1	0	0	0	0	0	5
$𝑥_{1}$	1	−1/3	1/3	0	−1/3	0	1/3	0	0	4/3
$𝑎_{2}$	1	−2	2	0	0	−1	0	1	0	6
$𝑎_{3}$	1	−1	1	0	0	0	0	0	1	2
$𝑤$	−5	4	−4	0	1	1	0	0	0	12

𝑅_{𝑎_{2}} = 𝑅_{𝑎_{2}} - 1 𝑅_{𝑥_{1}}

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	1	1	−1	1	0	0	0	0	0	5
$𝑥_{1}$	1	−1/3	1/3	0	−1/3	0	1/3	0	0	4/3
$𝑎_{2}$	0	−5/3	5/3	0	1/3	−1	−1/3	1	0	14/3
$𝑎_{3}$	1	−1	1	0	0	0	0	0	1	2
$𝑤$	−5	4	−4	0	1	1	0	0	0	12

𝑅_{𝑎_{3}} = 𝑅_{𝑎_{3}} - 1 𝑅_{𝑥_{1}}

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	1	1	−1	1	0	0	0	0	0	5
$𝑥_{1}$	1	−1/3	1/3	0	−1/3	0	1/3	0	0	4/3
$𝑎_{2}$	0	−5/3	5/3	0	1/3	−1	−1/3	1	0	14/3
$𝑎_{3}$	0	−2/3	2/3	0	1/3	0	−1/3	0	1	2/3
$𝑤$	−5	4	−4	0	1	1	0	0	0	12

𝑅_{𝑤} = 𝑅_{𝑤} + 5 𝑅_{𝑥_{1}}

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	1	1	−1	1	0	0	0	0	0	5
$𝑥_{1}$	1	−1/3	1/3	0	−1/3	0	1/3	0	0	4/3
$𝑎_{2}$	0	−5/3	5/3	0	1/3	−1	−1/3	1	0	14/3
$𝑎_{3}$	0	−2/3	2/3	0	1/3	0	0-1/3	0	1	2/3
$𝑤$	0	7/3	−7/3	0	−2/3	1	5/3	0	0	56/3

𝑅_{𝑠_{1}} = 𝑅_{𝑠_{1}} - 1 𝑅_{𝑥_{1}}

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	0	4/3	−4/3	1	1/3	0	−1/3	0	0	11/3
$𝑥_{1}$	1	−1/3	1/3	0	−1/3	0	1/3	0	0	4/3
$𝑎_{2}$	0	−5/3	5/3	0	1/3	−1	−1/3	1	0	14/3
$𝑎_{3}$	0	−2/3	2/3	0	1/3	0	−1/3	0	1	2/3
$𝑤$	0	7/3	−7/3	0	−2/3	1	5/3	0	0	56/3

Step 3: Perform the Second Pivot

Look at the $𝑤$ row (objective row) for the most negative coefficient:

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	0	4/3	−4/3	1	1/3	0	−1/3	0	0	11/3
$𝑥_{1}$	1	−1/3	1/3	0	−1/3	0	1/3	0	0	4/3
$𝑎_{2}$	0	−5/3	5/3	0	1/3	−1	−1/3	1	0	14/3
$𝑎_{3}$	0	−2/3	2/3	0	1/3	0	0-1/3	0	1	2/3
$𝑤$	0	7/3	−7/3	0	−2/3	1	5/3	0	0	56/3

The most negative is $- \frac{7}{3}$ for $𝑥_{2}^{″}$
- Pivot column is $𝑥_{2}^{″}$

Ratio

Compute ratios ( $𝑏 / 𝑥_{2}^{″}$ ) for rows with positive pivot entries:

Basis

𝑥_{1}

𝑥_{2}^{'}

𝑥_{2}^{″}

𝑠_{1}

𝑠_{2}

𝑠_{3}

𝑎_{1}

𝑎_{2}

𝑎_{3}

𝑏

𝑏 / 𝑥_{2}^{″}

𝑠_{1}

4/3

−4/3

1/3

−1/3

11/3

❌

𝑥_{1}

−1/3

1/3

−1/3

1/3

4/3

\frac{4}{3} \div \frac{1}{3} = 4

𝑎_{2}

−5/3

5/3

1/3

−1

−1/3

14/3

\frac{14}{3} \div \frac{5}{3} = 2.8

𝑎_{3}

−2/3

2/3

1/3

0-1/3

2/3

\frac{2}{3} \div \frac{2}{3} = 1

𝑤

7/3

−7/3

−2/3

5/3

56/3

Minimum ratio is $1$ , so we pivot on row $𝑎_{3}$ :

Basis

𝑥_{1}

𝑥_{2}^{'}

𝑥_{2}^{″}

𝑠_{1}

𝑠_{2}

𝑠_{3}

𝑎_{1}

𝑎_{2}

𝑎_{3}

𝑏

𝑏 / 𝑥_{2}^{″}

𝑠_{1}

4/3

−4/3

1/3

−1/3

11/3

❌

𝑥_{1}

−1/3

1/3

−1/3

1/3

4/3

\frac{4}{3} \div \frac{1}{3} = 4

𝑎_{2}

−5/3

5/3

1/3

−1

−1/3

14/3

\frac{14}{3} \div \frac{5}{3} = 2.8

𝑎_{3}

−2/3

2/3

1/3

0-1/3

2/3

\frac{2}{3} \div \frac{2}{3} = 1

𝑤

7/3

−7/3

−2/3

5/3

56/3

Step 4: Pivot $𝑎_{3} ⟶ 𝑥_{2}^{″}$

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	0	4/3	−4/3	1	1/3	0	−1/3	0	0	11/3
$𝑥_{1}$	1	−1/3	1/3	0	−1/3	0	1/3	0	0	4/3
$𝑎_{2}$	0	−5/3	5/3	0	1/3	−1	−1/3	1	0	14/3
$𝑥_{2}^{″}$	0	−2/3	2/3	0	1/3	0	−1/3	0	1	2/3
$𝑤$	0	7/3	−7/3	0	−2/3	1	5/3	0	0	56/3

Gauss-Jordan Elimination

𝑅_{𝑥_{2}^{″}} = 𝑅_{𝑥_{2}^{″}} / (2 / 3)

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	0	4/3	−4/3	1	1/3	0	−1/3	0	0	11/3
$𝑥_{1}$	1	−1/3	1/3	0	−1/3	0	1/3	0	0	4/3
$𝑎_{2}$	0	−5/3	5/3	0	1/3	−1	−1/3	1	0	14/3
$𝑥_{2}^{″}$	0	−1	1	0	1/2	0	−1/2	0	3/2	1
$𝑤$	0	7/3	−7/3	0	−2/3	1	5/3	0	0	56/3

𝑅_{𝑠_{1}} = 𝑅_{𝑠_{1}} - (- \frac{4}{3}) 𝑅_{𝑥_{2}^{″}} = 𝑅_{𝑠_{1}} + \frac{4}{3} 𝑅_{𝑥_{2}^{″}}

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	0	0	0	1	1	0	−1	0	2	5
$𝑥_{1}$	1	−1/3	1/3	0	−1/3	0	1/3	0	0	4/3
$𝑎_{2}$	0	−5/3	5/3	0	1/3	−1	−1/3	1	0	14/3
$𝑥_{2}^{″}$	0	−1	1	0	1/2	0	−1/2	0	3/2	1
$𝑤$	0	7/3	−7/3	0	−2/3	1	5/3	0	0	56/3

𝑅_{𝑥_{1}} = 𝑅_{𝑥_{1}} - \frac{1}{3} 𝑅_{𝑥_{2}^{″}}

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	0	0	0	0	−1/2	0	1/2	0	−1/2	1
$𝑥_{1}$	1	0	0	0	−1/2	0	1/2	0	−1/2	1
$𝑎_{2}$	0	−5/3	5/3	0	1/3	−1	−1/3	1	0	14/3
$𝑥_{2}^{″}$	0	−1	1	0	1/2	0	−1/2	0	3/2	1
$𝑤$	0	7/3	−7/3	0	−2/3	1	5/3	0	0	56/3

𝑅_{𝑎_{2}} = 𝑅_{𝑎_{2}} - \frac{5}{3} 𝑅_{𝑥_{2}^{″}}

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	0	0	0	0	−1/2	0	1/2	0	−1/2	1
$𝑥_{1}$	1	0	0	0	−1/2	0	1/2	0	−1/2	1
$𝑎_{2}$	0	0	0	0	−1/2	−1	1/2	1	−5/2	3
$𝑥_{2}^{″}$	0	−1	1	0	1/2	0	−1/2	0	3/2	1
$𝑤$	0	7/3	−7/3	0	−2/3	1	5/3	0	0	56/3

𝑅_{𝑤} = 𝑅_{𝑤} - (- \frac{7}{3}) 𝑅_{𝑥_{2}^{″}} = 𝑅_{𝑤} + \frac{7}{3} 𝑅_{𝑥_{2}^{″}}

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	0	0	0	0	−1/2	0	1/2	0	−1/2	1
$𝑥_{1}$	1	0	0	0	−1/2	0	1/2	0	−1/2	1
$𝑎_{2}$	0	0	0	0	−1/2	−1	1/2	1	−5/2	3
$𝑥_{2}^{″}$	0	−1	1	0	1/2	0	−1/2	0	3/2	1
$𝑤$	0	0	0	0	1/2	1	1/2	0	7/2	21

Step 5: Perform the Third Pivot

Look at the $𝑤$ row (objective row) for the most negative coefficient:

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$
$𝑠_{1}$	0	0	0	0	−1/2	0	1/2	0	−1/2	1
$𝑥_{1}$	1	0	0	0	−1/2	0	1/2	0	−1/2	1
$𝑎_{2}$	0	0	0	0	−1/2	−1	1/2	1	−5/2	3
$𝑥_{2}^{″}$	0	−1	1	0	1/2	0	−1/2	0	3/2	1
$𝑤$	0	0	0	0	−1/6	1	1/2	0	7/2	21

The most negative is $- \frac{1}{6}$ for $𝑠_{2}$
- Pivot column is $𝑠_{2}$

Ratio

Compute ratios ( $𝑏 / 𝑠_{2}$ ) for rows with positive pivot entries:

Basis	$𝑥_{1}$	$𝑥_{2}^{'}$	$𝑥_{2}^{″}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑎_{1}$	$𝑎_{2}$	$𝑎_{3}$	$𝑏$	$𝑏 / 𝑠_{2}$
$𝑠_{1}$	0	0	0	0	−1/2	0	1/2	0	−1/2	1	❌
$𝑥_{1}$	1	0	0	0	−1/2	0	1/2	0	−1/2	1	❌
$𝑎_{2}$	0	0	0	0	−1/2	−1	1/2	1	−5/2	3	❌
$𝑥_{2}^{″}$	0	−1	1	0	1/2	0	−1/2	0	3/2	1	2
$𝑤$	0	0	0	0	−1/6	1	1/2	0	7/2	21

Two-Phase

\begin{aligned} max & 𝑧 = 2 & 𝑥_{1} & + & 𝑥_{2} \\ 𝑠 . 𝑡 . & 𝑥_{1} & + & 𝑥_{2} & \geq & 2 \\ 𝑥_{1} & \geq & 1 \\ 𝑥_{1} & + & 𝑥_{2} & \leq & 5 \end{aligned}

\begin{aligned} max & 𝑧 = 2 & 𝑥_{1} & + & 𝑥_{2} & + & 0 & 𝑒_{1} & + & 0 & 𝑒_{2} & + & 0 & 𝑠_{1} \\ 𝑠 . 𝑡 . & 𝑥_{1} & + & 𝑥_{2} & - & 𝑒_{1} & \geq & 2 \\ 𝑥_{1} & - & 𝑒_{2} & \geq & 1 \\ 𝑥_{1} & + & 𝑥_{2} & + & 𝑠_{1} & \leq & 5 \end{aligned}

𝑧 - 2 𝑥_{1} - 𝑥_{2} = 0

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑒_{1}$	$𝑒_{2}$	$𝑠_{1}$	$𝑏$
???	1	1	$- 1$	0	0	2
???	1	0	0	$- 1$	0	1
$𝑠_{1}$	1	1	0	0	1	5
$𝑧$	−2	−1	0	0	0	0

\begin{aligned} min & 𝑤 = 0 & 𝑥_{1} & + & 0 & 𝑥_{2} & + & 0 & 𝑒_{1} & + & 0 & 𝑒_{2} & + & 0 & 𝑠_{1} \\ 𝑠 . 𝑡 . & 𝑥_{1} & + & 𝑥_{2} & - & 𝑒_{1} & \geq & 2 \\ 𝑥_{1} & - & 𝑒_{2} & \geq & 1 \\ 𝑥_{1} & + & 𝑥_{2} & + & 𝑠_{1} & \leq & 5 \end{aligned}

Degeneracy

Degeneracy occurs when a basic variable takes the value zero in a basic feasible solution. This leads to ties in the minimum ratio test, which determines the leaving variable during a pivot.

Example

Problem

\begin{aligned} max & 𝑧 = 𝑥_{1} + 2 𝑥_{2} \\ 𝑠 . 𝑡 . & 𝑥_{1} + 𝑥_{2} \leq 3 \\ 𝑥_{2} \leq 2 \\ \frac{1}{2} 𝑥_{1} + 𝑥_{2} \leq 2.5 \\ 𝑥_{1}, 𝑥_{2} \geq 0 \end{aligned}

Standard Form

\begin{matrix} 𝑧 - 𝑥_{1} - 2 𝑥_{2} = 0 \\ 𝑥_{1} + 𝑥_{2} + 𝑠_{1} = 3 \\ 𝑥_{2_{𝑠_{2}}} = 2 \\ \frac{1}{2} 𝑥_{1} + 𝑥_{2} + 𝑠_{3} \\ 𝑥_{1}, 𝑥_{2}, 𝑠_{1}, 𝑠_{2}, 𝑠_{3} \frac{>}{=} 0 \end{matrix}

Initialize Tableau

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	1	1	1	0	0	3
$𝑠_{2}$	0	1	0	1	0	2
$𝑠_{3}$	1/2	1	0	0	1	2.5
$𝑤$	−1	−1	0	0	0	0

\begin{matrix} 𝑥_{1} = 0 \\ 𝑥_{2} = 0 \end{matrix}

Minimum Test

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	1	1	1	0	0	3
$𝑠_{2}$	0	1	0	1	0	2
$𝑠_{3}$	1/2	1	0	0	1	2.5
$𝑤$	−1	−1	0	0	0	0

Ratio Test

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	1	1	1	0	0	3
$𝑠_{2}$	0	1	0	1	0	2
$𝑠_{3}$	1/2	1	0	0	1	2.5
$𝑤$	−1	−1	0	0	0	0

Pivot

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	1	1	1	0	0	3
$𝑥_{2}$	0	1	0	1	0	2
$𝑠_{3}$	1/2	1	0	0	1	2.5
$𝑤$	−1	−1	0	0	0	0

Gaussian Elimination

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	1	0	1	−1	0	1
$𝑥_{2}$	0	1	0	1	0	2
$𝑠_{3}$	1/2	0	0	−1	1	0.5
$𝑤$	−1	0	0	2	0	4

\begin{matrix} 𝑥_{1} = 0 \\ 𝑥_{2} = 2 \end{matrix}

Minimum Test

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	1	0	1	−1	0	1
$𝑥_{2}$	0	1	0	1	0	2
$𝑠_{3}$	1/2	0	0	−1	1	0.5
$𝑤$	−1	0	0	2	0	4

Ratio Test

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑠_{1}$	1	0	1	−1	0	1
$𝑥_{2}$	0	1	0	1	0	2
$𝑠_{3}$	1/2	0	0	−1	1	0.5
$𝑤$	−1	0	0	2	0	4

\begin{cases} \frac{1}{1} & = 1 \\ \frac{0.5}{0.5} & = 1 \end{cases}} Tie

Pivot

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑥_{1}$	1	0	1	−1	0	1
$𝑥_{2}$	0	1	0	1	0	2
$𝑠_{3}$	1/2	0	0	−1	1	0.5
$𝑤$	−1	0	0	2	0	4

Gaussian Elimination

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑠_{3}$	$𝑏$
$𝑥_{1}$	1	0	1	−1	0	1
$𝑠_{2}$	0	1	0	0	0	2
$𝑠_{3}$	0	0	−1/2	−1/2	1	0
$𝑤$	0	0	1	1	0	5

If after elimination a basic variable has a value of 0, it indicates degeneracy.

Degeneracy comes from redundant constraints

Bland’s Rule: Choose the variable with the lowest index in the basis

$𝑥_{1}$ over $𝑥_{2}$
$𝑥_{2}$ over $𝑠_{1}$

Unbounded Solution

When identifying the entering variable, look at its column in the tableau. If all entries in that column (above the objective row) are $\leq 0$ , the problem is unbounded

Can’t perform ratio test $⟶$ no constraint limits the entering variable $⟶$ objective function increases without bound

Example

Problem

\begin{aligned} max & 𝑥_{1} + 𝑥_{2} \\ 𝑠 . 𝑡 . & 𝑥_{1} - 𝑥_{2} \leq 1 \\ 𝑥_{1}, 𝑥_{2} \geq 0 \end{aligned}

Standard Form

\begin{aligned} max & 𝑧 - 𝑥_{1} - 𝑥_{2} = 0 \\ 𝑠 . 𝑡 . & 𝑥_{1} - 2 𝑥_{2} + 𝑠_{1} = 1 \\ 𝑥_{1}, 𝑥_{2}, 𝑠_{1} \geq 0 \end{aligned}

Initialize Tableau

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑏$
$𝑠_{1}$	1	−1	1	1
$𝑧$	−1	−1	0	0

Minimum and Ratio Test

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑏$
$𝑠_{1}$	1	−1	1	1
$𝑧$	−1	−1	0	0

Pivot

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑏$
$𝑥_{1}$	1	−1	1	1
$𝑧$	−1	−1	0	0

Gaussian Elimination

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑏$
$𝑥_{1}$	1	−1	1	1
$𝑧$	0	−2	1	1

Minimum and Ratio Test

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑏$
$𝑥_{1}$	1	−1	1	1
$𝑧$	0	−2	1	1

Check for Optimality

Objective row has −2 for $𝑥_{2}$ → not optimal

Entering variable: $𝑥_{2}$ (most negative coefficient)

Unboundedness Detection

Looking at the $𝑥_{2}$ column:

Entry in constraint row: −1 (which is ≤ 0)

All entries in $𝑥_{2}$ column are ≤ 0

Conclusion: Cannot perform ratio test $⟶$ Problem is unbounded

Alternative Solutions

Example

Problem

\begin{aligned} max & 2 𝑥_{1} + 4 𝑥_{2} \\ 𝑠 . 𝑡 . & 𝑥_{1} + 𝑥_{2} \geq 3 \\ \frac{1}{2} 𝑥_{1} + 𝑥_{2} \geq 2.5 \\ 𝑥_{1}, 𝑥_{2} \geq 0 \end{aligned}

Standard Form

\begin{matrix} 𝑧 - 2 𝑥_{1} - 𝑥_{2} = 0 \\ 𝑥_{1} + 𝑥_{2} + 𝑠_{1} = 3 \\ \frac{1}{2} 𝑥_{1} + 𝑥_{2} + 𝑠_{2} = 2.5 \\ 𝑥_{1}, 𝑥_{2}, 𝑥_{3} \geq 0 \end{matrix}

Initialize Tableau

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑏$
$𝑠_{1}$	1	1	1	0	3
$𝑠_{2}$	1/2	1	0	1	2.5
$𝑧$	−2	−4	0	0	0

Minimum Test

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑏$
$𝑠_{1}$	1	1	1	0	3
$𝑠_{2}$	1/2	1	0	1	2.5
$𝑧$	−2	−4	0	0	0

Ratio Test

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑏$
$𝑠_{1}$	1	1	1	0	3
$𝑠_{2}$	1/2	1	0	1	2.5
$𝑧$	−2	−4	0	0	0

Pivot

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑏$
$𝑠_{1}$	1	1	1	0	3
$𝑥_{2}$	1/2	1	0	1	2.5
$𝑧$	−2	−4	0	0	0

Gaussian Elimination

Basis	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	$𝑏$
$𝑠_{1}$	1/2	0	1	−1	0.5
$𝑥_{2}$	1/2	1	0	1	2.5
$𝑧$	0	0	0	4	10

In a maximization or minimization linear programming problem, if there is a 0 in the $𝑧$ row (objective function row) of the final (optimal) simplex tableau in a non-basic column (i.e. a variable not currently in the solution), then there are multiple optimal solutions.

Equalities: Convert inequalities (using slack, surplus, or artificial variables)
Non-negative variables: If a variable is unrestricted or can be negative, replace it with the difference of two non-negative variables

Example

\begin{matrix} 2 𝑥_{1} + 3 𝑥_{2} \leq - 4 \\ ⟺ \\ - 2 𝑥_{1} - 3 𝑥_{2} \geq 4 \end{matrix}

Nonpositive

\begin{matrix} 2 𝑥_{1} + 3 𝑥_{2} \leq 4, 𝑥_{1} \leq 0 \\ ⟺ \\ - 2 𝑥_{1} + 3 𝑥_{2} \leq 4, 𝑥_{1} \geq 0 \end{matrix}

Free (Unrestricted)

\begin{matrix} 2 𝑥_{1} + 3 𝑥_{2} \leq 6, 𝑥_{1} urs \\ ⟺ \\ 2 𝑥_{1}^{'} - 2 𝑥_{1}^{″} + 3 𝑥_{2} \leq 4, 𝑥_{1}^{'}, 𝑥_{1}^{″} \geq 0 \end{matrix}

Example

\begin{aligned} max & 7 𝑥_{1} + 6 𝑥_{2} \\ 𝑠 . 𝑡 . & 2 𝑥_{1} + 4 𝑥_{2} \leq 16 \\ 3 𝑥_{1} + 2 𝑥_{2} \leq 12 \\ 𝑥_{1}, 𝑥_{2} \geq 0 \end{aligned}

\begin{aligned} max & 7 𝑥_{1} + 6 𝑥_{2} + 0 & 𝑠_{1} & + 0 & 𝑠_{2} \\ 𝑠 . 𝑡 . & 2 𝑥_{1} + 4 𝑥_{2} + & 𝑠_{1} & = 16 \\ 3 𝑥_{1} + 2 𝑥_{2} & + & 𝑠_{2} & = 12 \end{aligned}

𝑥_{1} = 0, 𝑥_{2} = 0, 𝑠_{1} = 16, 𝑠_{2} = 12

		$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$
Basis	$𝑐_{𝐵}$	7	6	0	0	$𝑏$	Ratio
$𝑠_{1}$	0	2	4	1	0	16	16/2 = 8
$𝑠_{2}$	0	3	2	0	1	12	12/3 = 4
	$𝑧_{𝑗}$	0	0	0	0	0
	$𝑐_{𝑗} - 𝑧_{𝑗}$	7	6	0	0

Formulation

Objective Function

\begin{aligned} 𝑍 & = 𝑐_{1} 𝑥_{1} + 𝑐_{2} 𝑥_{2} + \dots + 𝑐_{𝑛} 𝑥_{𝑛} \\ = 𝑐^{𝑇} 𝑥 \end{aligned}

Constraints

\begin{matrix} 𝑎_{11} 𝑥_{1} + 𝑎_{12} 𝑥_{2} + \dots + 𝑎_{1 𝑛} 𝑥_{𝑛} \leq 𝑏_{1} \\ 𝑎_{21} 𝑥_{1} + 𝑎_{22} 𝑥_{2} + \dots + 𝑎_{2 𝑛} 𝑥_{𝑛} \geq 𝑏_{2} \\ ⋮ \\ 𝑎_{𝑚 1} 𝑥_{1} + 𝑎_{𝑚 2} 𝑥_{2} + \dots + 𝑎_{𝑚 𝑛} 𝑥_{𝑛} = 𝑏_{𝑚} \\ 𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛} \geq 0 \end{matrix}

Or,

\begin{matrix} 𝐴 𝑥 \leq, =, \geq 𝑏 \\ 𝑥 \geq 0 \end{matrix}

$\leq$ for maximization
$\geq$ for minimization

Convert to Canonical Form

In slack variable form

\begin{matrix} 𝑎_{11} + 𝑥_{1} + 𝑎_{12} 𝑥_{2} + \dots + 𝑎_{1 𝑛} 𝑥_{𝑛} + 𝑠_{1} = 𝑏_{1} \\ 𝑎_{21} + 𝑥_{1} + 𝑎_{22} 𝑥_{2} + \dots + 𝑎_{2 𝑛} 𝑥_{𝑛} + 𝑠_{2} = 𝑏_{2} \\ ⋮ \\ 𝑎_{𝑚 1} 𝑥_{1} + 𝑎_{𝑚 2} 𝑥_{2} + \dots + 𝑎_{𝑚 𝑛} 𝑥_{𝑛} + 𝑠_{𝑚} = 𝑏_{𝑚} \end{matrix}

𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛} \geq 0

𝑠_{1}, 𝑠_{2}, \dots, 𝑠_{𝑚} \geq 0

Or matrix notation,

\begin{aligned} max & 𝑧 = 𝑐^{𝑇} 𝑥 \\ 𝑠 . 𝑡 . & 𝐴 𝑥 + 𝐼 𝑠 = 𝑏_{𝑖} \\ 𝑥 \geq 0 \\ 𝑠 \geq 0 \end{aligned}

$max 𝑧$	$=$	$𝑐^{𝑇}$	$𝑥$
	$=$	$[𝑐_{1}, 𝑐_{2}, \dots, 𝑐_{𝑛}]$	$[\begin{matrix} 𝑥_{1} \\ 𝑥_{2} \\ ⋮ \\ 𝑥_{𝑛} \end{matrix}]$

$𝐴$	$𝑥$	$+$	$𝐼$	$𝑠$	$=$	$𝑏$
$[\begin{matrix} 𝑎_{11} & 𝑎_{12} & \dots & 𝑎_{1 𝑛} \\ 𝑎_{21} & 𝑎_{22} & \dots & 𝑎_{2 𝑛} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 𝑎_{𝑚 1} & 𝑎_{𝑚 2} & \dots & 𝑎_{𝑚 𝑛} \end{matrix}]$	$[\begin{matrix} 𝑥_{1} \\ 𝑥_{2} \\ ⋮ \\ 𝑥_{𝑛} \end{matrix}]$	$+$	$[\begin{matrix} 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & 1 \end{matrix}]$	$[\begin{matrix} 𝑠_{1} \\ 𝑠_{2} \\ ⋮ \\ 𝑠_{𝑚} \end{matrix}]$	$=$	$[\begin{matrix} 𝑏_{1} \\ 𝑏_{2} \\ ⋮ \\ 𝑏_{𝑚} \end{matrix}]$

Set up Simplex Tableau

	$𝑥_{1}$	$𝑥_{2}$	$\dots$	$𝑥_{𝑛}$	$𝑠_{1}$	$𝑠_{2}$	$\dots$	$𝑠_{𝑚}$	RHS
Constraint 1	$𝑎_{11}$	$𝑎_{12}$	$\dots$	$𝑎_{1} 𝑛$	1	0	$\dots$	0	$𝑏_{1}$
Constraint 2	$𝑎_{21}$	$𝑎_{22}$	$\dots$	$𝑎_{2} 𝑛$	0	1	$\dots$	0	$𝑏_{2}$
$⋮$	$⋮$	$⋮$	$⋱$	$⋮$	$⋮$	$⋮$	$⋱$	$⋮$	$⋮$
Constraint $𝑛$	$𝑎_{𝑚 1}$	$𝑎_{𝑚 2}$	$\dots$	$𝑎_{𝑚 𝑛}$	0	0	$\dots$	1	$𝑏_{𝑚}$
Objective Function	$- 𝑐_{1}$	$- 𝑐_{2}$	$\dots$	$- 𝑐_{𝑛}$	0	0	$\dots$	0	0

$-$ for maximization
$+$ for minimization

Perform Pivot Operation

Identify the Pivot Column: Choose the column with the most:
- Maximization: Negative coefficient
- Minimization: Positive coefficient (or multiply the objective by −1 and treat it as a maximization)

in the objective function row (this indicates which variable will enter the basis).

Identify the Pivot Row: Calculate the ratio of RHS to the pivot column’s coefficients (only where coefficients are positive). The row with the smallest ratio determines the variable to leave the basis.
Pivot: Perform row operations to change the pivot element to 1 and other elements in the pivot column to 0. This involves dividing the pivot row by the pivot element and then adjusting the other rows to zero out the pivot column.

Iterate

Repeat the pivot operations until there are no more negative coefficients in the objective function row, indicating that the current solution is optimal.

Read the Solution

The final tableau will give the values of the variables at the optimal solution. The basic variables are the variables corresponding to the columns with the identity matrix in the final tableau, while non-basic variables are set to zero.

Example

$Maximize : 𝑍 = 3 𝑥_{1} + 2 𝑥_{2}$

s.t.

$𝑥_{1} + 𝑥_{2} \leq 4$

$2 𝑥_{1} + 𝑥_{2} \leq 5$

$𝑥_{1}, 𝑥_{2} \geq 0$

1. Convert to Canonical Form

Introduce slack variables $𝑠_{1}$ and $𝑠_{2}$ to convert inequalities into equalities:

$𝑥_{1} + 𝑥_{2} + 𝑠_{1} = 4$

$2 𝑥_{1} + 𝑥_{2} + 𝑠_{2} = 5$

$𝑥_{1}, 𝑥_{2}, 𝑠_{1}, 𝑠_{2} \geq 0$

Initialize Simplex Tableau

	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	RHS
Constraint 1	1	1	1	0	4
Constraint 2	2	1	0	1	5
Objective Function	−3	−2	0	0	0

2. Identify the Pivot Column

In the objective function row, the coefficients are $[- 3, - 2, 0, 0]$ . The most negative coefficient is $- 3$ , which is in the $𝑥_{1}$ column. Therefore, $𝑥_{1}$ will enter the basis.

3. Identify the Pivot Row

Calculate the ratio of RHS to the pivot column’s coefficients (where the coefficients are positive):

For Row 1: $\frac{4}{1} = 4$ (pivot column coefficient is 1)
For Row 2: $\frac{5}{2} = 2.5$ (pivot column coefficient is 2)

The smallest ratio is 2.5, so Row 2 will be the pivot row. This means that $𝑠_{2}$ will leave the basis.

4. Pivot

Perform row operations to make the pivot element 1 and zero out other elements in the pivot column.

Pivot Element: The element at the intersection of Row 2 and $𝑥_{1}$ column is 2.

Steps:

Make Pivot Element 1: Divide all elements in Row 2 by the pivot element (2):

\begin{aligned} New Row 2 & = \frac{1}{2} \times Old Row 2 \\ = [1, 0.5, 0, 0.5, 2.5] \end{aligned}

Zero Out Pivot Column in Other Rows:

For Row 1: Subtract 1 times New Row 2 from Row 1:

\begin{aligned} New Row 1 & = Old Row 1 - [1, 0.5, 0, 0.5, 2.5] \\ = [0, 0.5, 1, - 0.5, 1.5] \end{aligned}

For Objective Function: Add 3 times New Row 2 to the Objective Function row

\begin{aligned} New Objective Function & = Old Objective Function + 3 \times [1, 0.5, 0, 0.5, 2.5] \\ = [0, - 0.5, 0, 1.5, 7.5] \end{aligned}

Updated Simplex Tableau

	$𝑥_{1}$	$𝑥_{2}$	$𝑠_{1}$	$𝑠_{2}$	RHS
Constraint 1	0	0.5	1	−0.5	1.5
Constraint 2	1	0.5	0	0.5	2.5
Objective Function	0	−0.5	0	1.5	7.5

$\begin{matrix} 0 \times 2 \\ + \\ 0 \times 3 \\ = 0 \end{matrix}$

$𝑐_{𝑗} - 𝑧_{𝑗}$

\begin{aligned} max & 𝑐^{𝑇} 𝑥 \\ 𝑠 . 𝑡 . & 𝐴 𝑥 = 𝑏 \\ 𝑥 \geq 0 \end{aligned}

\begin{aligned} 𝐴 & \in ℝ^{𝑚 \times 𝑛} \\ 𝑏 & \in ℝ^{𝑚 \times 1} \\ 𝑐 & \in ℝ^{𝑛 \times 1} \\ 𝑥 & \in ℝ^{𝑛 \times 1} \end{aligned}

\begin{aligned} max & 𝑐_{𝐵}^{𝑇} 𝑥_{𝐵} + 𝑐_{𝑁}^{𝑇} 𝑥_{𝑁} \\ 𝑠 . 𝑡 . & 𝐵 𝑥_{𝐵} + 𝑁 𝑥_{𝑁} = 𝑏 \\ 𝑥_{𝐵}, 𝑥_{𝑁} \geq 0 \end{aligned}

\begin{matrix} 𝑐^{𝑇} = [𝑐_{𝐵}^{𝑇}, 𝑐_{𝑁}^{𝑇}] \\ 𝐴 = [𝐵, 𝑁] \end{matrix}

Where:

$𝑥_{𝐵}$ : Basic variables (in the basis)
$𝑥_{𝑁}$ : Non-basic variables (not in the basis)
$𝑐_{𝐵}$ : Coefficients of basic variables in the objective function
$𝑐_{𝑁}$ : Coefficients of non-basic variables in the objective function
$𝐵$ : Columns of $𝐴$ corresponding to basic variables
$𝑁$ : Columns of $𝐴$ corresponding to non-basic variables
$𝑏$ : Right-hand side constants

Example

Standard form:

\begin{aligned} max & 𝑥_{1} \\ 𝑠 . 𝑡 . & 2 𝑥_{1} - 𝑥_{2} + 𝑥_{3} = 4 \\ 2 𝑥_{1} + 𝑥_{2} + 𝑥_{4} = 8 \\ 𝑥_{2} + 𝑥_{3} = 3 \\ 𝑥_{1}, 𝑥_{2}, 𝑥_{3}, 𝑥_{4} \geq 0 \forall 𝑖 = 1, \dots, 5 \end{aligned}

\begin{matrix} 𝑐^{𝑇} = [1, 0, 0, 0, 0] \\ 𝐴 = [\begin{matrix} 2 & - 1 & 1 & 0 & 0 \\ 2 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \end{matrix}] \\ 𝑏 = [\begin{matrix} 4 \\ 8 \\ 3 \end{matrix}] \end{matrix}

Given $𝑥_{𝐵} = (𝑥_{1}, 𝑥_{4}, 𝑥_{5})$ and $𝑥_{𝑁} = (𝑥_{2}, 𝑥_{3})$ :

\begin{matrix} 𝑐_{𝐵}^{𝑇} = [1, 0, 0], 𝑐_{𝑁}^{𝑇} = [0, 0] \\ 𝐵 = [\begin{matrix} 2 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}], 𝑁 = [\begin{matrix} - 1 & 1 \\ 1 & 0 \\ 1 & 0 \end{matrix}] \\ 𝑏 = [\begin{matrix} 4 \\ 8 \\ 3 \end{matrix}] \end{matrix}

Objective Function

\begin{matrix} 1 𝑥_{1} + 0 𝑥_{2} + 0 𝑥_{3} + 0 𝑥_{4} + 0 𝑥_{5} = 0 \\ 𝑥_{𝐵}^{𝑇} 𝑥_{𝑏} + 𝑥_{𝑁}^{𝑇} 𝑥_{𝑁} = 0 \end{matrix}

Constraints

\begin{matrix} 2 𝑥_{1} - 1 𝑥_{2} + 1 𝑥_{3} + 0 𝑥_{4} + 0 𝑥_{5} = 4 \\ 2 𝑥_{1} + 1 𝑥_{2} + 0 𝑥_{3} + 1 𝑥_{4} + 0 𝑥_{5} = 8 \\ 0 𝑥_{1} + 1 𝑥_{2} + 0 𝑥_{3} + 0 𝑥_{4} + 1 𝑥_{5} = 3 \\ 𝐴_{𝐵} 𝑥_{𝐵} + 𝐴_{𝑁} 𝑥_{𝑁} = 𝑏 \end{matrix}

Problem

\begin{aligned} max & 𝑐_{𝐵}^{𝑇} 𝑥_{𝐵} + 𝑐_{𝑁}^{𝑇} 𝑥_{𝑁} \\ 𝑠 . 𝑡 . & 𝐵 𝑥_{𝐵} + 𝑁 𝑥_{𝑁} = 𝑏 \\ 𝑥_{𝐵}, 𝑥_{𝑁} \geq 0 \end{aligned}

Rearange the the terms in the constrains:

\begin{aligned} max & 𝑐_{𝐵}^{𝑇} 𝑥_{𝐵} + 𝑐_{𝑁}^{𝑇} 𝑥_{𝑁} \\ 𝑠 . 𝑡 . & 𝑥_{𝐵} = 𝐵^{- 1} (𝑏 - 𝑁 𝑥_{𝑁}) \\ 𝑥_{𝐵}, 𝑥_{𝑁} \geq 0 \end{aligned}

Replace $𝑥_{𝐵}$ in the objective function:

\begin{aligned} max & 𝑐_{𝐵}^{𝑇} [𝐵^{- 1} (𝑏 - 𝑁 𝑥_{𝑁})] + 𝑐_{𝑁}^{𝑇} 𝑥_{𝑁} \\ 𝑠 . 𝑡 . & 𝑥_{𝐵} = 𝐵^{- 1} (𝑏 - 𝑁 𝑥_{𝑁}) \\ 𝑥_{𝐵}, 𝑥_{𝑁} \geq 0 \end{aligned}

Rearrange the terms in the objectcive function:

\begin{aligned} max & 𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑏 - (𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑁 - 𝑐_{𝑁}^{𝑇}) 𝑥_{𝑁} \\ 𝑠 . 𝑡 . & 𝑥_{𝐵} = 𝐵^{- 1} (𝑏 - 𝑁 𝑥_{𝑁}) \\ 𝑥_{𝐵}, 𝑥_{𝑁} \geq 0 \end{aligned}

The standard form LP becomes:

\begin{aligned} max & 𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑏 - (𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑁 - 𝑐_{𝑁}^{𝑇}) 𝑥_{𝑁} \\ 𝑠 . 𝑡 . & 𝑥_{𝐵} = 𝐵^{- 1} (𝑏 - 𝑁 𝑥_{𝑁}) \\ 𝑥_{𝐵}, 𝑥_{𝑁} \geq 0 \end{aligned}

Rearrange the terms of the constrains:

\begin{aligned} max & 𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑏 - (𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑁 - 𝑐_{𝑁}^{𝑇}) 𝑥_{𝑁} \\ 𝑠 . 𝑡 . & 𝐼 𝑥_{𝐵} + 𝐵^{- 1} 𝑁 𝑥_{𝑁} = 𝐵^{- 1} 𝑏 \\ 𝑥_{𝐵}, 𝑥_{𝑁} \geq 0 \end{aligned}

Ignore the sign constraints and let $𝑧$ be the objectctive value:

\begin{aligned} 𝑧 & + & (𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑁 - 𝑐_{𝑁}^{𝑇}) 𝑥_{𝑁} & = 𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑏 \\ 𝐼 𝑥_{𝐵} & + & 𝐵^{- 1} 𝑁 𝑥_{𝑁} & = 𝐵^{- 1} 𝑏 \end{aligned}

The Simplex Tableau is:

$0$	$𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑁 - 𝑐_{𝑁}^{𝑇}$	$𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑏$	$0$
$𝐼$	$𝐵^{- 1} 𝑁 𝑥_{𝑁}$	$𝐵^{- 1} 𝑏$	$1, \dots, 𝑚$
basic	non-basic	RHS

Example

Step 1. Standard form

\begin{aligned} max & 𝑥_{1} \\ 𝑠 . 𝑡 . 2 & 𝑥_{1} - & 𝑥_{2} & + & 𝑥_{3} & = 4 \\ 2 & 𝑥_{1} + & 𝑥_{2} & + & 𝑥_{4} & = 8 \\ 𝑥_{2} & + & 𝑥_{5} & = 3 \end{aligned}

Matrix notation:

𝑐^{𝑇} = [1, 0, 0, 0, 0], 𝐴 = [\begin{matrix} 2 & - 1 & 1 & 0 & 0 \\ 2 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \end{matrix}], 𝑏 = [\begin{matrix} 4 \\ 8 \\ 3 \end{matrix}]

Step 2. Initial Basis

𝐵 = (𝑥_{1}, 𝑥_{4}, 𝑥_{5}) 𝑁 = (𝑥_{2}, 𝑥_{3})

𝐵 = [\begin{matrix} 2 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] 𝑁 = [\begin{matrix} - 1 & 1 \\ 1 & 0 \\ 1 & 0 \end{matrix}]

Cost split:

𝑐_{𝐵}^{𝑇} = [1, 0, 0] 𝑐_{𝑁}^{𝑇} = [0, 0]

Compute inverse of $𝐵$ :

𝐵^{- 1} = [\begin{matrix} \frac{1}{2} & 0 & 0 \\ - 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] 𝑥_{𝐵} = 𝐵^{- 1} 𝑏 = [\begin{matrix} \frac{1}{2} & 0 & 0 \\ - 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] [\begin{matrix} 4 \\ 8 \\ 3 \end{matrix}] = [\begin{matrix} 2 \\ 4 \\ 3 \end{matrix}]

So the basic feasible solution (BFS) is:

\begin{matrix} 𝑥 = (𝑥_{1}, 𝑥_{2}, 𝑥_{3}, 𝑥_{4}, 𝑥_{5}) = (2, 0, 0, 4, 3) \\ 𝑧 = 𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑏 = [1, 0, 0] [\begin{matrix} 2 \\ 4 \\ 3 \end{matrix}] = 2 \end{matrix}

Step 3. Reduced costs and entering variable

\begin{aligned} {\bar{𝑐}}_{𝑁}^{𝑇} & = 𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑁 - 𝑐_{𝑁}^{𝑇} \\ = [\begin{matrix} 1 & 0 & 0 \end{matrix}] [\begin{matrix} \frac{1}{2} & 0 & 0 \\ - 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] [\begin{matrix} - 1 & 1 \\ 1 & 0 \\ 1 & 0 \end{matrix}] - [\begin{matrix} 0 & 0 \end{matrix}] \\ = [\begin{matrix} - \frac{1}{2} & \frac{1}{2} \end{matrix}] \end{aligned}

Since ${\bar{𝑐}}_{2} = - \frac{1}{2} < 0$ , the entering variable is $𝑥_{2}$

Step 4. Direction, ratio test and leaving variable

For $𝑥_{𝐵} = (𝑥_{1}, 𝑥_{4}, 𝑥_{5})$ , we have:

𝑑 = 𝐵^{- 1} 𝑁_{2} = [\begin{matrix} \frac{1}{2} & 0 & 0 \\ - 1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] [\begin{matrix} - 1 \\ 1 \\ 1 \end{matrix}] = [\begin{matrix} - \frac{1}{2} \\ 2 \\ 1 \end{matrix}]

Current basic solution:

𝑥_{𝐵} = 𝐴_{𝐵}^{- 1} 𝑏 = [\begin{matrix} 2 \\ 4 \\ 3 \end{matrix}]

The minimum ratios test:

\frac{𝑥_{4}}{2} = \frac{4}{2} = 2 \frac{𝑥_{5}}{1} = \frac{3}{1} = 3

Smallest ratio is $2 \Rightarrow 𝑥_{4}$ leaves the basis

Step 5. Pivot to the new basis

𝐵 = (𝑥_{1}, 𝑥_{2}, 𝑥_{5}) 𝑁 = (𝑥_{3}, 𝑥_{4})

𝐵 = [\begin{matrix} 2 & - 1 & 1 \\ 2 & 1 & 0 \\ 0 & 1 & 0 \end{matrix}] 𝑁 = [\begin{matrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix}]

Cost split:

𝑐_{𝐵}^{𝑇} = [1, 0, 0] 𝑐_{𝑁}^{𝑇} = [0, 0]

Compute inverse of $𝐵$ :

𝐵^{- 1} = [\begin{matrix} \frac{1}{2} & \frac{1}{4} & 0 \\ - \frac{1}{2} & 1 & 0 \\ \frac{1}{2} & - \frac{1}{2} & 1 \end{matrix}] 𝑥_{𝐵} = 𝐵^{- 1} 𝑏 = [\begin{matrix} \frac{1}{2} & \frac{1}{4} & 0 \\ - \frac{1}{2} & 1 & 0 \\ \frac{1}{2} & - \frac{1}{2} & 1 \end{matrix}] [\begin{matrix} 4 \\ 8 \\ 3 \end{matrix}] = [\begin{matrix} 3 \\ 2 \\ 1 \end{matrix}] = [\begin{matrix} 𝑥_{1} \\ 𝑥_{2} \\ 𝑥_{5} \end{matrix}]

So the new basic feasible solution (BFS) is:

\begin{matrix} 𝑥 = (𝑥_{1}, 𝑥_{2}, 𝑥_{3}, 𝑥_{4}, 𝑥_{5}) = (3, 2, 0, 0, 1) \\ 𝑧 = 𝑐_{𝐵}^{𝑇} 𝑥_{𝐵} = [1, 0, 0] [\begin{matrix} 3 \\ 2 \\ 1 \end{matrix}] = 3 \end{matrix}

Step 6. Check optimality (reduced costs)

\begin{aligned} {\bar{𝑐}}_{𝑁}^{𝑇} & = 𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑁 - 𝑐_{𝑁}^{𝑇} \\ = [\begin{matrix} 1 & 0 & 0 \end{matrix}] [\begin{matrix} \frac{1}{4} & \frac{1}{4} & 0 \\ - \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & - \frac{1}{2} & 1 \end{matrix}] [\begin{matrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix}] - [\begin{matrix} 0 & 0 \end{matrix}] \\ = [\begin{matrix} \frac{1}{4} & \frac{1}{4} \end{matrix}] \end{aligned}

No negative reduced costs $\Rightarrow$ optimal

𝑥^{*} = (3, 2, 0, 0, 1), 𝑧^{*} = 3

Example

Problem:

\begin{aligned} max 2 & 𝑥_{1} + & 3 & 𝑥_{2} \\ 𝑠 . 𝑡 . & 𝑥_{1} + & 𝑥_{2} & \leq 4 \\ 𝑥_{1} + & 2 & 𝑥_{2} & \leq 6 \end{aligned}

Standard form:

\begin{aligned} max 2 & 𝑥_{1} + & 3 & 𝑥_{2} \\ 𝑠 . 𝑡 . & 𝑥_{1} + & 𝑥_{2} + & 𝑠_{1} & = 4 \\ 𝑥_{1} + & 2 & 𝑥_{2} & + & 𝑠_{2} & = 6 \end{aligned}

Let $𝑥_{𝐵} = (𝑠_{1}, 𝑠_{2})$ and $𝑥_{𝑁} = (𝑥_{1}, 𝑥_{2})$

\begin{matrix} 𝑐_{𝐵} = [0, 0] 𝑐_{𝑁} = [2, 3] \\ 𝐴_{𝐵} = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] 𝐴_{𝑁} = [\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix}] \\ 𝑏 = [\begin{matrix} 4 \\ 6 \end{matrix}] \end{matrix}

\begin{matrix} 𝐴_{𝐵}^{- 1} = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] \\ 𝐴_{𝐵}^{- 1} 𝐴_{𝑁} = [\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix}] \\ 𝐴_{𝐵}^{- 1} 𝑏 = [\begin{matrix} 4 \\ 6 \end{matrix}] \\ 𝑐_{𝐵}^{𝑇} 𝐴_{𝐵}^{- 1} 𝐴_{𝑁} - 𝑐_{𝑁}^{𝑇} = [\begin{matrix} - 2 & - 3 \end{matrix}] \\ 𝑐_{𝐵}^{𝑇} 𝐴_{𝐵}^{- 1} 𝑏 = 0 \end{matrix}

$- 2$	$- 3$	$0$	$0$	$0$
$1$	$1$	$1$	$0$	$4$
$1$	$2$	$0$	$1$	$6$
basic		non-basic		RHS

Let $𝑥_{𝐵} = (𝑥_{1}, 𝑥_{2})$ and $𝑥_{𝑁} = (𝑠_{1}, 𝑠_{2})$

\begin{matrix} 𝑐_{𝐵} = [\begin{matrix} 2 \\ 3 \end{matrix}] 𝑐_{𝑁} = [\begin{matrix} 0 \\ 0 \end{matrix}] \\ 𝐴_{𝐵} = [\begin{matrix} 1 & 1 \\ 1 & 2 \end{matrix}] 𝐴_{𝑁} = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] \\ 𝑏 = [\begin{matrix} 4 \\ 6 \end{matrix}] \end{matrix}

\begin{matrix} 𝐴_{𝐵}^{- 1} = [\begin{matrix} 2 & - 1 \\ - 1 & 1 \end{matrix}] \\ 𝐴_{𝐵}^{- 1} 𝐴_{𝑁} = [\begin{matrix} 2 & - 1 \\ - 1 & 1 \end{matrix}] \\ 𝐴_{𝐵}^{- 1} 𝑏 = [\begin{matrix} 2 \\ 2 \end{matrix}] \\ 𝑐_{𝐵}^{𝑇} 𝐴_{𝐵}^{- 1} 𝐴_{𝑁} - 𝑐_{𝑁}^{𝑇} = [\begin{matrix} 1 & 1 \end{matrix}] \\ 𝑐_{𝐵}^{𝑇} 𝐴_{𝐵}^{- 1} 𝑏 = 10 \end{matrix}

$0$	$0$	$1$	$1$	$10$
$1$	$0$	$2$	$- 1$	$2$
$0$	$1$	$- 1$	$1$	$2$
basic		non-basic		RHS

Example

Step 1. Canonical form

\begin{aligned} max & 𝑥_{1} + & 3 & 𝑥_{2} \\ 𝑠 . 𝑡 . - & 𝑥_{1} + & 𝑥_{2} \leq & 3 \\ - & 𝑥_{1} + & 2 & 𝑥_{2} \leq & 8 \\ 3 & 𝑥_{1} + & 𝑥_{2} \leq & 18 \end{aligned}

Step 2. Standard form

\begin{aligned} max & 𝑥_{1} + & 3 & 𝑥_{2} \\ 𝑠 . 𝑡 . - & 𝑥_{1} + & 𝑥_{2} + & 𝑠_{1} & = 3 \\ - & 𝑥_{1} + & 2 & 𝑥_{2} & + & 𝑠_{2} & = 8 \\ 3 & 𝑥_{1} + & 𝑥_{2} & + & 𝑠_{3} & = 18 \end{aligned}

Matrix notation:

\begin{aligned} 𝑐^{𝑇} & = [\begin{matrix} 1 & 3 & 0 & 0 & 0 \end{matrix}] \\ 𝐴 & = [\begin{matrix} - 1 & 1 & 1 & 0 & 0 \\ - 1 & 2 & 0 & 1 & 0 \\ 3 & 1 & 0 & 0 & 1 \end{matrix}] 𝑏 = [\begin{matrix} 3 \\ 8 \\ 18 \end{matrix}] \end{aligned}

Step 3. Initial Basis

\begin{aligned} 𝐵 & = (𝑠_{1}, 𝑠_{2}, 𝑠_{3}) & 𝑁 & = (𝑥_{2}, 𝑥_{2}) \\ 𝐵 & = [\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] & 𝑁 & = [\begin{matrix} - 1 & 1 \\ - 1 & 2 \\ 3 & 1 \end{matrix}] \\ 𝑐_{𝐵}^{𝑇} & = [\begin{matrix} 0 & 0 & 0 \end{matrix}] & 𝑐_{𝑁}^{𝑇} & = [\begin{matrix} 1 & 3 \end{matrix}] \end{aligned}

Compute $𝐵^{- 1}$ :

𝐵^{- 1} = [\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}]

Compute basic feasible solution:

𝑥_{𝐵} = 𝐵^{- 1} 𝑏 = [\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] [\begin{matrix} 3 \\ 8 \\ 18 \end{matrix}] = [\begin{matrix} 3 \\ 8 \\ 18 \end{matrix}] = [\begin{matrix} 𝑠_{1} \\ 𝑠_{2} \\ 𝑠_{3} \end{matrix}]

Current basic feasible solution:

𝑥 = (𝑥_{1}, 𝑥_{2}, 𝑠_{1}, 𝑠_{2}, 𝑠_{3}) = (0, 0, 3, 8, 18)

𝑧 = 𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑏 = 𝑐_{𝐵}^{𝑇} 𝑥_{𝐵} = [\begin{matrix} 0 & 0 & 0 \end{matrix}] [\begin{matrix} 3 \\ 8 \\ 18 \end{matrix}] = 0

Step 4. Reduced costs and entering variable

\begin{aligned} {\bar{𝑐}}_{𝑁}^{𝑇} & = 𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑁 - 𝑐_{𝑁}^{𝑇} \\ = [\begin{matrix} 0 & 0 & 0 \end{matrix}] [\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] [\begin{matrix} - 1 & 1 \\ - 1 & 2 \\ 3 & 1 \end{matrix}] - [\begin{matrix} 1 & 3 \end{matrix}] \\ = [\begin{matrix} - 1 & - 3 \end{matrix}] \end{aligned}

Since ${\bar{𝑐}}_{1} = - 1 < 0$ , the entering variable is $𝑥_{1}$

Step 5. Direction, ratio test and leaving variable

For $𝑥_{𝐵} = (𝑠_{1}, 𝑠_{2}, 𝑠_{3})$ , we have:

𝑑 = 𝐵^{- 1} 𝑁_{1} = [\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] [\begin{matrix} - 1 \\ 1 \\ 3 \end{matrix}] = [\begin{matrix} - 1 \\ - 1 \\ 3 \end{matrix}]

Current basic solution:

𝑥_{𝐵} = 𝐵^{- 1} 𝑏 = [\begin{matrix} 3 \\ 8 \\ 18 \end{matrix}]

The minimum ratios test:

\frac{𝑠_{3}}{3} = \frac{18}{3} = 6

Smallest ratio is $3 \Rightarrow 𝑠_{3}$ leaves the basis (only consider ratios where the corresponding $𝑑_{𝑖} > 0$ )

Step 6. Pivot to the new basis

\begin{aligned} 𝐵 & = (𝑠_{1}, 𝑠_{2}, 𝑥_{1}) & 𝑁 & = (𝑠_{3}, 𝑥_{2}) \\ 𝐵 & = [\begin{matrix} 1 & 0 & - 1 \\ 0 & 1 & - 1 \\ 0 & 0 & 3 \end{matrix}] & 𝑁 & = [\begin{matrix} 0 & 1 \\ 0 & 2 \\ 1 & 1 \end{matrix}] \\ 𝑐_{𝐵}^{𝑇} & = [\begin{matrix} 0 & 0 & 1 \end{matrix}] & 𝑐_{𝑁}^{𝑇} & = [\begin{matrix} 0 & 3 \end{matrix}] \end{aligned}

Compute $𝐵^{- 1}$ :

𝐵^{- 1} = [\begin{matrix} 1 & 0 & 0.33 \\ 0 & 1 & 0.33 \\ 0 & 0 & 0.33 \end{matrix}]

Compute basic feasible solution:

𝑥_{𝐵} = 𝐵^{- 1} 𝑏 = [\begin{matrix} 1 & 0 & 0.33 \\ 0 & 1 & 0.33 \\ 0 & 0 & 0.33 \end{matrix}] [\begin{matrix} 3 \\ 8 \\ 18 \end{matrix}] = [\begin{matrix} 8.94 \\ 13.94 \\ 5.94 \end{matrix}] = [\begin{matrix} 𝑠_{1} \\ 𝑠_{2} \\ 𝑥_{1} \end{matrix}]

Current basic feasible solution:

\begin{matrix} 𝑥 = (𝑥_{1}, 𝑥_{2}, 𝑠_{1}, 𝑠_{2}, 𝑠_{3}) = (5.94, 0, 8.94, 13.94, 0) \\ 𝑧 = 𝑐_{𝐵}^{𝑇} 𝑥_{𝐵} = [\begin{matrix} 0 & 0 & 1 \end{matrix}] [\begin{matrix} 8.94 \\ 13.94 \\ 5.94 \end{matrix}] = 5.94 \end{matrix}

Step 7. Reduced costs and entering variable

\begin{aligned} {\bar{𝑐}}_{𝑁}^{𝑇} & = 𝑐_{𝐵}^{𝑇} 𝐵^{- 1} 𝑁 - 𝑐_{𝑁}^{𝑇} \\ = [\begin{matrix} 0 & 0 & 1 \end{matrix}] [\begin{matrix} 1 & 0 & 0.33 \\ 0 & 1 & 0.33 \\ 0 & 0 & 0.33 \end{matrix}] [\begin{matrix} 0 & 1 \\ 0 & 2 \\ 1 & 1 \end{matrix}] - [\begin{matrix} 0 & 3 \end{matrix}] \\ = [\begin{matrix} 0.33 & - 2.67 \end{matrix}] \end{aligned}

Since ${\bar{𝑐}}_{2} = −2.67 < 0$ , the entering variable is $𝑥_{2}$

Step 8. Direction, ratio test and leaving variable

For $𝑥_{𝐵} = (𝑠_{1}, 𝑠_{2}, 𝑥_{1})$ , we have:

𝑑 = 𝐵^{- 1} 𝑁_{2} = [\begin{matrix} 1 & 0 & 0.33 \\ 0 & 1 & 0.33 \\ 0 & 0 & 0.33 \end{matrix}] [\begin{matrix} 1 \\ 2 \\ 1 \end{matrix}] = [\begin{matrix} 1.33 \\ 2.33 \\ 0.33 \end{matrix}]

Current basic solution:

𝑥_{𝐵} = 𝐵^{- 1} 𝑏 = [\begin{matrix} 8.94 \\ 13.94 \\ 5.94 \end{matrix}]

The minimum ratios test:

\frac{𝑠_{1}}{1} = \frac{8.94}{1.33} = 6.75, \frac{𝑠_{2}}{2} = \frac{13.94}{2.33} = 6, \frac{𝑥_{1}}{1} = \frac{5.94}{0.33} = 18

Smallest ratio is $\frac{13.94}{2} \Rightarrow 𝑠_{2}$ leaves the basis (only consider ratios where the corresponding $𝑑_{𝑖} > 0$ )

Step 9. Pivot to the new basis

\begin{aligned} 𝐵 & = (𝑠_{1}, 𝑥_{2}, 𝑥_{1}) & 𝑁 & = (𝑠_{2}, 𝑠_{3}) \\ 𝐵 & = [\begin{matrix} 1 & 1 & - 1 \\ 0 & 2 & - 1 \\ 0 & 1 & 3 \end{matrix}] & 𝑁 & = [\begin{matrix} 0 & 0 \\ 1 & 1 \\ 0 & 1 \end{matrix}] \\ 𝑐_{𝐵}^{𝑇} & = [\begin{matrix} 0 & 3 & 1 \end{matrix}] & 𝑐_{𝑁}^{𝑇} & = [\begin{matrix} 0 & 0 \end{matrix}] \end{aligned}

Compute $𝐵^{- 1}$ :

𝐵^{- 1} = [\begin{matrix} 1 & - 0.57 & 0.14 \\ 0 & 0.43 & 0.14 \\ 0 & - 0.14 & 0.29 \end{matrix}]

Compute basic feasible solution:

𝑥_{𝐵} = 𝐵^{- 1} 𝑏 = [\begin{matrix} 1 & - 0.57 & 0.14 \\ 0 & 0.43 & 0.14 \\ 0 & - 0.14 & 0.29 \end{matrix}] [\begin{matrix} 3 \\ 8 \\ 18 \end{matrix}] = [\begin{matrix} 0.96 \\ 5.96 \\ 4.1 \end{matrix}] = [\begin{matrix} 𝑠_{1} \\ 𝑥_{2} \\ 𝑥_{1} \end{matrix}]

Current basic feasible solution:

\begin{matrix} 𝑥 = (𝑥_{1}, 𝑥_{2}, 𝑠_{1}, 𝑠_{2}, 𝑠_{3}) = (4, 6, 1, 0, 0) \\ 𝑧 = 𝑐_{𝐵}^{𝑇} 𝑥_{𝐵} = [\begin{matrix} 0 & 3 & 1 \end{matrix}] [\begin{matrix} 0.96 \\ 5.96 \\ 4.1 \end{matrix}] = 22 \end{matrix}

Nv = np.array(['x1', 'x2'])
Bv = np.array(['s1', 's2', 's3'])

A = np.array([
    [-1, 1, 1, 0, 0],
    [-1, 2, 0, 1, 0],
    [3, 1, 0, 0, 1],
])

c = np.array([1, 3, 0, 0, 0])

b = np.array([3, 8, 18])

cN = c[:2]
cB = c[2:]

N = A[:,:2]
B = A[:,2:]

print("Nv"), print(Nv)
print()
print("N"), print(N)
print()
print("cN"), print(cN)
print()
print("Bv"), print(Bv)
print()
print("B"), print(B)
print()
print("cB"), print(cB)
print()
print("b"), print(b)
print()

Binv = np.linalg.inv(B)
bfs = Binv @ b
z = cB @ bfs

print("B^(-1)"), print(Binv)
print()
print("BFS"), print(bfs)
print()
print("z"), print(z)
print()

reduced_cost = cB @ Binv @ N - cN

print("bar(c)_N^T"), print(reduced_cost)
print()

entering_var_index = 0

print("Entering var"), print(Nv[entering_var_index])
print()

d = Binv @ N[:,entering_var_index]
ratios = bfs / d

print(f"Ratios"), print(ratios)
print()

exiting_var_index = 2

print(f"Exiting variable"), print(Bv[exiting_var_index])
print()

B[:, exiting_var_index], N[:, entering_var_index] = N[:, entering_var_index].copy(), B[:, exiting_var_index].copy()
cB[exiting_var_index], cN[entering_var_index] = cN[entering_var_index].copy(), cB[exiting_var_index].copy()
Bv[exiting_var_index], Nv[entering_var_index] = Nv[entering_var_index].copy(), Bv[exiting_var_index].copy()

print("Nv"), print(Nv)
print()
print("N"), print(N)
print()
print("cN"), print(cN)
print()
print("Bv"), print(Bv)
print()
print("B"), print(B)
print()
print("cB"), print(cB)
print()

Binv = np.linalg.inv(B)
bfs = Binv @ b
z = cB @ bfs

print("B^(-1)"), print(Binv)
print()
print("BFS"), print(bfs)
print()
print("z"), print(z)
print()

reduced_cost = cB @ Binv @ N - cN

print("bar(c)_N^T"), print(reduced_cost)
print()

entering_var_index = 1

print("Entering var"), print(Nv[entering_var_index])
print()

d = Binv @ N[:,entering_var_index]
ratios = bfs / d

print(f"Ratios"), print(ratios)
print()

exiting_var_index = 1

print(f"Exiting variable"), print(Bv[exiting_var_index])
print()

B[:, exiting_var_index], N[:, entering_var_index] = N[:, entering_var_index].copy(), B[:, exiting_var_index].copy()
cB[exiting_var_index], cN[entering_var_index] = cN[entering_var_index].copy(), cB[exiting_var_index].copy()
Bv[exiting_var_index], Nv[entering_var_index] = Nv[entering_var_index].copy(), Bv[exiting_var_index].copy()

print("Nv"), print(Nv)
print()
print("N"), print(N)
print()
print("cN"), print(cN)
print()
print("Bv"), print(Bv)
print()
print("B"), print(B)
print()
print("cB"), print(cB)
print()

Binv = np.linalg.inv(B)
bfs = Binv @ b
z = cB @ bfs

print("B^(-1)"), print(Binv)
print()
print("BFS"), print(bfs)
print()
print("z"), print(z)
print()