Proof: The first part can be derived by induction. The second part follows from
the same line of the proof of Theorem 2.2. □
We point out that all theorems above will be constructively demonstrated by
the algorithm to be presented in the next section. Let us give some examples.
Example 1. We are given
P = { x ∈ R2 I ajx ≤ bi, i = 1, 2, 3 }
where α1 = (3,2)τ, α2 = (1, — l)τ and α3 = (—3, — l)τ, b1 = 1, b2 = — 1 and
b3 = 1. This example is shown in Figure 1 where there are three completely labeled
simplices. One of them is of type II. The other two are of type I.
Example 2. We are given
P = { X ∈ R2 I ajx ≤ bi, i = 1,2, 3 }
where α1 = (2, — l)τ, α2 = (3, l)τ and α3 = (—3,0)τ, b1 = 1, b2 = 2 and b3 = —1.
This example is illustrated in Figure 2 where there is a unique completely labeled
simplex of type II.
3 The algorithm
In this section we shall discuss how to operate the algorithm to End a completely
labeled simplex within a finite number of steps. In the rest of the section we assume
that the simplex P associated with matrix A is given such that
a. β(n+ιp ≤ 0 for j = 1, ∙ ∙ ∙, n∙,
b. ац > 0 for i = 1, ∙ ∙ ∙, n;
c. Ciij ≤ 0 and ∖aij I < ац for i ψ j, i, j = 1, ∙ ∙ ∙, n.