In red we highlighted the pivot element that we will explain below.

In this Simplex Tableau, if there is an mxm identity submatrix of A, the vector X

b
is an extreme point that allows us to begin the iterations of the algorithm.

Because such X

b is a solution it do contains the variables at the basis.
The vector C

B, is built with the elements of vector C at the the same basis.
For them we calculate the \( z_{j} - c_{j} \) elements. Remember that

\( z_{j} = X_{b}a_{j} \) or \(z_{j} = C^t_{B}B^{-1}a_{j}\).

And B is in this step an identity matrix as supossed at the begininig.

Once calculated, we check if optimality criterion hold, ie we test

\( c_{j} - z_{j} \geq 0, \; \forall j \)

In case of non-compliance, we take the less s index of j's that makes

\( s = min \{ k: \,\ c_{k} - z_{k} < 0 \} \)

In other words we take the minimum of negative from \( c_{k} - z_{k} \).

Now with this index s, we find the called

** pivot element **.
To do this divide each coordinate i of the vector X

b by the coordinate column
vector y

is and calculate the minimal of positive as follows

\( r = min \{ i : \frac {x_i}{y_{is}}, y_{is} \geqslant 0, x = B^{-1}b \} \)

If the previous minimum do not exist because all the \( \frac {x_i}{y_{is}} \) are negative, we are in the case of
unbounded solution as show in the

Simplex algotirhm section.

Otherwise we can find an index that minimizes y

ik. This is the number called Pivot Element

### Pivot Element of the Simplex Algorithm

It is called the Pivot element of Simplex Algoritm Tableau to an element of yij
the constraints matrix wich indexes s and r that meet:

\( s = min \{ k: \,\ c_{k} - z_{k} < 0 \} \)

\( r = min \{ i : \frac {x_i}{y_{is}}, y_{is} \geqslant 0, x = B^{-1}b \} \)

In this case, we have s wich is the new index of x entering into the basis and r, is the index of X

b leaving of the basis.

Now recalculate again the tableau in this new basis, for this we calculate the whole matrix A as follows:

### Constraints matrix at new basis calculation

\(\begin{cases} y'_{ij} = \displaystyle y_{ij}-y_{rj}\frac{y_{is}}{y_{rs}}& \text{ si } i \neq r \\ \displaystyle y'_{rj} = \frac{y_{rj}}{y_{rs}}& \text{ si } i = r \end{cases} \)
This is the basis of the algorithm to invert the constraints matrix .

To sum up: the pivot row new coefficients are calculated just by dividing by the pivot element, and for the other rows
are calculated by subtracting the y

i coefficient in the pivot row,
also multiplied by the coefficient corresponding to the column and then divided by the pivot element.

Calculations are a quite bit more difficult explain than to understand, we will see at the end of this
section an example showing how algorithm works in practicle.
You can can go to see it if directly you want to, but for now let us dealing with the following problems:

**1)** How to find a first solution to starts the iterations? This is equivalent to find any identity mxm submatrix of A.

**2)** In the event that the problem P contains inequality constraints. How to perform the operations?

**3)** Some of the variables may not be restricted in sign. How to operate in this case?

**4)** We have inconsistency or redundancy in some operation. What to do in this case?

**5)** What if we want to maximize instead of minimize?

**Answers to these questions**
**1)**The idea is to find a submatrix B of A such that, by rearranging the columns if necessary, B is a mxm identity matrix,
in this case the b vector, is a solution to our problem just by taking as vectors those whose columns make up the matrix B.

If it is not possible to find an identity matrix B within A then we use the

two-phase method.

**2)** We would have for any row i of matrix A any inequality constraint:

\( \sum_{j=1}^{n}a_{ij}x_j \leq b_i \)

At this case we define a positive slack variable such us

\( \sum_{j=1}^{n}a_{ij}x_j + s_i = b_i , \, s_i \geq 0 \)

And if we have for a row i

\( \sum_{j=1}^{n}a_{ij}x_j \geq b_i \)

we define the positive slack variable such as

\( \sum_{j=1}^{n}a_{ij}x_j - s_i = b_i , \, s_i \geq 0 \)

