Page 242 -

222 CHAPTER 5 LINEAR PROGRAMMING: THE SIMPLEX METHOD

We can apply the same logic to s 2 and s 3 in turn. For s 2 , introducing x 1 has no effect (a
zero coefficient) but for s 3 the maximum value that x 1 could take would be:
8x 1 ¼ 300 giving x 1 ¼ 37:5
This in turn would mean we were using all available warehouse space to store x 1 ,there
would be no slack (s 3 ¼ 0). If we now consider all three rows (constraints) simulta-
neously, we know that x 1 is set to enter the basic solution. The maximum possible
increase in x 1 is given by the smallest, nonzero ratio calculation. Here, the maximum
that x 1 can take at this stage in the procedure is a value of 37.5. At this level of
production, s 3 would takeazero value –thatis, s 3 would become a non-basic variable.
Criterion for Removing a Variable from the Current Basis (Minimum Ratio Test)
To determine which basic Suppose the incoming basic variable corresponds to column j in the A
variable will become portion of the simplex tableau. For each row i, compute the ratio b i /a ij for
nonbasic, only the
positive coefficients in each a ij greater than zero. The basic variable that will be removed from
the incoming column the basis corresponds to the minimum of these ratios. In case of a tie, we
correspond to basic follow the convention of selecting the variable that corresponds to the
variables that will uppermost of the tied rows.
decrease in value when
the new basic variable So, we now know that x 1 is set to enter the solution as a basic variable, s 3 is set to
enters.
leave the current solution and become non-basic and also that x 1 will take a value of
37.5 in the new solution. Clearly, if we are changing the basic solution, we will need
to change the tableau to reflect the new solution. We look at how we do this next.

5.5 Calculating the Next Tableau

The way in which we transform the simplex tableau so that it still represents an equivalent
system of constraint equations is to use the following elementary row operations.
Elementary Row Operations

1 Multiply any row (equation) by a nonzero number.
2 Replace any row (equation) by the result of adding or subtracting a
multiple of another row (equation) to it.
The application of these elementary row operations to a system of simultaneous
linear equations will not change the solution to the system of equations; however,
the elementary row operations will change the coefficients of the variables and the
values of the right-hand sides.
The purpose of these arithmetic operations is to transform the existing tableau
into one that represents the new basic solution. We show the initial tableau below
together with the ratio calculations we performed earlier.

Initial tableau
Value Ratio (Value/x 1 )
x 1 x 2 s 1 s 2 s 3
Basis C b 50 40 0 0 0

s 1 0 3 5 1 0 0 150 50
s 2 0 0 1 0 1 0 20 -
s 3 0 *8 5 0 0 1 300 37.5
0 0 0 0 0 0
z j
50 40 0 0 0 0
c j –z j

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.