Engineering Optimization: Theory and Practice, Fourth Edition

628 Integer Programming

10.3 Maximizef=^4 x 1 +^3 x 2

subject to

3 x 1 + 2 x 2 ≤ 18

x 1 , x 2 ≥ 0 ,integers

10.4 Maximizef=^3 x 1 −x 2

subject to

3 x 1 − 2 x 2 ≤ 3

− 5 x 1 − 4 x 2 ≤ − 10

x 1 , x 2 ≥ 0 ,integers

10.5 Maximizef=^2 x 1 +x 2

subject to

8 x 1 + 5 x 2 ≤ 15

x 1 , x 2 ≥ 0 ,integers

10.6 Solve the following problem using Gomory’s cutting plane method:

Maximizef= 6 x 1 + 7 x 2

subject to

7 x 1 + 6 x 2 ≤ 42

5 x 1 + 9 x 2 ≤ 45

x 1 −x 2 ≤ 4

xi≥0 and integer, i= 1 , 2

10.7 Solve the following problem using Gomory’s cutting plane method:

Maximizef=x 1 + 2 x 2

subject to

x 1 +x 2 ≤ 7

2 x 1 ≤ 11 , 2 x 2 ≤ 7

xi≥0 and integer, i= 1 , 2

10.8 Express 187 in binary form.

10.9 Three citiesA,B, andCare to be connected by a pipeline. The distances betweenAand

B,BandC, andCandAare 5, 3, and 4 units, respectively. The following restrictions

are to be satisfied by the pipeline:

1.The pipes leading out ofAshould have a total capacity of at least 3.