The Simplex Algorithm
Basic Concepts and Principles

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,
Min Ctx
Subject to
Ax = b
x ≥ 0
Where
A∈ Mmxn, rk(A)=m, b∈Rm, C∈Rn
If P has optimal solution x
k finite, we know from
Linear Programming Theory
that x
k is contained into the
extreme points
subset of feasible 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 x
k, then this x
k
is the solution that we are looking for.
Extended Theory
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 mxmsquare 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.
Lets w other point from the feasible region S. Then
Aw = b, ie
Bw
B + Nw
N = b
Because B is invertible
w
B = B
1b  B
1Nw
N
Applying C
t to w we obtain
C
tw = C
Btw
B + C
Ntw
N = C
Bt(B
1b  B
1Nw
N) + C
Ntw
N (*)
As w belongs to feasible region, we know that
w
N ≥ 0, so, if x were the optimal solution,
then it must holds
C
tw > C
tx = C
tB
1b
Now, we substitute at (*), obtain
C
Nt  C
BtB
1N > 0 (1)
This is the basic idea from the Simplex Algorithm that we were refering before,
and it is call
Optimality Criterion
The Simplex Algorithm Optimality Criterion
CNt  CBt B1 N > 0
If this condition holds, then x is the optimal solution of P.
The criterion equation has as coordinates
c
j  C
BtB
1 a
j
= c
j  C
Bty
j
= c
j  z
j
Being a
j, column vector of N.
In resume, optimality criterion is
z
j  c
j < 0, con z
j = C
Bt B
1 a
j
Suposse now than (1) does not holds, ie
C
Nt  C
Bt B
1 N ≥ 0 (2)
them there are two possibilities ...
1) yj = B1aj ≤ 0 ∀j, then we can build
x = w + λ d
j, being d
j = (B
1a
j, e
j)
t
we know that d
j is an extreme direction of feasible set S, in particular
Ad
j = 0
so x = w + λ d
j is also feasible solution ∀ λ ≥ 0.
In another way
C
tx = C
tw + λd
j = C
tw + λ(C
tB
1a
j) d
j = C
tw  λ(z
j  c
j) → ∞ 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 = B1aj 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 + λd
j
being d
j = (B
1a
j e
j)
t
and
λ = min{β/y
ij : y
ij > 0}, β = B
1 b.
With this value λ, x is feasible solution and if for example
λ = β
j/ y
ij
Then x is the basic solution associed to the matrix
B
, = (a
1, a
2, ..., a
r1, a
j, a
r+1, ..., , a
m )
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
z
j  c
j > 0
Then the operations is performed on the index k that satisfies
z
j  c
k = max (z
j  c
j), con z
j  c
j > 0
Overview of the Simplex Method
The extreme points x0, ..., xs, are the solutions for the systms
Bx=b, with B mxm submatrix of initial matrix A.
The optimal solution, if there, should be between these points...
Given an extreme point xi in the feasible set, we check if the Optimality criterion holds for it, if does then xi is the optimal solution founded.
Otherwise, one of these two situations can happen:
1) Unbouded Solution.
2) It is possible to iterate to next extreme point and
test the optimality criterion for it.
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.
Was useful? want add something?
Register here
Post here
Mathstools Forum
Post from other users
arun:
20121211 11:27:51
Thanks for this theory and worked samples.
It was very heplfull for me!!!
Rudra Prakash:
20130204 13:49:36
thnks a lot.its very very very useful to me...
bashir:
20131212 22:25:24
it was very benefit for me...
thank you...
could you post it to my Email?!
Malli:
20150129 10:39:14
z= 3x1 + 2X2  x3
min(Z)
Subject to
x1 + 2X2  3x3 = 4
4x1  x3 =7
2x1  3x2 + x3 <=5
Admin:
20150129 12:49:1
Hi Malli.
You can insert your problem in "the simplex algorithm" in this same web at
http://www.mathstools.com/section/main/simplex_online
To obtain
X1= 7/4,
X2=9/8,
X3=0
after 4 iterations
Post here