13
If ɑɪæ — bfl > O for all h ∈ N~∣s, then the label /(æ) = 0 is assigned to x.
Now we can apply the algorithm by using Γ(.) and q(.) instead of Z(.) and q(,~). It
is easy to verify that the algorithm will find an integral point in C,⅛ within a finite
number of steps. We are led to the following result.
Theorem 3.7 Let a simplex P be given in standard form. The procedure ter-
minates with either an integral point in P or a completely labeled simplex of type II
which shows that there is no integral point in P, within a finite number of iterations.
A proof of the above theorem will be given in the next section. Let us illustrate the
algorithm by some examples.
Example 3. The polytope is given by
P = { X ∈ R2 I ajx ≤ bi, i = 1, 2, 3 },
where ɑɪ = (2, — l)τ, α2 = ( —l,3)τ, and α3 = ( —1, — l)τ, b1 = 1, δ2 = —1,
and b3 = 1. The paths generated by the algorithm lead from cl = (4, —4)τ and
v2 = (4,4)τ to the integral point (0, — l)τ in P, respectively, and are shown in
Figure 3.
Example 4. The polytope is given by
P = { X ∈ R2 I ajx ≤ bi, i = 1, 2, 3 },
where ɑɪ = (5, — l)τ, α2 = (0, l)τ, and α3 = (—3,0)τ, b1 = 1, δ2 = 2, and b3 =
— 1. The path generated by the algorithm leads from v = (4, —4)τ to the unique
completely labeled simplex of type II and is demonstrated in Figure 4.
4 Reformulation
In order to conform to the standard form, let us come back to the original problem.
We are given an n-dimensional simplex
P = {x E Rn∖Ax <b},