Such a formulation of the polytope P is referred to as the standard form. Observe
that the standard form is rather similar to the well-known Hermite normal form (see
e.g., Section 6). In the next section we shall show that any n-dimensional simplex
P can be restructured into the standard form. We first derive the following lemma.
Lemma 3.1 Let a simplex P be given in standard form. If P contains two
integral points x1 and x2, it also contains the integral point
x = (max{æj, ʃɪ),∙∙∙, max{⅛, x2n})τ.
Proof: Since P contains two integral points æ1 and æ2, it implies that Ax1 ≤ b and
Ax2 ≤ b. Notice that
n
≤ 7,÷∣∙
J = I
and
n
j — ¼ι+l∙
7 = 1
Since α(n+ι)j ≤ 0 for j = 1, ∙ ∙ ∙, n, it follows that
n
α(n+ι)j maχ{3j? 3j} ≤ bn+l,
j=ι
i.e., ∑2j=ι α(n+ι)j^j ≤ ⅛ι÷ι∙ Moreover, for h = 1, 2, it holds that
n
∑az3%h3 <bi,i = 1,∙ ∙ ∙ ,n.
J = I
Since (⅛ ≤ 0 for j ψ i, it is easy to see that
⅛ - ∑3≠l <pj∑3
bl - ∑3≠t alj max{xj1, x2}
bi - ∑3≠t al3x3
for i = l,...,n. It means that
allxl ≤ bt - ]Γ ¾j⅜'
J≠i