gestion de operaciones
Hector Herrera Lavanchy
Alexis Olmedo Navarro
1
Algoritmo Método Simplex
Paso 1
PASO INICIAL
Paso 2
BUSCA NUEVA SOLUCION
Paso 3
PRUEBA DE OPTIMALIDAD
NO¿SOLUCION
OPTIMA?
Hector Herrera Lavanchy
Alexis Olmedo Navarro
SI
TERMINA
2
Paso 2: Busca nueva solución
2.A Determinar dirección de búsqueda
2.B Determinar frontera limitante
2.CDeterminar nueva solución
Hector Herrera Lavanchy
Alexis Olmedo Navarro
3
Método simplex
Se tiene el siguiente problema:
MAX Z = 3 x1 + 5 x2
s.a.
4
x1
2 x2
12
3 x1 + 2x2
18
x1 , x2
0
Hector Herrera Lavanchy
Alexis Olmedo Navarro
4
Método simplex
x2
(0,6)
(2,6)
6
4
(4,3)
2
(0,0)
2
(4,0)
4
6
Hector HerreraLavanchy
Alexis Olmedo Navarro
x1
5
Paso 1: Solución inicial
• Se agregan variables de holgura y variable Z
• Se hacen variables de decisión = 0
Solución: (x1 , x2 , x3 , x4 , x5 ) = ( 0, 0,4, 12, 18)
Z - 3 x1 - 5 x2
x1
= 0
+ x3
2 x2
3 x 1 + 2 x2
= 4
+ x4
= 12
+ x5
x1 , x2 , x3 , x4 , x5 ,
= 18
0
6
Paso 1: Solución inicial
Solución: (x1 , x2 , x3 , x4, x5 ) = ( 0, 0, 4, 12, 18)
x2
(0,6)
(2,6)
6
4
(4,3)
2
(0,0)
2
(4,0)
4
6
Hector Herrera Lavanchy
Alexis Olmedo Navarro
x1
7
Paso 2.A: Dirección de búsqueda
•Se comparan los coeficientes de las variables no básicas en
la FO
• Se selecciona X2 porque 5 > 3 (Var. no básica que entra)
Z - 3 x1 - 5 x2
x1
= 0
+ x3
2 x2
3 x1 + 2 x2
= 4
+x4
= 12
+ x5
x1 , x 2 , x3 , x4 , x5 ,
Hector Herrera Lavanchy
Alexis Olmedo Navarro
= 18
0
ITERACION 1
8
Paso 2.A: Dirección de búsqueda
x2
(0,6)
(2,6)
6
4
(4,3)2
(0,0)
2
(4,0)
4
6
Hector Herrera Lavanchy
Alexis Olmedo Navarro
x1
ITERACION 1
9
Paso 2.B: Límite de avance
• Se dividen “lados derechos” por los coeficientes...
Regístrate para leer el documento completo.