Optimization Methods in Management Science Tutorial 6 - Forming LP Duals

Forming an LP Dual I heard that today’s lecture is about forming the dual. Tim, the turkey Hamilton, you’re going to die. Burr, we shouldn’t be fighting. You misunderstood me when I said we needed a dual. Aaron Burr and Alexander Hamilton (not really) 1 Forming Dual LPs in General Every linear program has a unique dual. The dual of the dual linear program is the original linear program. We will explain rules for taking the dual of a maximization problem. The first thing to remember is that every linear program has a dual, and there are simple rules for formulating the dual. • • Some of the rules are common to all linear programs. These are the first rules to learn. FIRST RULES 1. There is a dual variable for every constraint 2. The constraint matrix of the dual is the transpose of the constraint matrix of the primal. 3. The objective function and RHS are swapped. • 2 Ollie A “standard” primal-dual pair The Primal LP Maximize z= subject to 1 x1 + 8 x1 12 x1 16 x1 x1 ≥ 0, 2 x2 + 3 x3 + Dual Variable 4 x4 + 9 x2 + 10 x3 + 11 x4 + 13 x2 + 14 x3 + 15 x4 + 17 x2 + 18 x3 + 19 x4 x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 ≤ 5 ≤ 6 ≤ 7 y1 y2 y3 The Dual LP Minimize subject to v= 5 y1 + 6 y2 + 7 y3 8 9 10 11 y1 + 12 y2 + 16 y3 y1 + 13 y2 + 17 y3 y1 + 14 y2 + 18 y3 y1 + 15 y2 + 19 y3 y1 ≥ 0 y2 ≥ 0 y3 ≥ 0 ≥ ≥ ≥ ≥ 1 2 3 4 3 All linear programs have an objective, linear inequalities and inequalities, and variables. What makes this pair of LPs the “standard” one? In the “standard” primal-dual pair (not to be confused with an LP in standard form), the max problem has “≤ constraints” and all variables are non-negative. The dual is a minimization problem with “≥ constraints” and non-negativity constraints. It’s important to remember this, as we shall soon see. 4 Ollie We will show how to form dual linear programs using the SOB approach. SOB approach! I object! We need to optimize family values, and this isn’t the way to go. Nooz, the most trusted name in fox. Don’t worry Reverend Falwell. As usual, your fears as absolutely groundless. Cleaver 5 For the max problem: Hi, I’m Art Benjamin. I invented the SOB approach. The letters stand for “sensible, odd, and bizarre”. Professor Orlin used to use “standard” but instead of “sensible” which is OK. Primal max i-th constraint ≤ S i-th constraint = O i-th constraint ≥ B In the max problem, we expect the constraints to be ≤. This is sensible. But if we get an “= constraint” we are only a little surprised. We find this odd. However, a “≥ constraint” is bizarre. S: sensible O: odd B: bizarre 6 I also do mathemagic, the art of mental calculation. For the min problem: Dual min i-th constraint ≥ S i-th constraint = O i-th constraint ≤ B In the min problem, we expect the constraints to be ≥. This is sensible. But if we get an “= constraint” we are only a little surprised. We find this odd. However, a “≤ constraint” is bizarre. S: sensible O: odd B: bizarre 7 Constraints on variables for all LPS I found that students really had trouble remembering the rules for forming the LP dual until I came up with the SOB approach. i-th variable ≥0 S i-th variable free O i-th variable ≤0 B For all linear programs, we expect variables to be nonnegative. This is sensible. But occasionally we get variables that are unconstrained in sign. This is odd. If we ever get variables to that are required to be non-positive, we view it as bizarre. 8 Combining all of the rules Primal max Dual min i-th constraint ≤ i-th variable ≥ 0 S i-th constraint = i-th variable free O i-th constraint ≥ i-th variable B i-th variable ≥ 0 i-th constraint ≥ S i-th variable free i-th constraint = O i-th variable ≤ 0 i-th constraint ≤ B ≤0 an“≥ constraint”, If If the the i-th i-th constraint constraint in in the the primal primal maximization maximization problem problem is is a a “≤“=constraint”, constraint”, then ≤ then the the i-th i-th variable variable in in the the dual dual problem problem is is free ≥ 0. 0. (unconstrained in sign). The rules areboth interpreted as follows: In case, constraints are bizarre. In this this case, both constraints are odd. sensible. If the i-th variable in the problem maximization problem is ≤ ≥ 0, then free, thenthe thei-th i-th 9 a “≥“= “≤constraint”. constraint”. constraint in the dual problem is an bizarre. sensible. In this case, both constraints are odd. Rules for creating a dual linear program The Primal LP Maximize z= subject to 1 x1 + 2 x2 + 3 x3 + 8 x1 + 9 x2 12 x1 + 13 x2 16 x1 + 17 x2 x1 ? x2 ? Dual Variable 4 x4 + 10 x3 + 11 x4 + 14 x3 + 15 x4 + 18 x3 + 19 x4 x3 ? x4 ? ? ? ? 5 6 7 y1 y2 y3 The Dual LP Minimize subject to v= 5 y1 + 6 y2 + 7 y3 8 9 10 11 y1 + 12 y2 + 16 y3 y1 + 13 y2 + 17 y3 y1 + 14 y2 + 18 y3 y1 + 15 y2 + 19 y3 y1 ? y2 ? y3 ? ? ? ? ? 1 2 3 4 10 The SOB approach sensible, odd, and bizarre The Primal LP Max s.t. z= 1 x1 + 2 x2 + 3 x 3 + 8 x1 + 9 x2 + 4 x4 10 x3 + 11 x4 12 x1 + 13 x2 + 14 x3 + 15 x4 16 x1 + 17 x2 + 18 x3 + 19 x4 x1 ≥ 0, x2 ≥ 0, x3 uis, x4 ≤ 0 ? S B S O ≥ 5 = 6 ≤ 7 B O S uis. unconstrained in sign, also known as free. This is a chance to practice determining which are constraints are S, O, or B. Then try to formulate the dual before turning to the next page by using the rules on page 9. 11 The SOB approach sensible, odd, and bizarre The Dual LP Min s.t v= 5 y1 + 6 y2 + 7 y3 ≥ 1 S 9 y1 + 13 y2 + 17 y3 ≥ 2 S 10 y1 + 14 y2 + 18 y3 = 3 O 11 y1 + 15 y2 + 19 y3 ≤4 8 y1 + 12 y2 + 16 y3 B y1 ≤ 0, y2 uis y3 ≥ 0 B O S 12 Tim, you have asked a very deep question. We’ll give a partial answer next. This whole approach seems a bit bizarre. Why do these rules work at all? Recall that the optimal dual variables are also the shadow prices. We will show that the rules for forming the signs of the dual variables correspond to what we know about shadow prices. 13 Ollie The Primal LP Max z= s.t. 1 x1 + 2 x2 + 3 x 3 + 8 x1 + 9 x2 + Dual Variable 4 x4 10 x3 + 11 x4 ≥ 5 12 x1 + 13 x2 + 14 x3 + 15 x4 = 6 16 x1 + 17 x2 + 18 x3 + 19 x4 ≤ 7 x1 ≥ 0, x2 ≥ 0, x3 uis, y1 y2 y3 x4 ≤ 0 ? The first constraint is a “≤ constraint”. If we increase the RHS from 5 to 5+Δ, then the problem becomes more constrained, and there are fewer options. The optimal objective value either stays the same or goes down. So the shadow price y1 ≤ 0. A similar argument shows that y3 ≥ 0. As for modifying the RHS of constraint 2. Changing the 6 to 6 + Δ will change the feasible region, but we don’t know whether the opt objective will go up or down. And so y2 is free. Ollie 14 Last Slide And on that note, we end our tutorial on on forming LP duals. We hope that this tutorial has been informative, and we look forward to seeing you again at the next tutorial.. Cleaver 15