Engineering Optimization: Theory and Practice, Fourth Edition

4.8 Quadratic Programming 233

By comparing this problem with the one stated in Eqs. (4.72) to (4.74), we find that

c 1 = − 4 , c 2 = 0 , D=

[

2 − 2

− 2 4

]

, A=

[

2 1

1 − 4

]

,

A 1 =

{

2

1

}

, A 2 =

{

1

− 4

}

, and B=

{

6

0

}

The necessary conditions for the solution of the problem stated in Eqs. (E 1 ) can be
obtained, using Eqs. (4.89) to (4.96), as

− 4 −θ 1 + 2 x 1 − 2 x 2 + 2 λ 1 +λ 2 = 0

0 −θ 2 − 2 x 1 + 4 x 2 +λ 1 − 4 λ 2 = 0

2 x 1 +x 2 − 6 =−Y 1

x 1 − 4 x 2 − 0 =−Y 2

(E 2 )

x 1 ≥ 0 ,x 2 ≥ 0 , Y 1 ≥ 0 , Y 2 ≥ 0 ,λ 1 ≥ 0 ,

λ 2 ≥ 0 ,θ 1 ≥ 0 , θ 2 ≥ 0

(E 3 )

λ 1 Y 1 = 0 , θ 1 x 1 = 0

λ 2 Y 2 = 0 , θ 2 x 2 = 0

(E 4 )

(IfYiis in the basis,λicannot be in the basis, and ifxj is in the basis,θjcannot be
in the basis to satisfy these equations.) Equations (E 2 ) can be rewritten as

2 x 1 − 2 x 2 + 2 λ 1 +λ 2 −θ 1 +z 1 = 4

− 2 x 1 + 4 x 2 +λ 1 − 4 λ 2 −θ 2 +z 2 = 0

2 x 1 +x 2 +Y 1 = 6

x 1 − 4 x 2 +Y 2 = 0

(E 5 )

wherez 1 andz 2 are artificial variables. To find a feasible solution to Eqs. (E 2 ) to (E 4 )
by using phase I of simplex method, we minimizew=z 1 +z 2 with constraints stated
in Eqs. (E 5 ), (E 3 ), and (E 4 ). The initial simplex tableau is shown below:

Basic Variables bi/ais
variables x 1 x 2 λ 1 λ 2 θ 1 θ 2 Y 1 Y 2 z 1 z 2 w bi forais> 0

Y 1 2 1 0 0 0 0 1 0 0 0 0 6 6
Y 2 1 − 4 0 0 0 0 0 1 0 0 0 0
z 1 2 − 2 2 1 − 1 0 0 0 1 0 0 4
z 2 − 2 4 1 − 4 0 −1 0 0 0 1 0 0 0←Smaller
one
−w 0 − 2 − 3 3 1 1 0 0 0 0 1 − 4
↑ ↑
x 2 selected for Most negative
entering next basis