Problema Primal y Dual
Páginas: 5 (1167 palabras)
Publicado: 3 de abril de 2013
INTERPRETACION ECONOMICA DEL DUAL
Introducción
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 simplex óptima de cualquiera de los dos problemas conduce en forma automática a la solución óptima del otro. El método simplex además de resolver un problema de PLllegando a una solución óptima nos ofrece más y mejores elementos para la toma de decisiones. La dualidad y el análisis de sensibilidad son potencialidades de éste método. 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. La experiencia nos indica queen ocasiones, los principiantes se confunden con los detalles de esas definiciones. Más importante aún es que el uso de esas definición es múltiples puede conducir a interpretaciones inconsistentes de los datos en la tabla simplex, sobre todo en lo que respecta a los signos de las variables .El concepto de dualidad indica que para cada problema de PL hay una asociación y una relación muy importante conotro problema de programación lineal, llamado precisamente dual.
La relación entre el problema dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades:
Aporta elementos que aumentan sustancialmente la compresión de la PL.
El análisis de dualidad es una herramienta útil en la solución de problemas de PL, por ejemplo: más restricciones que variables.
Elproblema dual tiene interpretaciones e informaciones importantes que muestran que los análisis marginales están siempre involucrados implícitamente al buscar la solución óptima a un problema de PL.
¿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 deminimización y viceversa.
2. Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes de disponibilidad en el problema dual.
3. Los coeficientes del vector de disponibilidad del problema original (primal) 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 elproblema primal, será la matriz de 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 Ymen el dual.
Relación entre el Problema Primal y Problema Dual
Como se ha comentado con anterioridad, tanto el programa primal como el programa dual son dos formas de abordar el mismo problema, y por lo tanto, si tienen solución, tienen la misma solución. Entonces, cabe preguntarse cuál es la relación entre las soluciones de ambos problemas.
Para ello haremos hincapié a dos teoremasimportantes que surgen de toda esta teoría:
Teorema de Dualidad
La condición necesaria y suficiente para que exista solución óptima del primal (x*), es que exista una solución óptima para el dual (y*) y que valor de la función objetivo de ambos programas sea igual, es decir Z(x*) = W (y*).
∃ x* ↔ ∃ λ* / Z(x*) = W(y*)
Teorema del Holgura complementaria.
La condición necesaria ysuficiente para que (x*, y*) sean soluciones óptimas del programa primal y dual, es que satisfagan las condiciones de holgura complementaria:
(c - y*A) x* = 0
y* ( b - A x* ) = 0
Visto de otra manera estos teoremas de manera implícita implican lo siguiente:
1) Variables principales del primal serán las variables de holgura del dual.
2) Variables de holgura del primal serán las...
INTERPRETACION ECONOMICA DEL DUAL
Introducción
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 simplex óptima de cualquiera de los dos problemas conduce en forma automática a la solución óptima del otro. El método simplex además de resolver un problema de PLllegando a una solución óptima nos ofrece más y mejores elementos para la toma de decisiones. La dualidad y el análisis de sensibilidad son potencialidades de éste método. 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. La experiencia nos indica queen ocasiones, los principiantes se confunden con los detalles de esas definiciones. Más importante aún es que el uso de esas definición es múltiples puede conducir a interpretaciones inconsistentes de los datos en la tabla simplex, sobre todo en lo que respecta a los signos de las variables .El concepto de dualidad indica que para cada problema de PL hay una asociación y una relación muy importante conotro problema de programación lineal, llamado precisamente dual.
La relación entre el problema dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades:
Aporta elementos que aumentan sustancialmente la compresión de la PL.
El análisis de dualidad es una herramienta útil en la solución de problemas de PL, por ejemplo: más restricciones que variables.
Elproblema dual tiene interpretaciones e informaciones importantes que muestran que los análisis marginales están siempre involucrados implícitamente al buscar la solución óptima a un problema de PL.
¿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 deminimización y viceversa.
2. Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes de disponibilidad en el problema dual.
3. Los coeficientes del vector de disponibilidad del problema original (primal) 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 elproblema primal, será la matriz de 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 Ymen el dual.
Relación entre el Problema Primal y Problema Dual
Como se ha comentado con anterioridad, tanto el programa primal como el programa dual son dos formas de abordar el mismo problema, y por lo tanto, si tienen solución, tienen la misma solución. Entonces, cabe preguntarse cuál es la relación entre las soluciones de ambos problemas.
Para ello haremos hincapié a dos teoremasimportantes que surgen de toda esta teoría:
Teorema de Dualidad
La condición necesaria y suficiente para que exista solución óptima del primal (x*), es que exista una solución óptima para el dual (y*) y que valor de la función objetivo de ambos programas sea igual, es decir Z(x*) = W (y*).
∃ x* ↔ ∃ λ* / Z(x*) = W(y*)
Teorema del Holgura complementaria.
La condición necesaria ysuficiente para que (x*, y*) sean soluciones óptimas del programa primal y dual, es que satisfagan las condiciones de holgura complementaria:
(c - y*A) x* = 0
y* ( b - A x* ) = 0
Visto de otra manera estos teoremas de manera implícita implican lo siguiente:
1) Variables principales del primal serán las variables de holgura del dual.
2) Variables de holgura del primal serán las...
Leer documento completo
Regístrate para leer el documento completo.