2 Theory of Linear Programming

Linear programming has a natural geometric interpretation, which has been demon-
strated in our introductory example. As we will see later, the canonical form determines
the extreme points and the polyhedral structure of the feasible region, whereas the stan-
dard form characterizes the problem as the non-negative solutions of a system of linear
equalities. Considering a linear program geometrically leads us to algorithmic ideas,
whereas the various parametrized descriptions of a solution set to a system of linear
equalities are the basis for the famous and trusted simplex method. We will discuss
both approaches and their relation in this chapter.

2.1 Geometric Properties by Means of an Example

Consider the canonical linear optimization problem:

max z = 400x1 + 900x2 ,

subject to
x1 + 4x2 ≤ 40 (constraint A),
2x1 + x2 ≤ 42 (constraint B),
1.5x1 + 3x2 ≤ 36 (constraint C),
x1 ≥ 0, x2 ≥ 0 (non-negativity).

The polygon a, b, c, d, e in Fig. 2.1 is a geometric description of the feasible solutions to

the LP. This set is convex, i.e., the line connecting any two points inside the set is entirely
contained in the set. The vertices a, b, c, d, e of the polygon are also called extreme points.
In general, a subset S of Rn is called convex if x ∈ S and y ∈ S implies that z =
λx + (1 − λ)y ∈ S for any 0 ≤ λ ≤ 1, i.e., S is closed with respect to convex linear
combinations.
Moreover, we remark that the set of feasible points in Fig. 2.1 is uniquely characterized
by the extreme points: the set of feasible solutions is the “convex hull of the extreme
points”, i.e., the set of all convex linear combinations. This property holds for any LP
whose feasible region is bounded.
In our example it is easy to see that the optimal value is attained at one of the extreme
points, known as the optimal solution. As we will see, this property also holds in general.

15
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

Figure 2.1: Feasible region.

Using the graphical solution method from Section 1.2, we immediately find the op-
timal solution x1 = 8, x2 = 8 at the extreme point d with the respective optimal value
z = 10400.

Multiple Optimal Solutions

If we change the coefficients of the objective function in such a way that the level lines
are parallel to one side of the polygon containing d, then the optimal solution will not
be unique anymore. However, in any case there will be an optimal solution which is
indeed a vertex of the polygon.

Example:
We change the objective function in the above example to:

z = 200x1 + 800x2 ,

subject to the same constraints. All points on the line segment d, e are now optimal
for the changed problem. The vertex d with x1 = 8, x2 = 8 is still optimal, but vertex e
with x1 = 0, x2 = 10 has the same objective value and is optimal as well.

d : z = 8 · (200) + 8 · (800) = 8000

e : z = 0 · (200) + 10 · (800) = 8000.

In fact, every point on the line segment d, e, i.e., every point x that can be written as
! ! !
x1 8 0
x= =λ + (1 − λ) for some 0 ≤ λ ≤ 1,
x2 8 10

16
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

has the same objective value. From

x1 = 8λ + 0(1 − λ) = 8λ, and
x2 = 8λ + 10(1 − λ) = 10 − 2λ
we get
z= (8λ)(200) + (10 − 2λ) (800)
= 1600λ + 8000 − 1600λ = 8000,
independently of λ. Moreover, the set of optimal solutions is a convex set itself.

Unbounded Polyhedra
Consider the problem
maximize z = −2x1 + 6x2 ,
subject to
−x1 − x2 ≤ −2,
−x1 + x2 ≤ 1,
x1 ≥ 0, x2 ≥ 0.

Figure 2.2: Unbounded polyhedron.

In this example the set of solutions is unbounded and the objective value can be made
arbitrarily large: for any given value of the objective function we can find a point (x1 , x2 )
in the feasible region with bigger objective value (cf. Fig. 2.2).

Infeasible Problem
Consider now the problem
maximize z = x1 + x2 ,

17
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

subject to

−x1 + x2 ≤ −1
x1 − x2 ≤ −1
x1 ≥ 0, x2 ≥ 0.

Figure 2.3: Infeasible problem.

The feasible region is empty, i.e., there is no point (x1 , x2 ), which satisfies all con-
straints simultaneously (cf. Fig. 2.3).

Brief summary of some important observations

(i) The feasible region is convex (the empty set is convex by definition), bounded or
unbounded.

(ii) If the feasible region is non-empty and bounded, then there exists an optimal
extreme point, a vertex of the polyhedron.

An algorithm for linear programming should

(i) detect whether the problem is feasible or infeasible,

(ii) in case of feasibility, detect whether it has a bounded or unbounded optimal value,
and

(iii) find an optimal solution in the (feasible) bounded case.

18
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

2.2 The Canonical Form of an LP

We define the following notation:
x j j = 1, . . . , n value of the j-th (decision) variable,
ai j i = 1, . . . , m, j = 1, . . . , n “coefficient” of variable j in constraint i,
bi i = 1, . . . , m bound for constraint i (”right-hand side”),
c j j = 1, . . . , n coefficient of x j in the objective function.
The problem is now to determine values x j , j = 1, . . . , n, as to
n
X
maximize z = c jx j, (2.1)
j=1

subject to
n
X
(LP) ai j x j ≤ bi , i = 1, . . . , m (2.2)
j=1

