METODO DUAL
Enviado por luislopez2 • 9 de Noviembre de 2013 • 4.595 Palabras (19 Páginas) • 649 Visitas
MÉTODO DUAL
JULIETH PATRICIA BOCANEGRA NIETO
KAREN JULIETH VILLADIEGOBAENA
NILSA PEÑALOZA GONZALEZ
Estudiantes
CARMEN MATÍAS
Docente
UNIVERSIDAD DE LA GUAJIRA EXTENSIÓN MAICAO
PROGRAMA DE ADMINISTRACION DE EMPRESAS
MAICAO-LA GUAJIRA
I P.A
2010
PROBLEMA DUAL
Todo problema de programación lineal tiene un problema relacionado con él, el cual se le llama problema dual o, simplemente dual. En un problema original de programación lineal, denominado problema primario o, simplemente primario, el dual puede formularse con la información obtenida en el primario. El problema dual es importante por muchas razones teóricas y, además, por motivos prácticos. Una de sus propiedades es que, al ser resuelto, suministra información indispensable sobre la solución del problema primario. De manera análoga, la solución del primario da toda la solución esencial relativa a la solución del problema dual. En un problema de programación lineal, su solución puede determinarse resolviendo el problema original o su dual. Las propiedades estructurales de los dos problemas pueden provocar una decidida preferencia por cuál problema solucionar. Aun con los métodos computarizados, las eficiencias del cómputo pueden provenir de la solución de una forma de problema.
En la mayoría de los procedimientos de Programación Lineal, 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 que en ocasiones, los principiantes se confunden con los detalles de esas definiciones. Más importante aún es que el uso de esas definiciones 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 Programación Lineal hay una asociación y una relación muy importante con otro 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 Programación Lineal.
El análisis de dualidad es una herramienta útil en la solución de problemas de Programación Lineal, por ejemplo: más restricciones que variables.
El problema 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 Programación Lineal.
LAS RELACIONES EXISTENTES ENTRE AMBOS PROBLEMAS
El dual tiene tantas variables como restricciones existen en el primal.
1. El dual tiene tantas restricciones como variables en el primal.
2. Los coeficientes de la función objetivo del primal son los términos independientes de las restricciones del dual.
3. Los términos independientes de las restricciones del primal son los coeficientes en la función objetivo del dual.
4. la matriz de coeficientes de las restricciones del dual es igual a la transpuesta de la del primal.
TIPOS DE PROBLEMAS DUALES
1. Duales Simétricos: para primales que incluyan restricciones de desigualdad.
2. Duales Asimétricos: para primales en forma estándar, es decir con restricciones de igualdad.
Otro tipo de restricciones entre los problemas primal y dual son las siguientes:
1. para duales simétricos el sentido de desigualdad de las restricciones del dual es inverso a las del primal; mientras que para asimétricos, las restricciones del dual son de sentido menor e igual en caso de que el problema dual sea de minimización, y de mayor e igual en caso de maximización. Además, las variables del dual, variables duales, no están sujeta a la condición de no negatividad.
2. El problema dual de uno de minimización es de maximización y viceversa.
3. El dual del dual es el primal.
La siguiente tabla sintetiza la simetría de los dos tipos de problema y sus relaciones:
Problema de maximización Problema de minimización
Numero de restricciones
Numero de variables
Restricción
Variable no negativa
Restricción
Variable no positiva
Restricción
Variable no restringida
Numero de Variables
Numero de restricciones
Variable no negativa
Restricción
Variable no positiva
Restricción
Variable no restringida
Restricción
Coeficiente de la función objetivo para la j-ésima variable
Constante del miembro derecho para la restricción j-ésima
Constante del miembro derecho para la j-ésima restricción
Coeficiente de la función objetivo para la variable j
Coeficiente en restricción i para la variable j
Coeficiente en restricción j para la variable i
Sin distinguir en el caso de duales simétricos o asimétricos, podemos formular una tabla general, que reúne las relaciones entre el problema primal y Dual sea cual sea su formulación:
PROBLEMA DE MINIMIZACION PROBLEMA DE MAXIMIZACION
VARIABLES ≥ 0
≤ 0
No restringidas ≤
≥
=
RESTRICCIONES
RESTRICCIONES ≥
≤
=
≥ 0
≤ 0
No restringidas
VARIABLES
TEOREMAS DE DUALIDAD
Los siguientes teoremas establecen las relaciones entre el problema primal, el dual y sus soluciones. En todas ellas se utiliza la forma primal-dual simétrica.
Teorema 1 El dual del dual es el primal.
Teorema 2 (Dualidad débil) Sean x e y soluciones factibles para los problemas primal y dual respectivamente. Se verifica
z = cTx ≤ bTy = G
Corolario 1 Si las soluciones factibles x* e y* verifican
cTx* = bTy*, entonces x e y son soluciones óptimas para el primal y el dual respectivamente.
Corolario 2 Si el problema primal es factible y no acotado, el dual no tiene solución.
Corolario 3 Si el problema dual es factible y no acotado, el
...