4.2. Correctness of the Simplex Algorithm

In this section, we prove that the Simplex Algorithm computes an optimal solution of the LP it is given. Consider the LP

\[\begin{gathered} \text{Maximize } cx\\ \begin{aligned} \text{s.t. }Ax &\le b\\ x &\ge 0 \end{aligned} \end{gathered}\tag{4.3}\]

and its dual

\[\begin{gathered} \text{Minimize } b^Ty\\ \begin{aligned} \text{s.t. }A^Ty &\ge c^T\\ y &\ge 0. \end{aligned} \end{gathered}\tag{4.4}\]

To solve (4.3) using the Simplex Algorithm, we convert it into an LP \(S\) in standard form:

\[\begin{gathered} \text{Maximize } c'z\\ \begin{aligned} \text{s.t. }A'z &= b\\ z &\ge 0, \end{aligned} \end{gathered}\tag{4.5}\]

where \(z_1, \ldots, z_m\) are slack variables corresponding to the \(m\) constraints of (4.3) and \(z_{j+m} = x_j\) for all \(1 \le j \le n\). \(c'\) is an \((m+n)\)-element vector with \(c_1' = \cdots = c_m' = 0\) and \(c'_{j+m} = c_j\) for all \(1 \le j \le n\). Finally, \(A'\) is an \(m \times (m + n)\) matrix whose leftmost \(m\) columns are the identity matrix and whose rightmost \(n\) columns are \(A\).

Now recall that the Simplex Algorithm produces a sequence of LPs \(S^{(0)}, \ldots, S^{(t)}\) equivalent to \(S\) and that the solution \(\hat z\) it outputs is the BFS of \(S^{(t)}\). Let \(S^{(t)}\) be the LP

\[\begin{gathered} \text{Maximize } c''z + d''\\ \begin{aligned} \text{s.t. }A''z &= b''\\ z &\ge 0. \end{aligned} \end{gathered}\tag{4.6}\]

Recall that since \(\hat z\) is the BFS of \(S^{(t)}\), its objective function value is \(d''\). Since \(S\) and \(S^{(t)}\) are equivalent, \(S\)'s objective function assigns the same objective function value to \(\hat z\):

\[c'\hat z = d''.\]

From \(\hat z\), we obtain a feasible solution \(\hat x\) of (4.3) as

\[\hat x_j = \hat z_{j+m} \quad \forall 1 \le j \le m.\tag{4.7}\]

Its objective function value is

\[c\hat x = c'\hat z = d''.\tag{4.8}\]

We can use \(S^{(t)}\) to construct a solution \(\hat y\) of (4.4):

\[\hat y_i = -c_i'' \quad \forall 1 \le i \le m.\tag{4.9}\]

The following lemma shows that \(\hat y\) is a feasible dual solution with objective function value \(b^T \hat y = d''\). Since we just observed that \(\hat x\) is a feasible primal solution with objective function value \(d''\), Corollary 4.2 proves that \(\hat x\) is an optimal primal solution and \(\hat y\) is an optimal dual solution, which is what we want to prove.

Lemma 4.4: \(\hat y\) is a feasible solution of (4.4) with objective function value \(b^T \hat y = d''\).

Proof: Given the definitions of \(A'\), \(c'\), \(c''\), \(\hat x\), and \(\hat y\), we have

\[\begin{aligned} \sum_{j=1}^n c_j\hat x_j &= \sum_{j=1}^{m+n} c_j'\hat z_j\\ &= \sum_{j=1}^{m+n} c_j''\hat z_j + d''\\ &= d'' + \sum_{i=1}^m c_i''\hat z_i + \sum_{j=1}^n c_{j+m}''\hat z_{j+m}\\ &= d'' + \sum_{i=1}^m (-\hat y_i)\left(b_i - \sum_{j=1}^n a_{i,j+m}' \hat z_{j+m}\right) + \sum_{j=1}^n c_{j+m}''\hat z_{j+m}\\ &= d'' + \sum_{i=1}^m (-\hat y_i)\left(b_i - \sum_{j=1}^n a_{ij} \hat x_j\right) + \sum_{j=1}^n c_{j+m}''\hat x_j\\ &= \left(d'' - \sum_{i=1}^m b_i\hat y_i\right) + \sum_{j=1}^n\left(c_{j+m}'' + \sum_{i=1}^m a_{ij}\hat y_i\right)\hat x_j. \end{aligned}\tag{4.10}\]

The second line follows from the first because \(S\) and \(S^{(t)}\) are equivalent. The fourth line follows from the third because \(\hat y_i = -c_i''\) for all \(1 \le i \le m\) (by (4.9)) and \(\hat z\) is a feasible solution of \(S\), so \(\hat z_i = b_i - \sum_{j=1}^n a_{i,j+m}'\hat z_{j+m}\) for all \(1 \le i \le m\). The fifth line follows from the fourth because \(a_{ij} = a'_{i,j+m}\) and \(\hat x_j = \hat z_{j+m}\) for all \(1 \le j \le n\) (by (4.7)). The third and sixth lines are simply rearrangements of the previous lines.

Next observe that, for any index \(1 \le k \le n\) and any real value \(\delta\), the vector \(\tilde z\) defined as

\[\tilde z_j = \begin{cases} \hat z_j - a_{jk}\delta & \text{if } 1 \le j \le m\\ \hat z_j + \delta & \text{if } j = k + m\\ \hat z_j & \text{if } m < j \le m+n, j \ne k + m \end{cases}\]

is also a (not necessarily feasible) solution of \(S\). Its corresponding solution of (4.3) is \(\tilde x = \bigl(\tilde z_{m+1}, \ldots, \tilde z_{m+n}\bigr)\), that is,

\[\tilde x_j = \begin{cases} \hat x_j + \delta & \text{if } j = k\\ \hat x_j & \text{if } j \ne k. \end{cases}\]

By substituting \(\tilde x\) into (4.10), we obtain

\[\begin{aligned} \sum_{j=1}^{n} c_j\tilde x_j = \left(d'' - \sum_{i=1}^m b_i\hat y_i\right) &+ \sum_{j=1}^n\left(c_{j+m}'' + \sum_{i=1}^m a_{ij}\hat y_i\right)\tilde x_j\\ \sum_{j=1}^{n} c_j\hat x_j + c_k\delta = \left(d'' - \sum_{i=1}^m b_i\hat y_i\right) &+ \sum_{j=1}^n\left(c_{j+m}'' + \sum_{i=1}^m a_{ij}\hat y_i\right)\hat x_j + \left(c_{k+m}'' + \sum_{i=1}^m a_{ik}\hat y_i\right)\delta. \end{aligned}\]

Since

\[\sum_{j=1}^{n} c_j\hat x_j = \left(d'' - \sum_{i=1}^m b_i\hat y_i\right) + \sum_{j=1}^n\left(c_{j+m}'' + \sum_{i=1}^m a_{ij}\hat y_i\right)\hat x_j\ \text{(by (4.10)),}\]

this shows that

\[c_k\delta = \left(c_{k+m}'' + \sum_{i=1}^m a_{ik}\hat y_i\right)\delta.\]

Since this is true for all \(\delta \in \mathbb{R}\), this implies that

\[c_k = c_{k+m}'' + \sum_{i=1}^m a_{ik}\hat y_i.\tag{4.11}\]

Since this holds for all \(1 \le k \le n\), we can substitute this equality into (4.10) and obtain

\[\begin{aligned} \sum_{j=1}^n c_j\hat x_j &= \left(d'' - \sum_{i=1}^m b_i\hat y_i\right) + \sum_{j=1}^n\left(c_{j+m}'' + \sum_{i=1}^m a_{ij}\hat y_i\right)\hat x_j\\ &= \left(d'' - \sum_{i=1}^m b_i\hat y_i\right) + \sum_{j=1}^nc_j\hat x_j \end{aligned}\]

and, hence,

\[d'' - \sum_{i=1}^m b_i\hat y_i = 0.\]

Thus, the objective function value of \(\hat y\) as a solution of (4.4) is

\[\sum_{i=1}^m b_i\hat y_i = d'',\]

as claimed.

To see that \(\hat y\) is feasible, observe that \(S^{(t)}\) satisfies \(c''_j \le 0\) for all \(1 \le j \le m+n\) (otherwise, the Simplex Algorithm would continue pivoting). Thus,

\[\hat y_i = -c''_i \ge 0\]

for all \(1 \le i \le m\). To see that \(\hat y\) satisfies all upper bound constraints in (4.4), observe that (4.11) and the fact that \(c_k'' \le 0\) for all \(1 \le k \le n\) imply that

\[c_k \le \sum_{i=1}^m a_{ik}\hat y_i,\]

for all \(1 \le k \le n\), that is,

\[c \le A^T \hat y.\]

\(\hat y\) is therefore a feasible solution of (4.4). ▨