xj ≥ 0 j = 1, . . . , n, (2.3)
where n is the number of variables and m is the number of constraints. The above form
of the LP, which is a maximization problem with nonnegative variables and less-than-
or-equal constraints is called the canonical form of an LP. In matrix notation, a general
LP in canonical form looks as follows
max cT x
Ax ≤ b
x ≥ 0.
We will now provide operations that allow for transforming an LP in general form
(see 1.3) into canonical form, thus showing that the canonical form captures any LP.
(i) The above formulation can also represent minimization problems:
n
X
minimize z= c jx j
j=1
n
X
↔ maximize −z = −c j x j .
j=1

(ii) Inequalities with lower bounds (≥) can be handled by switching the signs:
n
X
ai j x j ≥ bi
j=1
n
X
↔ − ai j x j ≤ −bi .
j=1

19
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

(iii) Equalities can be described using two inequalities:

n
X
a i j x j = bi
j=1

l
n
X
a i j x j ≤ bi
j=1
n
X
− ai j x j ≤ −bi .
j=1

(iv) A variable x j that has to fulfill x j ≤ 0 can be substituted by −x0j , where x0j ≥ 0 is a
new nonnegative variable.
(v) A real variable x j ∈ R that does not need to fulfill non-negativity constraints, can
be substituted by x j = x+j −x−j , where x+j , x−j ≥ 0 are two new nonnegative variables.

Since the canonical form captures any LP, any result that holds for an LP in canonical
form can be translated to general LPs.

2.3 The Standard Form of an LP

A well-known alternative form to write general LPs is the standard form, which turns
out to be handy in many situations. The standard form is based on equality instead of
inequality constraints, and a general LP in standard form looks as follows:

max cT x
Ax = b
x ≥ 0.
More precisely, starting with an LP in canonical form, we obtain the standard form
by introducing slack variables in the following way. For every inequality
n
X
a i j x j ≤ bi , (∗)
j=1

we introduce a slack variable yi and replace the inequality constraint by the equality
constraint
n
X
yi + a i j x j = bi . (∗∗)
j=1

In order to have the property that every solution (y1 , . . . ,ym ,x1 , . . . , xn ) of (∗∗) implies
a solution (x1 ,. . . , xn ) of (∗) and vice versa, we also require that yi ≥ 0, i = 1, . . . , m.

20
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

The canonical form with inequalities therefore has the following equivalent standard
form:
X n
maximize z = c jx j,
j=1

subject to
n
X
yi + ai j x j = bi , i = 1, . . . , m, (2.4)
j=1

yi ≥ 0, i = 1, . . . , m, (2.5)
x j ≥ 0, j = 1, . . . , n.

Terms:
An (m + n)-tuple (y1 , . . . , ym , x1 , . . . , xn ), satisfying the system (2.4), is called solution of
the LP. If a solution also satisfies (2.5), then it is called feasible.
We will first discuss solutions to the system of equations (2.4), a system of m equa-
tions and n + m unknowns. The system of inequalities in our introductory example
(Section 2.1), after introducing three slack variables, leads to the following system,
shown in a schematic tabular form:

y1 y2 y3 x1 x2 1
1 0 0 1 4 40 System of equations:
0 1 0 2 1 42 - three equations
I
0 0 1 1.5 3 36 - five unknowns

| {z } |{z}
coefficient matrix right-hand side

We can obtain the parametrized form of the set of solutions quite easily from this
special description, namely:

y1 = 40 − x1 − 4x2
y2 = 42 − 2x1 − x2
y3 = 36 − 1.5x1 − 3x2

Every choice of x1 and x2 determines a unique solution to the system and correspond-
ingly

(x1 , x2 ) are called “free” variables, and

(y1 , y2 , y3 ) are called “dependent” variables.

21
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

The dimension of the solution space is determined by the number of free variables.
Such an explicit description of the solutions to a system of equations is always possible
if there exists an m-dimensional index vector

B = (β(1), . . . , β(m)); β(l) ∈ {1, . . . , n + m}, l = 1, . . . , m,

such that the corresponding columns of the coefficient matrix form the identity matrix.
Example:

y1 y2 y3 x1 x2 1
1 1
4 0 0 4 1 10
II
− 14 1 0 7
4 0 32
− 34 0 1 3
4 0 6

The columns B = (5, 2, 3) form an identity matrix. The solution space in its parametrized
form with free variables (y1 , x1 ) can be read directly from the tableau:

x2 = 10 − 1
4 y1 − 1
4 x1
y2 = 32 + 1
4 y1 − 7
4 x1
y3 = 6 + 3
4 y1 − 3
4 x1

2.4 Equivalent Linear Systems

The systems of linear equations I and II have the same set of solutions, since, as we will
show below, system II is obtained from system I by elementary row operations, which
do not change the set of solutions.
Allowed elementary row operations are:

(i) changing the order of the equations,

(ii) multiplying an equation with a non-zero real number, and

(iii) adding a multiple of one equation to another equation.

We illustrate these operations using our example.

y1 y2 y3 x1 x2 1
1 0 0 1 4 40
I 0 1 0 2 1 42
0 0 1 1.5 3 36

Multiply the first equation by 14 :

22
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

y1 y2 y3 x1 x2 1
1 1
4 0 0 4 1 10
→ Ia 0 1 0 2 1 42
0 0 1 1.5 3 36

