7
$\begingroup$

Why are shadow prices associated with nonnegativity constraints also called as reduced costs, even if they have the same interpretation as shadow prices associated with an optimal solution? Why the use of the term "reduced cost"?

$\endgroup$
7
$\begingroup$

In the simplex method, the term "reduced cost" is used for the marginal cost to introduce a nonbasic variable into the basis. At each iteration, reduced costs are calculated and in a minimization (maximization) problem the variable with the most negative (positive) reduced cost enters the basis via a pivot operation. One can show that the shadow price of a nonnegativity constraint is equal to the reduced cost of that variable in the final (optimal) basic feasible solution.

So "reduced cost" is not an alternate term for shadow price; it's a term related to the simplex method for solving the primal problem.

| improve this answer | |
$\endgroup$
1
$\begingroup$

As @prubin mentioned, the "reduced cost" is not an alternative term for shadow price. Many of optimization software like AMPL, GAMS and others, have an automatic facility to calculate and show these terms.

For instance, in the classical transportation problem (using GAMS), you could try the following to show what you want easily, where the (.m) in the last line is the marginal syntax to show dual of constraints and the reduced cost of variables.

Model transport / all /;
solve transport using lp minimizing z;
display x.l, x.m, supply.m, demand.m;

The results are:

---- EQU supply  observe supply limit at plant i

             LOWER     LEVEL     UPPER    MARGINAL

seattle       -INF    350.000   350.000      EPS       
san-diego     -INF    550.000   600.000      .         

---- EQU demand  satisfy demand at market j

            LOWER     LEVEL     UPPER    MARGINAL

new-york   325.000   325.000     +INF      0.225      
chicago    300.000   300.000     +INF      0.153      
topeka     275.000   275.000     +INF      0.126      

---- VAR x  shipment quantities in cases

                      LOWER     LEVEL     UPPER    MARGINAL

seattle  .new-york      .       50.000     +INF       .         
seattle  .chicago       .      300.000     +INF       .         
seattle  .topeka        .         .        +INF      0.036      
san-diego.new-york      .      275.000     +INF       .         
san-diego.chicago       .         .        +INF      0.009      
san-diego.topeka        .      275.000     +INF       .         

I hope, it would be useful.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.