Duality Theory 153
4.6.1 Dual Simplex Method
We now develop a variant of the simplex method called the dual simplex
method. The strategy in this approach relaxes primal feasibility, but main-
tains dual feasibility and complementary slackness for all iterations and at
termination, satisfies primal feasibility. The dual simplex method is suitable
when it may be difficult to obtain an initial primal basic feasible solution,
but a dual feasible solution is readily available. However, its more substantial
value may be seen in its use in sensitivity analysis, which will be covered later
in this chapter.
The dual simplex method starts with a primal basic solution such that the
reduced costs are non-negative or equivalently π = (c
T
B
B
−1
)
T
is feasible for
the dual ...