2.6.2. Standard Form

The Simplex Algorithm expects its input in standard form.

An LP is in standard form if it has \(m + n\) variables \(x_1, \ldots, x_n, y_1, \ldots, y_m\) and is of the form:¹

\[\begin{gathered} \text{Maximize } \sum_{j=1}^n c_jx_j + d\\ \begin{aligned} \text{s.t. } y_i &= b_i - \sum_{j=1}^n a_{ij} x_j && \forall 1 \le i \le m\\ x_j &\ge 0 && \forall 1 \le j \le n\\ y_i &\ge 0 && \forall 1 \le i \le m \end{aligned} \end{gathered}\]

The variables \(y_1, \ldots, y_m\) are called basic variables (sometimes also slack variables). The variables \(x_1, \ldots, x_n\) are called non-basic variables.

Note that

• Only non-basic variables appear in the objective function. An alternative view, which we will take later is that all basic variables appear in the objective function with coefficient \(0\).

• There is a one-to-one correspondence between the equality constraints in the LP and the basic variables: The \(i\)th basic variable \(y_i\) occurs only in the \(i\)th equality constraint, with coefficient \(1\). Again, another way to say this is that the \(i\)th basic variable \(y_i\) has coefficient \(1\) in the \(i\)th equality constraint and coefficient \(0\) everywhere else.

If we collect the basic variables \(y_1, \ldots, y_m\) in a column vector \(y = (y_1, \ldots, y_m)^T\), the constant terms \(b_1, \ldots, b_m\) in a column vector \(b = (b_1, \ldots, b_m)^T\), the non-basic variables \(x_1, \ldots, x_n\) in a column vector \(x = (x_1, \ldots, x_n)^T\), the objective function coefficients \(c_1, \ldots, c_n\) in a row vector \(c = (c_1, \ldots, c_n)\), and the coefficients \(a_{ij}\) in a matrix \(A\), then we obtain a compact formulation of standard form similar to the compact formulation of canonical form (2.18):

\[\begin{gathered} \text{Maximize } cx + d\\ \begin{aligned} \text{s.t. } y &= b - Ax\\ x &\ge 0\\ y &\ge 0, \end{aligned} \end{gathered}\tag{2.19}\]

Once again, \(0\) is used to denote appropriate column vectors all of whose components are \(0\).

Since we want to use the Simplex Algorithm to solve arbitrary LPs but the Simplex Algorithm expects its input in standard form, we need to answer the question whether we can convert any LP into an equivalent one in standard form. Lemma 2.11 shows that we can convert any LP into an equivalent one in canonical form. The next lemma shows that any such LP in canonical form can be converted into an equivalent one in standard form. By chaining these two transformations together, we obtain a transformation of an arbitrary LP into an equivalent one in standard form.

Lemma 2.12: Every linear program in canonical form can be transformed into an equivalent linear program in standard form.

Proof: Consider the following two LPs:

\[\begin{gathered} \text{Maximize } \sum_{j=1}^n c_jx_j\\ \begin{aligned} \text{s.t. } \sum_{j=1}^n a_{ij} x_j &\le b_i && \forall 1 \le i \le m\\ x_j &\ge 0 && \forall 1 \le j \le n \end{aligned} \end{gathered}\tag{2.20}\]

\[\begin{gathered} \text{Maximize } \sum_{j=1}^n c_jx_j\\ \begin{aligned} \text{s.t. } y_i &= b_i - \sum_{j=1}^n a_{ij} x_j && \forall 1 \le i \le m\\ x_j &\ge 0 && \forall 1 \le j \le n\\ y_i &\ge 0 && \forall 1 \le i \le m \end{aligned} \end{gathered}\tag{2.21}\]

(2.20) is in canonical form. (2.21) is in standard form. We claim that they are equivalent.

Any feasible solution \(\hat x = \bigl(\hat x_1, \ldots, \hat x_n\bigr)\) of (2.20) can be extended to a feasible solution \(\bigl(\hat x, \hat y\bigr)\) of (2.21) by setting \(\hat y_i = b_i - \sum_{j=1}^n a_{ij}\hat x_j\) for all \(1 \le i \le m\). This explicitly ensures that \(\bigl(\hat x, \hat y\bigr)\) satisfies all equality constraints of (2.21). It also ensures that \(\hat x_j \ge 0\) for all \(1 \le j \le n\) and \(\hat y_i \ge 0\) for all \(1 \le i \le m\) because \(\hat x\) is a feasible solution of (2.20) and, therefore, \(\sum_{j=1}^n a_{ij}\hat x_j \le b_i\). Thus, \(\bigl(\hat x, \hat y\bigr)\) is a feasible solution of (2.21). Its objective function value in (2.21) is the same as the objective function value of \(\hat x\) in (2.20), because (2.20) and (2.21) have the same objective function.

