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.