gestion de operaciones

Método Simplex

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