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.