68 Introduction to Linear Optimization and Extensions with MATLAB
R
the extreme directions of P . Then, by the Resolution Theorem, every point
x ∈ P can be expressed as x =
P
k
i=1
λ
i
v
i
+
P
l
i=1
µ
i
d
i
where λ
1
, ..., λ
k
≥ 0
and
P
k
i=1
λ
i
= 1 and µ
i
≥ 0 for i = 1, ..., l. Without loss of generality, let
d =
P
l
i=1
µ
i
d
i
, which is a recession direction by Corollary 2.27. There are two
cases.
Case (1) d is such that c
T
d < 0. In this case, for any x
0
∈ P , the ray r =
{x ∈ R
n
|x
0
+ λd for λ ∈ [0, 1]} ⊂ P will be such that c
T
x = c
T
x
0
+ λc
T
d and
this can be made to diverge toward −∞ as λ → ∞ since c
T
d < 0 and λ ≥ 0.
Case (2) d is such that c
T
d ≥ 0. So x =
P
k
i=1
λ
i
v
i
+ d where λ
1
, ..., λ
k
≥ 0
and
P
k
i=1
λ
i
= 1. Now let v
min
be that extreme point that results in the
minimum value of c
T
v
i
over ...