The name is absent

28

(H) H ¹C is an integer matrix.

A polynomial-time algorithm for finding U and H can be also found in [8, 13]. Now
let H and U = (tʃɪ, U₂) be as in Theorem 6.2, with U₁ an n × m¹ matrix and U₂ an
n × (n — m¹) matrix.

Theorem 6.3

(i) Q is nonempty if and only if H~¹d ∈ Z^ml.

(H) IfQ is nonempty, every point x of Q can be written as

x = U₁H~¹d + U₂z, for some z ∈ Zⁿ~^ml.

When Q is nonempty, we have

Po = { У ∈ Rⁿ I AU у ≤ b, and CUy = d}

= {y ∈ Rⁿ   I AU у ≤ b, and [H, Q]y = d }

= { У ∈ Rⁿ   I У = ((B^¹d)^τ, z^γ)∖

and AU(fH~¹d)∖z^τ)^τ <b,zE pⁿ~^ml ɪ

= {y ∈ Rⁿ I у = ((H~¹d)∖ z^τ)^τ, and Az <b, z E Rⁿ~^ml }.

Let

P = {z ∈ Rⁿ~^ml ∖Az<b}.

Doing so leads to an (n — m¹)-dimensional polytope P in Rⁿ~^mλ. Now the remaining
discussions are the same as in the previous section. Let us demonstrate this by an
example. We are given a polytope

P = { x ∈ R³ I af x ≤ b_i, i = 1, 2, 3, and c₁x = d₁},

where a₁ = (—1,0, 0)^τ, a₂ = (0,-1, 0)^τ, a₃ = (0,0,—l)^τ, c₁ = (4,12,2)^τ, b₁ = 0,
b₂ = 0, b₃ = 1, and d₁ = 2. Then we have

C = [4 12 2],

<<   27   28   29   30   31   32   33   >>

More intriguing information