DUALIDAD

TEORIA DE LA DUALIDAD

Cada problema de programación lineal tiene un segundo problema asociado con él. Uno se denomina primal y el otro dual. Los 2 poseen propiedades muy relacionadas, de tal manera que la solución óptima a un problema proporciona información completa sobre la solución óptima para el otro.

Las relaciones entre el primal y el dual se utilizan para reducir el esfuerzo de cómputo en ciertos problemas y para obtener información adicional sobre las variaciones en la solución óptima debidas a ciertos cambios en los coeficientes y en la formulación del problema. Esto se conoce como análisis de sensibilidad o post-optimidad.

 DUALIDAD

El concepto de dualidad desempeña importantes papeles dentro de la programación lineal (también en la no lineal), tanto desde un punto de vista teórico como práctico. Todo programa lineal lleva asociado otro programa lineal conocido como su programa dual; el programa inicial se conoce también como programa primal

IMPORTANCIA DE LA DUALIDAD EN PROGRAMACIÓN LINEAL

La importancia de la teoría de la dualidad se puede resumir, entre otros aspectos, en lo siguiente:

Permite resolver problemas de programación lineal de forma más rápida y sencilla.

Es otra vía para resolver un problema de programación lineal

Facilita profundizar en el contenido económico del problema original (primal)

.

Puede ser utilizada para resolver el caso en que se debe considerar la introducción de una nueva variable en el primal una vez que ha de sido obtenida la solución óptima, sin tener que resolver completamente el problema.

RELACIONES ENTRE LOS MODELOS PRIMAL Y DUAL

1. Los coeficientes objetivos de uno son los coeficientes recurso del otro.

2. Los coeficientes recurso de uno son los coeficientes objetivo del otro.

3. La matriz de coeficientes tecnológicos de uno es la transpuesta de la matriz de coeficientes tecnológicos del otro.

4. Ambos problemas están en formato canónico, como lo comprueban más en detalle las siguientes características

4.1 El objetivo del primo es maximizar en cambio el objetivo del dual es minimizar.

4.2 Las restricciones del Primo son del tipo =, mientras que las del dual son del tipo =.

4.3 Las variables de ambos problemas están restringidas a ser mayores o iguales que cero.

TABLA DE TUCKER

¿CÓMO CONVERTIR UN PROBLEMA PRIMAL A DUAL?

Un problema dual se formula de un problema primal de la siguiente forma:

1. Si el primal es un problema de maximización su dual será un problema de minimización y viceversa.

2. Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes del vector de la disponibilidad en el problema dual.

3. Los coeficientes del vector de disponibilidad del problema original se convierten en los coeficientes de la función objetivo (vector de costo o precio) en el problema dual.

4. Los coeficientes de las restricciones en el problema primal, será la matriz de los coeficientes tecnológicos en el dual.

5. Los signos de desigualdad del problema dual son contrarios a los del primal.

6. Cada restricción en un problema corresponde a una variable en el otro problema. Si el primal tiene m restricciones y n variables, el dual tendrá n restricciones y m variables. Así, las variables Xn del primal se convierten en nuevas variables Ym en el dual.