Teoria De La Dualidad Y Planes De Corte Gomory

TEORÍA DE LA DUALIDAD

El dual es un problema de PL que se obtiene matemáticamente de un modelo primal de PL dado. Los problemas dual y primal están relacionados a tal grado, que la solución del simplex óptima de cualquiera de los dos problemas conduce en forma automática a la solución óptima del otro.

En la mayoría de los procedimientos de PL, el dual se define para varias formas del primal, dependiendo de los tipos de restricciones, de los signos de las variables y del sentido de la optimización.

DIFERENCIAS

Si el primo es un problema de Maximización, el dual es un problema de Minimización y viceversa.

Los coeficientes de la función objetivo del primo se convierten en las restricciones constantes de las ecuaciones del dual.

Las restricciones de las ecuaciones del primo se convierten en los coeficientes de la función objetivo del dual.

Los coeficientes de las variables del dual en las ecuaciones restrictivas son obtenidas sacando la transpuesta de la matriz de coeficientes del primo (los arreglos de los coeficientes en las columnas del primo se convierten en los coeficientes de las filas en el dual y viceversa).

Los signos de la desigualdad son invertidos.

Las X_n variables del primo son remplazadas por W_m variables en el dual.

El primo contiene m ecuaciones con n variables, el dual tiene n ecuaciones con m variables.

El método simplex dual trata con soluciones básicas infactibles hasta la última iteración, donde la solución básica asociada debe ser factible. En esencia, el método simplex primal solo trata con puntos extremos en tanto que en el método simplex dual todas las iteraciones, excepto la última están asociadas con puntos extremos infectables. Al final, ambos métodos dan soluciones básicas factibles como lo estipula la condición de no negatividad del modelo de PL

Para hallar la correspondencia entre los problemas dual y primal se suele utilizar la tabla primal-dual o de Tucker. En ella se puede observar el problema primal por filas, es decir verticalmente. Por columnas, es decir horizontalmente, se observa el problema dual.

Tabla tomada de: http://files.uladech.edu.pe/docente/32793925/INVE_OPER/Contenidos%20Unidad%202/Teoria_Dualidad.pdf

Interpretación Económica de las variables del Dual

La solución del problema Dual representa la interpretación económica que es una forma de análisis marginal (¿Qué pasará si una entidad adicional del insumo es utilizada?). Las variables del Dual W_m en un problema Primo de Maximización de ganancias, son las ganancias marginales de cada insumo o producto adicional. Las variables del Dual son llamadas algunas veces costos marginales o precios sombra. Las variables del Dual W_m en un problema primo de Minimización de costos, son los costos marginales de cada insumo ó producto adicional. La limitación b en las ecuaciones del Primo determina si las variables del Dual se relacionan en insumos ó productos marginales.

Si la limitación b restringe a los factores de producción, el análisis marginal se refiere al insumo. Si la limitación b en las ecuaciones restringe el producto el análisis marginal se refiere al producto. El conocimiento de cuanta ganancia o costo cambiarán con una unidad adicional de cada uno de los varios recursos, puede ser una información valiosa.

APORTES

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 sido obtenida la solución óptima, sin tener que resolver completamente el problema.

EJEMPLO:

Una compañía produce y vende 2 tipos de máquinas de escribir: manual y eléctrica. Cada máquina de escribir manual es vendida por un ingreso de 40 dls. Y cada máquina de escribir eléctrica produce un ingreso de 60 dls. Ambas máquinas tienen que ser procesadas (ensambladas y empacadas) a través de 2 operaciones diferentes (O1 y O2).

La compañía tiene una capacidad de 2000 hrs. Mensuales para la operación O1 y 1000 hrs. Mensuales de la operación O2.

El número de horas requeridas de O1 y O2 para producir un modelo terminado se da en la siguiente tabla.

HORAS REQUERIDAS CAPACIDAD

OPERACIÓN MANUAL ELECTRICA (HRS MENSUALES)

O1 3 2 2000

O2 1 2 1000

Encuentre el número óptimo de unidades de cada tipo de máquina de escribir que se debe producir mensualmente para maximizar el ingreso.

OBJETIVO: Maximizar el ingreso total

RESTRICCIONES: horas mensuales de las operaciones

VARIABLE DE DECISION: número de máquinas de escribir a producir

X1 = número de máquinas de escribir manuales

X2 = número de máquinas de escribir eléctricas

Maximizar

Sujeto a:

Minimizar

Sujeto a:

V. Básica Z W1 W2 S1 S2 Solución

...