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.