The basis of the simplex algorithm is that there is not need to invert matrix B to calculate the

extreme points
of feasible region (

**Remember**: B is an square submatrixz of A with rank m).

Instead, a series of calculations lead to an element of matrix A called "Pivot element" and it is used to pass through other calculations, from one

extreme point to
another one, testing each of them the optimality criterion, until one of these four cases holds .

### Simplex Algorithm and two-phase Method possible Outputs

**1)** The optimality criterion is fulfilled in one extreme point, in this case finite optimal solution holds.

Example here
**2)** The optimality criterion holds, but there are infinite points also holds, this is the case with infinite solutions.

Example here
**3)** Unbounded Solution: when the objective function can grow whatever we want within the feasible region.

Example here
**4)** We can not continue iterating and not reached the criterion of optimality. At this case restrictions are inconsistent and the problem has no solution

Example here.

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

The Simplex Tableau is constructed as follows:

y11 | ... |
y1k | ... |
y1n |

... | ... |
... | ... |
... |

yi1 | ... |
yik | ... |
yin |

... | ... |
... | ... |
... |

ym1 | ... |
ymk | ... |
ymn |

In red we've left the pivot element that we will explain below

In this Simplex tableau, if there is an mxm identity submatrix of A, the vector Xb would be an extreme point that allows us to begin the iterations of the algorithm, is for him to calculate the z

j - c

j
Once calculated, we check ifon the optimality criterion hold, ie we test

z

j - c

j <0, ∀j

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

z

k - c

k = max(z

j - c

j), such us z

j - c

j >0

ie, we take the highest positive in z

j - c

j.

Now, with this index k, we find the called the pivot element. To do this, divide each coordinate i of the vector Xb by its coordinate column vector i y

ik and calculate the minimal of positive, ie we calculate

y

ik = min {i: β

i/y

ik, y

ik>0 }, being β

i coordinates of vector Xb

If the previous minimum was -1 (there not exist positive), would be in the case of unbounded solution, as this would indicate that for every index i

β

i/y

ik ≤ 0

and we would be in the case of unbounded solution as we have seen in Section

Simplex Algorithm.

Otherwise we can find, as the index that minimizes y

ik. This is the number called Pivot Element

### Pivot Element of the Simplex Algorithm

It is called the Pivot element on Simplex Algoritm Tableau to those yik of the constraints matrix wich indexes i and k makes

k = max(zj - cj), such us zj - cj >0

i = min {i: βi/y ik, y ik>0 }
at this case, we have k, that will be the new index of x that enters the base i is the index Xb leaving the base.

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

### Constraints matrix at new basis calculation

y'sj = ysj - (ysk * ysj)/yik

y'ij = yij/yik
This is the basis of the algorithm to invert the constraints matrix .

That is, for the pivot row, the new coefficients are calculated by dividing by the pivot, and for the other rows are calculated by subtracting the ai coefficient in the pivot row multiplied by the coefficient corresponding to the column divided by the pivot element.

We will see the end of this section a practical example of the algorithm.

We have the following problems:

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

**2)** In the event that the problem contains inequality constraints P. 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 operation. What to do in this case?

**5)** What if we want to maximize and not 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 the mxm identity, in this case the b vector, is a solution to our problem by taking as vectors those whose columns form the matrix B

In the event that there is identity matrix B, we use the

two-phase method.

**2)** We would for any row i of matrix A

In this case we define a slack variable

And if we have to row i, we define the slack variable

So, our problem with inequalities, leads to an equalities issue.

**3)** If for any component i, the variable is not restricted in sign, then we can to do

x

i = x

i1 - x

i2 con x

i1, x

i2 ≥0

**4)** In the event that we incompatibility, we can try to reformulate the problem so that such restrictions are consistent, since incompatibility is the same as saying that our problem can not be resolved

At redundancy case. we can simply discard the redundant constraints and stick with only one

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

We can reformulate the problem so

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)

-x

1 + x

2 ≤6

x

1 + x

2 ≤5

2x

1 + 2x

2 ≤10

Aplicamos el punto

**3)** for constraints 2 and 3, both are the same, we remove one of them, so we

Max(- x

1 + 3x

2)

-x

1 + x

2 ≤6

x

1 + x

2 ≤5

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)

-x

1 + x

2 ≤6

x

1 + x

2 ≤5

We apply the point

**2)**
Min(x

1 - 3x

2 + 0x

3 + 0x

4)

-x

1 + x

2 + x

3 = 6

x

1 + x

2 + x

4 = 5

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 positive of z

j - c

j
In our case 3, is given for the variable y

2, so enters at the basis and the index 2, (or k=2).

Now we calculate the rate that leaves the base, for this we divide each element of the vector Xb

k
by its corresponding in the column k of matrix a, ie, the minimum of 6/2 and 5/1
min (6/2, 5/

**1)** = 3 ,
the index is out of the base 3 and the pivot element is

**2**
We can perform one iteration of the simplex algorithm, is thus

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

3/2 = 1 - (-1) * 1/2 = 1 + 1/2

0 = 1 - 2 * 1/2 = 1 - 1

-1/2 = 0 - 1 * 1/2 = 0 - 1/2

1 = 1 - 1 * 0/1 = 1 - 0

**3)** And the same for the Xb, simply 2 = 5 - 1 * 6/2 = 5 - 3

We perform now another iteration, now the leaving out index is 4 and the entering index is 1, so we have

Now fulfills the criterion on optimality because

z

j - c

j > 0, ∀j

Thus we have a finite optimal solution

x1 = 4/3

x2 = 11/3

What makes an optimization objective function

s = 12/3 - 11/3 = 1/3

In summary, the simplex algorithm forwards from one extreme point to another by pivoting the constraint matrix is, by a basis change and calculating the coefficients in the new basis by the pivot element.