3Solutions of linear programs
IB Optimisation
3.5 Simplex method
The simplex metho d is an algorithm that makes use of the result we just had.
To find the optimal solution to a linear program, we start with a basic feasible
solution of the primal, and then modify the variables step by step until the dual
is also feasible.
We start with an example, showing what we do, then explain the logic behind,
then do a more proper example.
Example. Consider the following problem:
maximize x
1
+ x
2
subject to
x
1
+ 2x
2
+ z
1
= 6
x
1
− x
2
+ z
2
= 3
x
1
, x
2
, z
1
, z
2
≥ 0.
We write everything in the simplex tableau, by noting down the coefficients:
x
1
x
2
z
1
z
2
Constraint 1 1 2 1 0 6
Constraint 2 1 -1 0 1 3
Objective 1 1 0 0 0
We see an identity matrix
1 0
0 1
in the
z
1
and
z
2
columns, and these correspond
to basic feasible solution: z
1
= 6, z
2
= 3, x
1
= x
2
= 0. It’s pretty clear that our
basic feasible solution is not optimal, since our objective function is 0. This is
since something in the last row is positive, and we can increase the objective by,
say, increasing x
1
.
The simplex method says that we can find the optimal solution if we make
the bottom row all negative while keeping the right column positive, by doing
row operations.
We multiply the first row by
1
2
and subtract/add it to the other rows to
obtain
x
1
x
2
z
1
z
2
Constraint 1
1
2
1
1
2
0 3
Constraint 2
2
3
0
1
2
1 6
Objective
1
2
0 −
1
2
0 -3
Our new basic feasible solution is
x
2
= 3
, z
2
= 6
, x
1
=
z
1
= 0. We see that the
number in the bottom-right corner is
−f
(
x
). We can continue this process to
finally obtain a solution.
Here we adopt the following notation: let
A ⊆ R
m×n
and
b ∈ R
m
. Assume
that
A
has full rank. Let
B
be a basis and set
B ⊆ {
1
,
2
, · · · , n}
with
|B|
=
m
,
corresponding to at most m non-zero entries.
We rearrange the columns so that all basis columns are on the left. Then we
can write our matrices as
A
m×n
=
(A
B
)
m×m
(A
N
)
m×(n−m)
x
n×1
=
(x
B
)
m×1
(x
N
)
(n−m)×1
T
c
1×n
=
(c
B
)
m×1
(c
N
)
(n−m)×1
.
Then the functional constraints
Ax = b
can be decomposed as
A
B
x
B
+ A
N
x
N
= b.
We can rearrange this to obtain
x
B
= A
−1
B
(b − A
N
x
N
).
In particular, when x
N
= 0, then
x
B
= A
−1
B
b.
The general tableau is then
Basis components Other components
A
−1
B
A
B
= I A
−1
B
A
N
A
−1
B
b
c
T
B
− c
T
B
A
−1
B
A
B
= 0 c
T
N
− c
T
B
A
−1
B
A
N
−c
T
B
A
−1
B
b
This might look really scary, and it is! Without caring too much about how the
formulas for the cells come from, we see the identity matrix on the left, which is
where we find our basic feasible solution. Below that is the row for the objective
function. The values of this row must be 0 for the basis columns.
On the right-most column, we have
A
−1
B
b
, which is our
x
B
. Below that is
−c
T
B
A
−1
B
b, which is the negative of our objective function c
T
B
x
B
.
3.5.1 The simplex tableau
We have
f(x) = c
T
x
= c
T
B
x
B
+ c
T
N
x
N
= c
T
B
A
−1
B
(b − A
N
x
N
) + c
T
N
x
N
= c
T
B
A
−1
B
b + (c
T
N
− c
T
B
A
−1
B
A
N
)x
N
.
We will maximize
c
T
x
by choosing a basis such that
c
T
N
− c
T
B
A
−1
B
A
N
≤
0, i.e.
non-positive everywhere and A
−1
B
b ≥ 0.
If this is true, then for any feasible solution
x ∈ R
n
, we must have
x
N
≥
0.
So (c
T
N
− c
T
B
A
−1
B
A
N
)x
N
≤ 0 and
f(x) ≤ c
T
B
A
−1
B
b.
So if we choose x
B
= A
−1
B
b, x
N
= 0, then we have an optimal solution.
Hence our objective is to pick a basis that makes
c
T
N
− c
T
B
A
−1
B
A
N
≤
0
while keeping
A
−1
B
b ≥
0. To do this, suppose this is not attained. Say (
c
T
N
−
c
T
B
A
−1
B
A
N
)
i
> 0.
We can increase the value of the objective function by increasing (
x
N
)
i
. As
we increase (
x
N
)
i
, we have to satisfy the functional constraints. So the value of
other variables will change as well. We can keep increasing (
x
N
)
i
until another
variable hits 0, say (x
B
)
j
. Then we will have to stop.
(However, if it so happens that we can increase (
x
N
)
i
indefinitely without
other things hitting 0, our problem is unbounded)
The effect of this is that we have switched basis by removing (
x
B
)
j
and
adding (
x
N
)
i
. We can continue from here. If (
c
T
N
− c
T
B
A
−1
B
A
N
) is negative, we
are done. Otherwise, we continue the above procedure.
The simplex method is a systematic way of doing the above procedure.
3.5.2 Using the Tableau
Consider a tableau of the form
a
ij
a
i0
a
0j
a
00
where a
i0
is b, a
0j
corresponds to the objective function, and a
00
is initial 0.
The simplex method proceeds as follows:
(i) Find an initial basic feasible solution.
(ii)
Check whether
a
0j
≤
0 for every
j
. If so, the current solution is optimal.
Stop.
(iii)
If not, choose a pivot column
j
such that
a
0j
>
0. Choose a pivot row
i ∈ {i
:
a
ij
>
0
}
that minimizes
a
i0
/a
ij
. If multiple rows are minimize
a
i0
/a
ij
, then the problem is degenerate, and things might go wrong. If
a
ij
≤
0 for all
i
, i.e. we cannot choose a pivot row, the problem is unbounded,
and we stop.
(iv)
We update the tableau by multiplying row
i
by 1
/a
ij
(such that the new
a
ij
= 1), and add a (
−a
kj
/a
ij
) multiple of row
i
to each row
k 6
=
i
,
including k = 0 (so that a
kj
= 0 for all k 6= i)
We have a basic feasible solution, since our choice of
a
ij
makes all right-hand
columns positive after subtracting (apart from a
00
).
(v) GOTO (ii).
Now visit the example at the beginning of the section to see how this is done
in practice. Then read the next section for a more complicated example.