Engineering Optimization: Theory and Practice, Fourth Edition

Problems 629

2.The pipes leading out ofBor ofCshould have total capacities of either 2 or 3.

3.No pipe between any two cities must have a capacity exceeding 2.

Only pipes of an integer number of capacity units are available and the cost of a pipe is

proportional to its capacity and to its length. Determine the capacities of the pipe lines

to minimize the total cost.

10.10 Convert the following integer quadratic problem into a zero–one linear programming
problem:
Minimizef= 2 x 12 + 3 x 22 + 4 x 1 x 2 − 6 x 1 − 3 x 2

subject to

x 1 +x 2 ≤ 1

2 x 1 + 3 x 2 ≤ 4

x 1 , x 2 ≥ 0 ,integers

10.11 Convert the following integer programming problem into an equivalent zero–one pro-
gramming problem:
Minimizef= 6 x 1 −x 2

subject to

3 x 1 −x 2 ≥ 4

2 x 1 +x 2 ≥ 3

−x 1 −x 2 ≥ − 3

x 1 , x 2 nonnegative integers

10.12 Solve the following zero–one programming problem using an exhaustive enumeration
procedure:
Maximizef= − 10 x 1 − 5 x 2 − 3 x 3

subject to

x 1 + 2 x 2 +x 3 ≥ 4

2 x 1 +x 2 +x 3 ≤ 6

xi=0 or 1, i= 1 , 2 , 3

10.13 Solve the following binary programming problem using an exhaustive enumeration pro-
cedure:
Minimizef= − 5 x 1 + 7 x 2 + 10 x 3 − 3 x 4 +x 5

subject to

x 1 + 3 x 2 − 5 x 3 +x 4 + 4 x 5 ≤ 0

2 x 1 + 6 x 2 − 3 x 3 + 2 x 4 + 2 x 5 ≥ 4

x 2 − 2 x 3 −x 4 +x 5 ≤ − 2

xi=0 or 1, i= 1 , 2 ,... , 5