1
$\begingroup$

I'm wondering how can I minimally prove that the dual variable of a linear program (LP) is the derivative of its optimal value w.r.t. to the RHS constants $b$.

$$ Maximize \space c^Tx $$ $$ s.t. \space Ax ≤ b, x ≥ 0; $$

My understanding of the dual variables is from duality of LP from wikipedia, and rather limited to the natural language interpretation therein.

I saw that it is mentioned here, that

The interpretation of the dual variables as derivatives of the optimal value of the objective function with respect to the elements of the right-hand-side is well known in mathematical programming. This result can be extended to ...

How can this be proved in an elementary way (with a minimum number of citation of other necessary theorems)?

I understand the form the dual problem and the formal definition of dual variables. But I have trouble envisioning the derivative of optimal objective value, since it is not a closed form linear function (but rather a linear function subject to a set of linear inequalities).

Is it possible to convert the optimal solution to a closed form function of the RHS, and then take the derivative using linear algebra? (I guess not).

$\endgroup$
  • $\begingroup$ Could you give your definition of 'reduced price'? The Lagrangian is a linear function of the dual variables btw. $\endgroup$ – LinAlg Jul 23 '18 at 13:55
  • $\begingroup$ @LinAlg Thanks for your clarification. I may have some misconception about reduced price/cost. Just changed mention of "reduced cost" to "dual variables" to be minimal and consistent with the quote. $\endgroup$ – tinlyx Jul 23 '18 at 14:06
  • $\begingroup$ the statement is true only if the basis does not change; a proof follows trivially from revised simplex $\endgroup$ – LinAlg Jul 23 '18 at 14:37
  • $\begingroup$ Related: math.stackexchange.com/questions/3460124/…. $\endgroup$ – user76284 Dec 11 '19 at 23:14

Your Answer

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

Browse other questions tagged or ask your own question.