Programa lineal dual

El dual de un programa lineal (PL) dado es otro PL que se deriva del PL original (el primal) de la siguiente forma:

• Cada variable en el PL primal se convierte en una restricción en el PL dual;
• Cada restricción en el PL primal se convierte en una variable PL dual;
• La función objetivo se invierte – maximizar en el PL primal se convierte en minimizar en el PL dual y viceversa.

Construyendo el PL dual

Dado un PL primal, el siguiente algoritmo puede ser utilizado para construir su PL dual. El PL primal está definido por:

• Un conjunto de ${\displaystyle n}$ variables: ${\displaystyle x_{1},\ldots ,x_{n}}$
• Para cada variable ${\displaystyle x_{i}}$, le corresponde un signo de restricción – tiene que ser no negativo (${\displaystyle x_{i}\geq 0}$), no positivo (${\displaystyle x_{i}\leq 0}$) o irrestrica ${\displaystyle x_{i}\in \mathbb {R} }$.
• Una función objetivo:${\displaystyle {\text{maximizar}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}}$
• Una lista de ${\displaystyle m}$ restricciones. Cada restricción ${\displaystyle j}$ es: ${\displaystyle a_{j1}x_{1}+\cdots +a_{jn}x_{n}\lesseqqgtr b_{j}}$ donde el símbolo antes de ${\displaystyle b_{j}}$ puede ser ${\displaystyle \geq }$ o ${\displaystyle \leq }$ o ${\displaystyle =}$.

El PL dual se construye como sigue:

• Cada restricción en el primal se convierte en una variable en el dual, por lo que hay ${\displaystyle m}$ variables: ${\displaystyle y_{1},\ldots ,y_{m}}$.
• El constreñimiento de señal de cada variable dual es "opuesto" al signo de su primal constreñimiento. Por lo que “${\displaystyle \geq b_{j}}$” se convierte en ${\displaystyle y_{j}\leq 0}$, “${\displaystyle \leq b_{j}}$” se convierte en ${\displaystyle y_{j}\geq 0}$ y “${\displaystyle =b_{j}}$” se convierte en ${\displaystyle y_{j}\in \mathbb {R} }$.
• La función objetiva dual es${\displaystyle {\text{minimizar }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}}$
• Cada variable primal se convierte en una restricción dual, por lo que hay ${\displaystyle n}$ restricciones. El coeficiente de una variable dual en la restricción dual es el coeficiente de su variable primal en su restricción primal, por lo que cada restricción ${\displaystyle i}$ es: ${\displaystyle a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}}$ donde el símbolo antes de ${\displaystyle c_{i}}$ es similar a la restricción en variable ${\displaystyle i}$ en el PL primal, por lo que ${\displaystyle x_{i}\leq 0}$ se convierte en “${\displaystyle \leq c_{i}}$”, ${\displaystyle x_{i}\geq 0}$ se convierte en “${\displaystyle \geq c_{i}}$” y ${\displaystyle x_{i}\in \mathbb {R} }$ se convierte en “${\displaystyle =c_{i}}$”.

De este algoritmo, es fácil de ver que el dual del dual es el primal.

Formulación vectorial

Si todas las restricciones tienen el mismo signo, es posible representar el algoritmo de arriba en una manera más corta utilizando matrices y vectores. La siguiente tabla muestra la relación entre varios tipos de PL primales y duales.

Primal	Dual	Nota
Maximizar ${\displaystyle {\mathbf {c}}^{T}{\mathbf {x}}}$ sujeto a ${\displaystyle A{\mathbf {x}}\geq {\mathbf {b}},\;{\mathbf {x}}\geq {\mathbf {0}}}$	Minimizar ${\displaystyle {\mathbf {b}}^{T}{\mathbf {y}}}$ sujeto a ${\displaystyle A^{T}{\mathbf {y}}\geq {\mathbf {c}},\;{\mathbf {y}}\geq {\mathbf {0}}}$	Es llamado problema dual "simétrico"
Maximizar ${\displaystyle {\mathbf {c}}^{T}{\mathbf {x}}}$ sujeto a ${\displaystyle A^{T}{\mathbf {y}}\leq {\mathbf {b}}}$	Minimizar ${\displaystyle {\mathbf {b}}^{T}{\mathbf {y}}}$ sujeto a ${\displaystyle A^{T}{\mathbf {y}}={\mathbf {c}},\;{\mathbf {y}}\geq {\mathbf {0}}}$	Es llamado problema dual “asimétrico”
Maximizar ${\displaystyle {\mathbf {c}}^{T}{\mathbf {x}}}$ sujeto a ${\displaystyle A{\mathbf {b}}={\mathbf {b}},\;{\mathbf {x}}\geq {\mathbf {0}}}$	Minimizar ${\displaystyle {\mathbf {b}}^{T}{\mathbf {y}}}$ sujeto a ${\displaystyle A^{T}{\mathbf {y}}\geq {\mathbf {c}}}$

Los teoremas duales

En lo siguiente, suponga que el PL primal es "maximizar ${\displaystyle {\mathbf {c}}^{T}{\mathbf {x}}}$ sujeto a [restricciones]" y el PL dual es "minimizar ${\displaystyle {\mathbf {b}}^{T}{\mathbf {y}}}$ sujeto a [restricciones]".

Ejemplos

Considere el PL primal con dos variables y una restricción:

${\displaystyle {\begin{aligned}{\text{maximizar }}&3x_{1}+4x_{2}\\{\text{sujeto a }}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{aligned}}}$

Aplicando el algoritmo de arriba obtenemos el siguiente PL dual con una variable y dos restricciones:

${\displaystyle {\begin{aligned}{\text{minimizar }}&7y_{1}\\{\text{sujeto a }}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}}$

Véase también

• Programación lineal
• Investigación de operaciones