The name is absent

26

where a₁ = (3, —2)^τ, α₂ = ( —l,4)^τ, α₃ = (—5, — 8)^τ, α₄ = (3,2)^τ, and a₅ =
(O, — 4)^τ, b₁ = 2, b₂ = 3, b₃ = —4, δ₄ = 4, and b₅ = —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 R² I ɑʃæ ≤ b_i, i = 1, ∙ ∙ ∙ , 5 }

where α₁ = (3, —2)^τ, α₂ = ( —l,2)^τ, α₃ = ( —1, —2)^τ, α₄ = (0,5)^τ, and a₅ =
(0, — 5)^τ, δι = 6, b₂ = 2, b₃ = 0, δ₄ = 4, and b₅ = —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 R² I af^γ x ≤ lχ. i = 1,2, 3,4 }

where ɑɪ = (2, — l)^τ, a₂ = ( —1, 2)^τ a₃ = (0, —2)^τ, and α₄ = (—10,0)^τ, b₁ = 4,
b₂ = — 2, b₃ = 3, and δ₄ = 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 c^l ∈ C^,₁, υ² ∈ C^,₂, and v³ ∈ C₃.
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 v^k E C∖. Take for instance к = 3
and V = (—2, — 3)^τ. The algorithm finds an integral point in C^,₃, 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 Rⁿ is ^-dimensional
and that none of the constraints of x ≤ bi is redundant. If the set P is a lower-

<<   25   26   27   28   29   30   31   >>

More intriguing information