therefore our inequalities problem leads to an equalities one.

**3)** If for any component i, the variable is not restricted in sign, then we can decompose it as follows

\( x_i = x_{i1} - x_{i2}, \, x_{i1},x_{i2} \geq 0 \)

this is: decompose the i variable into two positive variables.

**4)** If we have uncompatibility, we can try to reformulate the problem so that such constraints become consistent.
Uncompatible constraits is the same as saying that our problem can not be resolved.

In redundancy case. we can simply discard the redundant constraints.

**5)** If we have as an objective function

\( max\sum_{j=1}^{n}C_j x_j \)

We can reformulate the problem by change the sign of objective function, like this:

\( min\sum_{j=1}^{n}C_j (-x_j) \)

Thus, we have the rule that "maximize one variable is the same as that variable change signs and minimize that variable".

**Example**

\( max(-x_1+3x_2) \\ \text{ subject to} \\ \left\{ \begin{matrix} -x_1+2x_2 \leq & 6 \\ x_1+x_2 \leq & 5 \\ 2x_1+2x_2 \leq & 10 & \end{matrix}\right. \).

Constraints 2 and 3, both are the same, we remove one of them, so we

\( max(-x_1+3x_2) \\ \text{ subject to} \\ \left\{\begin{matrix} -x_1+2x_2 \leq & 6\\
x_1+x_2 \leq & 5 & \end{matrix}\right. \).

We apply the point

**5)**, ie 'maximize a variable is the same as the sign change of variable and minimize the variable'.

\( min(x_1-3x_2) \\ \text{ subject to} \\ \left\{\begin{matrix} -x_1+2x_2 \leq & 6\\
x_1+x_2 \leq & 5 & \end{matrix}\right. \).

We apply the point

**2)** to obtain equality constraits

\( min(x_1-3x_2+0x_3+0x_4) \\ \text{ subject to} \\ \left\{\begin{matrix} -x_1+2x_2+x_3 = & 6\\
x_1+x_2 + x_4 = & 5 & \end{matrix}\right. \).

Now we have solved the point

**1)**,because we already have an identity submatrix of A, the variables concerning to x3, x4 variables

We build the Simplex Tableau and solve the problem

We take the minimum of the negative from z

j - c

j = -3, it occurs at x

2, so entering variable is 2, s=2

Now we calculate the index leaving from the basis, to this we divide each one element of Xb

k for the corresponding k-column at matrix, is minimum from \( \frac{6}{3} = 3\) and \( \frac{5}{1} = 1\) values. We take the minimum, so the index leaving r is 3 and pivot element is

**2**
Now wwe can do an iteration fo Simplex algorithm, por example for the x

4 row

\( \begin{matrix} \frac{3}{2}&=1-(-1)*\frac{1}{2}=1+\frac{1}{2} & =\frac{3}{2}\\ 0&=1-2*\frac{1}{2}=1-1 & =0\\
-\frac{1}{2}&=0-1*\frac{1}{2}&=-\frac{1}{2}\\ 1 &=1-1*\frac{0}{1}= & =1 \end{matrix} \)

And the same for Xb elements: \( 2 = 5 - 1 * \frac{6}{2} = 5 - 3 \)

Let's see how we have performed these calculations:

**1)** For the pivot row, we have simply divided each coefficient by the Pivot element.

**2)** For the other rows we have subtracted for each one the coefficient of Pivot column multiplied by the coefficient at the Pivot row and divided by the Pivot, for example

The entire iterations is

Next iteration: the entering index is 1 and leaving index is 4, so we have

Now optimallity criterion holds because

z

j - c

j > 0, ∀j

So we have a finite optimal solution:

\( \begin{matrix} x_1=\frac{4}{3}\\ x_2=\frac{11}{3} \end{matrix} \)

Wich gives a value for objective function:

\( s = -\frac{4}{3} + \frac{33}{3} = \frac{29}{3} \)

To sum up: the simplex algorithm takes one extreme point and forwards to another by pivoting the constraint matrix using a change of basis
to calculate the new constraint coefficients matrix.