Add (−1)× first row to the second row, and add (−3)× first row to the third row:

y1 y2 y3 x1 x2 1
1 1
4 0 0 4 1 10
II − 14 1 0 7
4 0 32
− 34 0 1 3
4 0 6

Definition 2.1. Systems of linear equations, which can be transformed to each other
using elementary row operations, are called equivalent.

I , Ia , and II are equivalent systems and have therefore the same set of solutions.
Tableau form, basic solutions: A system of equations is in tableau form, if there exists
an index vector B = (β(1), . . . , β(m)) with β(`) ∈ 1, . . . , n + m and

AB = I,

where AB is the submatrix consisting of the m columns β(1), β(2), . . . , β(m) of the coeffi-
cient matrix, I is the m-dimensional identity matrix.
• B is called a basis of the system.
• The variables corresponding to the basic columns are called basic variables.
• The other variables are called non-basic variables.

Example:
System I above is in tableau form with B = (1, 2, 3) and basic variables y1 , y2 , and y3 .
System II is in tableau form with B = (5, 2, 3) and basic variables x2 , y2 , and y3 , whereas
system Ia is not in tableau form!
In a tableau the basic variables can be uniquely described as a function of the non-basic
variables, which corresponds to a parametrized description of the set of solutions. Setting the
values of the non-basic variables to zero in such a representation yields a basic solution.
In tableau II
(y∗1 = 0, y∗2 = 32, y∗3 = 6, x∗1 = 0, x∗2 = 10)
is a basic solution.

This solution corresponds to the extreme point e in the polygon (cf. Fig. 2.1).

In general, the extreme points of the polygon correspond to the non-negative basic
solutions of the system.

23
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

2.5 Exchange Step

Transforming one tableau into another can be done using exchange steps. An exchange
step is a sequence of elementary row operations, which are uniquely determined by
the variables “entering” and “leaving” the basis. Let B be the basis of a tableau and
k < B with aik , 0 for some i ∈ {1, . . . , m}, where A is the current coefficient matrix. The
following rules yield the coefficient matrix of an equivalent tableau with basis B0 , whose
elements are 
 β(`), ` = 1, . . . , m, ` , i

