8.4 Duality Theory 111- If Cjy — XN > 6, stop; the current solution is optimal. Otherwise, if the
most negative component is eth component, choose eth column of N to
enter the basis. Denote it by u. - Compute v = B~lu.
- Calculate ratios of B~lb to v = B~lu, admitting only positive compo-
nents of v. If there are no positive components, the minimal cost is —oo;
if the smallest ratio occurs at component I, then Ith column of current B
will be replaced with u. - Update B (or £?_1) and the solution is XB = B~lb. Return to SI.
Remark 8.3.1 We need to compute X = cB^B~l,v = B~lu, and XB =
B~*b. Thus, the most popular way is to work only on B"^1. With the help of
previous remark, we can update B~l 's by premultiplying E_1 's.The excessive computing (multiplying with E~lys) could be avoided by
directly reinverting the current B at a time and deleting the current E~l,s
that contain the history.Remark 8.3.2 The alternative way of computing X,v and XB is XB =
Cg,Bv — u, and BXB = b. Then, the standard decompositions (B = QR
or PB = LU) lead directly to these solutions.Remark 8.3.3 How many simplex iterations do we have to take?
There are at most (^) extreme points. In the worst case, the simplex method
may travel almost all of the vertices. Thus, the complexity of the simplex
method is exponential. However, experience supports the following average be-
havior. The simplex method travels about m extreme points, which means an
operation count of about m^2 n, which is comparable to ordinary elimination to
solve Ax = b, and that is the reason of its success.8.4 Duality Theory
The standard primal problem is: Minimize cTx subject to Ax > b and x > 6.
The dual problem starts from the same A, b, and c and reverses everything:
Maximize yTb subject to ATy < c and y > 8.
There is a complete symmetry between the two. The dual of the dual is
the primal problem. Both problems are solved at once. However, one must
recognize that the feasible sets of the two problems are completely different.
The primal polyhedron is a subset of M.n, marked out by matrix A and the
right hand side b. The dual polyhedron is a subset of Km, determined by AT
and the cost vector c.
The whole theory of linear programming hinges on the relation between
them.
Theorem 8.4.1 (Duality Theorem) // either the primal problem or the
dual has an optimal vector, then so does the other, and their values are the