Duality Notes 18 310 Fall 2005 Prof Peter Shor One of the most important aspects of linear programming is the duality theorem Let s consider a linear program in the standard form we talked about last time max X subject to vk xk k X Ajk xk bj j and k xk 0 k Now how might we come up with an upper bound for the objective function k vk xk Recall the example we did at the end of last class where we took a sum of some multiple of the inequalities and found that this gave us an upper bound on the objective function We ll use the same trick in greater abstraction So what we ll try to do is to take all these inequalities P X Ajk xk bj k multiply each of them by some value y j and add all the equations up We want to choose these values of yj so that this is a bound on xk What happens when we sum these inequalities We get X yj X j Ajk xk X bj yj j k We need that all the yj 0 because if we multiplied by a negative y j we would reverse the sign of the inequality However if all the yj are positive then the above equation must hold for any feasible point x1 x2 xn since a feasible point satisfies all the inequalities P How can we make sure that the resulting sum is a bound on vk xk We need to make sure that X XX vk xk yj Ajk xk j k k for all feasible points xk One way to ensure this is to make sure that the coefficient on xk on the left is less than the coefficient on x k on the right Thus we would need vk X yj Ajk j 1 k Note that here we are using the fact that x k 0 P Any set of yj satisfying the above equations gives us an upper bound j bj yj on the objective function How do we get the best bound on the objective function P We need to minimize j bj yj P When we minimize j bj yj we get another linear program although this one isn t in our standard form We have the linear program min X subject to bj yj j X Ajk yj vk k and j yj 0 j What have we done The right hand side of the constraints variables b j have switched places with the constants in the objective variables v k We ve effecP P tively transposed the matrix Ajk so instead of k Ajk xk we have j Ajk yj We ve swapped min for max and for Now we ve got a new linear program which we call the dual We call the original linear program the primal The dual of the dual will be the primal We have seen that if we have two feasible sets of variables x k and yj for the primal and dual respectively the objective function of the dual is always at least the objective function of the primal This shows that the optimal value of the dual is always at least the optimal value of the primal Now a truly amazing fact about linear programming and the source of a lot of its effectiveness is that these two values are equal This is known as the duality theorem of linear programming We will prove it in a little bit The theorem actually says a bit more about infeasible and unbounded linear programs We won t prove this in class but it s not hard to generalize the proof to handle these cases Theorem The duality theorem for linear programming If both the primal and the dual are feasible and unbounded the optimal value of the primal is equal to the optimal value of the dual The primal is infeasible if the dual is unbounded The dual is infeasible if the primal is unbounded It is possible for both the dual and the primal to be infeasible One can get this situation by combining a linear progrma with an infeasible primal and unbounded dual by one with an unbounded primal and infeasible dual There is a recipe for taking a linear program whether or not it s in standard form and finding it s dual Inequalities turn into variables y j with the constraint yj 0 Equations turn into variables yj which can be either positive or negative and so 2 on However the recipe is complicated enough that if you memorize it you re likely to forget it or remember it wrong when you have to use it especially if you try to memorize the recipe for general linear programs and not just standard form The best way of remembering how to find the dual is remembering the proof above that the dual optimum is at least the primal optimum and reproducing it whenever you need it We now want to prove the duality theorem That is we want to show that the optimal value of the primal is equal to the optimal value of the dual We ve shown one inequality already this was the easy one so now we need to show the other inequality We will be able to do this by looking at the final tableau in the simplex algorithm and show that the objective function it gives is not only a feasible solution for the primal but also a feasible solution for the dual So let s recall the simplex algorithm We started by taking all the inequalities that weren t of the form xk 0 and adding a slack variable sj to them so that we get inequalities and equalities of the form xk 0 k sj 0 j X Ak xk b k k We then let all these equalities be a row in a tableau and put the objective function on the bottom row and performed row operations on the tableau We stopped and claimed we had the optimum value of the objective function when the bottom row had all non positive entries Suppose that at the end of the algorithm the last row is w1 w 2 w 3 w n r 1 r 2 r m F where wk is in the column whose variable is xk and rk is in the column whose variable is sk Assuming that the simplex algorithm found an optimum all entries in the last row will be non positive and there will be at least m zeros Now we know this last row is obtained by taking the original objective function v1 v2 v3 vn 0 0 0 0 and adding some linear combination of the rows to it A typical row is Aj 1 Aj 2 Aj 3 Aj n 0 0 1 0 0 0 where the 1 is in the column belonging to s j Now suppose we take the last row to be the original last row minus yj times the j th row This means that wk v k X j 3 yj Aj k and rj …