β (`) = 
0

 k, `=i


ai`
(i) a0i` = aik ` = 1, . . . , n + m,
a jk ·ai`
(ii) a0j` = a j` − aik ` = 1, . . . , n + m, j , i, j = 1, . . . , m,
bi
(iii) b0i = aik ,
a jk ·bi
(iv) b0j = b j − aik j = 1, . . . , m, j , i,

where

• aik is called pivot element (pivot);

• the row of index i is called pivot row;

• the column of index k is called pivot column.

The variable corresponding to the i-th unit vector is called basis leaving variable, and
the one corresponding to the k-th column the basis entering variable.
Example:

y1 y2 y3 x1 x2 1
1 1
4 0 0 4 1 10
II − 14 1 0 7
0 32
4
− 34 0 1 3
0 6
4

Exchange step with k = 4, i = 3, aik = 3

4
↓

y1 y2 y3 x1 x2 1
1
2 0 − 31 0 1 8
III + 64 1 - 37 0 0 18
4
-1 0 3 1 0 8

24
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

New basis: B0 = (5, 2, 4).

Basic variables: (x2 , y2 , x1 )
Parametrized Solution Set for (III):

x2 = 8 − 1
2 y1 + 1
3 y3
y2 = 18 − 6
4 y1 + 7
3 y3
x1 = 8 + y1 − 4
3 y3

Basic solution: y∗1 = 0, y∗2 = 18, y∗3 = 0, x∗1 = 8, x∗2 = 8

(Corresponds to vertex d in Fig. 2.1.)

2.6 Short Tableau

Notice that in a tableau, the unit vectors corresponding to basic variables are not needed:
using a suited labeling of the basic variables they can be generated from them. Exploiting
this fact, one can derive a more compact tableau form, that we call the short tableau. The
short tableau has several advantages. First, as already mentioned, it reduces the amount
of data that has to be carried along when doing operations on the tableau. And at least
equally importantly, it will prove very useful when we talk about the dual of a linear
program, many of whose properties can be read more naturally from the short tableau.
Let B be the basis, i.e., an index vector of length m, whose i-th component determines
the place of the i-th unit vector in the tableau:

B = (β(1), . . . , β(m)), β(i) ∈ {1, . . . , n + m}, i = 1, . . . , m,

s.t. Aβ(i) = ei or AB = I, where A` is the `-th column of the tableau and ei is the i-th unit
vector of Rm .

Example (Tableau II):

β(2) β(3) β(1)

=

1 2 3 4 5 ← column index
y1 y2 y3 x1 x2 1
1 1
4 0 0 4 1 10
IIa − 14 1 0 7
4 0 32
− 34 0 1 3
4 0 6

By marking the i-th row of the tableau with the (basic) variable of the column Aβ(i)
and by deleting the corresponding unit vectors, we obtain a short tableau with basis B:

25
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

y1 x1 1
x2 1 1
10
IIb 4 4 B = (5, 2, 3)
7
y2 − 41 4 32
y3 − 43 3
4 6

An exchange step with pivot αik , 0 in a short tableau  leads to a modification of

the boundary, caused by exchanging the basis leaving variable with the basis entering
variable. The following rules yield the coefficient matrix of an equivalent tableau for
the new basis:

α̂0ik = 1
α̂ik (pivot element)
α̂ jk
α̂0jk = − α̂ik (pivot column) j = 1, . . . , m, j,i
α̂i`
α̂0i` = α̂ik (pivot row) ` = 1, . . . , n, `,k
α̂ jk ·α̂i`
α̂0j` = α̂ j` − α̂ik j = 1, . . . , m, j , i
` = 1, . . . , n, ` , k
bi
b0i = α̂ik
α̂ jk ·bi
b0j = bj − α̂ik j = 1, . . . , m, j,i

The exchange step in IIb gives us:

y1 y3 1
1
x2 2 − 31 8
y2 6
4 − 37 18 with B0 = (5, 2, 4)
4
x1 −1 3 8

Exercise 2.2. Verify the validity of the above rules using the full tableau.

Example:
For the following system of equations we can directly find a tableau for the basis
B = (1, 2, 3):

x1 + 2x4 + x5 = 3
x2 + x4 – x5 = 0
x3 + x4 = 2

26
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

x4 x5 1

x1 2 1
3
B = (1, 2, 3) x2 1 -1 0 tableau (a)
x3 1 0 2

The corresponding basic solution for this basis is:

x1 = 3, x2 = 0, x3 = 2, x4 = 0, x5 = 0.
We perform exchange steps to compute further basic solutions (the pivot element is
marked).

(b): (c): (d):

x4 x1 1 x2 x1 1 x2 x4
x5 2 1 3 x5 − 32 1
1 x5 -1 -1 0
  3
x2 1 1 x1
3
1 3 x4 3 1 1 3 3
3

x3 1 0 2 x3 − 31 − 13 1 x3 0 1 2

= ≡
x = (0, 3, 2, 0, 3) x = (0, 0, 1, 1, 1) x = (3, 0, 2, 0, 0)

basic solutions

Exercise 2.3. Consider x1 , x2 , and x3 as slack variables in tableau (a), and draw the basic
solutions for the tableaus (a)-(d) in the (x4 , x5 )-space.

2.7 The Simplex Method for Linear Programs in Standard

Form
We consider the general linear program (2.4), (2.5), where we allow the objective function
to contain additionally a constant term q ∈ R.

n
X
max z = c jx j + q
j=1
n
X
(P) yi + ai j x j = bi , i = 1, . . . , m
j=1

yi ≥ 0, x j ≥ 0, i = 1, . . . , m, j = 1, . . . , n

27
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

We will slightly change the formulation of the problem:

 n
c jx j = q
P
z −






 j=1
 n
(2.6)

yi + a i j x j = bi , i = 1, . . . , m
 P


j=1



i = 1, . . . , m, j = 1, . . . , n,

z maximal, y ≥ 0, x ≥ 0,

i j

where z ∈ R. Now (2.6) is a system of equations in the n+m+1 variables z, y1 , . . . , ym , x1 , . . . , xn ,

namely

n
X
z− c j x j = q,
j=1
n (2.7)
X
yi + a i j x j = bi , i = 1, . . . , m.
j=1

We now consider the tableau corresponding to (2.7) in matrix form:

z y1 . . . ym x1 . . . xn 1
1 0 ... 0 −c1 . . . −cn q (2.8)
0 I A b

This tableau can be written in its short form as:

x1 ... xn 1
z −c1 . . . −cn q
y1 a11 ... a1n b1 initial tableau (2.9)
.. .. .. ..
. . . .
ym am1 . . . amn bm

In the following the artificial variable z will stay in the basis, therefore we will refer
to a basic solution only with respect to the remaining variables y1 , . . . , ym , x1 , . . . , xn . We
identify this fact in the tableau by isolating the equation for the objective function. We
will refer to a “basis” also only with respect to the remaining columns.
The tableau (2.9) is called feasible if b1 , . . . , bm ≥ 0, i.e., if the corresponding basic
solution is feasible.

28
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

Example (introductory example from Section 2.1):

x1 x2 1
z −400 −900 0
y1 1 4 40
y2 2 1 42
y3 1.5 3 36

This tableau is feasible.

Motivated by our geometrical interpretation, it is our goal to find an optimal basic
solution (w.r.t. the objective function) among the finite number of feasible basic solutions
to (P). We will use the following approach: starting with a feasible tableau, we will
determine a finite sequence of feasible tableaus in such a way, that the objective values
of the corresponding basic solutions increase at each step.
The following sequence of tableaus leads to a solution to our introductory example
(cf. Section 2.1). The corresponding sequence of vertices of the polygon are from a over
b and c to d (cf. Fig. 2.1).

x1 x2 1 y2 x2 1
z −400 −900 0 z 200 −700 8400
y1 1 4 40 y1 − 12 7
19
 2
1 1
y2 2
1 42 −→ x1 21
2  2
y3 1.5 3 36 y3 − 34 9 9
4
2

“vertex a” “vertex b”
↓
y1 y3 1 y2 y3 1
700
z 50 10400 z − 100 2800
9800
3  3 9
3
y2 2 − 73 18 y1 2
− 14 12
3
9
4 2
x1 −1 3 8 ←− x1 3 − 29 20
1 1
x2 2 −3 8 x2 − 13 4
9 2

“vertex d” “vertex c”

The following simplex method will describe how such a sequence can be found system-
atically in the general case.
We are given a feasible tableau in the general short form (2.9).

29
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

xN 1
z α01 . . . α0n q0 ← 0-th row corresponding to objective function!
α11 . . . α1n b01 (2.10)
.. .. ..
xB . . .
αm1 . . . αmn b0m


xB = vector of basic variables 

 “boundary” of the tableau

xN = vector of non-basic variables 


In the introductory example xB = (y1 , y2 , y3 ) and xN = (x1 , x2 ).

Basic solution: xB = b0 , x0N = 0 ⇒ objective value of the basic solution = q0 .

Tableau is feasible ⇔ b0 ≥ 0 (component wise), i.e., if and only if the basic solution
is feasible.

Theorem 2.4 (Choice of the pivot). Let a feasible tableau be given as in 2.10 (e.g. the
starting tableau).

(i) Pivot choice feasible

If possible, choose the pivot αik according to the following rules:
1. pivot column: Choose k ∈ {1, . . . , n}, such that there exists an l ∈ {1, . . . , m}
with
αlk > 0.

2. pivot row: Choose i ∈ {1, . . . , m} such that:

b0i b0l
( )
= min l ∈ {1, . . . , m}, αlk > 0 [quotient rule].
αik αlk

The exchange step with pivot αik leads to a feasible tableau of (P).

(ii) If the pivot column in (i.1) also satisfies α0k < 0, then the objective value will not
decrease when changing to the new basic solution. If, in addition, b0i > 0, then the
objective value will increase.

Proof.

(i) Based on the rules for the exchange step with pivot aik , the following holds for the

30
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

right-hand side of the tableau:

b0i
pivot row: b̂0i = αik ≥ 0, since αik > 0, b0i ≥ 0
αlk ·b0i b0l αik −αlk b0i
for l , i : b̂0l = b0l − αik = αik , l = 1, . . . , m, l , i

and therefore
b̂0l ≥ 0 ⇔ b0l αik − αlk b0i ≥ 0, since αik > 0.

Hence it is sufficient to prove the latter inequality in order to prove the feasibility
of the new tableau. We consider two cases.
a) αlk ≤ 0 ⇒ b0l αik −αlk b0i ≥ 0, since αik > 0.
|{z} |{z}
≥0 ≥0
b) αlk > 0 : b0l αik − αlk b0i ≥0
b0l b0
⇔ αlk ≥ αiki
b0i b0l
 
