25
If afx ≤ bfl for all h ∈ M, then /(æ) = 0.
As before, we have the following results.
Theorem 5.1 If P does not contain any integral point, then the Generalized
Labeling Rule results in a unique completely labeled simplex. Moreover, the unique
completely labeled simplex must be of type II.
Theorem 5.2 If P contains an integral point, then the Generalized Labeling
Rule results in at least two completely labeled simplices. Moreover, there exists at
most one completely labeled simplex of type II.
Correspondingly, we can reformulate any п-dimensional polytope P into the stan-
dard form, meaning that the first n ⅛ 1 rows of the matrix A satisfy the conditions
(a), (b) and (c) as defined in Section 3. Observe that the standard form does not
impose any condition on the constraint vectors c⅛ for i ∈ M∖N. This indicates
that if we transform the problems into the standard form, we only need to focus on
the first n + 1 constraint vectors and then postmultiply the remaining constraint
vectors by the resulting unimodular matrix U.
Now we can directly apply the procedure to polytopes. Let us give some exam-
ples.
Example 10. We are given
P = { X ∈ R2 I aj x ≤ bi, i = 1, ∙ ∙ ∙, 5 }
where ɑɪ = (2, — l)τ, α2 = (—l,3)τ, α3 = ( —1, —2)τ, α4 = (2, l)τ, and α5 =
(—2, 0)τ, δι = 1, ⅛ = ɜ, ⅛ = 2, δ4 = 2, and b5 = 3. This example is shown in
Figure 7 where there are three completely labeled simplices of type I.
Example 11. We are given
P = { X E R2 I ɑɪx ≤ bi, i = 1, ∙ ∙ ∙, 5 }