Page 238 -

218 CHAPTER 5 LINEAR PROGRAMMING: THE SIMPLEX METHOD

The simplex tableau is row associated with the basic variable. In the tableau, row 2 is associated with
nothing more than a table basic variable s 1 because this row has a 1 in the unit column corresponding to s 1 .
that helps keep track of
the simplex method So, the value of s 1 is given by the right-hand side value b 1 : s 1 ¼ b 1 ¼ 150. In a
calculations. similar fashion, s 2 ¼ b 2 ¼ 20, and s 3 ¼ b 3 ¼ 300.
Reconstructing the If we study the standard-form representation of the HighTech constraint equa-
original problem can be tions closely, we can identify two properties that make it possible to find an initial
accomplished from the
initial simplex tableau. basic feasible solution. The first property requires that the following conditions be
satisfied:
a. For each constraint equation, the coefficient of one of the m basic variables in
that equation must be 1, and the coefficients for all the remaining basic variables
in that equation must be 0.
b. The coefficient for each basic variable must be 1 in only one constraint
equation.

When these conditions are satisfied, exactly one basic variable with a coefficient of 1
is associated with each constraint equation, and for each of the m constraint
equations, it is a different basic variable. Thus, if the n–m non-basic variables are
set equal to zero, the values of the basic variables are the values of the right-hand
Try Problem 5(a) for sides of the constraint equations.
practise in setting up the The second property that enables us to find a basic feasible solution requires the
complete initial simplex values of the right-hand sides of the constraint equations to be nonnegative. This
tableau for a problem
with less-than-or-equal- nonnegativity ensures that the basic solution obtained by setting the basic variables
to constraints. equal to the values of the right-hand sides will be feasible.
If a linear programming problem satisfies these two properties, it is said to be in
tableau form.

5.4 Improving the Solution

Having found a basic feasible solution, the Simplex procedure now searches for an
improved solution. The general principle is simple: will we get an improved,
feasible solution if we add one of the non-basic variables to the current solution?
In our HighTech problem, this would mean adding either variable x 1 or x 2 to the
current solution (since these are the two non-basic variables). Effectively, this
would mean letting either x 1 or x 2 take a nonzero value (or, in a business context,
that we decide to produce some number of units of either the Deskpro model or
the UltraPortable).
Referring to Figure 5.1, our initial solution puts us at Point 1 on the graph (the
origin where both decision variables are zero). The Simplex procedure now deter-
mines whether a move to an adjacent corner point (either Point 5 or Point 2), would
give an improved solution. (Note that Points 3 and 4 are not considered at this time
since they are not adjacent to the current solution at Point 1.) However, if we were
to introduce one of the non-basic variables into the solution then we would have to
remove one of the existing basic variables – one of s 1 , s 2 or s 3 would then take a zero
value.
To help decide whether an improved solution is possible and determine which
variables would be part of the solution and which would leave, we add some addi-
tional information to the Simplex tableau. To help with the Simplex calculations, we
first add two more rows to the tableau.

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.