The Pivot element and the Simplex method calculations

The basis of the simplex algorithm is that there is not need to calculate the inverse of the matrix B to obtain the extreme points of feasible region (Remember: B is an square submatrix of A with rank m).

Instead of this, a series of calculations lead us to an element of matrix A called "Pivot element" wich is used to iterate over the extreme point set, until one of these four cases holds:

As it was said, to perform the calculations in practice there is not need to invert the B matrix (remember that B is a square submatrix A of mxm with rank m). Instead of it, we create a table, called Tabeau for each iteration in which the calculations are much easier to do than to explain. Lets go...

The Simplex Tableau is built as follows:

Base

x1

...

xi

...

xm

Xb

β1

...

βi

...

βm

Cb

Cb1

...

Cbi

...

Cbm

a1	...	ak	...	an
y11	...	y1k	...	y1n
...	...	...	...	...
yi1	...	yik	...	yin
...	...	...	...	...
ym1	...	ymk	...	ymn
z1-c1	...	zk-ck	...	zn-cn

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 Xb is an extreme point that allows us to begin the iterations of the algorithm.

Because such Xb is a solution it do contains the variables at the basis. The vector CB, 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 Xb by the coordinate column vector yis 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 yik. This is the number called Pivot Element

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

Now recalculate again the tableau in this new basis, for this we calculate the whole matrix A as follows:
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 yi 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 zj - cj = -3, it occurs at x2, so entering variable is 2, s=2

Now we calculate the index leaving from the basis, to this we divide each one element of Xbk 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 x4 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

zj - cj > 0, ∀j

So we have a finite optimal solution: 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.