360 COMPUTER AIDED ENGINEERING DESIGN
the goal is to determine the optimal solution(s) among the feasible set. The system aX = b can be
solved using the well known Gauss elimination technique. Using a sequence of row reductions, we
may arrive at the canonical form
1 + 0xx 1 2 +... + 0xax axm + 1, +1′′mm (^) +1 + 1, +2mm+2 +... + axb1,′′nn = 1
0 + 1 +... + 0xx 1 2 xax axm + 2, +1′′mm (^) +1 + 2, +2mm+2 +... + axb′′2,nn = 2
...
0 + 0xx 1 2 +... + 1xa x axm + ′′mm, +1 (^) m+1 + mm, +2 m+2 +... + axbmn n′′, = m (12.30)
We can arrive at a solution [x 1 ,x 2 ,... , xm,xm+1,xm+2,... , xn]T = [bb 12 ′′, ,... , bm′, 0, 0,... , 0]T
called the basic solution by choosing xm+1 = xm+2 =... = xn = 0, since the solution vector contains
no more than m nonzero terms. The pivotal variables x 1 ,x 2 ,... , xm are also called basic variables
while the rest are called non-pivotal, non-basic orindependentvariables. If bb 12 ′′, ,... , bm′ are all
positive, the condition X≥ 0 is satisfied and the solution then is termed as basic feasible solution. It
is possible to obtain the other basic solutions from the canonical system in Eq. (12.30) by performing
an additional pivotal operation. For this, we choose apq′, as the pivot term where q > m while p is any
row among 1, 2,... , m. The new canonical system will have xq as the pivotal variable in place of
xp and thus will yield a new basic solution that may or may not be feasible.
From the foregoing, a basic solution for a system of n variables bound in m constraints (n>m) can
be obtained by setting any n – m of the nvariables to zero and solving for the rest. The resulting
solutions may or may not be feasible. Of the feasible ones, checks may then be imposed to determine
which basic solution renders a function minimum. The number of basic solutions to be inspected for
feasibility and optimality is equal to
n
mn m
!
!( – )!
, that is, the number of ways in which m variables
can be selected from the parent set [x 1 ,x 2 ,... , xn]T. For large number of variables and constraints,
this value may be large. We thus need a systematic technique to examine the basic feasible solutions
such that the subsequent solution renders a lower function value than the previous one, until the
function minimum is attained.
12.4.1 Simplex Method
The commencing point in the Simplex method is a set of equations in the canonical form which gives
a basic feasible solution. In addition, the objective function is also included in the row reduced form,
that is
1 + 0xx 1 2 +... + 0xax axm + 1, +1′′mm (^) +1 + 1, +2mm+2 +... + axb1,′′nn = 1
0 + 1 +... + 0xx 1 2 xax axm + 2, +1′′mm (^) +1 + 2, +2mm+2 +... + axb′′2,nn = 2
...
0 + 0xx 1 2 +... + 1xa x axm + mm′′, +1 (^) m+1 + mm, +2 m+2 +... + axbmn n′′, = m
0 + 0xx 1 2 +... + 0xfcx cxm – + mm′′+1 +1 + m m+ 2 + 2 +... + cx fnn′′ = – 0 (12.31)
Note that –f is treated as a basic variable in the canonical from. If all bii′ 0, = 1,... , ,≥ m then a
basic feasible solution can be deduced such that