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:
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):
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