# Linear programming & duality theory: how to calculate the value of the dual variables

• Apr 21st 2013, 07:44 AM
LouisPhilippe
Linear programming & duality theory: how to calculate the value of the dual variables
Hi everyone

I have been working on optimization with linear programming and mixed integer programming. A way in which a solution can be proven to be optimal is when the solution in the dual problem is feasible.

The basic principles of duality theory are clear to me and I know how to construct to dual problem. One thing keeps eluding me and that is how I can calculate the precise value of the dual variables for any given solution of the primal problem. I know that these variables can be interpreted as the 'shadow prices' aka the improvement of the objective function by increasing the left hand side of an equation (in case of a maximization problem) and I know that they can be deduced from simplex tables but I can't find how I could calculate them for any given solution.

A practical example I have been working on is the simple knapsack problem as stated below:

Attachment 28063

And I should be able to prove that this solution is an optimal one for the fractional knapsack problem (so without the integrality constraints, but still restricting the x variables to less than one):

Attachment 28064

All help on this is greatly appreciated.

Again my question is: How can I calculate what the value is for the dual variables for any given value of the primal variables? (Without solving it with excel or another type of software) - the problem is only included as an illustration.