Consider our prototype LP in standard form, repeated below for convenience:
s.t.
Finding an initial bfs To start the Simplex algorithm on this
problem, we need to identify an initial bfs. For this particular
problem, a bfs will have two basic variables, since we have two
technological constraints. Taking a closer look to the structure of
these constraints in Equation 28, it can be seen that
a convenient selection is 
, where 
denotes the set
of basic variables (basis). Indeed, setting 
, we
readily obtain, 
.
The above easy computation of the values of the basic variables resulted from the fact that each of these variables could be associated with one and only one constraint. More specifically, (i) each of these variables appeared in only one constraint, (ii) the coefficient of the variable in that constraint was equal to 1.0, and (iii) any pair of basic variables showed up in different constraints. An LP the constraints of which satisfy these three properties with respect to a certain basis, is said to be in canonical form with respect to that basis.
On the other hand, the feasiblity of the above basis, ,
was established by the fact that the right-hand-side
coefficients of the constraints in their canonical form with respect
to basis are non-negative. We shall address the problem of how to
compute an initial bfs in the more general case where one is not
readily available by inspection, in a later section.
Testing bfs optimality: Checking the sign of the objective
function coefficients for nonbasic variables
Notice that the LP objective value corresponding to basis is
determined by the fact that , and therefore, z=
0. So, we pose the question: Is it possible that there exists another
bfs with a better objective value? Obviously, any bfs for which 
and/or 
is a basic variable has a considerable chance of
having a better (i.e., strictly positive) objective value, since the
objective function coefficients for these variables are positive
numbers. Hence, the answer to the previous question is that the
nonnegativity of the objective function coefficients of the nonbasic
variables 
implies that there is potential for improvement
of the objective value, z, and both variables are good
candidates for entering the basis.
Selecting the entering variable Given that at every
objective-improving iteration the Simplex algorithm considers
adjacent bfs's, it follows that only one of the candidate nonbasic
variables will eventually enter the basis. Typically, the variable
selected to enter the basis is the one that will incur the maximum
improvement to the objecive value per unit of increase of the
variable. In our case, this translates to selecting the (nonbasic)
variable with the most positive coefficient in the objective
function, i.e., variable .
Selecting the variable to leave the basis:
the ratio test Once we have selected the variable to enter the basis,
we are faced with the question of which of the current basic variables
will be dropped out of it, in order to obtain the improving adjacent
bfs. The logic behind this step is as follows: Since increasing
from its current (zero) value improves the objective value, we would
like to increase it as much as we can. What constrains us in this
increase, is the requirement to meet the technological constraints:
as well as the sign (nonnegativity) restrictions imposed on the LP
variables. In particular, since variable will remain nonbasic,
its value will remain equal to zero, and therefore it vanishes from
the above set of equations. Hence, we have:
Notice that as increases, both 
and 
are
decreased. Obviously, cannot increase beyond a value that makes
any of and negative. So, the maximal allowable increase
for is obtained by solving the system of inequalities:
Hence,
i.e., 
. Equation 30 is known as the
ratio test in the theory of Simplex algorithm, and for an entering
variable 
, its general form is:
The variable leaving the basis is anyone of those corresponding to a
technological constraint with index i minimizing the ratio of
Equation 31; indeed, setting to the min-ratio
value drives these variables to zero. Hence, in our case, the variable to leave
the basis is , and the new bfs is 
. The new
(improved) objective value is 
.
Obtaining the canonical form with respect to
the new bfs: Pivoting the entering variable At this point, we must
reset to ourselves the question regarding the optimality of basis
. Notice, however, that the way that we addressed
this question - as well as all the other questions - with respect to
basis , was facilitated by
the fact that the original set of technological constraints in
Equation 28 were in
canonical form with respect to that basis. To be able to
address the same set of questions regarding basis , we must transform the original set of constraints into canonical
form with respect to this new basis.
To perform this transformation, first, we rewrite the original LP equations in the form:
This representation of the LP technological constraints and the objective-function equation is known as the LP tableau. In particular, the row corresponding to the objective-function equation is known as the Row-0 of the tableau, and the coefficients of the (nonbasic) variables in that row are known as the Row-0 coefficients. Notice also that the right-hand-side entry of Row-0 provides the objective value of the current bfs.
Under the above tableau representation, the columns
corresponding to the basic variables and are essentially
the elementary (unit) vectors: 
and 
, respectively, while the third unit vector 
is the column of the objective variable z. This is another way to
characterize the fact that the above tableau is in canonical form with
respect to variables 
. Hence, to obtain the tableau corresponding
to basis , we must convert the column of in
the above tableau to the unit vector , making sure
that while we are doing so, we do not alter the content of these three
equations. This can be done by exploiting the following two properties
of a system of linear equations (generally, known as elementary
row operations):
Multiplying the third equation above with -1/60 and adding it to the second equation, we get:
Finally, multiplying the third equation with 400 and adding it to the first equation, we get:
This the new tableau is in canonical form with respect to basis
. As it was expected, the transformation provided also
(automatically) the values of the new basic variables, and the
objective function value corresponding to the new basis (i.e.,
the right-hand-side of Row-0).
Considering the signs of the Row-0
coefficients in this new tableau, we can see that increasing any of the non-basic
variables from their zero value will have a descreasing effect on the
objective value. Hence, we can conclude that is an optimal basis
for our example LP. The optimal values for the basic variables
are: 
and 
, and the optimal objective value is
.
You can extend your understanding of this basic Simplex logic, by seeing how it applies to your own examples. Remember that for this basic Simplex version to work, all the constraints must be of the "<=" type, and all the decision variables as well as the rhs-coefficients must be nonnegative. Submit your examples
Obtaining an initial bfs in the general
case As we saw in the previous example, if all the constraints in the
original LP formulation are of the ` 
'-type, we can readily
obtain an initial bfs for Simplex, consisting of all the slack
variables in the corresponding ``standard form'' formulation. In this
section we consider the more general case, where the original LP
formulation might contain also ` 
'-type inequality as well as
equality constraints. To facilitate the subsequent discussion, let us
consider the following LP:
s.t.
which in ``standard form'' becomes:
s.t.
For this LP, can constitute an initial basic variable associated
with the first constraint. However, the excess variable 
cannot be a basic variable for constraint 2, even though it appears
only in this constraint, since this would imply a negative value for
it (i.e., 
), and the resulting basic solution would not be
feasible. The last constraint (#3), does not even involve an
auxiliary variable.
To overcome this problem, we ``synthesize'' an initial bfs by
introducing additional (artificial) variables 
for
the two ``problematic'' constraints, with 
. Hence,
our initial bfs is 
, with 
. Notice, however, that even though we obtained a bfs
for our set of constraints, we have altered the structure - and
therefore, the content - of the original formulation. In fact, it is
easy to check that this bfs (together with the implied zero values for
the nonbasic variables) is not even feasible for the original LP! On
the other hand, if we were able to obtain another bfs for the
modified problem in which the introduced artificial variables are
nonbasic, then this bfs would be also feasible for the
original LP: the artificial variables, being nonbasic, would be equal
to zero, and therefore, they would vanish
(i.e., have no effective contribution) in
the corresponding ``canonical form'' representation. To obtain the
effect just described, we try to drive the artificial variables to
zero, by initially trying to achieve the following objective:
s.t.
Synthesizing and solving the above LP is known as the Phase I -
step of the Simplex algorithm. If the original LP (Eq. 36)
has a feasible solution, then the nonnegativity of implies
that the optimal value of this new LP will be zero, and by the
end of its solution we shall also have a feasible bfs for the original
formulation. On the other hand, having a strictly positive optimal
objective value for the LP of Equation 37 implies that the
artificial variables are absolutely necessary to obtain a feasible
solution for this set of constraints, and therefore, our original LP
is infeasible. Hence, infeasibility is tested during the
Phase-I step of the Simplex algorithm.
Applying the previously described Simplex algorithm on the Phase-I LP of Equation 37, we obtain the optimal tableau:
Therefore, a feasible basis for the original LP is 
. The canonical form of the original tableau with respect to
basis is obtained by:
from the tableau of Equation 38:
and
must be zero in the corresponding canonical-form formulation):
Then, we are ready to restart Simplex, but this time on the original
LP formulation. In this particular case, it is easy to see that, since
we have a minimization problem, the current basis is already
optimal (i.e., increasing from its zero value will only increase
the objective function).
Unbounded LP's and LP's with many optimal solutions In the previous section, we saw that Simplex detects infeasibility while trying to solve the Phase-I LP. It is instructive to consider how the algorithm behaves on unbounded LP's as well as on LP's with many optimal solutions. To understand these aspects of the algorithm, try to implement it on the corresponding examples provided in Section 2. What is happening?
In your...explorations, and for further experimentation with
the (2-phase) Simplex algorithm, you can use the software developed by
Dr. Timothy Wisniewski, in a collaboration of Argonne National
Laboratory and Northwestern University. In interpreting the
program calculations, it should be noticed, however, that in that
code, the reduced costs of the nonbasic variables are defined as the
opposites of the reduced costs used in this
document. Therefore, in the logic of the optimality test, the interpretation of
the reduced cost signs must be inverted. As an example, optimality of a
basis for a minimization problem is implied by the reduced costs of
all nonbasic variables being nonnegative. Additional instructions
about the software can be found in its introductory homepage.
RUN SIMPLEX
