10
The geometric context of the next theorem can be easily understood in two
dimension.
Theorem 3.5 Exclusion Theorem
Let a simplex P be given in standard form with the additional condition that
ff1≠i ∣t¾∣ < aa holds for all i = 1, , n. Then the Labeling Rule precludes the
possibility of the coexistence of a completely labeled simplex of type I and a com-
pletely labeled simplex of type II. If P contains an integral point, then there exists
no completely labeled simplex of type II.
Proof: We only need to consider the case in which P contains an integral point,
say æ0, i.e., Ax0 ≤ b. Let us suppose to the contrary that there is a completely
labeled simplex of type II, say σ(⅛1,π) with vertices x1, ■■■, xn+1, where π =
(τr(l), ∙ ∙ ∙ , π(n ⅛ 1)) is a permutation of the n ⅛ 1 elments of N, and
xt+1 = xt ⅛ q(π(if), i = 1, ∙ ∙ ∙ , n;
x1 = xn+1 + q(π(n + 1)).
Now it is easy to see that there exist nonnegative integers k^, ∙ ∙ ∙, such that
x1 = x° + ∑ k⅛(i),
ieN
and
min kl = 0.
heN n
Let
I = argmin{ π 1(∕z) ∣ kjl = max: k1j
Then there exist nonnegative integers kt1, ■ ■ - , ktn+1 such that
xt = x0 + ∑ ktjq(f)
j∈N