7.7 Zoutendijk’s Method of Feasible Directions 403subject to
t 1 + 2 t 2 +α+y 1 = 3−^43 t 1 −^43 t 2 +α+y 2 = −^83
t 1 +y 3 = 2t 2 +y 4 = 2
t 1 ≥ 0
t 2 ≥ 0α≥ 0wherey 1 toy 4 are the nonnegative slack variables. Since an initial basic feasible
solution is not readily available, we introduce an artificial variabley 5 ≥ into 0
the second constraint equation. By adding the infeasibility formw=y 5 , the
LP problem can be solved to obtain the solution:t 1 ∗ = 2 , t 2 ∗= 103 , α∗= 104 , y 4 ∗=^1710 , y∗ 1 =y∗ 2 =y 3 ∗= 0−fmin= −α∗= − 104Asα∗> 0 , the usable feasible direction is given byS=
{
s 1
s 2}
=
{
t∗ 1 − 1
t∗ 2 − 1}
=
{
1. 0
− 0. 7
}
Step 4: Sinceα∗>ε 1 , we go to the next step.
Step 5: We have to move along the directionS 2 =
{ 1. 0
− 0. 7}
from the pointX 2 ={ 1 33. 3
1. 333}
.
To find the minimizing step length, we minimizef (X 2 +λS 2 ) =f( 1. 333 +λ, 1. 333 − 0. 7 λ)= 1. 49 λ^2 − 0. 4 λ+ 0. 889Asdf/dλ= 2. 98 λ− 0. 4 =0 atλ= 0 .134, the new point is given byX 3 =X 2 +λS 2 ={
1. 333
1. 333
}
+ 0. 134
{
1. 0
− 0. 7
}
=
{
1. 467
1. 239
}
At this point, the constraint is satisfied sinceg 1 (X 3 ) =− 0 .055. Since pointX 3
lies in the interior of the feasible domain, we go to step 2.
The procedure is continued until the optimum pointX∗={ 1. 6
1. 2}
andfmin= 0. 8
are obtained.