Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I use great textbook (Linear Programming and Network Flows by Bazaraa II ed)

On the page 240 the author states that for every primal problem, regardless of it's type (canonical or standard), dual problem can be found by using the following converting table.

table for finding dual problem

Unfortunately, it remains unclear how exactly should I use this table.

There was an example

Consider the following linear programm

$$max \space 8x_{1}+3x_{2}$$ $$x_{1}-6x_{2} \geq 2$$ $$5x_{1}+7x_{2} = -4$$ $$x_{1} \leq 0$$ $$x_{2} \geq 0$$

applying the results of the table, we can immediatly write down the dual

$$min \space 2w_{1}-4w_{2}$$

$$w_{1}+5w_{2} \leq 8$$ $$-6w_{1}+7w_{2} \geq 3$$ $$w_{1} \leq 0$$ $$w_{2} unrestricted$$

Please, show me how can I use this table and get this result. And in you opininon what's the best technique for finding dual problem: converting to one of the form (canonical or standartd and find the dual), memorize the table, or something else.

Thanks!

share|improve this question

1 Answer 1

up vote 3 down vote accepted

One quick way to think about it is that you're transposing the entire problem. Imagine placing the primal coefficients in a matrix, with the objective at the bottom. This gives $P = \begin{bmatrix} 1 & -6 & 2 \\ 5 & 7 & -4 \\ 8 & 3 & \end{bmatrix}$. Transposing yields $P^T = D = \begin{bmatrix} 1 & 5 & 8 \\ -6 & 7 & 3 \\ 2 & -4 & \end{bmatrix}.$ Thus the dual (coefficients and variables only) looks like $$ \begin{align} \text{max or min } &2w_1 - 4w_2 \\ \text{subject to } &w_1 + 5w_2 \text{ ? } 8\\ &-6w_1 + 7w_2 \text{ ? } 3. \end{align} $$ Now we have to figure out whether we are maximizing or minimizing, what should go where the ?'s are, and whether the dual variables are nonnegative, nonpositive, or unrestricted. The table tells us all of this.

Since the primal problem is maximizing, the dual is minimizing. Everything else can be read by pairing rows with columns in the transposition: Row $x$ in $P$ goes with Column $x$ in $D$, and Column $y$ in $P$ goes with Row $y$ in $D$. Then the table says...

  1. Row 1 in $P$ is a $\geq$ constraint in a maximization problem $\Rightarrow$ The variable associated with Column 1 in $D$, $w_1$, has $w_1 \leq 0$.
  2. Row 2 in $P$ is a $=$ constraint $\Rightarrow$ $w_2$ is unrestricted.
  3. Column 1 in $P$ is for $x_1$, and $x_1 \leq 0$ $\Rightarrow$ The constraint associated with Row 1 in $D$ is a $\leq$ constraint.
  4. Column 2 in $P$, with $x_2 \geq 0$ $\Rightarrow$ The second constraint in the dual is a $\geq$ constraint.

Thus we get the complete form of the dual $$ \begin{align} \min &2w_1 - 4w_2 \\ \text{subject to } &w_1 + 5w_2 \leq 8\\ &-6w_1 + 7w_2 \geq 3 \\ &w_1 \leq 0 \\ &w_2 \text{ unrestricted.} \end{align} $$


For remembering how to do this, I prefer something called the "SOB" method instead of memorizing the table. "SOB" here stands for "sensible," "odd," or "bizarre." The SOB table is the following:

           Variables      Constraints, Maximizing   Constraints, Minimizing
Sensible     ≥ 0                     ≤                         ≥
Odd       Unrestricted               =                         =
Bizarre      ≤ 0                     ≥                         ≤

Hopefully it makes sense why these are "sensible," "odd," and "bizarre," at least relatively speaking.

The idea then is that sensible maps to sensible, odd maps to odd, and bizarre maps to bizarre when you're switching from the primal to the dual. Let's take the example problem. It's "bizarre" to have a $\geq$ constraint in a maximization problem, so the variable in the dual associated with the first constraint, $w_1$, must have the "bizarre" nonpositivity restriction $w_1 \leq 0$. It's "odd" to have an equality constraint, and so the variable in the dual associated with the second constraint, $w_2$, must have the "odd" unrestricted property. Then, it's "bizarre" to have a variable $x_1$ with a nonpositivity restriction, so the constraint in the dual associated with $x_1$ must have the "bizarre" $\leq$ constraint for a minimization problem. Finally, it's "sensible" to have a variable $x_2$ with a nonnegativity restriction, so the constraint in the dual associated with $x_2$ must have the "sensible" $\geq$ constraint for a minimization problem.

I've found that after a few practice examples my students generally internalize the SOB method well enough that they can construct duals without needing to memorize anything.

share|improve this answer
    
Great, thanks. I want to be your student –  com Nov 20 '11 at 15:03
    
@com: I'm glad it was helpful. :) –  Mike Spivey Nov 20 '11 at 15:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.