Computer Aided Engineering Design

OPTIMIZATION 363

Note that the coefficient of x 2 is most negative in the third row. Next, in the same column, both
coefficients a 12 and a 22 are positive. However, the one that corresponds to the minimum bi/aisvalue
is the coefficient in the first row. Thus, the coefficient in the box is made the pivot element allowing
x 2 to become the new basic variable replacing x 4. Pivot operations yield

with the new basic feasible solution as [0 3/2 0 0 17/2]T and the function value as – 15/2. Note that
the coefficient of x 3 in the third row is most negative and in the same column, coefficient in the
second row is positive. Thus, 3/2 as bordered becomes the new pivot coefficient replacing x 3 by x 5
in the basic variable set. Row operations yield

x 1 x 2 x 3 x 4 x 5 bi bi/ais,ais > 0

x 2 1 1 0 1/3 1/3 13/3

x 3 1 0 1 –1/3 2/3 17/3

• f 7 0 0 2/3 11/3 116/3

where the new basic feasible solution is [0 13/3 17/3 0 0]T and the function value is –116/3. Since
now all coefficients pertaining to x 1 ,x 2 and x 3 in the third row are non-negative, the solution is
optimal.

12.5 Sequential Linear Programming (SLP)

Given an optimization problem in standard form, that is

Minimize: f(X)

Subject to: gj(X)≤ 0, j= 1,... , m

hk(X) = 0, k = 1,... , p

the problem is linearized about the solution Xi using the Taylor series, that is

f(X) = f(Xi) + ∇f(Xi)T(X – Xi)

gj(X) = gj(Xi) + ∇gj(Xi)T(X – Xi), j = 1,... , m

hk(X) = hk(Xi) + ∇hk (Xi)T(X – Xi), k = 1,... , p (12.35)

The above problem is solved using the Simplex method to determine a new solution vector Xi+1. The
problem is linearized again about Xi+1 and the process is continued until the convergence is achieved
and a suitable optimal solution X* is found. Also note that SLP is a first order method requiring to
compute the first derivatives of the function and constraints.

x 1 x 2 x 3 x 4 x 5 bi bi/ais,ais > 0

x 2 1/2 1 –1/2 1/2 0 3/2

x 5 3/2 0 3/2 –1/2 1 17/2 17/3

• f 3/2 0 –11/2 5/2 0 15/2

→ Smallestbi/ais for ais > 0

Most negative, x 3 enters the basis x 5 leaves the basis

←