Page 251 -

TABLEAU FORM: THE GENERAL CASE 231

Now let us consider how we obtain an initial basic feasible solution to start the
Simplex method. Previously, we set x 1 ¼ 0and x 2 ¼ 0 and selected the slack variables
as the initial basic variables. The extension of this notion to the modified HighTech
problem would suggest setting x 1 ¼ 0and x 2 ¼ 0 and selecting the slack and surplus
variables as the initial basic variables. Doing so results in the basic solution:
x 1 ¼ 0
x 2 ¼ 0
s 1 ¼ 150
s 2 ¼ 20
s 3 ¼ 300
s 4 ¼ 25
Clearly this solution is not a basic feasible solution because s 4 ¼ 25 violates the
nonnegativity requirement. Here, with the Simplex method, we are trying to set x 1
and x 2 to zero. However, the minimum total production constraint we added
requires that combined production must be at least 25 units and clearly we cannot
set x 1 and x 2 to zero and meet the constraint requirement. The difficulty is that the
standard form and the tableau form are not equivalent when the problem contains
greater-than-or-equal-to constraints.
To set up the tableau form, we shall resort to a mathematical ‘trick’ that will
enable us to find an initial basic feasible solution in terms of the slack variables s 1 , s 2
and s 3 and a new variable we shall denote a 4 . Variable a 4 really has nothing to do
with the HighTech problem; it merely enables us to set up the tableau form and thus
obtain an initial basic feasible solution. This new variable, which has been artificially
Artificial variables are created to start the Simplex method, is referred to as an artificial variable.
appropriately named; The notation for artificial variables is similar to the notation used to refer to the
they have no physical elements of the A matrix. To avoid any confusion between the two, recall that the
meaning in the real
problem. elements of the A matrix (constraint coefficients) always have two subscripts,
whereas artificial variables have only one subscript referring to the constraint.
With the addition of an artificial variable, we can convert the standard form of the
problem into tableau form. We add artificial variable a 4 to constraint Equation (5.12)
to obtain the following representation of the system of equations in tableau form:
¼ 150
3x 1 þ 5x 2 þ 1s 1
1x 2 þ 1s 2 ¼ 20
¼ 300
8x 1 þ 5x 2 þ 1s 3
1x 1 þ 1x 2 1s 4 þ 1a 4 ¼ 25
Note that the subscript on the artificial variable identifies the constraint with which it
is associated. Thus, a 4 is the artificial variable associated with the fourth constraint.
Because the variables s 1 , s 2 , s 3 and a 4 each appear in a different constraint with a
coefficient of 1, and the right-hand side values are nonnegative, both requirements
of the tableau form have now been satisfied. We can now obtain an initial basic
feasible solution by setting x 1 ¼ x 2 ¼ s 4 ¼ 0. The complete solution is:
x 1 ¼ 0
x 2 ¼ 0
s 1 ¼ 150
s 2 ¼ 20
s 3 ¼ 300
s 4 ¼ 0
a 4 ¼ 25

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.