Ad ogni problema di PL (Primale) è associato un problema Duale
$min \space c_1 x_1+..+c_nx_n \\ a_{11}x_1 +..+ a_{1n}x_n \geq b_1 \\ .. \\ a_{m1}x_1 +..+a_{mn} x_n \geq b_m \\ \underline{x} \geq \underline{0}$
$max \space b_1 w_1+..+b_mw_m \\ a_{11}w_1 +..+ a_{m1}w_m \leq c_1 \\ .. \\ a_{1n}w_1 +..+a_{mn} w_m \leq c_n \\ \underline{w} \geq \underline{0}$
Il problema D ha tante variabili quanti sono i vincoli di P e tanti vincoli quante sono le variabili di P
Uno scalare $lb$ è un lower bound per il problema P se e solo se $lb \leq \underline{c}^T \underline{x}$ $\forall \underline{x} \in X$ $\Rightarrow lb \leq \underline{c}^T \underline{x}^* = z^*$ (stima del valore ottimo)
Il duale del problema duale è il problema primale
Trasformiamo i vincoli di uguaglianza in vincoli di maggiore o uguale come segue: $A \underline{x} = \underline{b}$ equivale a $\begin{cases} A\underline{x} \geq \underline{b} \\ A \underline{x} \leq \underline{b} \Rightarrow -A\underline{x} \geq -\underline{b} \end{cases}$
quindi si introducono $2m$ variabili duali $\underline{u}$ e $\underline{v}$
$max \space (\underline{b}^T \underline{u} - \underline{b}^T \underline{v}) \\ A^T \underline{u} - A^T \underline{v} \leq \underline{c} \\ \underline{u} \geq \underline{0}, \underline{v} \geq \underline{0}$