3Solutions of linear programs

IB Optimisation

3.2 Basic solutions

Here we will assume that the rows of

A

are linearly independent, and any set

of

m

columns are linearly independent. Otherwise, we can just throw away the

redundant rows or columns.

In general, if both the constraints and the objective functions are linear, then

the optimal point always lies on a “corner”, or an extreme point.

Definition

(Extreme point)

.

An extreme point

x ∈ S

of a convex set

S

is a

point that cannot be written as a convex combination of two distinct points in

S, i.e. if y, z ∈ S and δ ∈ (0, 1) satisfy

x = δy + (1 − δ)z,

then x = y = z.

Consider again the linear program in standard form, i.e.

maximize c

T

x subject to Ax = b, x ≥ 0, where A ∈ R

m×n

and b ∈ R

m

.

Note that now we are talking about maximization instead of minimization.

Definition

(Basic solution and basis)

.

A solution

x ∈ R

n

is basic if it has at

most

m

non-zero entries (out of

n

), i.e. if there exists a set

B ⊆ {

1

, · · · , n}

with

|B|

=

m

such that

x

i

= 0 if

i 6∈ B

. In this case,

B

is called the basis, and

x

i

are

the basic variables if i ∈ B.

We will later see (via an example) that basic solutions correspond to solutions

at the “corners” of the solution space.

Definition

(Non-degenerate solutions)

.

A basic solution is non-degenerate if it

has exactly m non-zero entries.

Note that by “solution”, we do not mean a solution to the whole maximization

problem. Instead we are referring to a solution to the constraint

Ax

=

b

. Being a

solution does not require that

x ≥

0. Those that satisfy this regional constraint

are know n as feasible.

Definition

(Basic feasible solution)

.

A basic solution

x

is feasible if it satisfies

x ≥ 0.

Example. Consider the linear program

maximize f(x) = 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

where we have included the slack variables.

Since we have 2 constraints, a basic solution would require 2 non-zero entries,

and thus 2 zero entries. The possible basic solutions are

x

1

x

2

z

1

z

2

f(x)

A 0 0 6 3 0

B 0 3 0 6 3

C 4 1 0 0 5

D 3 0 3 0 3

E 6 0 0 −4 6

F 0 −3 12 0 −3

Among all 6,

E

and

F

are not feasible solutions since they have negative entries.

So the basic feasible solutions are A, B, C, D.

A B

C

D

x

1

x

2

x

1

− x

2

= 3

x

1

+ 2x

2

= 6

E

F

In previous example, we saw that the extreme points are exactly the basic

feasible solutions. This is true in general.

Theorem.

A vector

x

is a basic feasible solution of

Ax

=

b

if and only if it is

an extreme point of the set X(b) = {x

0

: Ax

0

= b, x

0

≥ 0}.

We will not prove this.