UNIDAD 4

UNIDAD 4: PROBLEMA DUAL

El problema dual se define sistemáticamente a partir del modelo de PL primal (u original).

Los dos problemas están estrechamente relacionados en el sentido de que la solución óptima de uno proporciona automáticamente la solución óptima al otro.

En la mayoría de los tratamientos de PL, el dual se define para varias formas del primal según el sentido de la optimización (maximización o minimización), los tipos de restricciones (#,$ o =), y el signo de las variables (no negativas o irrestrictas). Este capítulo ofrece una definición única que abarca de manera automática todas las formas del primal.

Nuestra definición del problema dual requiere expresar el problema primal en la forma de ecuación (todas las restricciones son ecuaciones con lado derecho no negativo, y todas las variables son no negativas). Este requerimiento es consistente con el formato de la tabla inicial simplex. De ahí que cualesquier resultados obtenidos a partir de la solución óptima primal se aplican directamente al problema dual asociado.

Características del problema Dual

1. Cada restricción en un problema corresponde a una variable en el otro.

2. Los elementos del lado derecho de las restricciones en un problema son iguales a los coeficientes correspondientes de la función objetivo en el otro.

3. Un problema busca Maximizar y el otro Minimizar.

4. El problema de maximizar tiene restricciones menor o igual, y el problema de minimizar tiene restricciones mayor o igual.

5. Las variables en ambos problemas son No Negativas.

Las ideas clave para construir el dual a partir del primal se resumen como sigue:

1. Asigne una variable dual por cada restricción primal.

2. Construya una restricción dual por cada variable primal.

3. Los coeficientes de restricción (columna) y el coeficiente objetivo de la variable primal j-ésima definen respectivamente los lados izquierdo y derecho de la restricción dual j-ésima.

4. Los coeficientes objetivo duales son iguales a los lados derechos de las ecuaciones de restricción primales.

5. Las reglas que aparecen en la tabla 4.1 rigen el sentido de optimización, la dirección de las desigualdades y los signos de las variables en el dual. Una forma fácil de recordar el tipo de restricción en el dual (es decir,# o $) es que si el objetivo dual es de minimización (es decir, apunta hacia abajo), entonces todas las restricciones serán del tipo $ (es decir, apuntan hacia arriba). Lo opuesto aplica cuando el objetivo dual es de maximización.

Relaciones Primal-Dual

Los cambios realizados en los datos de un modelo de PL pueden afectar la optimalidad y/o factibilidad de la solución óptima actual. Esta sección presenta varias relaciones primal-dual que pueden usarse para calcular de nuevo los elementos de la tabla simplex óptima. Estas relaciones constituyen la base de la interpretación económica del modelo de PL y del análisis post óptimo.

La sección se inicia con un breve repaso de las matrices, una herramienta muy útil para realizar los cálculos de tabla simplex. Un repaso más detallado de las matrices se da en el apéndice en el sitio web.