I describe the relationship between the pivot operations of the simplex
method on the Primal LP and the corresponding operations on the Dual
LP. So given a sequence of pivot operations on the Primal LP, these
is a corresponding sequence of pivot operations on the Dual LP. We
assume we start with the Primal LP in standard form.
We shall assume the
are greater than or equal to
, so
that the initial
can be taken to be
. The Dual LP can be
written in the form
Now rewrite both the Primal and Dual in augmented form to turn the
inequalities into equalities.
There is a fundamental relationship between the
variables
of the Primal and the
variables of the Dual. We'll refer
to these variables as dual to one another. There is a similar relationship
between the variables
of the Dual and the
of the Primal.
Again, refer to the variables as dual to one another. We can indicate
the correspondence by a table.
Assuming the
are all nonnegative, we have a natural initial
starting basic feasible solution for the Primal. We indicate this
by a new table with an additional two rows to indicate which variables
are basic (*) and which are non basic (no * ). We indicate basic
for both Primal and Dual.
Note that the variables that are basic in the Primal correspond to
variables that are nonbasic in the Dual, and variables that are basic
in the Dual correspond to variables that are nonbasic in the Primal.
Now suppose we perform a pivot operation on the Primal. We get a new
set of basic and nonbasic variables. To perform the corresponding
pivot operation on the Dual one must select a pivot element such that
this basic-nonbasic relationship between the Primal variables and
corresponding Dual variables continues to hold. Hence if at some point
during the simplex procedure one has a table with basic variable for
the Primal indicated by
then, after performing the corresponding
pivot operation on the Dual, the basic variables for the Dual must
be those whose corresponding Primal variables are nonbasic. This is
indicated in the following table.
If one performs the simplex algorithm on the Primal and performs the
corresponding pivot operation on the Dual ( as indicated above), then
if the Primal becomes optimal, the Dual will become feasible. The
feasibility of the Dual will be indicated by obtaining nonnegative
values for the basic variables. Note that in the initial table above
for the Dual, the basic variables for the Dual, the
are not
feasible unless all of the
are nonpositive.
File translated from
TEX
by
TTM,
version 3.72. On 10 Oct 2007, 15:47.