Linear Programming & the Simplex Algorithm

Part II
P&S Chapter 2
Last Revised – October 13, 2004

1
 Outline

• Moving from BFS to BFS.

• Organizing information in a tableau.

• How to move from a BFS to a better BFS and

proving that an optimal BFS exists.

• The Simplex Algorithm.

2
 Moving From BFS to BFS

For LP in standard form with matrix A, let x0 be a BFS

corresponding to the basis columns

B = {AB(i) : i = 1, . . . , m}.
Let the basic components of x0 be xi,0, i = 1, . . . , m,
i.e.,
m
X
xi,0AB(i) = b, where xi,0 ≥ 0.
i=1

Any nonbasic column, Aj ∈ Rm, Aj 6∈ B can be writ-

ten as
m
X
xi,j AB(i) = Aj .
i=1

Multiplying the 2nd by θ > 0 and subtracting from the

first gives

Pm  
i=1 xi,0 − θ xi,j AB(i) + θ Aj = b
3
Given basis

B = {AB(i) : i = 1, . . . , m}
we have seen that for every non-basis column Aj 6∈ B
Pm  
i=1 xi,0 − θ xi,j AB(i) + θ Aj = b

Assuming for the moment that x0 is nondegenerate,

so all xi,0 > 0,

Fixing j, start at θ = 0 and then increase θ. As soon

as θ > 0 we have moved from a BFS to a feasible
solution with m + 1 positive components.

How long does this solution remain feasible?

As long as xi,0 − θxi,j ≥ 0, i.e.,
xi,0
θ0 = min
i s.t. xi,j
xi,j >0

4
 Pm  
i=1 xi,0 − θ xi,j AB(i) + θ Aj = b

xi,0
θ0 = min
i s.t. xi,j
xi,j >0

There are two special cases:

a) x0 is degenerate because some xi,0 = 0 and cor-

responding xi,j > 0. Then θ0 = 0 and we do not
move at all in Rn.

We actually stay at the same vertex but can think of

what happened as moving to a new BFS in the LP,
representing the same vetex, with column j replacing
column B(i),

In this case we sometimes say that xj entered the

basis at level 0.

b) If all the xi,j , i = 1, . . . , m are nonpositive we

would be able to move arbitrarily far without becom-
ing infeasible. This would mean that F is unbounded,
violating Assumption 3.
5
Theorem: Let x0 be a BFS with basic components
xi,0,, i = 1, . . . , m and basis
B = {AB(i) : i = 1, . . . , m}.
Let j be s.t. Aj 6∈ B.
Then the new feasible solution determined by

xi,0 xl,0
θ0 = min =
i s.t. xi,j xl,j
x >0 i,j

(
xi,0 − θ0xi,j i 6= l
x′i,0 =
θ0 i=l

is a BFS with basis B′ defined by

(
B(i) i 6= l
B ′ (i) =
j i=l

When there is a tie in the min operation then the new

BFS is degenerate
6
Proof: We already saw that this solution is feasible.

We now must show that it is basic, i.e, that the set of

basis columns B′ is linearly independent

Suppse not, then for some constants di, we have

m
X m
X
0= di AB ′(i) = dl Aj + di AB ′(i)
i=1 i=1
i6=l
Plugging in (why does this exist)
m
X
Aj = xi,j AB(i)
i=1
gives
m 
X 
dl xi,j + di AB ′(i) + dl xl,j AB(l) = 0
i=1
i6=l

Since B is a basis all of these coefficients must be

zero so, in particular, dl xl,j = 0 so dl = 0. But then,
from the first equality (why) all of the di = 0 so the
new basis is linearly independent.

If there is a tie then more than one of the components

of x0 become 0 and the basis is degenerate.
7
We just saw how to move from one BFS to another
by removing one column B(l) out of the basis and re-
placing it by another column. This method is called
pivoting. Column B(l) leaves the basis and new col-
umn j enters the basis.

Geometrically (to be proven later), a pivot either

a) moves from one vertex to another along an edge or

b) does nothing, i.e., stays at the same vertex. In this

case, the corresponding BFSs must be degenerate.

We now see how to organize the equation information

to make it easy to recognize and calculate pivots. In
particular, we will see how to maintain the xi,j infor-
mation in a tableau.

8
 Organization of a Tableau

3x1 + 2x2 + x3 = 1
5x1 + x2 + x3 + x4 = 3
2x1 + 5x2 + x3 + x5 = 4

We will keep a set of m equations in n unknowns in

an m × n tableau:

x1 x2 x3 x4 x5
1 3 2 1 0 0
3 5 1 1 1 0
4 2 5 1 0 1

Note that the RHS of the equations has now become

column 0 in tableau.

9
The Elementary row operations

• Multiplying a row by a non-zero element

• Adding a multiple of one row to another row

do not change the solutions to the set of equations.

We can therefore use elementary row operations to
manipulate the rows until a set of (basis) columns be-
comes an identity matrix.

As an example we can manipulate

3x1 + 2x2 + x3 = 1
5x1 + x2 + x3 + x4 = 3
2x1 + 5x2 + x3 + + x5 = 4

so that it becomes
3x1 + 2x2 + x3 = 1
2x1 − x2 + x4 = 2
−x1 + 3x2 + x5 = 3

