The name is absent

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 x¹ and x², it also contains the integral point

x = (max{æj, ʃɪ),∙∙∙, max{⅛, x²_n})^τ.

Proof: Since P contains two integral points æ¹ and æ², it implies that Ax¹ ≤ b and

Ax² ≤ 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χ{³j? ³j} ≤ b_n+l,
j=ι

i.e., ∑2j=ι ^α(n+ι)j^j ≤ ⅛ι÷ι∙ Moreover, for h = 1, 2, it holds that

n

∑^az₃%^h₃ <b_i,i = 1,∙ ∙ ∙ ,n.

J = I

Since (⅛ ≤ 0 for j ψ i, it is easy to see that

⅛ - ∑₃≠_l <pj∑₃

b_l - ∑₃≠_t a_lj max{x_j¹, x²}

b_i - ∑₃≠_t a_l3x₃

for i = l,...,n. It means that

a_llx_l ≤ b_t - ]Γ ¾j⅜'
J≠i

<<   4   5   6   7   8   9   10   >>

More intriguing information