Programa lineal dual
# 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 $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}}$

