title: Programa lineal dual
text: # 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.
  
  # Programa lineal dual
  ## 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.
  
  # Programa lineal dual
  ## 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}}$ | |
  
  # Programa lineal dual
  ## 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]".
  
  # Programa lineal dual
  ## Los teoremas duales
  ### 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.
  
  # Programa lineal dual
  ## Los teoremas duales
  ### 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.
  
  # Programa lineal dual
  ## 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 lineal dual
  ## Ejemplos
  ### 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}}$