Relations Between Primal And Dual

Relations between Primal and DualIf the primal problem isMaximize ct x subject to Ax b, x 0then the dual isMinimize bt y subject to At y c (and y unrestricted)Easy fact:If x is feasible for the primal, and y is feasible for the dual, thenct x bt ySo (primal optimal) (dual optimal) (Weak Duality Theorem)Much less easy fact: (Strong Duality Theorem)If one of the primal and the dual have finite optima, they both have and(primal optimal) (dual optimal)1

The “Inverse Matrix”In the initial simplex tableau, there’s an identity matrix. At a later simplextableau, the “inverse matrix” is the matrix occupying the same space asthat original identity matrix.The inverse matrix conveys all information about the current state of thealgorithm, as we will see.2

3

Computing dual values from Inverse MatrixIf we have reached the optimal primal tableau, these methods give theoptimal dual values; at earlier iterations, they give a certain “dual” of thecurrent basic feasible solutionMethod 1:Row vector of dual values Row vector of original objective values ofcurrent basic variables (listed in order they appear along basic column ofcurrent tableau) X current inverseMethod 2: (see textbook for this)Write wi for initial basic variable in row i.Value of dual variable yi current z-row coefficient of wi originalobjective coefficient of wi4

Example — Primal problemMinimize 4x1 2x2 x3subject tox1 x2 2x3 32x1 2x2 4x3 5x1 , x2 , x3 0.In standard form:Minimize 4x1 2x2 x3 0s1 M R 0s2subject tox1 x2 2x3 s1 R 32x1 2x2 4x3 s2 5x1 , x2 , x3 , s1 , R, s2 0.5

Example — The dualMaximize 3y1 5y2subject toy1 2y2 4y1 2y2 22y1 4y2 1 y1 0, i.e. y1 0y1 My2 0Note that the addition of the artificial variable to the primal adds a newconstraint to the dual: y1 M . But since we imagine M to be very large,this effectively puts no new constraint on y1 . For convenience, we’ll takeM 100.6

Example — initial tableaux1x2x3s1Rs2solnz-row9698201 10000300R112 1103s22 240015Inverse matrix is boldedCurrent solution: R 3, s2 5, z 300. Feasible, but not optimalCurrent “dual solution”: (y1 y2 ) (100 0) 1001 (100 0)i.e. y1 100, y2 0, zdual 300We will see later that this is “optimal but not feasible”.7

Example — first iterationx1z-row 4.5x2x3s1Rs2soln198.50 1000 50.2548.75R020 11 .5.5x3.5 .5100.251.25Inverse matrix is boldedCurrent solution: R .5, x3 .25, z 48.75. Feasible, but not optimalCurrent “dual solution”: (y1 y2 ) (100 1) 1 .50.25i.e. y1 100, y2 50.25, zdual 48.75Again, “optimal but not feasible”.8 (100 50.25)

Example — optimal tableaux1z-row 4.5x2x3s1R00 .75s2 99.25 .625soln .875x2010 .5.5 .25.25x3.501 .25.25.1251.375Inverse matrix is boldedOptimal solution: x2 .25, x3 1.375, z .875.Optimal dual solution: (y1 y2 ) (2 1) .5 .25.25.125 (.75 .625)i.e. y1 .75, y2 .625, zdual .875This is readily checked to be feasible and optimal for dual9

Getting whole tableau from Inverse (and initial data)Constraint columns:New constraint column current inverse X original constraint columnObjective coefficients:Objective coefficient (z-row entry) of variable xj Left hand side of jthdual constraint (evaluated at current “dual solution”) - right hand side ofjth dual constraint10

Example — first iteration of previous problemx1z-row 4.5x2x3s1Rs2soln198.50 1000 50.2548.75R020 11 .5.5x3.5 .5100.251.25We look at (bolded) x2 constraint column and objective entry 1 .512 0 .25 2 .5(Inverse X original x2 column new x2 column)Coefficient of x2 in z-row is computed by(y1 2y2 ) 2 ([100] 2[ 50.25]) 2 198.5using values of y1 , y2 computed earlier.11

Relations between Primal and Dual If the primal problem is Maximize ctx subject to Ax b, x ‚ 0 then the dual is Minimize bty subject to Aty ‚ c (and y unrestricted) Easy fact: If x is feasible for the primal, and y is feasible for the dual, then ctx bty So (primal optimal) (dual optimal) (Weak Duali