The name is absent

13

If ɑɪæ — bf_l > 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 ∈ R² I ajx ≤ b_i, i = 1, 2, 3 },

where ɑɪ = (2, — l)^τ, α₂ = ( —l,3)^τ, and α₃ = ( —1, — l)^τ, b₁ = 1, δ₂ = —1,
and b₃ = 1. The paths generated by the algorithm lead from c^l = (4, —4)^τ and
v² = (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 ∈ R² I ajx ≤ b_i, i = 1, 2, 3 },

where ɑɪ = (5, — l)^τ, α₂ = (0, l)^τ, and α₃ = (—3,0)^τ, b₁ = 1, δ₂ = 2, and b₃ =
— 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 Rⁿ∖Ax <b},

<<   12   13   14   15   16   17   18   >>

More intriguing information