3.2. Overview of the Simplex Algorithm

The Simplex Algorithm consists of two phases:

Initialization

The initialization phase is concerned with finding any feasible solution of the given LP \(P\) or deciding that there is no feasible solution. If the LP has a feasible solution, then we transform \(P\) into an equivalent LP \(P^{(0)}\) such that the basic solution \(\hat z^{(0)}\) of \(P^{(0)}\) is feasible. As we discuss in Section 3.4, we can apply the Simplex Algorithm itself to an auxiliary LP \(Q\) to implement this initialization step.

Optimization

If the initialization succeeds in finding an LP \(P^{(0)}\) that is equivalent to \(P\) and has a BFS, it remains to find an optimal solution of \(P^{(0)}\). The optimization phase either finds such a solution or determines that the LP is unbounded, that is, it has a feasible solution whose objective function value is \(\infty\). The optimization phase achieves this by constructing a sequence of LPs \(P^{(0)}, \ldots, P^{(t)}\) that are all equivalent and such that

• The basic solution \(\hat z^{(s)}\) of every LP \(P^{(s)}\) is a BFS.

• The BFS \(\hat z^{(s+1)}\) of \(P^{(s+1)}\) achieves an objective function value that is no less than the objective function value of the BFS \(\hat z^{(s)}\) of \(P^{(s)}\). Ideally, we want \(\hat z^{(s+1)}\) to have a greater objective function value than \(\hat z^{(s)}\).

• The BFS \(\hat z^{(t)}\) of \(P^{(t)}\) is an optimal solution of \(P^{(t)}\) and, thus, of \(P\) (because the LPs \(P, P^{(0)}, \ldots, P^{(t)}\) are all equivalent).

The construction of \(P^{(s+1)}\) from \(P^{(s)}\) for all \(0 \le s < t\) is called pivoting and is discussed next.