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.

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

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

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 $m$ variables: $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 “ $\geq b_{j}$ ” se convierte en $y_{j}\leq 0$ , “ $\leq b_{j}$ ” se convierte en $y_{j}\geq 0$ y “ $=b_{j}$ ” se convierte en $y_{j}\in \mathbb {R}$ .
La función objetiva dual es ${\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 $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 $i$ es: $a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}$ donde el símbolo antes de $c_{i}$ es similar a la restricción en variable $i$ en el PL primal, por lo que $x_{i}\leq 0$ se convierte en “ $\leq c_{i}$ ”, $x_{i}\geq 0$ se convierte en “ $\geq c_{i}$ ” y $x_{i}\in \mathbb {R}$ se convierte en “ $=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 ${\mathbf {c}}^{T}{\mathbf {x}}$ sujeto a $A{\mathbf {x}}\geq {\mathbf {b}},\;{\mathbf {x}}\geq {\mathbf {0}}$	Minimizar ${\mathbf {b}}^{T}{\mathbf {y}}$ sujeto a $A^{T}{\mathbf {y}}\geq {\mathbf {c}},\;{\mathbf {y}}\geq {\mathbf {0}}$	Es llamado problema dual "simétrico"
Maximizar ${\mathbf {c}}^{T}{\mathbf {x}}$ sujeto a $A^{T}{\mathbf {y}}\leq {\mathbf {b}}$	Minimizar ${\mathbf {b}}^{T}{\mathbf {y}}$ sujeto a $A^{T}{\mathbf {y}}={\mathbf {c}},\;{\mathbf {y}}\geq {\mathbf {0}}$	Es llamado problema dual “asimétrico”
Maximizar ${\mathbf {c}}^{T}{\mathbf {x}}$ sujeto a $A{\mathbf {b}}={\mathbf {b}},\;{\mathbf {x}}\geq {\mathbf {0}}$	Minimizar ${\mathbf {b}}^{T}{\mathbf {y}}$ sujeto a $A^{T}{\mathbf {y}}\geq {\mathbf {c}}$

Los teoremas duales

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

Dualidad débil

El teorema de dualidad débil dice que para cada solución factible ${\mathbf {x}}$ del primal y cada solución factible ${\mathbf {y}}$ del dual: ${\mathbf {c}}^{T}{\mathbf {x}}\leq {\mathbf {b}}^{T}{\mathbf {y}}$ . En otras palabras,, el valor objetivo en cada solución factible del dual es un superior-atado en el valor objetivo del primal, y valor objetivo en cada solución factible del primal es un más bajo-atado en el valor objetivo del dual. Esto implica:

$\max _{\mathbf {x}}{\mathbf {c}}^{T}{\mathbf {x}}\leq \min _{\mathbf {y}}{\mathbf {b}}^{T}{\mathbf {y}}$

En particular, si el primal es no acotado entonces el dual no tiene solución factible y si el dual es no acotado entonces el primal no tiene solución factible.

Dualidad fuerte

El teorema de dualidad fuerte dice que si uno de los dos problemas tiene una solución óptima entonces también el otro, además

$\max _{\mathbf {x}}{\mathbf {c}}^{T}{\mathbf {x}}=\min _{\mathbf {y}}{\mathbf {b}}^{T}{\mathbf {y}}$

El teorema de dualidad fuerte es más difícil de demostrar; las demostraciones normalmente utilizan el teorema de dualidad débil como una sub-rutina.

Ejemplos

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

{\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:

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

Programa no factible

Un PL puede ser no acotado o no factible. La teoría de la dualidad menciona que:

Si el primal es no acotado entonces el dual es no factible;
Si el dual es no acotado entonces el primal es no factible.

Sin embargo, es posible para ambos (el dual y el primal) ser no factibles. Aquí es un ejemplo:

${\begin{aligned}{\text{maximizar }}&2x-y\\{\text{sujeto a }}&x-y\leq 1\\&-x+y\leq -2\\&x,y\geq 0\end{aligned}}$