Constructing the Dual of a Standard-Form LP

Given a standard-form maximization LP, mechanically write down its dual. The standard primal is $\max\ \mathbf{c}^T\mathbf{x}$ subject to $A\mathbf{x}\le\mathbf{b}$ , $\mathbf{x}\ge\mathbf{0}$ ; its dual is $\min\ \mathbf{b}^T\mathbf{y}$ subject to $A^T\mathbf{y}\ge\mathbf{c}$ , $\mathbf{y}\ge\mathbf{0}$ . Students practice extracting both the full dual and individual pieces (objective, one constraint).

Step 1 of 157%

Tutorial

Standard Form and Its Dual

A standard-form linear program (LP) in maximization form is

\max\ \mathbf{c}^T\mathbf{x}\quad\text{subject to}\quad A\mathbf{x}\le\mathbf{b},\ \mathbf{x}\ge\mathbf{0},

where $A$ is an $m\times n$ matrix, $\mathbf{b}\in\mathbb{R}^m$ , $\mathbf{c}\in\mathbb{R}^n$ , and the $n$ decision variables $x_1,\dots,x_n$ are required to be nonnegative.

Bounding the primal objective from above amounts to choosing nonnegative multipliers $y_1,\dots,y_m\ge 0$ so that the weighted combination of the rows of $A$ dominates $\mathbf{c}$ . The dual LP is the problem of finding the tightest such bound:

\min\ \mathbf{b}^T\mathbf{y}\quad\text{subject to}\quad A^T\mathbf{y}\ge\mathbf{c},\ \mathbf{y}\ge\mathbf{0}.

There is one dual variable $y_i$ per primal constraint, and one dual constraint per primal variable.

Recipe for converting primal to dual:

Replace $\max$ with $\min$ .
The primal RHS vector $\mathbf{b}$ becomes the dual objective coefficients.
The primal objective coefficients $\mathbf{c}$ become the dual RHS.
Transpose the constraint matrix and flip $\le$ to $\ge$ .
Both primal and dual variables are nonnegative.

For example, the dual of

\max\ 4x_1+x_2\quad\text{s.t.}\quad x_1+2x_2\le 6,\ 3x_1+x_2\le 9,\ x_1,x_2\ge 0

\min\ 6y_1+9y_2\quad\text{s.t.}\quad y_1+3y_2\ge 4,\ 2y_1+y_2\ge 1,\ y_1,y_2\ge 0.