Analisis del problema dual

Solo disponible en BuenasTareas
  • Páginas: 5 (1168 palabras)
  • Descarga(s): 0
  • Publicado: 23 de mayo de 2011
Leer documento completo
Vista previa del texto
Análisis del problema dual


Materia:
Elementos de Investigación de Operaciones.
Prof. Ricardo Alonso.
Pregrado:
Diurno

Guacara, abril del 2011
INTRODUCCIÓN

Muchos problemas de programaciónlineal tienen su contrapartida en lo que se llama su dual; es importante el estudio de la teoría del problema dual porque puede resultar más fácil de resolver que el problema original. Así mismo, como consecuencia de que el vector solución del problema dual esté formado por los <precios ocultos>, que miden la efectividad en el uso de los recursos por el programa óptimo del primal, hacenecesario el conocer la solución de este problema. Por último, la teoría de la dualidad juega un papel clave en la interpretación y realización del análisis de sensibilidad.

Todo problema de Programación Lineal tiene asociado un segundo problema, conocido como su problema Dual. Ambos están relacionados estrechamente, hasta el punto de que el modelo de uno puede obtenerse a partir del modelo del otroy la solución óptima del modelo del primero proporciona información completa acerca de la solución óptima del segundo.

Una de las ventajas de la existencia del problema dual es la posibilidad de reducir el esfuerzo computacional al resolver ciertos modelos de Programación Lineal. Pero más importante aún es la relación que existe entre la dualidad y el análisis de sensibilidad, tema del próximocapitulo, el cual estudia el efecto que las variaciones en los parámetros de un modelo tienen en la solución óptima de este. Además, los valores óptimos de las variables del modelo dual suministran información económica muy importante acerca del valor implícito de los recursos que se utilizan en el problema que se está resolviendo.

El matemático norteamericano John Von Neumann fue el primeroen destacar la existencia de la dualidad en la programación lineal y a partir de allí el concepto se ha usado en una gran variedad de áreas teóricas y prácticas de la misma. Para comprender el concepto de dualidad analicemos los dos casos siguientes.

TEORIA DE LA DUALIDAD.
Cada problema de programación lineal tiene un segundo problema asociado con el. Uno se denomina primal y el otro dual. Los2 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.

Modelo Primal <----> Modelo Dual.

Las relaciones existentes entre ambos modelos son las siguientes:
• El dual tiene tantas variables como restricciones existen en el primal.
• El dual tiene tantas restricciones comovariables tiene el primal.
• Los coeficientes de la función objetivo del primal son los términos independientes de las restricciones del dual.
• Los términos independientes de las restricciones del primal son los coeficientes en la función objetivo del dual.
• La matriz de coeficientes de las restricciones del dual es igual a la traspuesta de la del primal.

Las relaciones entre el primal y el dualse utilizan para reducir el esfuerzo de computo 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.

Para duales simétricos el sentido de desigualdad de las restricciones del dual es inverso al de las delprimal; mientras que para asimétricos, las restricciones del dual son de sentido menor o igual en caso de que el problema primal sea de minimización, y de mayor o igual en caso de maximización.  Además, las variables del dual, variables duales, no están sujetas a la condición de no negatividad
El problema dual de uno de minimización es de maximización y viceversa.
El dual del programa dual es...
tracking img