3Solutions of linear programs
IB Optimisation
3.6 The two-phase simplex method
Sometimes we don’t have a nice identity matrix to start with. In this case, we
need to use the two-phase simplex method to first find our first basic feasible
solution, then to the actual optimization.
This method is illustrated by example.
Example. Consider the problem
minimize 6x
1
+ 3x
2
subject to
x
1
+ x
2
≥ 1
2x
1
− x
2
≥ 1
3x
2
≤ 2
x
1
, x
2
≥ 0
This is a minimization problem. To avoid being confused, we maximize
−
6
x
1
−
3
x
2
instead. We add slack variables to obtain
maximize −6x
1
− 3x
2
subject to
x
1
+ x
2
− z
1
= 1
2x
1
− x
2
− z
2
= 1
3x
2
+ z
3
= 2
x
1
, x
2
, z
1
, z
2
, z
3
≥ 0
Now we don’t have a basic feasible solution, since we would need
z
1
=
z
2
=
−
1
, z
3
= 2, which is not feasible. So we add more variables, called the artificial
variables.
maximize −6x
1
− 3x
2
subject to
x
1
+ x
2
− z
1
+ y
1
= 1
2x
1
− x
2
− z
2
+ y
2
= 1
3x
2
+ z
3
= 2
x
1
, x
2
, z
1
, z
2
, z
3
, y
1
, y
2
≥ 0
Note that adding
y
1
and
y
2
might create new solutions, which is bad. We solve
this problem by first trying to make
y
1
and
y
2
both 0 and find a basic feasible
solution. Then we can throw away
y
1
and
y
2
and then get a basic feasible for
our original problem. So momentarily, we want to solve
minimize y
1
+ y
2
subject to
x
1
+ x
2
− z
1
+ y
1
= 1
2x
1
− x
2
− z
2
+ y
2
= 1
3x
2
+ z
3
= 2
x
1
, x
2
, z
1
, z
2
, z
3
, y
1
, y
2
≥ 0
By minimizing y
1
and y
2
, we will make them zero.
Our simplex tableau is
x
1
x
2
z
1
z
2
z
3
y
1
y
2
1 1 -1 0 0 1 0 1
2 -1 0 -1 0 0 1 1
0 3 0 0 1 0 0 2
-6 -3 0 0 0 0 0 0
0 0 0 0 0 -1 -1 0
Note that we keep both our original and “kill-
y
i
” objectives, but now we only
care about the second one. We will keep track of the original objective so that
we can use it in the second phase.
We see an initial feasible solution
y
1
=
y
2
= 1
, z
3
= 2. However, this is not a
proper simplex tableau, as the basis columns should not have non-zero entries
(apart from the identity matrix itself). But we have the two
−
1s at the bottom!
So we add the first two rows to the last to obtain
x
1
x
2
z
1
z
2
z
3
y
1
y
2
1 1 -1 0 0 1 0 1
2 -1 0 -1 0 0 1 1
0 3 0 0 1 0 0 2
-6 -3 0 0 0 0 0 0
3 0 -1 -1 0 0 0 2
Our pivot column is
x
1
, and our pivot row is the second row. We divide it by 1
and add/subtract it from other rows.
x
1
x
2
z
1
z
2
z
3
y
1
y
2
0
3
2
-1
1
2
0 1 −
1
2
1
2
1 −
1
2
0 −
1
2
0 0
1
2
1
2
0 3 0 0 1 0 0 2
0 -6 0 -3 0 0 3 3
0
3
2
−1
1
2
0 0 −
3
2
1
2
There are two possible pivot columns. We pick
z
2
and use the first row as the
pivot row.
x
1
x
2
z
1
z
2
z
3
y
1
y
2
0 3 -2 1 0 2 -1 1
1 1 -1 0 0 1 0 1
0 3 0 0 1 0 0 2
0 3 -6 0 0 6 0 6
0 0 0 0 0 -1 -1 0
We see that
y
1
and
y
2
are no longer in the basis, and hence take value 0. So we
drop all the phase I stuff, and are left with
x
1
x
2
z
1
z
2
z
3
0 3 -2 1 0 1
1 1 -1 0 0 1
0 3 0 0 1 2
0 3 -6 0 0 6
We see a basic feasible solution z
1
= x
1
= 1, z
3
= 2.
We pick
x
2
as the pivot column, and the first row as the pivot row. Then we
have
x
1
x
2
z
1
z
2
z
3
0 1 −
2
3
1
3
0
1
3
1 0 −
1
3
−
1
3
0
2
3
0 0 2 -1 1 1
0 0 -4 -1 0 5
Since the last row is all negative, we have complementary slackness. So this
is a optimal solution. So
x
1
=
2
3
, x
2
=
1
3
, z
3
= 1 is a feasible solution, and our
optimal value is 5.
Note that we previously said that the bottom right entry is the negative
of the optimal value, not the optimal value itself! This is correct, since in the
tableau, we are maximizing
−
6
x
1
−
3
x
2
, whose maximum value is
−
5. So the
minimum value of 6x
1
+ 3x
2
is 5.