Re: Question on linear programming duality

[EMAIL PROTECTED] wrote in news:3171ed12.0311230958.4a043bf9
@posting.google.com:

> What is the relationship (if any) between the reduced costs of
> variables in a constraint to the dual value of the constraint itself ?
> If a variable appears in more than one row, what is the relationship
> between the dual values of the constraints and the variables' reduced
> cost ?
> 
> Thanks
> Ani
> 

Don't think you'll find anything useful for the first question.  If the 
primal problem is

opt c'x
s.t. Ax = b
      x >= 0

where prime (') denotes transpose, all vectors begin life as column 
vectors, and "opt" is your choice of min or max, and if we denote the 
dual vector by y, then the reduced cost vector r is given by

r' = c' - y'A.

So the reduced costs of the variables in a given row i are indeed related 
to the dual value (y_i) for that row, but they are also related to the 
dual values of all other rows.  The second question is more tractable:  
if primal variable x_j appears in (has non-zero coefficients A_{ij} in) 
rows indexed by set I, then its reduced cost is

r_j = c_j - sum_{i \in I} y_i*A_{ij}.

-- Paul

*************************************************************************
Paul A. Rubin                                  Phone:    (517) 432-3509
Department of Management                       Fax:      (517) 432-1111
The Eli Broad Graduate School of Management    E-mail:   [EMAIL PROTECTED]
Michigan State University                      http://www.msu.edu/~rubin/
East Lansing, MI  48824-1122  (USA)
*************************************************************************
Mathematicians are like Frenchmen:  whenever you say something to them,
they translate it into their own language, and at once it is something
entirely different.                                    J. W. v. GOETHE