3.3.2. Transforming the LP

To complete the pivoting step, we need to construct an LP \(P^{(s+1)}\)

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

with basis \(B^{(s+1)}\) from the LP \(P^{(s)}\)

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

with basis \(B^{(s)}\) that is equivalent to \(P^{(s)}\) and has \(\hat z^{(s+1)}\) as its BFS. Let us spell out what this means:

• Equivalence: A vector \(\tilde z\) satisfies \(b = A\tilde z\) if and only if it satisfies \(b' = A'\tilde z\) and, for any such vector \(\tilde z\), \(c \tilde z + d = c'\tilde z + d'\).

• \(\boldsymbol{B^{(s+1)}}\) is a basis: If \(B^{(s+1)} = (j_1', \ldots, j_m')\), then every \(j'_i \in B^{(s+1)}\) satisfies \(c'_{j'_i} = 0\), \(a_{ij'_i} = 1\), and \(a_{i'j'_i} = 0\) for all \(i' \ne i\).

• \(\boldsymbol{\hat z^{(s+1)}}\) is a BFS of \(\boldsymbol{P^{(s+1)}}\): \(\hat z_h^{(s+1)} = 0\) for all \(h \notin B^{(s+1)}\).

Making \(\boldsymbol{\hat z^{(s+1)}}\) a BFS of \(\boldsymbol{P^{(s+1)}}\)

We choose the basis \(B^{(s+1)}\) of \(P^{(s+1)}\) as \(B^{(s+1)} = (j_1, \ldots, j_{k-1}, j, j_{k+1}, \ldots, j_m)\), that is, \(z_j\) replaces \(z_{j_k}\) as the basic variable corresponding to the \(k\)th constraint. We say that \(z_j\) enters the basis in this pivoting step and \(z_{j_k}\) leaves the basis in this pivoting step. This explicitly ensures that \(\hat z^{(s+1)}\) is a basic solution of \(P^{(s+1)}\). Indeed, we have \(\hat z_h^{(s+1)} = \hat z_h^{(s)} = 0\) for all \(h \notin B^{(s)} \cup \{j\}\). The only other index \(h \notin B^{(s+1)}\) is \(h = j_k\). Since \(\hat z_{j_k}^{(s+1)} = b_k - a_{kj}\Delta_k = b_k - a_{kj}\frac{b_k}{a_{kj}} = 0\), we thus have \(\hat z_h^{(s+1)} = 0\) for all \(h \notin B^{(s+1)}\).

Since we have argued in Section 3.3.1 that \(\hat z^{(s+1)}\) is a feasible solution of \(P^{(i)}\) and we ensure that \(P^{(i)}\) and \(P^{(i+1)}\) are equivalent, \(\hat z^{(s+1)}\) is a feasible solution of \(P^{(i+1)}\). We have just verified that it is a basic solution of \(P^{(i+1)}\). Thus, it is a basic feasible solution of \(P^{(i+1)}\).

Making \(\boldsymbol{B^{(s+1)}}\) a Basis of \(\boldsymbol{P^{(s+1)}}\)

To ensure that \(B^{(s+1)}\) is a basis of \(P^{(s+1)}\), we construct \(P^{(s+1)}\) in two steps. First we construct an LP \(P'\)

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

with the same objective function as \(P^{(s)}\), equivalent to \(P^{(s)}\), and such that \(a'_{ij_i'} = 1\) and \(a'_{i'j_i'} = 0\) for all \(1 \le i \ne i' \le m\). Then we replace the objective function of \(P'\) with an objective function \(c'z + d'\) that satisfies \(c'_{j'_i} = 0\) for all \(1 \le i \le m\) and \(c\tilde z + d = c'\tilde z + d'\) for every solution \(\tilde z\) of the system of linear equations \(b' = A'z\). Thus, the resulting LP \(P^{(s+1)}\) is equivalent to \(P'\), and thus to \(P^{(s)}\), and \(B^{(s+1)}\) is a basis of \(P^{(s+1)}\).

For the construction of \(P'\) from \(P^{(s)}\), we use the following fact from linear algebra:

Given a set of linear equations \(b = Az\), an elementary row operation does one of two things:

• Multiply an entire row (an equation) with a non-zero coefficient.

  For example, multiplying

  \[3x - 4y = 5\]

  with \(2\) produces

  \[6x - 8y = 10.\]

• Add a multiple of one row to another row.

  For example, adding \(3\) times the first row to the second row in the system

  \[\begin{aligned} 3x - 4y &= 5\\ -9x + 2y &= 10 \end{aligned}\]

  produces the system

  \[\begin{aligned} 3x - 4y &= 5\\ -10y &= 25. \end{aligned}\]

Lemma 3.2: If \(b' = A'z\) is a system of linear equations obtained from another system of linear equations \(b = Az\) using only elementary row operations, then \(b = Az\) and \(b' = A'z\) have the same set of solutions.

Observe that every basic variable \(z_{j_i}\) with \(j_i \in B^{(s)}\) satisfies \(a_{ij_i} = 1\) and \(a_{i'j_i} = 0\) for all \(i' \ne i\). The only basic variable of \(P^{(s+1)}\) that is not a basic variable of \(P^{(s)}\) is \(z_j\), and it is the basic variable corresponding to the \(k\)th constraint in \(P^{(s+1)}\). Thus, our construction of \(P'\) needs to ensure that \(z_j\) has coefficient \(1\) in the \(k\)th constraint of \(P'\) and coefficient \(0\) in all other constraints of \(P'\) while not changing the coefficients of any variable \(z_h\) with \(h \in B^{(s)} \setminus \{j_k\}\). Here is how we do this:

• Rewrite the \(\boldsymbol{k}\)th constraint: To ensure that \(z_j\) has coefficient \(1\) in the \(k\)th constraint, we divide this constraint by \(a_{kj}\), that is, the constraint

  \[b_k = \sum_{h=1}^{m+n} a_{kh}z_h\]

  becomes

  \[\frac{b_k}{a_{kj}} = \sum_{h=1}^{m+n} \frac{a_{kh}}{a_{kj}}z_h.\tag{3.1}\]

  Since \(a_{kj} > 0\) (otherwise, \(\Delta_k\) wouldn't be finite), this is a valid elementary row operation, and it ensures that the coefficient of \(z_j\) is \(\frac{a_{kj}}{a_{kj}} = 1\).

• Rewrite the remaining constraints: To ensure that \(z_j\) has coefficient \(0\) in every constraint other than the \(k\)th constraint, we subtract (3.1) multiplied with \(a_{ij}\) from the \(i\)th constraint for all \(i \ne k\). The constraint

  \[b_i = \sum_{h=1}^{m + n} a_{ih}z_h\]

  becomes

  \[b_i - \frac{b_k}{a_{kj}}a_{ij} = \sum_{h=1}^{m + n} \left(a_{ih} - \frac{a_{kh}}{a_{kj}}a_{ij}\right)z_h.\]

  This does indeed ensure that the coefficient of \(z_j\) in the \(i\)th constraint becomes \(0\) because \(z_j\)'s coefficient becomes \(a_{ij} - \frac{a_{kj}}{a_{kj}}a_{ij} = 0\).

This gives us the LP \(P'\)

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

with

\[b_i' = \begin{cases} \frac{b_k}{a_{kj}} & \text{if } i = k\\ b_i - \frac{b_k}{a_{kj}}a_{ij} & \text{if } i \ne k \end{cases}\]

and

\[a_{ih}' = \begin{cases} \frac{a_{kh}}{a_{kj}} & \text{if } i = k\\ a_{ih} - \frac{a_{kh}}{a_{kj}}a_{ij} & \text{if } i \ne k. \end{cases}\]

Since the system of equations \(b' = A'z\) is obtained from \(b = Az\) using only elementary row operations, and \(P'\) has the same objective function as \(P^{(s)}\), Lemma 3.2 shows that these two LPs are equivalent.

The two transformations above explicitly ensure that \(z_j\) has coefficient \(1\) in the \(k\)th constraint of \(P'\) and coefficient \(0\) in every other constraint. For any basic variable \(z_{j'_i}\) of \(P'\) with \(i \ne k\), note that \(j'_i = j_i\), so \(a_{kj'_i} = 0\) and, therefore,

\[a'_{kj'_i} = \frac{a_{kj'_i}}{a_{kj}} = 0.\]

For \(i' \ne k\), we have

\[a'_{i'j'_i} = a_{i'j'_i} - \frac{a_{kj'_i}}{a_{kj}}a_{i'j'_i} = a_{i'j'_i}.\]

In particular, \(a'_{i'j'_i} = 1\) if \(i' = i\) and \(a'_{i'j'_i} = 0\) if \(i' \ne i\). This shows that every variable \(z_{j'_i}\) with \(j'_i \in B^{(s+1)}\) satisfies \(a'_{ij'_i} = 1\) and \(a'_{i'j'_i} = 0\) for all \(i' \ne i\). Therefore, \(B^{(s+1)}\) is almost a basis of \(P'\). To make it a proper basis, it remains to replace the objective function \(cz + d\) with an objective function \(c'z + d'\) such that \(c'_{j'_i} = 0\) for all \(j'_i \in B^{(s+1)}\) and \(c\tilde z + d = c'\tilde z + d\) for every solution \(\tilde z\) of \(A'z = b'\).

Again, for \(i \ne k\), we have \(j'_i = j_i\), so \(c_{j'_i} = 0\). Thus, we only need to ensure that \(c'_j = 0\) while also ensuring that \(c'_{j'_i} = c_{j'_i}\) for all \(j'_i \in B^{(s+1)} \setminus \{j\}\).

Every solution \(\tilde z\) of \(A'z = b'\) satisfies

\[b'_k = \sum_{h=1}^{m+n}a'_{kh}\tilde z_h,\]

that is,

\[\tilde z_j = b'_k - \sum_{h=1}^{j-1}a'_{kh}\tilde z_h - \sum_{h=j+1}^{m+n}a'_{kh}\tilde z_h = \frac{b_k}{a_{kj}} - \sum_{h=1}^{j-1}\frac{a_{kh}}{a_{kj}}\tilde z_h - \sum_{h=j+1}^{m+n}\frac{a_{kh}}{a_{kj}}\tilde z_h. \]

Substituting this equation into the objective function \(cz + d\) gives

\[\begin{aligned} \sum_{h=1}^{m+n}c_h\tilde z_h + d &= \sum_{h=1}^{j-1} c_h\tilde z_h + c_j \left( \frac{b_k}{a_{kj}} - \sum_{h=1}^{j-1} \frac{a_{kh}}{a_{kj}}\tilde z_h - \sum_{h=j+1}^{m+n} \frac{a_{kh}}{a_{kj}}\tilde z_h \right) + \sum_{h=j+1}^{m+n} c_h\tilde z_h + d\\ &= \sum_{h=1}^{j-1} \left(c_h - \frac{a_{kh}}{a_{kj}}c_j\right) \tilde z_h + \sum_{h=j+1}^{m+n} \left(c_h - \frac{a_{kh}}{a_{kj}}c_j\right) \tilde z_h + \left(d + \frac{b_k}{a_{kj}}c_j\right)\\ &= \sum_{h=1}^{m+n}c_h' \tilde z_h + d', \end{aligned}\]

where

\[c'_h = \begin{cases} 0 & \text{if } h = j\\ c_h - \frac{a_{kh}}{a_{kj}}c_j & \text{if } h \ne j \end{cases}\]

and

\[d' = d + \frac{b_k}{a_{kj}}c_j.\]

This is the objective function \(c'z + d'\) of \(P^{(s+1)}\).

The construction explicitly ensures that \(c'\tilde z + d' = c \tilde z + d\) for every solution \(\tilde z\) of \(A'z = b'\). Thus, \(P^{(s+1)}\) and \(P'\) are equivalent, as are \(P^{(s+1)}\) and \(P^{(s)}\).

The construction also ensures that \(c'_j = 0\). For \(j'_i \in B^{(s+1)}\) with \(i \ne k\), we have \(c'_{j'_i} = c_{j'_i} - \frac{a_{kj'_i}}{a_{kj}}c_j = 0\) because \(c_{j'_i} = c_{j_i} = 0\) and, as observed above, \(a_{kj'_i} = a_{kj_i} = 0\). \(B^{(s+1)}\) is thus a valid basis of \(P^{(s+1)}\).

This is the complete pivoting step: We convert the BFS \(\hat z^{(s)}\) of the current LP \(P^{(s)}\) into another feasible solution \(\hat z^{(s+1)}\) by choosing a non-basic variable \(z_j\) with \(c_j > 0\) and choosing \(\hat z_j^{(s+1)}\) maximally so that \(b = A\hat z^{(s+1)}\) and \(\hat z^{(s+1)} \ge 0\). Then we convert \(P^{(s)}\) into an equivalent LP \(P^{(s+1)}\) that has \(\hat z^{(s+1)}\) as its BFS. Remember that the Simplex Algorithm repeatedly applies this pivoting step until it either determines that the LP is unbounded (because \(\Delta_k = \infty\)) or \(c_j \le 0\) for all \(j \notin B^{(s)}\), at which point \(\hat z^{(s)}\) is an optimal solution of the LP.

If \(0 < \Delta_k < \infty\), then the BFS \(\hat z^{(s+1)}\) of \(P^{(s+1)}\) has objective function value \(c_j\Delta_k + d > d\), while the BFS \(\hat z^{(s)}\) of \(P^{(s)}\) has objective function value \(d\). Thus, pivoting increases the objective function value. If \(\Delta_k = 0\), on the other hand, then \(\hat z^{(s+1)}\) and \(\hat z^{(s)}\) have the same objective function value. Such a pivoting operation changes only the LP and its basis but not the BFS.

A pivoting step that changes the LP and its basis but not the BFS is called degenerate.

The next iteration may choose to undo the replacement or \(z_{j_k}\) with \(z_j\) as a basic variable or there may be a longer sequence of degenerate pivoting operations that lead back to the current LP without any improvement in the objective function value. This is known as cycling and may cause the Simplex Algorithm to run forever. We discuss in Section 3.6 that choosing the non-basic variable entering the basis and the basic variable leaving the basis in each pivoting operation carefully prevents cycling.