Engineering Optimization: Theory and Practice, Fourth Edition

630 Integer Programming

10.14 Find the solution of Problem 10.1 using the branch-and-bound method coupled with the

graphical method of solution for the branching problems.

10.15 Find the solution of the following problem using the branch-and-bound method coupled

with the graphical method of solution for the branching problems:

Maximizef=x 1 − 4 x 2

subject to

x 1 −x 2 ≥ − 4 , 4 x 1 + 5 x 2 ≤ 45

5 x 1 − 2 x 2 ≤ 20 , 5 x 1 + 2 x 2 ≥ 10

xi≥0 and integer, i= 1 , 2

10.16 Solve the following mixed integer programming problem using a graphical method:

Minimizef= 4 x 1 + 5 x 2

subject to

10 x 1 +x 2 ≥ 10 , 5 x 1 + 4 x 2 ≥ 20

3 x 1 + 7 x 2 ≥ 21 , x 2 + 12 x 2 ≥ 12

x 1 ≥0 and integer, x 2 ≥ 0

10.17 Solve Problem 10.16 using the branch-and-bound method coupled with a graphical

method for the solution of the branching problems.

10.18 Convert the following problem into an equivalent zero–one LP problem:

Maximizef=x 1 x 2

subject to

x^21 +x 22 ≤ 25 , xi≥0 and integer, i= 1 , 2

10.19 Consider the discrete variable problem:

Maximizef=x 1 x 2

subject to

x 12 +x^22 ≤ 4

x 1 ∈ { 0. 1 , 0. 5 , 1. 1 , 1. 6 , 2. 0 }

x 2 ∈ { 0. 4 , 0. 8 , 1. 5 , 2. 0 }

Approximate this problem as a zero–one LP problem at the vector,X^0 =

{ 1. 1

0. 8

}

.