3.3.1. Finding a Better Solution

Let \(P^{(s)}\) be the LP

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

and let \(B^{(s)} = (j_1, \ldots, j_m)\) be its basis.

We prove in Section 4.2 that \(\hat z^{(s)}\) is an optimal solution of \(P^{(s)}\) if \(c \le 0\). The Simplex Algorithm exits in this case and reports \(\hat z^{(s)}\) as its output.

If \(c \not\le 0\), then there exists an index \(j\) such that \(c_j > 0\). Since \(c_h = 0\) for all \(h \in B^{(s)}\), we must have \(j \notin B^{(s)}\), that is, \(z_j\) is a non-basic variables. The algorithm picks an arbitrary non-basic variable \(z_j\) with \(c_j > 0\).¹ Increasing \(z_j\) above its current value \(\hat z_j^{(s)} = 0\) while leaving all other non-basic variables unchanged clearly increases the objective function value. Since every basic variable \(z_h\) satisfies \(c_h = 0\), this is true even if increasing the value of \(z_j\) forces us to change the values of basic variables to maintain a solution, that is, to maintain the equality constraints \(b = Az\). Our goal is to choose \(\hat z_j^{(s+1)}\) as large as possible while ensuring that \(\hat z^{(s+1)}\) is a feasible solution of \(P^{(s)}\) and keeping all non-basic variables other than \(z_j\) unchanged: \(\hat z_h^{(s+1)} = \hat z_h^{(s)} = 0\) for all \(h \notin B^{(s)} \cup \{j\}\).

How large can we choose \(\hat z_j^{(s+1)}\)? We need to be able to complement our choice of \(\hat z_j^{(s+1)}\) with values \(\hat z_{j_1}^{(s+1)}, \ldots, \hat z_{j_m}^{(s+1)}\) assigned to the basic variables \(z_{j_1}, \ldots, z_{j_m}\) of \(P^{(s)}\) so that \(\hat z^{(s+1)}\) is feasible, that is, \(b = A\hat z^{(s+1)}\) and \(\hat z^{(s+1)} \ge 0\).

Since \(\hat z_h^{(s+1)} = \hat z_h^{(s)} = 0\) for all \(h \notin B^{(s)} \cup \{j\}\), we have \(b = A\hat z^{(s+1)}\) if and only if every basic variable \(z_{j_i}\) satisfies

\[\hat z_{j_i}^{(s+1)} = b_i - \sum_{h \notin B^{(s)}} a_{ih} \hat z_h^{(s+1)} = b_i - a_{ij}\hat z_j^{(s+1)}.\]

If \(a_{ij} \le 0\), we obtain

\[\hat z_{j_i}^{(s+1)} = b_i - a_{ij}\hat z_j^{(s+1)} \ge b_i = \hat z_{j_i}^{(s)} \ge 0\]

because \(\hat z_j^{(s+1)} \ge 0.\) In other words, \(\hat z_{j_i}^{(s+1)} \ge 0\) no matter the (non-negative) value \(\hat z_j^{(s+1)}\) we assign to \(z_j\): the non-negativity constraint of the \(i\)th basic variable \(z_{j_i}\) imposes no limit on \(\hat z_j^{(s+1)}\).

If \(a_{ij} > 0\), on the other hand, then

\[\hat z_{j_i}^{(s+1)} = b_i - a_{ij}\hat z_j^{(s+1)} \ge 0\]

only as long as

\[\hat z_j^{(s+1)} \le \frac{b_i}{a_{ij}}.\]

Since we need to ensure that all basic variables remain non-negative, we must therefore choose \(\hat z_j^{(s+1)}\) so that \(\hat z_j^{(s+1)} \le \frac{b_i}{a_{ij}}\) for all \(1 \le i \le m\) with \(a_{ij} > 0\).

This gives the following strategy for choosing \(\hat z^{(s+1)}\):

