Engineering Optimization: Theory and Practice, Fourth Edition

600 Integer Programming

where

a+ij=

{

aij if aij≥ 0

0 if aij< 0

(10.11)

a−ij=

{

0 if aij≥ 0

aij if aij< 0

(10.12)

Eq. (10.2) can be rewritten as

∑n

j= 1

(a+ij+ai−j)yj=βi+(bˆi−xi) (10.13)

Here, by assumption,xiis restricted to integer values whilebiis not an integer. Since

0 <βi< and 1 bˆiis an integer, we can have the value ofβi+(bˆi−xi) ithere ≥0 or

<0. First, we consider the case where

βi+(bˆi−xi)≥ 0 (10.14)

In this case, in order forxito be an integer, we must have

βi+(bˆi−xi)=βi or βi+ 1 or βi+ 2 ,... (10.15)

Thus Eq. (10.13) gives

∑n

j= 1

(a+ij+a−ij)yj≥βi (10.16)

Sinceaijare nonpositive andyjare nonnegative by definition, we have

∑n

j= 1

a+ijyj≥

∑n

j= 1

(ai+j−a−ij)yj (10.17)

and hence

∑n

j= 1

a+ijyj≥βi (10.18)

Next, we consider the case where

βi+(bˆi−xi) < 0 (10.19)

Forxito be an integer, we must have (since 0<βi< ) 1

βi+(bˆi−xi) =− 1 +βi or − 2 +βi or − 3 +βi,... (10.20)