Metodo dual simplex

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