• For each constraint \(b_i = \sum_{h=1}^{m+n} a_{ih}z_h\), set

  \[\Delta_i = \begin{cases} \frac{b_i}{a_{ij}} & \text{if } a_{ij} > 0\\ \infty & \text{if } a_{ij} \le 0. \end{cases}\]

  \(\Delta_i\) is the upper bound on \(\hat z_j^{(s+1)}\) imposed by this constraint.

• Let \(k\) be any index such that

  \[\Delta_k = \min \{ \Delta_1, \ldots, \Delta_m \}.\]

  The \(k\)th constraint imposes the tightest upper bound on \(\hat z_j^{(s+1)}\).

• If \(\Delta_k = \infty\), then there is no constraint that limits how large we can choose \(\hat z_j^{(s+1)}\): \(\hat z_j^{(s+1)} = \infty\) is a feasible choice. The corresponding objective function value is \(c_j\hat z_j^{(s+1)} + d = \infty\), so the LP is unbounded in this case. The algorithm exits and reports this fact.

• If \(\Delta_k \ne \infty\), then set

  \[\hat z_h^{(s+1)} = \begin{cases} \Delta_k & \text{if } h = j\\ 0 & \text{if } h \notin B^{(s)} \cup \{j\}\\ b_i - a_{ij}\Delta_k & \text{if } h = j_i \in B^{(s)}. \end{cases}\]

  Since \(\hat z_j^{(s+1)} = \Delta_k\) and \(\hat z_h^{(s+1)} = 0\) for all \(h \notin B^{(s)} \cup \{j\}\), the solution \(\hat z^{(s+1)}\) satisfies \(b = A\hat z^{(s+1)}\).

  To verify that \(\hat z^{(s+1)} \ge 0\), observe that for all \(1 \le i \le m\), either \(\Delta_i = \infty\) or \(\Delta_i = \frac{b_i}{a_{ij}}\). In the former case, \(\Delta_i \ge 0\). The latter holds only if \(a_{ij} > 0\). Since \(\hat z^{(s)}\) is feasible, we have \(b_i = \hat z_{j_i}^{(s)} \ge 0\). Thus, once again, \(\Delta_i = \frac{b_i}{a_{ij}} \ge 0\). Since \(\Delta_k = \min \{ \Delta_1, \ldots, \Delta_m \}\), this implies that \(\hat z_j^{(s+1)} = \Delta_k \ge 0\), that is, \(\hat z_h^{(s+1)} \ge 0\) for all \(h \notin B^{(s)}\).

  For \(1 \le i \le m\), we have

  \[\hat z_{j_i}^{(s+1)} = b_i - a_{ij} \Delta_k.\]

  Since \(\Delta_k \ge 0\), we have

  \[b_i - a_{ij}\Delta_k \ge b_i = \hat z_{j_i}^{(s)} \ge 0\]

  if \(a_{ij} \le 0\).

  If \(a_{ij} > 0\), then \(\Delta_k \le \Delta_i = \frac{b_i}{a_{ij}}\) and

  \[b_i - a_{ij}\Delta_k \ge b_i - a_{ij}\Delta_i = b_i - a_{ij} \frac{b_i}{a_{ij}} = 0.\]

  In both cases, \(\hat z_{j_i}^{(s+1)} \ge 0\). Thus, \(\hat z^{(s+1)}\) is a feasible solution of \(P^{(s)}\).

  The objective function value of \(\hat z^{(s)}\) is \(d\) because \(\hat z_h^{(s)} = 0\) for all \(h \notin B^{(s)}\). The objective function value of \(\hat z^{(s+1)}\) is

  \[c_j\hat z_j^{(s+1)} + d = c_j\Delta_k + d \ge d\]

  because both \(c_j > 0\) and \(\Delta_k \ge 0\). This proves that the objective function value of \(\hat z^{(s+1)}\) is no less than the objective function value of \(\hat z^{(s)}\). It is strictly greater whenever \(\Delta_k > 0\).