10
The manipulation on the previous page can also be
performed in tableau form with
x1 x2 x3 x4 x5
1 3 2 1 0 0
3 5 1 1 1 0
4 2 5 1 0 1
becoming
x1 x2 x3 x4 x5
1 3 2 1 0 0
2 2 −1 0 1 0
3 −1 3 0 0 1

In this example the basis B = {A3, A4, A5}.

The important things to notice are that

• Column 0 gives the values of the basic variables

xB(i) = xi,0, i = 1, . . . , m and

• The non basic columns contain exactly the values

xi,j s.t. Aj = i xi,j AB(i).
P

Pm
Example: A1 = 3A3+2A4−A5 = i=1 xi1 AB(i)

11
Current basis is B = {A3, A4, A5}. Suppose we
want to move column j = 1 into basis.
x1 x2 x3 x4 x5
1 3 2 1 0 0
2 2 −1 0 1 0
3 −1 3 0 0 1
Then
!
xi0 1
θ0 = min = for i = l = 1
i xij 3
s.t. xij >0

This means that we will introduce column A1 into ba-

sis with the “1” in row l = 1. Doing this by elementary
row operations gives a new basis B′ = {A1, A4, A5}
and tableau

x1 x2 x3 x4 x5
1/3 1 2/3 1/3 0 0
4/3 0 −7/3 −2/3 1 0
10/3 0 11/3 1/3 0 1

12
Old
x1 x2 x3 x4 x5
1 3 2 1 0 0
2 2 −1 0 1 0
3 −1 3 0 0 1
Setting (col) j = 1 gives θ1 = 1/3, i = l = 1, and
x1 x2 x3 x4 x5
1/3 1 2/3 1/3 0 0
4/3 0 −7/3 −2/3 1 0
10/3 0 11/3 1/3 0 1

In general, if xi,j and x′i,j are the old and new vari-
ables, B, B′ the old and new bases and pivot is xi,j
then the elementary row operations inserting column
j into basis can be written as
x
x′lq = xlq q = 0, . . . , n
lj
x′iq = xiq − x′lq xij i = 1, . . . , m; i 6= l
( q = 0, . . . n
B(i) i 6= l
B ′ (i) =
j i=l

Important: Basis remains feasible by definition of θ1.

13
So far we have seen

• How to move from one BFS B to another BFS B′

by moving a new column Aj into the basis set

• How to efficiently implement the above using a

tableau representation

– Given new column Aj , tableau permits cal-

culating which old column AB(i) should be
thrown out (this will be the i found when cal-
culating θ0).

– Given i, j, tableau permits modifying old xl,q

into new x′l,q

It remains to show how to maintain cost in the tableau.

This will be done introducing a new row into the tableau.

Before doing this we first show that there is a simple

criteria to decide whether a BFS is optimal.

This criteria will have the added advantage of implying

that there is always an optimal BFS.
14
 Pm
Cost of BFS x0 with basis B is z0 = i=1 xi,0cB(i) .

Before Aj is brought into basis we have

Aj = m i=1 xi,j AB(i).
P

This means that for every unit of xj that enters BFS,

xi,j units of xB(i) must leave. A unit increase of xj
implies a net change in cost or relative cost of
Pm
c̄j = cj − i=1 xi,jcB(i) = cj − zj

where zj = m i=1 xi,j cB(i).

P

It is therefore profitable to bring column j into basis iff

c̄j < 0.
We will soon see that BFS is optimal iff ∀j, c̄j ≥ 0.

Notation: For tableau X let B be the m × n ma-

trix containing basis columns in X. Let cB be the
m-vector of costs corresponding to this basis. Let
z = col(z1, . . . , zn) Then, since X comes from di-
agonalizing basis columns of A,
X = B −1A and z ′ = c′B X = c′B B −1A

15
Optimality Theorem:
At BFS x0 a pivot step in which xj enters the basis
changes the cost by
θ0c̄j = θ0(cj − zj )
Furthermore, if
c̄ = c − z ≥ 0
then x0 is optimal.

Proof: Recall that original cost was z0 = m

i=1 xi,0cB(i).
P

If j moves into basis we have already seen that

(
xi,0 − θ0xi,j i 6= l
x′i,0 =
θ0 i=l
so new cost is
m
z0′ =
X
(xi,0 − θ0xi,j )cB(i) + θ0cj
i6=l;i=1
= z0 + θ0(cj − zj )
proving first part. To prove second part let y be any
feasible vector (not necessarily basic), i.e, Ay = b
and y ≥ 0. Then
c′y ≥ z ′y = c′B B −1Ay = c′B B −1b = c′x0
where last equality comes from fact that b = Bx0.
16
Optimality Theorem:
At BFS x0 a pivot step in which xj enters the basis
changes the cost by
θ0c̄j = θ0(cj − zj )
Furthermore, if
c̄ = c − z ≥ 0
then x0 is optimal.

This is the most important theorem we will see in

this section!!

Consider the following algorithm:

Start at some BFS and loop the following line

If any c̄j < 0, pivot on Aj and construct new BFS.

(Ignoring degeneracy and assumptions we made) the-

orem implies that pivot always decreases cost, so cost
is decreasing monotonically and we can never loop
back to previously seen BFS. Since there are only a
finite number of BFSs, the algorithm must terminate.
The theorem then implies that the BFS at which we
terminated was an optimal solution.

This algorithm is the SIMPLEX ALGORITHM.

17