26
where a1 = (3, —2)τ, α2 = ( —l,4)τ, α3 = (—5, — 8)τ, α4 = (3,2)τ, and a5 =
(O, — 4)τ, b1 = 2, b2 = 3, b3 = —4, δ4 = 4, and b5 = —1. This example is illustrated
in Figure 8 where there is a unique completely labeled simplex of type II.
Example 12. We are given
P = { x E R2 I ɑʃæ ≤ bi, i = 1, ∙ ∙ ∙ , 5 }
where α1 = (3, —2)τ, α2 = ( —l,2)τ, α3 = ( —1, —2)τ, α4 = (0,5)τ, and a5 =
(0, — 5)τ, δι = 6, b2 = 2, b3 = 0, δ4 = 4, and b5 = —1. This example is depicted in
Figure 9 where there is a unique completely labeled simplex of type II.
Example 13. We are given
P = { x E R2 I afγ x ≤ lχ. i = 1,2, 3,4 }
where ɑɪ = (2, — l)τ, a2 = ( —1, 2)τ a3 = (0, —2)τ, and α4 = (—10,0)τ, b1 = 4,
b2 = — 2, b3 = 3, and δ4 = 11. This example is shown in Figure 10 where there are
three completely labeled simplices. One of them is of type II. The other two are of
type I. The procedure is shown in Figure 10 where cl ∈ C,1, υ2 ∈ C,2, and v3 ∈ C3.
The procedure leads to the integral point (2, 0)τ. Using the same example, we also
illustrate in Figure 11 how to End a starting point vk E C∖. Take for instance к = 3
and V = (—2, — 3)τ. The algorithm finds an integral point in C,3, namely, (3, l)τ.
We conclude with the following observation.
Theorem 5.3 Given a polytope P in standard form, the procedure terminates
either with an integral point in P or a completely labeled simplex of type II which
proves there is no integral point in P, within a finite number of steps.
6 Extension to lower-dimensional polytopes
In the previous section we assumed that the polytope P in Rn is ^-dimensional
and that none of the constraints of x ≤ bi is redundant. If the set P is a lower-