⇔ αik = min αlk αlk > 0 , which corresponds to rule (i.2).
Therefore (i) is a feasible exchange step.

(ii) Consider now the change of q0 after the exchange step:

α0k · b0i
q̂0 = q0 − .
αik
If α0k < 0 and b0i ≥ 0, αik > 0, then

q̂0 ≥ q0 .

If, in addition, b0i > 0, then the increase is indeed positive:

(−α0k ) b0i
.
αik

This finishes the proof of Theorem 2.4. 

Remark:
In order to achieve the largest marginal increase, we have to choose the pivot column
which has the most negative element a0k .
Choosing the pivot according to Theorem 2.4 is not possible, if and only if one of the
following two cases occurs:

(1) α0l ≥ 0 for l = 1, . . . n;

(2) For every k ∈ {1, . . . , n} with α0k < 0 it holds that αlk ≤ 0 for l = 1, . . . , m.

31
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

However, in this case continuing the computation is useless, as the following theorem
shows.

Theorem 2.5. Let a feasible tableau be given as in (2.10).

(i) If α0l ≥ 0 for every l = 1, . . . , n, then the basic solution corresponding to (2.10) is an
optimal solution to (P).

(ii) If there exists a k ∈ {1, . . . , n} such that α0k < 0 and αlk ≤ 0 for every l = 1, . . . , m,
then the optimal value of (P) is unbounded.

Proof.
(i) Consider the parametrized objective function in the feasible tableau:
z(xN ) = −α01 (xN )1 − α02 (xN )2 − . . . − α0n (xN )n + q0 .
Since any feasible solution satisfies (xN )i ≥ 0 (i = 1, . . . , n), we get the following
estimate from assumption (i) of Theorem 2.5:
z(xN ) ≤ q0 for any feasible solution.
But since z(0) = q0 and xB = b0 , xN = 0 is a feasible basic solution, it must be optimal.
(ii) To prove (ii), consider the following special set of solutions to the system of equa-
tions: set the value of all non-basic variables except for (xN )k to zero and let
xB = b0 − ( Â.k )(xN )k , (xN )k ≥ 0.
|{z}
k-th column of the tableau

Since Â.k ≤ 0 (component-wise), this “halfline” is feasible for all values (xN )k ≥ 0, i.e.,
it is entirely contained in the polyhedron. Considering the objective values along this
halfline, which are
z((xN )k ) = q0 − α0k (xN )k ,
we get that z is not bounded from above, because α0k < 0. 

Example:
Next to the tableau below, the quotients are indicated when choosing x2 as entering
variable, i.e., x2 is the variable that will enter the basis.

x1 x2 1 quotient b0l /αlk

z −400 −900 0

