|
|
|
|
Linear
Programming Supplements
|
|
|
Supplements are PDF files covering subjects
not included in the textbook.
|
|
|
|
In this article, a variant of the primal approach, known as the
dual simplex method, is considered that works in just the opposite
fashion as the primal simplex. Until the final iteration, each
basis examined is primal infeasible (some negative values on the
right-hand side) and dual feasible (all elements in row 0 are
nonnegative). At the final (optimal) iteration the solution will
be both primal and dual feasible. For a given problem, both the
primal and dual simplex algorithms will terminate at the same
solution but arrive there from different directions. |
|
|
|
In this section, we deal implicitly with the issue of uncertainty
in the data elements by determining the bounds over which each
such element can range without effecting a change in either the
optimal solution or optimal basis. Such investigations fall under
the heading of sensitivity analysis. |
|
|
|
When a solution is obtained for a linear program with the simplex
method, the solution to a second model, called the dual problem,
is readily available and provides useful information for sensitivity
analysis. There are several benefits to be gained from studying
the dual problem, not the least of which is that it often has
a practical interpretation that enhances the understanding of
the original model. Duality also has important implications for
the theoretical basis of mathematical programming algorithms.
In this section, the dual problem is defined, the properties that
link it to the original (called the primal) are listed, and the
procedure for identifying the dual solution from the tableau is
presented. |
|
|
|
All forms of the simplex method reach the optimum by traversing
a series of basic solutions. Since each basic solution represents
an extreme point of the feasible region, the track followed by
the algorithm moves around the boundary of the feasible region.
In the worst case, it may be necessary to examine most if not
all of the extreme points. Interior point methods (IMPs) approach
the optimal solution from the strict interior of the feasible
region. . IPMs are of interest from a theoretical point of view
because they have polynomial complexity, and from a practical
point of view because they have produced solutions to many industrial
problems that were hitherto intractable. |
|
