Graphics Reference
In-Depth Information
The most famous method for solving linear programming problems is the
simplex
method
, due to Danzig. A highly readable presentation of the simplex method is given
in [Chvatal83]. When the LP problems are, as here, of low dimension and with few
constraints, other (simpler) methods are often preferred. One such method, and the
one presented here, is a randomized algorithm due to [Seidel90]. Before describing
Seidel's algorithm, another even simpler algorithm is introduced. This algorithm,
Fourier-Motzkin elimination, gives further insight into the problem of determining
whether a set of inequality constraints provides a feasible solution. (Fourier-Motzkin
elimination is also the method of choice for solving small systems by hand.)
9.4.1.1 Fourier-Motzkin Elimination
A simple approach for determining the consistency of a system of linear inequalities
is the method known as
Fourier-Motzkin elimination
. It operates by successive rewrites
of the system, eliminating one variable from the system on each rewrite. When only
one variable is left, the system is trivially consistent if the largest lower bound for the
variable is less than the smallest upper bound for the variable. More specifically, let
the system be given as
m
constraints in
n
variables:
a
11
x
1
+
a
12
x
2
+
...
+
a
1
n
x
n
≤
b
1
a
21
x
1
+
a
22
x
2
+
...
+
a
2
n
x
n
≤
b
2
.
a
m
1
x
1
+
a
m
2
x
2
+
...
+
a
mn
x
n
≤
b
m
A variable
x
k
is selected for elimination and each inequality is “solved” for
x
k
,
resulting in
s
lower and
t
upper bounds on
x
k
:
L
1
(
x
1
,
x
2
,
...
,
x
k
−
1
,
x
k
+
1
,
...
,
x
n
)
≤
x
k
x
k
≤
U
1
(
x
1
,
x
2
,
...
,
x
k
−
1
,
x
k
+
1
,
...
,
x
n
)
L
2
(
x
1
,
x
2
,
...
,
x
k
−
1
,
x
k
+
1
,
...
,
x
n
)
≤
x
k
x
k
≤
U
2
(
x
1
,
x
2
,
...
,
x
k
−
1
,
x
k
+
1
,
...
,
x
n
)
.
.
L
s
(
x
1
,
x
2
,
...
,
x
k
−
1
,
x
k
+
1
,
...
,
x
n
)
≤
x
k
x
k
≤
U
t
(
x
1
,
x
2
,
...
,
x
k
−
1
,
x
k
+
1
,
...
,
x
n
)
Because every lower bound on
x
k
must be less than or equal to every upper bound
on
x
k
, it is possible to completely eliminate
x
k
by replacing the current set of inequal-
ities with a new set of
st
inequalities formed by all pairwise combinations of lower
and upper bounds for
x
k
. That is,
L
i
(
x
1
,
x
2
,
...
,
x
k
−
1
,
x
k
+
1
,
...
,
x
n
)
≤
U
j
(
x
1
,
x
2
,
...
,
x
k
−
1
,
x
k
+
1
,
...
,
x
n
)
≤
≤
≤
≤
for all 1
i
s
,1
j
t
.
