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

editar

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

  • Un conjunto de   variables:  
  • Para cada variable  , le corresponde un signo de restricción – tiene que ser no negativo ( ), no positivo ( ) o irrestrica  .
  • Una función objetivo: 
  • Una lista de   restricciones. Cada restricción   es:   donde el símbolo antes de   puede ser   o   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   variables:  .
  • El constreñimiento de señal de cada variable dual es "opuesto" al signo de su primal constreñimiento. Por lo que “ ” se convierte en  , “ ” se convierte en   y “ ” se convierte en  .
  • La función objetiva dual es 
  • Cada variable primal se convierte en una restricción dual, por lo que hay   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   es:   donde el símbolo antes de   es similar a la restricción en variable   en el PL primal, por lo que   se convierte en “ ”,   se convierte en “ ” y   se convierte en “ ”.

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

Formulación vectorial

editar

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   sujeto a   Minimizar   sujeto a   Es llamado problema dual "simétrico"
Maximizar   sujeto a   Minimizar   sujeto a   Es llamado problema dual “asimétrico”
Maximizar   sujeto a   Minimizar   sujeto a  

Los teoremas duales

editar

En lo siguiente, suponga que el PL primal es "maximizar   sujeto a [restricciones]" y el PL dual es "minimizar   sujeto a [restricciones]".

Dualidad débil

editar

El teorema de dualidad débil dice que para cada solución factible   del primal y cada solución factible   del dual:  . 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:

 

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

editar

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

 

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

editar

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

 

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

 

Programa no factible

editar

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:

 

Véase también

editar