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:minimizeb1y1+b2y2subject toa11y1+a21y2 c1a12y1+a22y2 c2a13y1+a23y2 c3y1, y2 Problem.

2 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?Primal ValuesDual ValuesPrimal ValuesDual ValuesGapNo GapAnswer is provided by the Strong Duality Theorem (coming later).

3 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, .. , 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).

4 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).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.

5 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). 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!

6 Fourth Pivot Phase IICurrent dictionary:It s fake the real thing (top row).Primal pivot:x3enters, DictionaryAfter pivot:Problem isunbounded!