The simplex algorithm finds the optimal solution of a LP problem
by an iterative process that traverses along a sequence of edges
of the polytopic feasible region, starting at the origin and through
a sequence of vertices #tex2html_wrap_inline8988# with progressively greater objective
value #tex2html_wrap_inline8990#, until eventually reaching the optimal solution.
By doing so, it avoids checking exhaustively all vertices of the
feasible region for optimality.
We first consider the equality constraint
#math947##tex2html_wrap_inline8992#
of the standard LP problem. This is an under-determined linear system
of #tex2html_wrap_inline8994# variables but only #tex2html_wrap_inline8996# equations, only #tex2html_wrap_inline8998# of its #tex2html_wrap_inline9000#
columns of the coefficient matrix #tex2html_wrap_inline9002# are independent (assuming
#math948##tex2html_wrap_inline9004#). Initially we choose the #tex2html_wrap_inline9006# columns of the
identity coefficient matrix #tex2html_wrap_inline9008# as the independent columns, but
subsequently we can choose any other #tex2html_wrap_inline9010# columns of #tex2html_wrap_inline9012# as the
independent columns and convert them into a standard basis vector by
Gauss-Jordan elimination
together with the corresponding variables in #tex2html_wrap_inline9014#. The resulting
equation #math949##tex2html_wrap_inline9016# remains equivalent to the original one,
i.e., the #tex2html_wrap_inline9018# equality constraints are always preserved and never
violated in the process.
For convenience of discussion and without loss of generality, we could
reorder (not actually carried out) the #tex2html_wrap_inline9020# columns in #tex2html_wrap_inline9022#,
together with the corresponding variables in #tex2html_wrap_inline9024#, so that the
constraining equation would always takes the following form:
#math950# #tex2html_wrap_indisplay20319#
(220)
Now the variables in the M-D vector #tex2html_wrap_inline9026# corresponding to the
#tex2html_wrap_inline9028# independent columns in #tex2html_wrap_inline9030# are the <#5101#>basic variables<#5101#>,
while the N-D vector #tex2html_wrap_inline9032# corresponding to the remaining #tex2html_wrap_inline9034#
dependent columns, now denoted by #tex2html_wrap_inline9036#, are the <#5104#>non-basic
variables<#5104#>. This equation will always hold if #math951##tex2html_wrap_inline9038# and
#math952##tex2html_wrap_inline9040#. Such a solution is called a <#5109#>basic solution<#5109#>
of the linear system #math953##tex2html_wrap_inline9042#:
#math954# #tex2html_wrap_indisplay20330#
(221)
Initially, #tex2html_wrap_inline9044# is the coefficient matrix in the inequality
constraint #math955##tex2html_wrap_inline9046#, and the corresponding non-basic
variables #math956##tex2html_wrap_inline9048# is actually the origin. But through
the iteration, we will keep converting some other columns of #tex2html_wrap_inline9050#
into standard basis vectors #math957##tex2html_wrap_inline9052#, the
column vectors of #tex2html_wrap_inline9054#, by Gauss-Jordan elimination. The variables
in #tex2html_wrap_inline9056# corresponding to the new standard basis vectors become
the basic variables, while those corresponding to columns that become
non-standard basis vectors become non-basis variables.
The basic solutions corresponding the #tex2html_wrap_inline9058# ways to choose #tex2html_wrap_inline9060#
of the #tex2html_wrap_inline9062# columns of #tex2html_wrap_inline9064# as independent are actually the
intersections formed by any #tex2html_wrap_inline9066# of the #tex2html_wrap_inline9068# constraining hyper-planes
in the N-D space. As noted before, only a subset of these #tex2html_wrap_inline9070#
basic solutions satisfy the #tex2html_wrap_inline9072# constraints, and they are called
<#5139#>basic feasible solutions (BFS)<#5139#>. The goal of the iterative
process of the simplex algorithm is to find the optimal basic feasible
solution that maximizes #tex2html_wrap_inline9074# without exhausting all #tex2html_wrap_inline9076#
possibilities. This is done by selecting the columns in such a way
that the value of the objective function will always be maximally
increased, until eventually we find the optimal solution #tex2html_wrap_inline9078#
at one of the vertex of the polytopic feasible region.
Specially, the implementation of the simplex algorithm is based on a
tableau with #tex2html_wrap_inline9080# columns and #tex2html_wrap_inline9082# rows, initialized as below:
- The first #tex2html_wrap_inline9084# rows are for the coefficients in the equality
constraints #math958##tex2html_wrap_inline9086# (#tex2html_wrap_inline9088#). An
additional #tex2html_wrap_inline9090# row at the bottom is for the coefficients
in the objective function #math959##tex2html_wrap_inline9092#, which
is zero initially at the origin #math960##tex2html_wrap_inline9094#, i.e.,
#math961##tex2html_wrap_inline9096#.
- The first #tex2html_wrap_inline9098# columns contain the coefficients for the #tex2html_wrap_inline9100#
original variables #math962##tex2html_wrap_inline9102# and the #tex2html_wrap_inline9104# slack variables
#math963##tex2html_wrap_inline9106#, and an additional #tex2html_wrap_inline9108# column is for
the constants #math964##tex2html_wrap_inline9110# on the right-hand side of
the #tex2html_wrap_inline9112# constraint equations. The last element of the column is the
right-hand side of the objective equation #tex2html_wrap_inline9114#, which is
initially zero.
#math965# #tex2html_wrap_indisplay20368#
(222)
At this initial stage of the iteration, the #tex2html_wrap_inline9116# original variables
#math966##tex2html_wrap_inline9118# are the non-basic variables, while the
#tex2html_wrap_inline9120# slack variables #math967##tex2html_wrap_inline9122# are the basic variables
and their coefficients form an #tex2html_wrap_inline9124# identity matrix #tex2html_wrap_inline9126#,
composed of the standard basis vectors. The corresponding feasible basic
solution is simply
#math968# #tex2html_wrap_indisplay20376#
(223)
that satisfies all the constraints
#math969##tex2html_wrap_inline9128#.
In each of the subsequent iterations, we will select one of the non-basic
variables, called the <#5182#>entering variable<#5182#>, to replace one of the basic
variables, called the <#5183#>leaving variable<#5183#>, in such a way that the value
of the objective function value #tex2html_wrap_inline9130# in the last row will be
maximally increased, while all constraints remain satisfied. Here are the
steps in each iteration:
- <#5186#>Selection of the entering variable<#5186#>
This section is based on the maximization of #tex2html_wrap_inline9132#. We select
#tex2html_wrap_inline9134# in the jth column of the tableau if #tex2html_wrap_inline9136# is most negative, i.e.,
#tex2html_wrap_inline9138# is most heavily weighted by #math970##tex2html_wrap_inline9140#, so that
it will increase #math971##tex2html_wrap_inline9142# more than any other #math972##tex2html_wrap_inline9144#.
- <#5189#>Selection of the leaving variable<#5189#>
This selection is based on the constraints imposed on the selected
entering variable #tex2html_wrap_inline9146#. In general, the restriction on #tex2html_wrap_inline9148# set by
the kth constraint #math973##tex2html_wrap_inline9150# is #math974##tex2html_wrap_inline9152#
when #tex2html_wrap_inline9154#. If #math975##tex2html_wrap_inline9156#, then
the ith constraint is most restrictive on #tex2html_wrap_inline9158#, we will therefore
select the corresponding basic variable #tex2html_wrap_inline9160# as the leaving variable,
i.e., it becomes a non-basic variable to be set to zero, so that #tex2html_wrap_inline9162#
can be maximally increased without violating the constraints. If all
#tex2html_wrap_inline9164# for all #tex2html_wrap_inline9166#, variable #tex2html_wrap_inline9168# is not bounded.
- <#5198#>Gauss-Jordan elimination based on Pivoting<#5198#>
To convert the entering variable #tex2html_wrap_inline9170# to a basic variable to replace the
leaving variable #tex2html_wrap_inline9172#, we need to turn the corresponding jth column into a
standard basis vector #tex2html_wrap_inline9174#. This is realized by pivoting on #tex2html_wrap_inline9176#
in the following steps:
- Divide the pivot row #tex2html_wrap_inline9178# by #tex2html_wrap_inline9180#:
#math976##tex2html_wrap_inline9182#. Now #tex2html_wrap_inline9184#.
- Subtract #math977##tex2html_wrap_inline9186# from the kth row:
#math978##tex2html_wrap_inline9188# so that
#tex2html_wrap_inline9190# for all #math979##tex2html_wrap_inline9192#, #tex2html_wrap_inline9194#, including the
last row #tex2html_wrap_inline9196#.
Now the jth column corresponding to the entering variable #tex2html_wrap_inline9198# becomes
a standard basis vector #tex2html_wrap_inline9200#, i.e., #tex2html_wrap_inline9202# becomes a basic variable
that takes the value of #tex2html_wrap_inline9204#, and the column corresponding to the leaving
variable #tex2html_wrap_inline9206# is no longer a standard basis vector, and #tex2html_wrap_inline9208# as it is
now a non-basic variable.
As Gauss-Jordan elimination converts the linear equations to a set of
equivalent equations, the constraints remain satisfied through out the
process. Although the membership of the basic and non-basic variable
groups keeps changing in the iteration, so long as #math980##tex2html_wrap_inline9210#
and #math981##tex2html_wrap_inline9212#, the #tex2html_wrap_inline9214# constraint equations
#math982##tex2html_wrap_inline9216# always holds.
This iterative process keeps replacing the slack variables
#math983##tex2html_wrap_inline9218# (the basic variables initially) by the original
variables #math984##tex2html_wrap_inline9220# (the non-basic variables initially),
one at a time, until all original variables become basic variables
and all elements in the last row are non-negative.
The final result can be read out directly from the tableau. The variables
corresponding to the #tex2html_wrap_inline9222# standard basis vectors #tex2html_wrap_inline9224# (#tex2html_wrap_inline9226#)
are the final basic variables that take the values in #tex2html_wrap_inline9228# in the
right-most column of the tableau. They form the optimal basic solution,
with the maximum of the objective function #tex2html_wrap_inline9230# given by the last
element also in the last column. The remaining #tex2html_wrap_inline9232# variables corresponding
to non-standard columns are non-basic variables that take the value zero.
When #tex2html_wrap_inline9234# (more constraints than variables), some of the slack variables
may remain in the basic variable group taking non-zero values; when #tex2html_wrap_inline9236#,
some of the original variable may be in the non-basic group taking the value
zero.
<#5233#>Example:<#5233#>
We re-solve the LP problem considered in the previous examples, now
in the standard form:
#math985# #tex2html_wrap_indisplay20433#
The standard form is further converted to a tableau as shown below. The
left-most column indicates the basic variables, the next #tex2html_wrap_inline9238# columns
are for the variables #tex2html_wrap_inline9240# and #tex2html_wrap_inline9242#,the next #tex2html_wrap_inline9244# columns are for the slack
variables #tex2html_wrap_inline9246#, #tex2html_wrap_inline9248#, and #tex2html_wrap_inline9250#, the right most column is for the constants
#tex2html_wrap_inline9252#, #tex2html_wrap_inline9254#, and #tex2html_wrap_inline9256# on the right-hand side of the equations.
#math986# #tex2html_wrap_indisplay20445#
In this initial state, the basic variables are #tex2html_wrap_inline9258#, #tex2html_wrap_inline9260#,
and #tex2html_wrap_inline9262#, the non-basic variables are #tex2html_wrap_inline9264#. The
corresponding basic feasible solution is at the origin.
- Select column #tex2html_wrap_inline9266# as the pivot column, as #tex2html_wrap_inline9268# is
the most negative coefficient.
- Select #tex2html_wrap_inline9270# as the pivot row, as
#math987##tex2html_wrap_inline9272#.
- Divide pivot row #math988##tex2html_wrap_inline9274#
by the pivot element #tex2html_wrap_inline9276# to get
#math989##tex2html_wrap_inline9278#.
- Subtract #math990##tex2html_wrap_inline9280# from row #tex2html_wrap_inline9282#,
so that #math991##tex2html_wrap_inline9284#, including
the last row #tex2html_wrap_inline9286#.
#math992# #tex2html_wrap_indisplay20462#
The entering variable #tex2html_wrap_inline9288# becomes a basic variable, and
the leaving variable #tex2html_wrap_inline9290# becomes a non-basic variable,
replaced by new basic variable #tex2html_wrap_inline9292#. The corresponding basic
feasible solution is at #math993##tex2html_wrap_inline9294#, with #tex2html_wrap_inline9296#,
#tex2html_wrap_inline9298#, #tex2html_wrap_inline9300#. The objective function value is
#math994##tex2html_wrap_inline9302#.
- Select column #tex2html_wrap_inline9304# as the pivot column, as #tex2html_wrap_inline9306# is
the most (only) negative coefficient in the last row.
- Select row #tex2html_wrap_inline9308# as the pivot row, as the ratio
#math995##tex2html_wrap_inline9310#.
- Divide pivot row #math996##tex2html_wrap_inline9312#
by the pivot element #math997##tex2html_wrap_inline9314# to get
#math998##tex2html_wrap_inline9316#.
- Subtract #math999##tex2html_wrap_inline9318# from row #tex2html_wrap_inline9320#,
so that #math1000##tex2html_wrap_inline9322#, including the
last row #tex2html_wrap_inline9324#.
#math1001# #tex2html_wrap_indisplay20483#
The entering variable #tex2html_wrap_inline9326# becomes a basic variable, and
the leaving variable #tex2html_wrap_inline9328# becomes a non-basic variable,
replaced by the new basic variable #tex2html_wrap_inline9330#. The corresponding
basic feasible solution is at #math1002##tex2html_wrap_inline9332#, with
#math1003##tex2html_wrap_inline9334#. The objective function value is
#math1004##tex2html_wrap_inline9336#. Now that both #tex2html_wrap_inline9338# and #tex2html_wrap_inline9340# have
become basic variables, the optimal solution has been obtained.
This problem has #math1005##tex2html_wrap_inline9342# basic solutions, corresponding
to the same number of intersections, out of which five are feasible,
as previously obtained. The simplex method finds three of these feasible
solutions, starting from #tex2html_wrap_inline9344# at the origin with #tex2html_wrap_inline9346#, through
the vertex at #tex2html_wrap_inline9348# and #tex2html_wrap_inline9350# with #tex2html_wrap_inline9352#, to the optimal solution
at #tex2html_wrap_inline9354# and #tex2html_wrap_inline9356# with #tex2html_wrap_inline9358#.
The Matlab code for implementing the simplex algorithm is
listed below. The function takes input including matrix #tex2html_wrap_inline9360#
as well as the vectors #tex2html_wrap_inline9362# and #tex2html_wrap_inline9364#, and generates
the optimal solution #tex2html_wrap_inline9366#, the corresponding maximum value
of the objective function #math1006##tex2html_wrap_inline9368#, together
with the values of the slack variable #tex2html_wrap_inline9370#.
verbatim339#