Linear Programming: Chapter 5 Duality

1 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.

2 Minimizeb1y1+b2y2subject toa11y1+a21y2 c1a12y1+a22y2 c2a13y1+a23y2 c3y1, y2 Problem:maximizen j=1cjxjsubject ton j=1aijxj bii= 1,2, .. , mxj 0j= 1,2, .. , n,Has a dual :minimizem i=1biyisubject tom i=1yiaij cjj= 1,2, .. , nyi 0i= 1,2, .. , of DualPrimal Problem:maximizen j=1cjxjsubject ton j=1aijxj bii= 1, .. , mxj 0j= 1, .. , n,Original problem problem is definedby its data (notationused for the variablesis arbitrary). dual in Standard Form: maximizem i=1 biyisubject tom i=1 aijyi cjj= 1, .. , nyi 0i= 1, .. , negativetranspose of of dual is Duality TheoremIf(x1, x2, .. , xn)is feasible for the primal and(y1, y2, .. , ym)is feasible forthe dual , then jcjxj jcjxj j( iyiaij)xj= ijyiaijxj= i jaijxj yi or No Gap?An important question:Is there a gap between the largest primal value and the smallest dualvalue?

3 Primal ValuesDual ValuesPrimal ValuesDual ValuesGapNo GapAnswer is provided by the Strong Duality Theorem (coming later).Simplex Method and DualityA Primal Problem:Its dual :Notes: dual is negative transpose ofprimal. Primal is feasible, dual is primal to choose pivot:x2enters, analogous pivot in dual :z2leaves, IterationAfter First Pivot:Primal (feasible): dual (still not feasible):Note:negative transpose property , use primal to pick pivot:x3enters, analogous pivot in dual :z3leaves, Second IterationPrimal: : Negative transpose propertyremains intact. method applied to primal problem (two phases , if necessary),solves both the primal and the Duality TheoremConclusion on previous slide is the essence of thestrong Duality theoremwhich wenow the primal problem has an optimal solution,x = (x 1, x 2.)

4 , x n),then the dual also has an optimal solution,y = (y 1, y 2, .. , y m),and jcjx j= ibiy :If primal has an optimal solution, then there is no Duality GapFour possibilities: Primal optimal, dual optimal (no gap). Primal unbounded, dual infeasible (no gap). Primal infeasible, dual unbounded (no gap). Primal infeasible, dual infeasible (infinite gap).Example ofinfinite gap:maximize2x1 x2subject tox1 x2 1 x1+x2 2x1, x2 optimality, we havexjzj= 0,forj= 1,2, .. , n,wiyi= 0,fori= 1,2, .. , the proof of the Weak Duality Theorem: jcjxj j(cj+zj)xj= j( iyiaij)xj= ijyiaijxj= i jaijxj yi= i(bi wi)yi ibiyi,The inequalities come from the fact thatxjzj 0,for allj,wiyi 0,for Strong Duality Theorem, the inequalities are equalities at Simplex MethodWhen: dual feasible, primal infeasible ( , pinks on the left, not on top).

5 An both primal and dual dictionaries:Looking at dual dictionary:y2enters, the primal dictionary:w2leaves, Simplex Method: Second PivotGoing in, we have:Looking at dual :y1enters, at primal:w1leaves, Simplex Method Pivot RuleRefering to the primal dictionary: Pick leaving variable from those rows that areinfeasible. Pick entering variable from a box with a negative value and which can beincreased the least (on the dual side).Next primal dictionary shown on next Simplex Method: Third PivotGoing in, we have:Which variable must leave and which must enter?See next Simplex Method: Third Pivot AnswerAnswer is:x2leaves, dictionary is OPTIMAL: dual -Based Phase I MethodExample:Notes: Two objective functions: the true objective (on top), and a fake one (belowit).

6 ForPhase I, use the fake objective it s dual feasible. Two right-hand sides: the real one (on the left) and a fake (on the right). Ignore the fake right-hand side we ll use it in another algorithm I First Pivot:w3leaves, first Phase I Method Second PivotRecall current dictionary: dual pivot:w2leaves, pivot: dual -Based Phase I Method Third PivotCurrent dictionary: dual pivot:w1leaves, pivot:It sfeasible!Fourth Pivot Phase IICurrent dictionary:It s fake the real thing (top row).Primal pivot:x3enters, DictionaryAfter pivot:Problem isunbounded!