Analisis De Dualidad

MÉTODO DEL DUAL (TEORIA DE DUALIDAD)

La programación lineal puede ser usada para resolver una extensa variedad de problemas propios de los negocios, ya sea para maximizar utilidades o minimizar costos. Las variables de decisión en tales problemas fueron, por ejemplo, el número de productos a producir, la cantidad de pesos a emplear, etc. En cada caso la solución óptima no explicó cómo podrían ser asignados los recursos (ejemplo: materia prima, capacidad de las máquinas, el dinero, etc.) para obtener un objetivo establecido.

Todo problema de programación lineal tiene asociado con él otro problema de programación lineal llamado DUAL. El problema inicial es llamado PRIMO y el problema asociado (sombra) es llamado el problema PRIMO. Los dos juntos son llamados problemas duales ya que ambos están formados por el mismo conjunto de datos. La solución básica factible óptima de estos problemas es tal que una puede fácilmente ser usada para la solución de la otra. La dimensión del problema de programación lineal influencia la elección del cálculo del primo o del dual.

Si el primo tiene más ecuaciones que variables, es frecuentemente más fácil obtener la solución de dual ya que menor número de iteraciones son requeridas. Además si el primo tiene solución, el dual tendrá solución. Una vez que el problema dual es formulado, el procedimiento de solución es exactamente el mismo que para cualquier problema de programación lineal.

Mecánicamente el dual es formulado partiendo del problema primo en la siguiente forma:

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

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

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

3. 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 ).

4. Los signos de la desigualdad son invertidos.

5. Las Xn variables del primo son remplazadas por Wm variables en el dual.

Notación matemática:

Primo Contiene m ecuaciones y n variables.

Dual Contiene n ecuaciones y m variables.

La notación matricial del Primo es:

Max Z = CX

Sujeto a :

AX ≤ b

x ≥ 0

La notación matricial del Dual es:

Min Z = bt W

Sujeto a:

At W ≥ Ct

W ≥ 0

Relación Prima-Dual.

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.

La relación principal entre ellos es que tanto el problema primal como el dual buscan el valor óptimo del sistema.

Existe una estrecha relación entre el problema primal y dual que puede expresarse en lo siguiente:

El dual tiene la matriz D transpuesta, es decir, si suponemos que D es de orden sx r, entonces Dt es de orden r x s. Además las variables del primal y el dual son diferentes, ya que X será un vector de r-componentes mientras que el vector Y tendrá s-componentes.

Los términos independientes del conjunto de las restricciones del problema primal forman los coeficientes de la función objetivo del dual.

Los coeficientes de la función objetivo del primal forman los términos independientes de las restricciones del dual.

...