As we saw in the simplex post, at each iteration it is considered a basis in a form of a matrix \(A_B.\) This matrix is constructed with a subset of linear independent columns of the matrix \(A.\) The construction of this matrix arises two questions:

1. How can we choose linearly independent columns of \(A\) to form the matrix \(A_B\)?
2. How can we assure that the vector \(x_B=A_B^{-1}b\) has nonnegative coordinates?

The simplex method requires the linear program (LP) to be in the standard form: a minimization problem with all constraints as equations, nonnegative decision variables, and nonnegative right-hand-side. To transform the LP above into the standard form we add slack variables \(x_3\) and \(x_4,\) to obtain the following: \[ \begin{array}{rrl} \min & 2x_1 + x_2 + 0x_3 +0x_4 \\ \text{s.t.} & x_1 - x_2 + x_3 & = 1 \\ & x_1 + 2x_2 + x_4 & = 4 \\ & x_1,x_2, x_3, x_4 &\geq 0. \end{array} \]

In this case, \[ A= \begin{bmatrix} 1 & -1 & 1 & 0 \\ 1 & 2 & 0 & 1 \end{bmatrix}, \quad b= \begin{bmatrix} 1 \\ 4 \end{bmatrix}. \] Notice that the rank of \(A\) is two, in other words, \(A\) has full rank, which is a necessary condition to construct the matrix \(A_B.\) Also, since \(A\) has four columns, we have six possible ways to choose the two columns that will compose the matrix \(A_B.\)

While we could analyze each of the six combinations for such a small matrix \(A,\) this approach would easily become intractable for larger matrices. Also, some of those combinations might not even meet the requirements to compose a basis. For example, some combinations might yield a matrix \(A_B\) with linearly dependent columns or an infeasible solution (with negative coordinates). To overcome this issue, and at the same time answer the two previous questions, we consider a new problem: Since the rank of \(A\) is two, we add two new variables: \(x_5\) and \(x_6\), and set the cost vector for this new problem as \(c^T=(0, 0, 0, 0, 1, 1).\) The result is the following LP: \[ \begin{array}{rrl} \min & 0x_1 + 0x_2 + 0x_3 + 0x_4 + x_5 + x_6 \\ \text{s.t.} & x_1 - x_2 + x_3 + x_5 & = 1 \\ & x_1 + 2x_2 + x_4 + x_6 & = 4 \\ & x_1,x_2, x_3, x_4, x_5, x_6 &\geq 0. \end{array} \] The objective is to minimize \(x_5\) and \(x_6\) because any feasible solution to this LP with \(x_5=0\) and \(x_6=0\) is a feasible solution to the original problem.

The coefficients and right-hand-side of the new LP in matrix form are as follows: \[ A= \begin{bmatrix} 1 & -1 & 1 & 0 & 1 & 0\\ 1 & 2 & 0 & 1 & 0 & 1 \end{bmatrix}, \quad b= \begin{bmatrix} 1 \\ 4 \end{bmatrix}. \] This new problem is known as Phase I, and it has an obvious basis \(A_B = [A^5 \; A^6],\) which is the identity matrix. With this choice of basis, the corresponding solution will be \(x= (0, 0, 0, 0, 1, 4).\) Notice that this solution will always be feasible by construction because the right-hand-side \(b\) is always nonnegative when the LP is in standard form.

At this point we have the following: \[ \begin{array}{rl} x_N & = (0, 0, 0, 0) \\ x_B & = (4, 2) \\ c_N^T & = (0, 0, 0, 0) \\ c_B^T & = (1, 1). \end{array} \] If we evaluate the expression for the reduced cost we obtain: \[-(c_N^T-c_B^TA_B^{-1}A_N) = -(2, 1, 1, 1).\] All the entries of this vector are negative, which implies that if we increase any of the non-basic variables, then we will get a reduction in the value of the cost function. We can pick any of them. Let's pick the first entry, which corresponds to the non-basic variable \(x_1.\) This will be the entering variable to the basis.

To choose the leaving variable, we consider the expression: \[x_B= A_B^{-1}b-A_B^{-1}A^1x_1 = \begin{bmatrix} 1\\ 4 \end{bmatrix} - \begin{bmatrix} 1 \\ 1 \end{bmatrix}x_1. \] Notice that both entries of the vector \(A_B^{-1}A^1\) are positive. Now, if we increase the value of \(x_1\) from zero, which entry will become zero first? The answer to this question will tell us the leaving variable. In this case, if we increase \(x_1\) up to 1, we obtain: \[x_B = \begin{bmatrix} 0 \\ 3 \end{bmatrix}.\] The first entry become zero first with the minimum value of \(x_1,\) this entry corresponds to the variable \(x_5,\) so this is the leaving variable. This step is actually done with the so-called ratio test, which is to take the minimum of the ratios: \[\dfrac{(A_B^{-1}b)_i}{(A_B^{-1}A^1)_i}, \quad \mbox{with }(A_B^{-1}A^1)_i>0.\]

After this first iteration of the simplex algorithm, we have moved from the basic feasible solution \((0, 0, 0, 0, 1, 4)\) to the basic feasible solution \((1, 0, 0, 0, 3).\)

After repeating this process two more iterations, we reach the solution of the Phase I, which is \(x=(2, 1, 0, 0, 0, 0)\). This corresponds to the feasible point\((2, 1, 0, 0)\) in the original problem, indicating that a basis to start the Simplex Algorithm on the original problem, namely the Phase II, is \(A_B = [A^1 \; A^2].\)

Let's address these questions with an example: \[ \begin{array}{rrl} \min & 2x_1 + x_2 \\ \text{s.t}. & x_1 - x_2 & \leq 1 \\ & x_1 + 2x_2& \leq 4 \\ & x_1,x_2 &\geq 0. \end{array} \]