2 Attachment(s)

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.

Thanks in advance!

Louis-Philippe