Etiqueta: primal

Relaciones de Dualidad en Programación Lineal (Pasar de Primal a Dual)

El modelo dual de un problema de Programación Lineal consiste en una instancia alternativa de modelamiento matemático que nos permite rescatar la información del problema original conocido comúnmente como modelo primal.

En consecuencia es suficiente con resolver uno de ellos (primal o dual) para poder obtener la solución óptima y valor óptimo del problema equivalente (primal o dual según sea el caso). Para ello se puede utilizar, por ejemplo, las condiciones establecidas en el Teorema de Holguras Complementarias.

Las relaciones de dualidad se pueden resumir en el siguiente cuadro:

relaciones-primal-dual

La tabla anterior se puede interpretar tanto de izquierda a derecha como de derecha a izquierda.

Primal Minimización – Dual Maximización

Por ejemplo, leyendo la tabla desde izquierda a derecha, es decir, pasar de un problema primal de minimización a un problema dual de maximización, tenemos:

  • Si el problema primal es de minimización, entonces su correspondiente dual será uno de maximización.
  • Si el problema primal tiene una restricción del tipo >=, la variable dual asociada a dicha restricción debe ser >=0.
  • Si el problema primal tiene una restricción del tipo <=, la variable dual asociada a dicha restricción debe ser <=0.
  • Si el problema primal tiene una restricción del tipo =, la variable dual asociada a dicha restricción debe ser irrestricta (libre de signo).
  • Si el problema primal tiene una variable >=0, la correspondiente restricción asociada en el dual debe ser <=.
  • Si el problema primal tiene una variable <=0, la correspondiente restricción asociada en el dual debe ser >=.
  • Si el problema primal tiene una variable irrestricta (libre de signo), la correspondiente restricción asociada en el dual debe ser =.

Primal Maximización – Dual Minimización

De forma análoga, interpretando la tabla desde derecha a izquierda, es decir, pasar de un problema primal de maximización a un problema dual de minimización, tenemos:

  • Si el problema primal es de maximización, entonces su correspondiente dual será uno de minimización.
  • Si el problema primal tiene una restricción del tipo <=, la variable dual asociada a dicha restricción debe ser >=0.
  • Si el problema primal tiene una restricción del tipo >=, la variable dual asociada a dicha restricción debe ser <=0.
  • Si el problema primal tiene una restricción del tipo =, la variable dual asociada a dicha restricción debe ser irrestricta (libre de signo).
  • Si el problema primal tiene una variable >=0, la correspondiente restricción asociada en el dual debe ser >=.
  • Si el problema primal tiene una variable <=0, la correspondiente restricción asociada en el dual debe ser <=.
  • Si el problema primal tiene una variable irrestricta (libre de signo), la correspondiente restricción asociada en el dual debe ser =.

Ejemplo Relaciones de Dualidad en Programación Lineal

A continuación presentamos un modelo de optimización que consideraremos como el problema primal y que en un artículo previo fue resuelto a través del Método Simplex de 2 Fases.

ejemplo-simplex-dual

Como en este caso el problema primal es de minimización, para definir su respectivo problema dual leeremos la tabla que resume las relaciones de dualidad desde izquierda a derecha. En consecuencia, el problema dual será uno de maximización.

Adicionalmente la primera y segunda restricción del problema primal definirán las variables de decisiones (variables duales) en el problema dual (Y1 e Y2, respectivamente), siendo los coeficientes en la función objetivo los actuales valores de los lados derechos de las restricciones del problema primal.

De esta forma la función objetivo del problema dual queda definida por la siguiente expresión:

funcion-objetivo-dual

Luego por cada variable en el problema primal vamos a tener la misma cantidad de restricciones en el problema dual. En este caso las variables X1, X2 y X3 definirán la estructura de las restricciones 1, 2 y 3 en nuestro problema dual. Por ejemplo la primera restricción del problema dual (asociada a la variable primal X1) sería 2Y1+2Y2<=160.

Notar que los coeficientes que ponderan a las variables duales son los parámetros asociados a la variable X1 en el primal en la primera y segunda restricción, respectivamente. La restricción en el dual es del tipo «<=» debido a que la variable X1 en el problema primal de minimización tiene la condición de no negatividad («>=0»). Por último el lado derecho de la restricción es el coeficiente que tiene la variable X1 en la función objetivo del problema primal. Siguiendo el procedimiento las restricciones del problema dual serían:

restricciones-dualidad

Finalmente como las 2 primeras restricciones del problema primal son del tipo «>=» en el problema primal de minimización, las respectivas variables duales asociadas en el problema de maximización serán no negativas. De esta forma el problema dual es:

problema-dual

Ejercicio Propuesto: Utilizando las relaciones de dualidad en Programación  Lineal, dado un problema primal P, demuestre que su correspondiente dual D queda definido de acuerdo a:

ejemplo primal dual

En lo que sigue, combinaremos las distintas restricciones del problema primal, ponderando por los valores no negativos \pi_{1},\pi_{2} y \pi_{3} cada una, respectivamente, de modo de obtener la mejor cota superior del valor óptimo del problema P). Vale decir:

relación primal dual

De modo de garantizar que el lado derecho de esta última desigualdad sea una cota superior de la función objetivo del problema primal se debe cumplir que:

2\pi_{1}+\pi_{2}+\pi_{3}\geq 40

\pi_{1}+\pi_{2}+3\pi_{3}\geq 60

La mejor elección de esta cota se obtendría al resolver el siguiente problema de optimización:

dual d

Este problema se conoce como el problema “Dual” D) asociado al problema “Primal” P).

También resulta que al formular el problema dual de D) se obtiene el problema primal P) (o uno equivalente). Cualquiera de los dos entrega la misma información y el valor óptimo alcanzado es el mismo.