We first consider the case where some \(x_j\) is allowed to be negative, which we denote as \(\ec{x_j}\text{.}\)
\(x_1\)
\(x_2\)
\(\cdots\)
\(x_{j-1}\)
\(\ec{x_j}\)
\(x_{j+1}\)
\(\cdots\)
\(x_m\)
\(-1\)
\(a_{11}\)
\(a_{12}\)
\(\cdots\)
\(a_{1(j-1)}\)
\(a_{1j}\)
\(a_{1(j+1)}\)
\(\cdots\)
\(a_{1m}\)
\(b_1\)
\(=-t_1\)
\(a_{21}\)
\(a_{22}\)
\(\cdots\)
\(a_{2(j-1)}\)
\(a_{2j}\)
\(a_{2(j+1)}\)
\(\cdots\)
\(a_{2m}\)
\(b_2\)
\(=-t_2\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(a_{i1}\)
\(a_{i2}\)
\(\cdots\)
\(a_{i(j-1)}\)
\(a_{ij}\)
\(a_{i(j+1)}\)
\(\cdots\)
\(a_{im}\)
\(b_i\)
\(=-t_i\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(a_{n1}\)
\(a_{n2}\)
\(\cdots\)
\(a_{n(j-1)}\)
\(a_{nj}\)
\(a_{n(j+1)}\)
\(\cdots\)
\(a_{nm}\)
\(b_n\)
\(=-t_n\)
\(c_1\)
\(c_2\)
\(\cdots\)
\(c_{j-1}\)
\(c_j\)
\(c_{j+1}\)
\(\cdots\)
\(c_m\)
\(d\)
Note that should we pivot on \(a_{ij}^*\)
\(x_1\)
\(x_2\)
\(\cdots\)
\(x_{j-1}\)
\(t_i\)
\(x_{j+1}\)
\(\cdots\)
\(x_m\)
\(-1\)
\(a_{11}\)
\(a_{12}\)
\(\cdots\)
\(a_{1(j-1)}\)
\(a_{1j}\)
\(a_{1(j+1)}\)
\(\cdots\)
\(a_{1m}\)
\(b_1\)
\(=-t_1\)
\(a_{21}\)
\(a_{22}\)
\(\cdots\)
\(a_{2(j-1)}\)
\(a_{2j}\)
\(a_{2(j+1)}\)
\(\cdots\)
\(a_{2m}\)
\(b_2\)
\(=-t_2\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(a_{i1}\)
\(a_{i2}\)
\(\cdots\)
\(a_{i(j-1)}\)
\(a_{ij}\)
\(a_{i(j+1)}\)
\(\cdots\)
\(a_{im}\)
\(b_i\)
\(=-\ec{x_j}\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(a_{n1}\)
\(a_{n2}\)
\(\cdots\)
\(a_{n(j-1)}\)
\(a_{nj}\)
\(a_{n(j+1)}\)
\(\cdots\)
\(a_{nm}\)
\(b_n\)
\(=-t_n\)
\(c_1\)
\(c_2\)
\(\cdots\)
\(c_{j-1}\)
\(c_j\)
\(c_{j+1}\)
\(\cdots\)
\(c_m\)
\(d\)
that having a slack variable that can be negative serves no purpose, since the point of the non-negativity constraint is to reinforce the inequality. Also note that the hyperplane \(x_j=0\) also plays no role in this problem, since it does not serve as a bounding hyperplane. Thus, we may simply delete this row (after recording the equality) as this equality will have no bearing on future steps or the final solution.
\(x_1\)
\(x_2\)
\(\cdots\)
\(x_{j-1}\)
\(t_i\)
\(x_{j+1}\)
\(\cdots\)
\(x_m\)
\(-1\)
\(a_{11}\)
\(a_{12}\)
\(\cdots\)
\(a_{1(j-1)}\)
\(a_{1j}\)
\(a_{1(j+1)}\)
\(\cdots\)
\(a_{1m}\)
\(b_1\)
\(=-t_1\)
\(a_{21}\)
\(a_{22}\)
\(\cdots\)
\(a_{2(j-1)}\)
\(a_{2j}\)
\(a_{2(j+1)}\)
\(\cdots\)
\(a_{2m}\)
\(b_2\)
\(=-t_2\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(a_{n1}\)
\(a_{n2}\)
\(\cdots\)
\(a_{n(j-1)}\)
\(a_{nj}\)
\(a_{n(j+1)}\)
\(\cdots\)
\(a_{nm}\)
\(b_n\)
\(=-t_n\)
\(c_1\)
\(c_2\)
\(\cdots\)
\(c_{j-1}\)
\(c_j\)
\(c_{j+1}\)
\(\cdots\)
\(c_m\)
\(d\)
Figure3.4.1.A summary of unconstrained variables.
Next we consider the case where the feasible region is bound by an equality, rather than an inequality. In such a case, the slack variable \(t_i\) must be zero.
\(x_1\)
\(x_2\)
\(\cdots\)
\(x_{j-1}\)
\(x_j\)
\(x_{j+1}\)
\(\cdots\)
\(x_m\)
\(-1\)
\(a_{11}\)
\(a_{12}\)
\(\cdots\)
\(a_{1(j-1)}\)
\(a_{1j}\)
\(a_{1(j+1)}\)
\(\cdots\)
\(a_{1m}\)
\(b_1\)
\(=-t_1\)
\(a_{21}\)
\(a_{22}\)
\(\cdots\)
\(a_{2(j-1)}\)
\(a_{2j}\)
\(a_{2(j+1)}\)
\(\cdots\)
\(a_{2m}\)
\(b_2\)
\(=-t_2\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(a_{i1}\)
\(a_{i2}\)
\(\cdots\)
\(a_{i(j-1)}\)
\(a_{ij}\)
\(a_{i(j+1)}\)
\(\cdots\)
\(a_{im}\)
\(b_i\)
\(=-0\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(a_{n1}\)
\(a_{n2}\)
\(\cdots\)
\(a_{n(j-1)}\)
\(a_{nj}\)
\(a_{n(j+1)}\)
\(\cdots\)
\(a_{nm}\)
\(b_n\)
\(=-t_n\)
\(c_1\)
\(c_2\)
\(\cdots\)
\(c_{j-1}\)
\(c_j\)
\(c_{j+1}\)
\(\cdots\)
\(c_m\)
\(d\)
Now in this case, if we pivot on \(a_{ij}^*\) entry, we obtain:
\(x_1\)
\(x_2\)
\(\cdots\)
\(x_{j-1}\)
\(0\)
\(x_{j+1}\)
\(\cdots\)
\(x_m\)
\(-1\)
\(a_{11}\)
\(a_{12}\)
\(\cdots\)
\(a_{1(j-1)}\)
\(a_{1j}\)
\(a_{1(j+1)}\)
\(\cdots\)
\(a_{1m}\)
\(b_1\)
\(=-t_1\)
\(a_{21}\)
\(a_{22}\)
\(\cdots\)
\(a_{2(j-1)}\)
\(a_{2j}\)
\(a_{2(j+1)}\)
\(\cdots\)
\(a_{2m}\)
\(b_2\)
\(=-t_2\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(a_{i1}\)
\(a_{i2}\)
\(\cdots\)
\(a_{i(j-1)}\)
\(a_{ij}\)
\(a_{i(j+1)}\)
\(\cdots\)
\(a_{im}\)
\(b_i\)
\(=-x_j\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(a_{n1}\)
\(a_{n2}\)
\(\cdots\)
\(a_{n(j-1)}\)
\(a_{nj}\)
\(a_{n(j+1)}\)
\(\cdots\)
\(a_{nm}\)
\(b_n\)
\(=-t_n\)
\(c_1\)
\(c_2\)
\(\cdots\)
\(c_{j-1}\)
\(c_j\)
\(c_{j+1}\)
\(\cdots\)
\(c_m\)
\(d\)
Note that what the coefficients \(a_{ij}, c_j\) are, they are coefficients of the “variable” \(0\) and are thus irrelevant. Moreover, we cannot pivot away from this plane, since our feasible region is contained completely within the plane. Thus we may delete this column.
