The simplex algorithm performs iterations into the extreme points set of feasible region, checking for each one if Optimalit criterion holds.

The Simplex Algorithm whose invention is due to George Dantzig in 1947 and in 1975 earned him the National Medal of Science is the main method for solving linear programming problems.

Given a linnear programming standard problem P,

If P has optimal solution xk finite, we know from Linear Programming Theory that xk is contained into the extreme points subset of feasible points set, S.

Simplex Algorithm basic idea is to perform iterations into extreme points set until a condition called "optimality criterion" holds.

If it holds at a certain extreme point xk, then this xk is the solution that we are looking for.

Suppose that x, extreme point of S.

Because the extreme points set is formed by solutions of Ax=b subsystems, x can be write as

x = [B-1b, 0]t, with B mxm-square A submatrix with rank m.

We can decompose A in B and N submatrices, B as said, is submatrix with rank m and N is the matrix formed with the remaining columns from A.(Remember that n≥m).

Lets w another point from the feasible region S. Then

Aw = b, ie

BwB + NwN = b

Because B is invertible

wB = B-1b - B-1NwN

Applying Ct to w we obtain

Ctw = CBtwB + CNtwN = CBt(B-1b - B-1NwN) + CNtwN     (*)

As w belongs to feasible region, we know that wN ≥ 0, so, if x were the optimal solution, then it must holds

Ctw > Ctx = CtB-1b

Now, we substitute at (*), obtain

CNt - CBtB-1N > 0        (1)

This is the basic idea from the Simplex Algorithm that we were refering before, and it is call Optimality Criterion



The criterion equation has as coordinates

cj - CBtB-1 aj = cj - CBtyj = cj - zj

Being aj, column vector of N.

In resume, optimality criterion is

zj - cj < 0, con zj = CBt B-1 aj

Suposse now than (1) does not holds, ie

CNt - CBt B-1 N ≥ 0       (2)

them there are two possibilities ...

   1) yj = B-1aj ≤ 0 ∀j, then we can build

x = w + λ dj, being dj = (-B-1aj, ej)t

we know that dj is an extreme direction of feasible set S, in particular

Adj = 0

so x = w + λ dj is also feasible solution ∀ λ ≥ 0.

In another way
Ctx = Ctw + λdj = Ctw + λ(-CtB-1aj) dj = Ctw - λ(zj - cj) → -∞ when λ → ∞

This means that we can make the solution as small as want without leaving the feasible set S and so this is a Unbounded case solution


   2) The Vector yj = B-1aj has someone positive component

Them is possible to build other feasible solution (it will be into the extreme point of S) where the function is smaller

The new solutions is build as follows
x = w + λdj

being dj = (-B-1aj ej)t and λ = min{β/yij : yij > 0}, β = B-1 b.

With this value λ, x is feasible solution and if for example

λ = βj/ yij
Then x is the basic solution associed to the matrix

B, = (a1, a2, ..., ar-1, aj, ar+1, ..., , am )

Ie, That is, we changed a vector by another (we have substituted the vector in r position for which is in place j).

In resume we have built a solution from other.
Note: if there are various indexes satisfying

zj - cj > 0

Then the operations is performed on the index k that satisfies

zj - ck = max (zj - cj), con zj - cj > 0

This is the simplex algorithm basic idea, iterating between the extreme points of feasible set, which are solutions of linear systems equations taken from square submatrices of constraints matrix A, and make this until one of them meets the optimality criterion.
There remains the problem of obtaining these solutions, we will see in section Simplex calculations how Simplex algorithm offers us a calculation in which there is not need to perform the inverse of the matrix A. This calculation is called pivoting the matrix and is another basic element of the simplex algorithm.