Now consider any feasible solution \(\bigl(\hat x, \hat y\bigr)\) of (2.21). Then \(\hat x\) is a feasible solution of (2.20): Indeed, we have \(\hat x_j \ge 0\) for all \(1 \le j \le n\) because \(\bigl(\hat x, \hat y\bigr)\) is a feasible solution of (2.21). We also have \(\hat y_i = b_i - \sum_{j=1}^n a_{ij}x_j\) and \(\hat y_i \ge 0\) for all \(1 \le i \le m\). Thus, \(\sum_{j=1}^n a_{ij}x_j \le b_i\) for all \(1 \le i \le m\). Once again, since (2.20) and (2.21) have the same objective function, \(\bigl(\hat x, \hat y\bigr)\) and \(\hat x\) achieve the same objective function values as solutions of (2.21) and (2.20), respectively.

Since every feasible solution of (2.20) has a corresponding feasible solution of (2.21) with the same objective function value and vice versa, it follows that the feasible solution of (2.21) associated with an optimal solution of (2.20) is an optimal solution of (2.17) and vice versa. Thus, (2.20) and (2.21) are equivalent. ▨

In Section 2.6.1, we gave an example of converting an arbitrary LP into an equivalent one in canonical form. Next we continue this example by converting the LP in canonical form into an equivalent one in standard form. The LP in canonical form we obtained was

\[\begin{gathered} \text{Maximize } \sum_{u \in V} b_up_u' - \sum_{u \in V} b_up_u'' - \sum_{(u,v) \in E_b} c_{u,v}s_{u,v}\\ \begin{aligned} \text{s.t. } p_u' - p_u'' - p_v' + p_v'' - s_{u,v} &\le q_{u,v} && \forall (u,v) \in E_b\\ p_u' - p_u'' - p_v' + p_v'' &\le -q_{u,v} && \forall (u,v) \in E_u\\ p_v' &\ge 0 && \forall v \in V\\ p_v'' &\ge 0 && \forall v \in V\\ s_{u,v} &\ge 0 && \forall (u,v) \in E_b. \end{aligned} \end{gathered}\tag{2.22}\]

To convert this LP into standard form, we introduce a slack variable \(y_{u,v}\) for every edge \((u, v) \in E\) and rewrite the upper bound constraints in (2.22) as equality constraints:

\[\begin{gathered} \text{Maximize } \sum_{u \in V} b_up_u' - \sum_{u \in V} b_up_u'' - \sum_{(u,v) \in E_b} c_{u,v}s_{u,v}\\ \begin{aligned} \text{s.t. } y_{u,v} &= q_{u,v} - p_u' + p_u'' + p_v' - p_v'' + s_{u,v} && \forall (u,v) \in E_b\\ y_{u,v} &= -q_{u,v} - p_u' + p_u'' + p_v' - p_v'' && \forall (u,v) \in E_u\\ p_v' &\ge 0 && \forall v \in V\\ p_v'' &\ge 0 && \forall v \in V\\ s_{u,v} &\ge 0 && \forall (u,v) \in E_b\\ y_{u,v} &\ge 0 && \forall (u,v) \in E \end{aligned} \end{gathered}\]

The following alternative representation of standard form will be more useful for manipulating LPs in the Simplex Algorithm and in many other circumstances. We can clearly write (2.19) as

\[\begin{gathered} \text{Maximize } cx + d\\ \begin{aligned} \text{s.t. } b &= y + Ax\\ x &\ge 0\\ y &\ge 0, \end{aligned} \end{gathered}\]

which is the same as

\[\begin{gathered} \text{Maximize } 0y + cx + d\\ \begin{aligned} \text{s.t. } b &= Iy + Ax\\ x &\ge 0\\ y &\ge 0, \end{aligned} \end{gathered}\tag{2.23}\]

where \(I\) is the \(m \times m\) identity matrix and \(0\) is the \(m\)-element \(0\)-vector.

Now let \(c'\) be the concatenation of \(0\) and \(c\), \[c' = (\underbrace{0, \ldots, 0}_{m\ \text{times}}, c_1, \ldots, c_n),\]

let

\[A' = [I|A] = \left( \begin{matrix} 1 & 0 & \cdots & 0\\ 0 & 1 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & 1\\ \end{matrix} \,\left|\, \begin{matrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\ a_{2,1} & a_{2,2} & \cdots & a_{2,n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{matrix} \right. \right),\]

and let

\[z = \begin{pmatrix} z_1\\ \vdots\\ z_{m+n} \end{pmatrix} = \begin{pmatrix} y_1\\ \vdots\\ y_m\\ x_1\\ \vdots\\ x_n \end{pmatrix}.\]

Then (2.23) becomes

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

An LP written in this form is in standard form if it is equipped with a basis \(B = \{ j_1, \ldots, j_m \} \subseteq \{ 1, \ldots, m + n \}\)² of \(m\) indices such that for all \(1 \le i \le m\), \(c_{j_i} = 0\), \(a_{ij_i} = 1\), and \(a_{ij} = 0\) for all \(1 \le j \le m\) with \(j \ne j_i\). The variables \(z_{j_1}, \ldots, z_{j_m}\) are the basic variables of the LP. To clearly associate each index \(j_i \in B\) with the \(i\)th equality constraint in (2.24), we write \(B\) as a vector \((j_1, \ldots, j_m)\), not as a set, but we still use standard set notation such as \(h \in B\) to indicate that an index \(h\) occurs in this vector. The above translation of (2.23) into (2.24) together with the basis \(B = (1, \ldots, m)\) clearly satisfies these conditions.