Transcription of Linear Programming: Chapter 5 Duality - Princeton University
{{id}} {{{paragraph}}}
Example: barber
Linear Programming: Chapter 5 Duality - Princeton University
Linear Programming: Chapter 5 DualityRobert J. VanderbeiOctober 17, 2007 Operations Research and Financial EngineeringPrinceton UniversityPrinceton, NJ 08544 rvdbResource AllocationRecall the resource allocation problem (m= 2,n= 3):maximizec1x1+c2x2+c3x3subject toa11x1+a12x2+a13x3 b1a21x1+a22x2+a23x3 b2x1, x2, x3 0,wherecj=profit per unit of productjproducedbi=units of raw materialion handaij=units raw materialirequired to produce1unit of Up ShopIf we produce one unit less of productj, then we free up: a1junits of raw material1and a2junits of raw these unused raw materials fory1andy2dollars/unityieldsa1jy1+ interested if this exceeds lost profit on each productj:a1jy1+a2jy2 cj,j= 1,2, a buyer offering to purchase our entire to above constraints, buyer wants to minimize cost:minimizeb1y1+b2y2subject toa11y1+a21y2 c1a12y1+a22y2 c2a13y1+a23y2 c3y1, y2 Problem:maximizen j=1cjxjsubject ton j=1aijxj bii= 1,2.
Strong Duality Theorem Conclusion on previous slide is the essence of the strong duality theorem which we now state: Theorem. If the primal problem has an optimal solution, x = (x 1;x 2;:::;x n); then the dual also has an optimal solution, y = (y 1;y 2;:::;y m); and X j c jx j = X i b iy i: Paraphrase: If primal has an optimal solution, then ...
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: