Engineering Optimization: Theory and Practice, Fourth Edition

232 Linear Programming II: Additional Topics and Extensions

phase I. This procedure involves the introduction ofnnonnegative artificial variables

ziinto the Eqs. (4.89) so that

cj−θj+

∑n

i= 1

xidij+

∑m

i= 1

λiaij+zj= 0 , j= 1 , 2 ,... , n (4.97)

Then we minimize

F=

∑n

j= 1

zj (4.98)

subject to the constraints

cj−θj+

∑n

i= 1

xidij+

∑m

i= 1

λiaij+zj= 0 , j= 1 , 2 ,... , n

ATiX+Yi=bi, i= 1 , 2 ,... , m

X≥ 0 , Y≥ 0 , λ≥ 0 , θ≥ 0

While solving this problem, we have to take care of the additional conditions

λiYi= 0 , j= 1 , 2 ,... , m

θjxj= 0 , j= 1 , 2 ,... , n

(4.99)

Thus when deciding whether to introduceYiinto the basic solution, we first have to

ensure that eitherλiis not in the solution orλiwill be removed whenYienters the

basis. Similar care has to be taken regarding the variablesθjandxj. These additional

checks are not very difficult to make during the solution procedure.

Example 4.14

Minimizef= − 4 x 1 +x 12 − 2 x 1 x 2 + 2 x 22

subject to

2 x 1 +x 2 ≤ 6

x 1 − 4 x 2 ≤ 0

x 1 ≥ 0 , x 2 ≥ 0

SOLUTION By introducing the slack variablesY 1 =s 12 andY 2 =s 22 and the surplus

variablesθ 1 =t 12 andθ 2 =t 22 , the problem can be stated as follows:

Minimizef=(−4 0)

{

x 1

x 2

}

+

1

2

(x 1 x 2 )

[

2 − 2

− 2 4

] {

x 1

x 2

}

subjectto

[

2 1

1 − 4

] {

x 1

x 2

}

+

{

Y 1

Y 2

}

=

{

6

0

}

−x 1 +θ 1 = 0

−x 2 +θ 2 = 0

(E 1 )