Metodo dual simplex

Solo disponible en BuenasTareas
  • Páginas : 5 (1043 palabras )
  • Descarga(s) : 0
  • Publicado : 10 de octubre de 2010
Leer documento completo
Vista previa del texto
METODO DUAL SIMPLEX.

 
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. Los 2 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.
 
Las relaciones entre el primal y el dual se utilizanpara 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.
 
DEFINICION DEL PROBLEMA DUAL.
 
Para poder elaborar el problema dual a partir del primal, este se debe presentar ensu forma canónica de la siguiente forma:
 
Maximizar
 
Sujeto a:
 

 

 
El problema dual se puede obtener a partir del problema primal y viceversa de la siguiente manera:
 
1. Cada restricción de un problema corresponde a una variable en el otro.
 
2. Los elementos del lado derecho de las restricciones en un problema son iguales a los coeficientes respectivos de la función objetivoen el otro.
 
3. Un problema busca maximizar y el otro minimizar.
 
4. El problema de maximización tiene restricciones que y el problema de minimización tiene restricciones que.
 
5. Las variables en ambos casos son no negativas.
 
EJEMPLO:
 
Considere el problema primal siguiente:
 
Maximizar
 
Sujeto a:
 

 
Elaborar el dual a partir del primal.
 
Minimizar
 
Sujeto a: 

 
Cuando el problema primal no está en forma canónica, es necesario hacer ajustes para poder presentarlo así. Los cambios más frecuentes son:
 
1. Si la función objetivo es minimizar, se puede transformar a una función objetivo de maximizar de la siguiente forma:
 
Minimizar
 

Maximizar
 
2. Una restricción mayor o igual que se transforma en una restricción menor o igual que de lasiguiente manera:

 
 
 
 
 
 
 
 
 
 
 
 
 
 
3. Una restricción de igualdad se transforma en 2 inecuaciones.
 

 

 

 
EJEMPLO: (PRIMAL).
 
Maximizar
 
Sujeto a:
 

 
Maximizar
 
Sujeto a:
 

 
Dual
 
Miminizar
 
Sujeto a:
 

 
 
Encuentre el problema dual a partir del primal siguiente:
 
EJEMPLO:
 
Maximizar
 
Sujeto a:
 

 
 Maximizar
 
Sujeto a:
 

 
Maximizar
 
Sujeto a:
 

 
Minimizar
 
Sujeto a:
 

 
 
 
 
 
 
 
EJEMPLO:
 
Minimizar
 
Sujeto a:
 

 
 
Maximizar
 
Sujeto a:
 

 
Maximizar
 
Sujeto a:
 

 
Minimizar
 
Sujeto a:
 

 
 
 
 
 
 
 
 
Maximizar
 
Sujeto a:
 

 
 
EJEMPLO:
 
Minimizar
 
Sujeto a:
 

 
Maximizar
 
Sujeto a:
  
Minimizar
 
Sujeto a:
 

 
 
 
 
 
 
 
 
 
 
 
 
Maximizar
 
Sujeto a:
 

 
Encuentre el problema dual asociado al problema primal siguiente:
 
 
Minimizar
 
Sujeto a:
 

 
Maximizar
 
Sujeto a:
 

 
Minimizar
 
Sujeto a:
 

 
Maximizar
 
Sujeto a:
 

 
SOLUCION OPTIMA PRIMAL (2FASES)
 
V. Básica | Z | X1 | X2 | S1 | S2 |Solución |
Z | 1 | -5000/3 | 0 | -500/3 | 0 | 6000 |
S2 | 0 | 1 | 0 | -2 | 1 | 12 |
X2 | 0 | 2/3 | 1 | -1/3 | 0 | 12 |
 

 
SOLUCION OPTIMA DEL DUAL
 
V. Básica | Z | W1 | W2 | S1 | S2 | Solución |
Z | 1 | 0 | 12 | 0 | 12 | 6000 |
S1 | 0 | 0 | -1 | 1 | -2/3 | 5000/3 |
W1 | 0 | 1 | 2 | 0 | 1/3 | 500/3 |
 

 
 
EJEMPLO:
 
Unacompañí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...
tracking img