Simplex method : Duality by Bazaraa

linear-programming

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

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$.
Row 2 in $P$ is a $=$ constraint $\Rightarrow$ $w_2$ is unrestricted.
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.
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.

The SOB table by Mike Spivey is actually seems really good, but here is a method I sometimes used when I forgot the identities.

If you know how to convert the primal to dual abstractly, but not the precise direction of the inequalities, write down the lagrangian. You can easily derive the direction by the requirement that the value of lagrangian is finite. This method corresponds to using the economic interpretation but I find that one just as hard to remember.

In the case of your example:

$L = \min_w \max_{x_1\leq 0;\, x_2 \geq 0} \quad 8x_1 + 3x_2 + w_1(2 - (x_1 - 6x_2)) + w_2(-4 - (5x_1 +7x_2)$

The order of min / max means that for every choice of $w$, $x$ will obtain or tend to its extrema. You just need to find the condition which bounds the behaviour of $x$,

The dual variables induce a multiplying factor on deviation of the primal constraints in terms of (rhs - coefficient vector).
- In this case the deviation for the first constraint is positive if it's violated, and the primal is a maximization problem, therefore unless $w_1 \leq 0$, the value of L will always tend to infinity.
- The second constraint is an equality so $w_2$ must be free to be able to counteract violations on both sides, this actually does not bounds that specific term of the lagrangian per se, but this part you can just remember.
If you rewrite $L$ you wil see that for every primal var, the coefficients in the column times the dual variable associated with the row are subtracted from objective function. In the economic interpretation the dual vars are therefore also called shadow prices. The value of the row gives you the cost/savings depending on whether your primal is in min or max. Depending on the sign of the primal var and the direction of optimization you can easily see if this cost/saving must be bounded above or below by the value/cost.
- The primal var $x_1\leq 0$. This means that if that cost exceeds the value of $x_1$, $x_1$ has negative marginal value, and decreasing $x_1$ to -$\infty$ will maximize $L$. Ergo $w_1 + 5w_2 \leq 8$.
- Similarly the 'net value' of $x_2$ must non-positive since $x_2\geq 0$ so $-6w_1 + 7w_2 \geq 3$.