3.4. Initialization of the Algorithm

To complete the description of the Simplex Algorithm, we need to discuss how to decide whether a given LP \(P\)

\[\begin{gathered} \text{Maximize } cz + d\\ \begin{aligned} \text{s.t. } b &= Az\\ z &\ge 0 \end{aligned} \end{gathered}\]

has a feasible solution and, if so, how to turn it into an equivalent LP \(P^{(0)}\) whose basic solution is feasible. This LP \(P^{(0)}\) then forms the input to the optimization phase of the Simplex Algorithm.

If the basic solution \(\hat z\) of \(P\) is feasible, that is, if \(b \ge 0\), then \(P\) clearly has a feasible solution and \(\hat z\) is in fact a BFS, so we can set \(P^{(0)} = P\). Therefore, assume that \(P\)'s basic solution is infeasible.

To decide whether \(P\) has any feasible solution, we solve the following auxiliary LP \(Q\):

\[\begin{gathered} \text{Maximize } {-s}\\ \begin{aligned} \text{s.t. } b &= Az - 1s\\ z &\ge 0\\ s &\ge 0, \end{aligned} \end{gathered}\]

where \(1 = (1, \ldots, 1)^T\) is the \(m\)-element vector with all components equal to \(1\) and \(s\) is a new slack variable. In other words, \(Q\) is obtained from \(P\) by subtracting \(s\) from the right-hand side of each equality constraint and changing the objective function to \(-s\). \(Q\) has the same basis \(B\) as \(P\). If \(\hat z\) is the basic solution of \(P\), then \(\bigl(\hat z, \hat s\bigr)\) with \(\hat s = 0\) is the basic solution of \(Q\). Since we assume that \(\hat z\) is not a feasible solution of \(P\), \(\bigl(\hat z, \hat s \bigr)\) is not a feasible solution of \(Q\) either.

Let us defer the discussion of how to solve \(Q\) to Section 3.4.4. How does solving it help us to decide whether \(P\) is feasible?

Lemma 3.3: \(P\) is feasible if and only if \(Q\)'s optimal solution \(\bigl(\tilde z, \tilde s\bigr)\) has objective function value \(-\tilde s = 0\).

Proof: Given the constraint \(s \ge 0\), \(Q\) has no feasible solution with objective function value greater than \(0\), so any solution with objective function value \(0\) must be optimal.

If \(P\) is feasible, then there exists a solution \(\tilde z\) of \(P\) such that \(b = A\tilde z\) and \(\tilde z \ge 0\). Setting \(\tilde s = 0\) gives \(b = A\tilde z - 1\tilde s\) and \(\tilde s \ge 0\). Thus, \(\bigl(\tilde z, \tilde s\bigr)\) is a feasible solution of \(Q\) with objective function value \(-\tilde s = 0\) and is thus an optimal solution of \(Q\).

Conversely, assume that \(Q\) has an optimal solution \(\bigl(\tilde z, \tilde s\bigr)\) with objective function value \(-\tilde s = 0\). Then \(\tilde s = 0\). Thus, \(b = A\tilde z - 1\tilde s = A\tilde z\) and \(\tilde z \ge 0\), that is, \(\tilde z\) is a feasible solution of \(P\). ▨

By Lemma 3.3, we can answer that \(P\) is infeasible if \(Q\)'s optimal solution has objective function value less than \(0\). So assume that \(Q\) has an optimal solution \(\bigl(\tilde z, \tilde s\bigr)\) with objective function value \(0\). As shown in the proof of Lemma 3.3, \(\tilde z\) is a feasible solution of \(P\). Thus, it suffices to convert \(P\) into an equivalent LP \(P^{(0)}\) that has \(\hat z^{(0)} = \tilde z\) as its BFS.

As we discuss below, we solve \(Q\) using the Simplex Algorithm. Thus, \(\bigl(\tilde z, \tilde s\bigr)\) is the BFS of an LP \(Q'\) equivalent to \(Q\) and the Simplex Algorithm finds this LP along with \(\bigl(\tilde z, \tilde s\bigr)\). Let \(Q'\) be the LP

\[\begin{gathered} \text{Maximize } \sum_{j=1}^{m+n}p'_jz_j + q's + d'\\ \begin{aligned} \text{s.t. } b' &= A'z + r's\\ z &\ge 0\\ s &\ge 0, \end{aligned} \end{gathered}\]

and let \(B'\) be its basis. We construct \(P^{(0)}\) from \(Q'\) in three steps:

• We transform \(Q'\) into an equivalent LP \(Q''\) with the same BFS \(\bigl(\tilde z, \tilde s\bigr)\) and with \(s\) as a non-basic variable.

• We drop \(s\) from \(Q''\) and restore \(P\)'s objective function to obtain an LP \(P'\) equivalent to \(P\) with the same basis \(B''\) as \(Q''\). \(\tilde z\) is a basic solution of \(P'\) but technically \(B''\) isn't quite a valid basis of \(P'\): Some basic variables may have non-zero coefficients in the objective function.

• To turn \(B''\) into a proper basis and obtain our final LP \(P^{(0)}\), we replace the objective function of \(P'\) with an equivalent objective function—one that assigns the same objective function value to every solution—in which every basic variable has coefficient \(0\). This last step is very similar to the second part of a pivoting operation, discussed in Section 3.3.2.