Dual of an LP with Mixed Constraint Types

In the standard-form max primal $\max\ \mathbf{c}^T\mathbf{x}$ s.t. $A\mathbf{x}\leq \mathbf{b}$, $\mathbf{x}\geq 0$, every primal constraint produces a nonnegative dual variable. When the primal has constraint types other than $\leq$, the sign restriction on the corresponding dual variable changes.

For a maximization primal

$$\max\ \mathbf{c}^T\mathbf{x}\quad \text{s.t.}\quad \mathbf{a}_i^T\mathbf{x}\ \square_i\ b_i,\ i=1,\dots,m,\quad \mathbf{x}\geq 0,$$

where each $\square_i\in\{\leq,\geq,=\}$, the dual is

$$\min\ \mathbf{b}^T\mathbf{y}\quad \text{s.t.}\quad A^T\mathbf{y}\geq \mathbf{c},$$

with the sign restriction on $y_i$ determined by the type of the $i$-th primal constraint:

$$\begin{array}{c|c}\textbf{Primal constraint} & \textbf{Dual variable} \\ \hline \mathbf{a}_i^T\mathbf{x}\leq b_i & y_i\geq 0 \\ \mathbf{a}_i^T\mathbf{x}\geq b_i & y_i\leq 0 \\ \mathbf{a}_i^T\mathbf{x}= b_i & y_i\ \text{free} \end{array}$$

For instance, in a max primal, the constraint $2x_1+x_2\geq 5$ contributes $5y_i$ to the dual objective and forces $y_i\leq 0$. An equality constraint contributes a free dual variable.