Engineering Optimization: Theory and Practice, Fourth Edition

242 Linear Programming II: Additional Topics and Extensions

subject to

x 1 +x 2 + 2 x 3 −x 5 −x 6 = 1

− 2 x 1 +x 3 +x 4 +x 5 −x 7 = 2

xi≥ 0 , i=1 to 7

4.10 Solve Problem 3.1 by solving its dual.

4.11 Show that neither the primal nor the dual of the problem

Maximizef= −x 1 + 2 x 2

subject to

−x 1 +x 2 ≤ − 2

x 1 −x 2 ≤ 1

x 1 ≥ 0 , x 2 ≥ 0

has a feasible solution. Verify your result graphically.

4.12 Solve the following LP problem by decomposition principle, and verify your result by

solving it by the revised simplex method:

Maximizef= 8 x 1 + 3 x 2 + 8 x 3 + 6 x 4

subject to

4 x 1 + 3 x 2 +x 3 + 3 x 4 ≤ 16

4 x 1 −x 2 +x 3 ≤ 12

x 1 + 2 x 2 ≤ 8

3 x 1 +x 2 ≤ 10

2 x 3 + 3 x 4 ≤ 9

4 x 3 +x 4 ≤ 12

xi≥ 0 , i=1 to 4

4.13 Apply the decomposition principle to the dual of the following problem and solve it:

Minimizef= 10 x 1 + 2 x 2 + 4 x 3 + 8 x 4 +x 5

subject to

x 1 + 4 x 2 −x 3 ≥ 16

2 x 1 +x 2 +x 3 ≥ 4

3 x 1 +x 4 +x 5 ≥ 8

x 1 + 2 x 4 −x 5 ≥ 20

xi≥ 0 , i=1 to 5