Simplex Algorithm

Abstract

This is pseudocode for the core of the Simplex Algorithm, adapted from A Gentle Introduction to Optimization.

\SetAlgoCaptionSeparator

{algorithm}

Simplex Algorithm

\AlgoDisplayBlockMarkers\AlgoDisplayGroupMarkers\SetAlgoBlockMarkers

{ } \SetAlgoNoEnd\SetAlgoNoLine

\SetKwInOut

InputInput\SetKwInOutOutputOutput \InputLinear program (P) and feasible basis $B$ \OutputAn optimal solution for (P) or a certificate proving that (P) is unbounded Rewrite (P) so that it is in canonical form for the basis $B$
Let $\vec{x}$ be the basic feasible solution for $B$
\If $\vec{c_{N}}\leq\vec{0}$ stop
( $\vec{x}$ is optimal) Select $k\in N$ such that $c_{k}>0$
\If $A_{k}\leq\vec{0}$ stop
((P) is unbounded) Let r be any index i where the following minimum is attained:

t=\operatorname{min}\left\{\frac{b_{i}}{A_{i,k}}:A_{i,k}>0\right\}

(1)

Let $\iota$ be the $r^{th}$ basis element
Set $B:=B\cup\{k\}$ \ $\{\iota\}$
Go to step 1

Notes:

1.

Recall $\vec{c}$ is the vector of coefficients in our objective function $z(\vec{x})$ , and $c_{k}$ is the $k$ th element of $\vec{c}$ .
2.

$B$ is the set of columns in $A$ that comprise our basis; $N$ is the rest of the columns.
3.

$\vec{c_{N}}$ is $\vec{c}$ with the columns corresponding to basis $B$ removed.
4.

$A$ is the $m\times n$ matrix with linearly independent rows that comprise our constraints. $A_{k}$ is the $k$ th column of $A$ (a vector, though we aren’t writing it with the arrow above), and $A_{B}$ or $A_{N}$ is a matrix comprised of a subset of the columns of $A$ , keeping them in the original order.