y1 1 4
40 10 ← minimum
y2 2 1 42 42
y3 1.5 3 36 12

32
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

Tableau is feasible.

x1 y1 1 quotient
z − 700
4 + 900
4 9000
1 1
x2 4 4 10 40
7 1
y2 −4 32 128/7
 4
3
y3 − 34 6 8 ← minimum
4

The new feasible basic solution is

(y1 = 0, y2 = 32, y3 = 6, x1 = 0, x2 = 10)

and the corresponding value of the objective function is z = 9000.

y3 y1 1
700
z 3 50 10400
x2 − 13 1
2 8
y2 − 73 6
4 18 tableau feasible, optimal by Theorem 2.4 point (i)
4
x1 3 −1 8

Optimal basic solution: (y1 = 0, y2 = 18, y3 = 0, x1 = 8, x2 = 8).

Objective value z = 10400 ⇒ optimal tableau.
Theorems 2.4 and 2.5 help us formulate the simplex algorithm for problem (P) in
standard form:
Simplex Algorithm (starting at a feasible basic solution)

(1) Initialization
We start from a feasible tableau (as in 2.10) for problem (P).

(2) Choice of the pivot

a) pivot column index k:
Choose k ∈ {1, . . . , m} such that α0k < 0. If no such k exists, stop (the corre-
sponding basic solution is optimal).

b) pivot row index i:

Choose i ∈ {1, . . . , m} such that
 0 
b0i  bj
 
= min  . . . , α >
 
| j ∈ {1, m}, 0 (“quotient rule”).

jk
αik  α jk
 



If this is not possible, stop (the objective function is unbounded).

33
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

(3) Exchange step

Using the formulas for the exchange step, compute a new matrix with pivot αik .

