Dea Duality and Sensitivity Analysis

Getting Duality/Sensitivity Information in Different Modeling Environments

When covering duality, we went over the Strong Duality Theorem and the Complementarity Slackness Theorem.  Both of these theorems showed that in order to declare optimality we need

• A primal solution that is feasible
• A dual solution that is feasible
• These primal and dual solutions must give a zero duality gap or, equivalently, satisfy complementarity.

Therefore, all linear programming solvers simultaneously solve BOTH the primal and the dual problems in order to guarantee that they have found the optimal solution.  This also means that as long as you model and solve one of the two problems, all you have to do is dig around to find the solution to the other (remember that the dual of the dual is the primal problem!).  You do not need to model and solve the other problem separately.  In this document, we will go over how to obtain the dual solution from models written and solved in AMPL, Matlab, SAS/OR, and R.  Of course, this will all be illustrated using the Beaver Creek Pottery example.

AMPL

The Beaver Creek Pottery problem can be modeled as follows in AMPL:

var B >= 0;

var M >= 0;

maximize profit:

        40*B + 50*M;

subject to labor_avail:

        1*B + 2*M <= 40;

subject to clay_avail:

        4*B + 3*M <= 120;

We can solve this problem on NEOS using any solver we want, including Gurobi.  But Gurobi only shows us the optimal value of the objective function after it solves our problem.  If we want to see more than the optimal value of the objective function, we can also write the following command file:

solve;

display B;

display M;

This command file will tell Gurobi to go ahead and solve the problem and then display the optimal number of bowls and mugs.  Similarly, we can also ask Gurobi to give us the dual optimal solution as well:

solve;

display B;

display M;

display labor_avail;

display clay_avail;

Note that we have used the names of the constraints in order to display the values of the dual variables.  Remember that dual variables are shadow prices and are associated with each constraint, so we can use the names of the constraints to access the optimal values of their corresponding dual variables.

If we also want to obtain the reduced costs associated with each decision variable, we can expand the command file to

solve;

display B;

display M;

display labor_avail;

display clay_avail;

display B.rc;

display M.rc;

The .rc extension is for the reduced cost.  There are other extensions that show the upper and lower bounds on the variables, etc., but they are not particularly useful.

SAS/OR

The setup in SAS/OR is very similar to AMPL.  After the solve command, we can use print commands to display the dual optimal solution.

Remember our Beaver Creek Pottery model from Week 1:

proc optmodel;

var bowls >= 0;

var mugs >= 0;

maximize Total_Profit= 40*bowls + 50*mugs;

con labor: 1*bowls + 2*mugs <= 40;

con clay: 4*bowls + 3*mugs <= 120;

solve;

print bowls.sol;

print mugs.sol;

quit;

Right now, we are asking SAS/OR to display the number of bowls and the number of mugs in the optimal solution using the .sol extension for the decision variables.  In order to print the reduced costs associated with the variables, include the following print statements before the quit command:

...