Page 234 -

214 CHAPTER 5 LINEAR PROGRAMMING: THE SIMPLEX METHOD

and hence x 1 ¼ 150/3 ¼ 50. Equation (5.7) provides s 2 ¼ 20. Finally, substituting
x 1 ¼ 50 into Equation (5.8) results in:
8ð50Þþ 1s 3 ¼ 300
Solving for s 3 , we obtain s 3 ¼ 100.
So, we obtain the following solution to the three-equation, five-variable set of
linear equations:
x 1 ¼ 50
x 2 ¼ 0
s 1 ¼ 0
s 2 ¼ 20
s 3 ¼ 100
A basic solution is
obtained by setting two This solution is referred to as a basic solution. To state a general procedure for
of the five variables equal determining a basic solution, we must consider a standard-form linear programming
to zero and solving the
three equations problem consisting of n variables and m linear equations, where n is greater than m.
simultaneously for the
values of the other three Basic Solution
variables. To determine a basic solution, set n m of the variables equal to zero, and
Mathematically, we are solve the m linear constraint equations for the remaining m variables. 1
guaranteed a solution
only if the resulting three In terms of the HighTech problem, a basic solution can be obtained by setting any two
equations are linearly variables equal to zero and then solving the system of three linear equations for the
independent. Fortunately,
the Simplex method is remaining three variables. We shall refer to the n m variables set equal to zero as the
designed to guarantee nonbasic variables and the remaining m variablesasthe basic variables.So,in thepreced-
that a solution exists for ing example, x 2 and s 1 are the nonbasic variables, and x 1 , s 2 ,and s 3 are the basic variables.
the basic variables at
each iteration.
Basic Feasible Solution
A basic solution can be either feasible or infeasible. A basic feasible solution is a basic
solution that also satisfies the nonnegativity conditions. The basic solution found by
setting x 2 and s 1 equal to zero and then solving for x 1 , s 2 and s 3 is a basic infeasible
solution because s 3 ¼ 100 and negative values are not allowed in the formulation.
However, suppose that we had chosen instead to make x 1 and x 2 nonbasic variables by
setting x 1 ¼ 0and x 2 ¼ 0. Solving for the corresponding basic solution is easy because
with x 1 ¼ x 2 ¼ 0, the three constraint equations reduce to:

¼ 150
1s 1
1s 2 ¼ 20
1s 3 ¼ 300
The complete solution with x 1 ¼ 0 and x 2 ¼ 0 is then:

x 1 ¼ 0
x 2 ¼ 0
s 1 ¼ 150
s 2 ¼ 20
s 3 ¼ 300
This solution is a basic feasible solution because all of the variables satisfy the
nonnegativity conditions.
The following graph shows all the constraint equations and basic solutions for
the HighTech problem. Circled points *1–*5 are basic feasible solutions; circled

1
In some cases, a unique solution cannot be found for a system of m equations and n variables. However, these
cases will never be encountered when using the Simplex method.

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.