α̂ik = 1
αik (pivot element)
α jk
α̂ jk = − αik (pivot column) j = 0, . . . , m, j,i
αi`
α̂i` = αik (pivot row) ` = 1, . . . , n, `,k
α jk ·αi`
α̂ j` = α j` − αik j = 0, . . . , m, j , i
` = 1, . . . , n, ` , k
b0i
b̂0i = αik
α jk ·b0i
b̂0j = bj − αik j = 1, . . . , m, j,i
α0k ·b0i
q̂0i = q0 − αik

 
column k 
↓

 α01 . . . α0n q0   α̂01 . . . α̂0n q̂0 

   
   
 α11 . . . α1n  α̂11 . . . α̂1n
   
 
   .   . −→  .. .
   
 .. α .
. 0
b 

 . .. 0
b̂ 

row i →   ik 

  
αm1 . . . αmn α̂m1 . . . α̂mn
   

Let    
 q0   q̂0 
  :=
  .
α b  α̂ b̂ 
   
 0  0

Convert the boundary of the matrix as follows:

Basis: Replace (xB )i by (xN )k
Non-Basis: Replace (xN )k by former (xB )i .
Go to step (2).

Example:
Maximize − 3x1 + 2x2 ,

subject to
x1 − x2 ≤ 1,
−2x1 + x2 ≤ 1,
−x1 + x2 ≤ 2,
x1 , x2 ≥ 0.

34
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

We introduce additional variables y j ≥ 0 (j = 1, 2, 3) and convert the problem to

standard form (2.9):
maximize z, subject to:
z + 3x1 − 2x2 = 0
y1 + x1 − x2 = 1
y2 − 2x1 + x2 = 1
y3 − x1 + x2 = 2
y1 , y2 , y3 ≥ 0, x1 , x2 ≥ 0.
We will apply the simplex method to the corresponding short and feasible tableau I:

I x1 x2 1 II x1 y2 1 III y3 y2 1
z 3 −2 0 z −1 2 2 z 1 1 3
y1 1 −1 1 → y1 −1 +1 2 → y1 1 0 3

y2 −2 1
1 x2 −2 1 1 x2 2 −1 3

y3 −1 1 2 y3 1
−1 1 x1 1 −1 1

Since α01 = 1 and α02 = 1, the basic solution to III is optimal:

y∗1 = 3, y∗2 = 0, y∗3 = 0, x∗1 = 1, x∗2 = 3, z∗ = 3.
Fig. 2.4 illustrates the process geometrically in the x1 , x2 -space.

Figure 2.4: Sketch of the simplex algorithm.

If we replace the objective function with z1 = x2 (z1 maximal), then the algorithm will
stop with the following tableau:
↑

35
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

III’ y3 y2
z1 2 −1 3
y1 1 0 3
x2 2 −1 3
x1 1 −1 1,
showing that the objective function is unbounded.

Exercise 2.6. Verify that one can indeed obtain Tableau III’ through pivoting steps
when using the objective max z = x2 .

Degenerate Basic Solutions

The basic solution corresponding to a tableau (2.10) (see page 30) is called degenerate,
if there is an index i ∈ 1, . . . , m, such that

(xB )i = b0i = 0.

If this is the case, the corresponding tableau is also called degenerate.

Theorem 2.7 (Finiteness of the Simplex Algorithm). If none of the feasible basic so-
lutions to (P) is degenerate, then the simplex algorithm will stop after a finite number of
steps.

Proof. The set of all tableaus to (P) and therefore also the set of all basic solutions is
finite. If the algorithm only computes non-degenerate feasible basic solutions, then the
objective value will increase strictly in every step (Theorem 2.4 (ii)). This implies that
after each step, a new basic solution is obtained. Because there is only a finite number
of basic solutions, the simplex algorithm must stop after a finite number of steps. 

At this point we give the following summarizing remarks. If there exists a feasible
basic solution and all feasible basic solutions are non-degenerate, then the simplex
algorithm either outputs an optimal basic solution, i.e., a geometrically optimal extreme
point, or it gives proof of the unboundedness of the objective function and of the feasible
region. However, we need to be able to handle the case of degenerate basic solutions as
well.

Anti-Cycling Techniques
When the simplex algorithm is applied to a tableau in which the pivot row has to be
chosen such that b0i = 0, then the exchange step will lead to a change in the tableau, but it
does not change the corresponding basic solution. In this situation it may happen, even

36
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

when the pivot choice is uniquely determined, that the algorithm can become cyclic.
The following example demonstrates this behavior.
Example:
Consider the problem

maximize z = 2x3 + 2x4 − 8x5 − 2x6 ,

subject to:
x2 − 7x3 − 3x4 + 7x5 + 2x6 = 0,
x1 + 2x3 + x4 − 3x5 − x6 = 0,
x j ≥ 0, j = 1, . . . , 6.
We will apply the simplex algorithm. We make the choice of the pivot so that when
several possibilities for the index exist, we choose the left most or up most, respectively,
index.
I x3 x4 x5 x6 1 II x1 x4 x5 x6 1
z −2 −2 8 2 0 z 1 −1 5 1 0

7 1
x2 −7 −3 7 2 0 x2 2 − 72 − 23 0
 2

1 1
x1 2
1 −3 −1 0 x3 2 2 − 32 − 21 0
B = (2, 1) B = (2, 3)

III x1 x2 x5 x6 1 IV x1 x2 x3 x6 1
z 8 2 −2 −2 0 z 5 1 1 −1 0

x4 7 2 −7 −3 0 x4 − 72 − 32 7
2
1
0
 2

x3 −3 −1 2
1 0 x5 − 32 − 12 1
2
1
2 0
B = (4, 3) B = (4, 5)

V x1 x2 x3 x4 1 VI x5 x2 x3 x4 1
z −2 −2 8 2 0 z 1 −1 5 1 0

7 1
x6 −7 −3 7 2 0 x6 2 − 72 − 32 0
 2

1 1
x5 2
1 −3 −1 0 x1 2 2 − 32 − 12 0
B = (6, 5) B = (6, 1)

VII x5 x6 x3 x4 1
z 8 2 −2 −2 0
x2 7 2 −7 −3 0
x1 −3 −1 2 1 0
B = (2, 1)

37
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

After six iterations we find a tableau with basis B = (2, 1) again. The tableaus will
keep changing in this cyclic order if we keep taking the same pivot choices. We can
circumvent this problem by using a specialized pivot choice. The following method is
known as “Bland’s Rule.”
We are given a feasible tableau and enumerate the variables 1, . . . , n + m. We fix the
pivot choice in the following order.

(a) pivot column: (degenerate case)

Choose column k with α0k < 0, whose corresponding variable index is minimum.

(b) pivot row:

Choose i ∈ {1, . . . , m} such that
 0 
b0i  bj
 
= min  . . . , α > .
 
j ∈ {1, m}, 0

jk
αik  α jk
 


If the tableau is degenerate, then choose that row i, for which the corresponding
variable has the smallest index.

Using “Bland’s Rule” in the above example leads to a different pivot choice in the
sixth tableau:
VI x5 x2 x3 x4 1
z 1 −1 5 1 0
7 1
x6 − 72 − 32 0
2  2
1 1
x1 2 − 32 − 12 0
2

↓

x5 x1 x3 x4 1
z 2 2 2 0 0
x6 3 −1 −2 −1 0
x2 1 2 −3 −1 0

B = (6, 2)
“Optimal tableau”
Practical experience shows, that the “modified” rule for the pivot choice increases the
running time of the simplex algorithm. On the other hand, countless practical examples
also show that the simplex algorithm with the simple pivot rule almost never gets stuck
in a degeneracy, because it almost always escapes it. It is therefore understandable,
that in programs for linear optimization it is the simple pivot choice which is used very
often. One way to get a practical pivot rule that is guaranteed not to get stuck is to
generally use the simple pivot rule and only change to a different rule, like Bland’s rule,

38
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

if the simple pivot rule does not strictly improve the objective value during a predefined
number of steps.
However, there are problem settings, e.g., in combinatorial optimization, in which
high degeneracies occur very often, and specialized pivot rules are often more efficient
than the simple pivot rule.

2.8 Finding a Feasible Basic Solution

As we have described the simplex algorithm so far, it “solves” the LP problem, if it
knows a feasible basic solution, i.e., if the right-hand side of the simplex tableau with
which we start is nonnegative. How do we, however, find a feasible basic solution, if
the right-hand side b has negative components?
As it is often done in mathematics, we reduce this problem to one that we already
know how to handle. In this case we consider the following auxiliary problem (in matrix
form):

minimize x0 ,
subject to:
Ax − e · x0 ≤ b
x ≥ 0, x0 ≥ 0,
where eT = (1, . . . , 1).
By letting x0 ≥ − min bi , we immediately obtain a feasible solution to the auxiliary
i=1,...,m
problem. Introducing slack variables xs the auxiliary problem can be written as:

minimize x0 ,
s.t. Ax + Ixs − e · x0 = b
x ≥ 0, xs ≥ 0, x0 ≥ 0.
Equivalently, we write

maximize −x0
s.t. Ax + Ixs − e · x0 = b
x ≥ 0, xs ≥ 0, x0 ≥ 0
and get the corresponding tableau:

x x0 1
f˜ 0 +1 0
−1
xs A −1 b
−1

39
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

Step 1
Bring x0 into the basis using an exchange step, so that the following tableau becomes
feasible.
⇒ pivot column x0
⇒ pivot row determined by the index r with min (bi ) = br .
i∈1,...,m
The pivot element is (−1) and from the pivot step we get:

b̂r = −br > 0 exchange step rules, and

b̂k = bk − (br ) ≥ 0 for k , r.
After this exchange step we get that the tableau is feasible for the auxiliary problem
and the optimal solution for the auxiliary problem can be found using the simplex
algorithm. We demonstrate this with the next example.
Example

maximize x1 − x2 + x3 , subject to

2x1 − x2 + 2x3 ≤ 4
2x1 − 3x2 + x3 ≤ −5
−x1 + x2 − 2x3 ≤ −1
x1 , x2 , x3 ≥ 0.
Corresponding auxiliary tableau:

maximize − x0 , subject to

2x1 − x2 + 2x3 − x0 ≤ 4
2x1 − 3x2 + x3 − x0 ≤ −5
−x1 + x2 − 2x3 − x0 ≤ −1
x1 , x2 , x3 , x0 ≥ 0.

Using the term f˜ we get:

↓
x1 x2 x3 x0 1
f˜ 0 0 0 1 0
x4 2 −1 2 −1 4
 
→ x5 2 −3 1 -1  −5
x6 −1 1 −2 −1 −1

40
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

↓
x1 x2 x3 x5 1
f˜ 2 −3 1 1 −5
x4 0 2 1 −1 9
x0 −2 3 −1 −1 5

→ x6 −3 4
−3 −1 4

↓
x1 x6 x3 x5 1
f˜ −0.25 +0.75 −1.25 0.25 −2
x4 1.5 −0.5 2.5 −0.5 7
 
→ x0 0.25 −0.75 1.25
  −0.25 2
x2 −0.75 0.25 −0.75 −0.25 1

x1 x6 x0 x5 1
f˜ 0 0 1 0 0
x4 1 1 −2 0 3
x3 0.2 −0.6 0.8 −0.2 1.6
x2 −0.6 −0.2 0.6 −0.4 2.2
The auxiliary tableau is optimal with optimal value 0. A feasible basic solution to the
original problem is
x1 = 0, x2 = 2.2, x3 = 1.6, x4 = 3, x5 = 0, x6 = 0
| {z }
Feasible basis {2,3,4} of the original problem.

In order to solve this problem starting at this basis, we have to convert the original
objective function with respect to the new basis.
Plugging in:
From the tableau we get (using x0 = 0)

x3 = −0.2x1 + 0.6x6 + 0.2x5 + 1.6,

x2 = 0.6x1 + 0.2x6 + 0.4x5 + 2.2.
By plugging in the above expressions for x2 and x3 into the objective function x1 −
x2 + x3 , we get:

x1 − (0.6x1 + 0.2x6 + 0.4x5 + 2.2)

+ (−0.2x1 + 0.6x6 + 0.2x5 + 1.6)
= 0.2x1 + 0.4x6 − 0.2x5 − 0.6.

41
Introduction to Mathematical Optimization, Fall 2015 Lecturer: Rico Zenklusen

Introducing z for the objective function we get the equation:

z − 0.2x1 − 0.4x6 + 0.2x5 = − 0.6,
which we put as the objective row in the short tableau.

x1 x6 x5 1
z −0.2 −0.4 0.2 −0.6
x4 1 1 0 3
x3 0.2 −0.6 −0.2 1.6
x2 −0.6 −0.2 −0.4 2.2
Starting from this feasible tableau, we can now apply the regular simplex algorithm.
Summary
(I) : If x0 = 0 holds in the optimal auxiliary tableau, then the original problem has a
feasible basic solution and the corresponding tableau (after x0 has been made non-basic)
is equivalent to the auxiliary tableau with respect to the original constraints, which we
obtain by deleting the x0 -column in the tableau.
The original objective function can be obtained by plugging in or by keeping it along
in the auxiliary tableau.
(II) : If x0 > 0 holds in the optimal auxiliary tableau, then the corresponding feasible
region (polyhedron) must be empty.

This method is known as the 2-phase simplex algorithm.

Phase 1: Determine feasibility of the problem using a auxiliary tableau.
Phase 2: Determine optimality or unboundedness.

Tableau (short) for 2-phase method, starting from the canonical form:
Ax ≤ b, x ≥ 0, b 6≥ 0.
cT x → max!

auxiliary column

↓
x x0 1
auxiliary row → f˜ 0 1 0 ← objective function Phase I

objective function → z −c 0 0 ← objective function Phase II

−1
xs A −1 b
−1

42