Computer Aided Engineering Design

362 COMPUTER AIDED ENGINEERING DESIGN

xbaas = /i′′ ′is,,, is > 0, = 1,... , i m (12.33)

Since we require the largest possible value for xs for which all xi,i = 1,... , m are non-negative,

xbasiis* = min ( ′′/ ,) = barrs′′/ (say) for all aiis′, > 0, = 1,... , m. The choice of r in case of a tie is

arbitrary. If in case b′r = 0,xs = 0 and cannot be increased in which case the solution is degenerate.
For a non-degenerate basic feasible solution, a new basic feasible solution can be constructed with
a lower function value as follows. Substituting the value of xs gives

xxss = *

xbaxiiiss = – ′′, *, i≠r

xr = 0

xj = 0, j=m + 1, m + 2,... , n and j≠s

ff cx f = + 0 ′′ss* ≤ 0 ′ (12.34)

which is a feasible solution different from the previous one. Since ars′, > 0, a pivot operation
involving the rth row will yield a new basic feasible solution that has a function value lower than the
previous one. The new solution can be tested for optimality by inspecting the coefficients c′j and if
they are all positive, the procedure should be stopped. Else, a new basic feasible solution should be
formed and the method should be repeated. The following example illustrates the working of the
Simplex method.

Example 12.10

Minimize:f= – x 1 – 5x 2 – 3x 3
Subject to: x 1 + 2x 2 – x 3 ≤ 3
2 x 1 + x 2 + x 3 ≤ 10, x 1 ,x 2 ,x 3 ≥ 0
We first convert the inequality constraints to equality constraints by introducing slack variables x 4
andx 5 and reduce the following equations to the canonical form

R 1 x 1 + 2x 2 – x 3 +x 4 = 3

R 2 2 x 1 +x 2 +x 3 +x 5 = 10

R 3 – x 1 –5x 2 –3x 3 – f = 0

With two rows R 1 and R 2 and five variables, there can atmost be two basic variables. To commence,
x 4 and x 5 can be treated as basic variables and x 1 = x 2 = x 3 = 0. Then x 4 = 3 and x 5 = 10. Also, note
that the starting value of the function is zero. Following table can be formed:

←

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

x 4 12–1103 3/2

x 5 2110110 10

• f –1 –5 –3 0 0 0

→ Smallestbi/ais,ais > 0

Most negative, x 2 enters the basis x 4 leaves the basis