28-Abril TP3 -2021 Metodo Simplex (Clase 5)

Vista previa del material en texto

CLASE PRACTICA: Investigación Operativa
Trabajo Practico Nº 3 – Método Simplex
Profesores: JTP. Ing. Néstor O. Cruz
AY1. Ing. Mariela E. Rodríguez
Facultad de Ingeniería
Universidad Nacional de Jujuy
MAX Z = 70 X1 + 40 X2 
S.a. 
2 X1 + 5 X2 ≤ 2000
2 X1 + 1 X2 ≤ 800
1 X1 + 1 X2 ≤ 500
X1 , X2 ≥ 0
MAX Z = 70 X1 + 40 X2 + 0 X3 + 0 X4 + 0 X5
S.a. 
2 X1 + 5 X2 + 1 X3 + 0 X4 + 0 X5 = 2000
2 X1 + 1 X2 + 0 X3 + 1 X4 + 0 X5 = 800
1 X1 + 1 X2 + 0 X3 + 0 X4 + 1 X5 = 500
X1 , X2, X3 , X4, X5 ≥ 0
Llevar el problema a Forma Estándar 
Matriz identidad
Trabajo Practico Nº 3 – Método Simplex
Elementos de la tabla Simplex
MAX Z = 70 X1 + 40 X2 + 0 X3 + 0 X4 + 0 X5
S.a. 
2 X1 + 5 X2 + 1 X3 + 0 X4 + 0 X5 = 2000
2 X1 + 1 X2 + 0 X3 + 1 X4 + 0 X5 = 800
1 X1 + 1 X2 + 0 X3 + 0 X4 + 1 X5 = 500
X1 , X2, X3 , X4, X5 ≥ 0
Cj
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
X3
X4
X5
ZJ
ZJ - CJ
Elementos de la tabla Simplex
Coeficientes de Función Objetivo
Variables Básicas
Coeficientes tecnológicos
MAX Z = 70 X1 + 40 X2 + 0 X3 + 0 X4 + 0 X5
S.a. 
2 X1 + 5 X2 + 1 X3 + 0 X4 + 0 X5 = 2000
2 X1 + 1 X2 + 0 X3 + 1 X4 + 0 X5 = 800
1 X1 + 1 X2 + 0 X3 + 0 X4 + 1 X5 = 500
X1 , X2, X3 , X4, X5 ≥ 0
Cj 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0
0 X4 800 2 1 0 1 0
0 X5 500 1 1 0 0 1
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
Cálculos para obtener Zj y (Zj – Cj)
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0
0 X4 800 2 1 0 1 0
0 X5 500 1 1 0 0 1
Zj 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
Cj
Multiplicamos Ci * Bj
Sumamos ∑ Ci * Bj
Obtenemos Zj
Restamos Zj - Cj
1
2
1
2
3
4
2
3
4
Seleccionamos Pivote
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0
0 X4 800 2 1 0 1 0
0 X5 500 1 1 0 0 1
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
Cj Seleccionamos ZJ – Cj
Si es Max
Seleccionar el más negativo
Si es Min
Seleccionar el más positivo
Variable que ingresa
Seleccionamos Pivote
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
Cj
Obtenemos 
ϴj = Bj / Xi
Seleccionamos ϴj
El valor mínimo positivo 
(tanto para Max o Min)
Seleccionamos ZJ – Cj 
Si es Max
Seleccionar el más negativo
Si es Min
Seleccionar el más positivo
Variable que ingresa
Variable 
que sale
Seleccionamos Pivote
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
Cj
Obtenemos 
ϴj = Bj / Xi
Seleccionamos ϴj
El valor mínimo positivo 
(tanto para Max o Min)
Encontramos el pivote
A21 = 2
Seleccionamos ZJ – Cj 
Si es Max
Seleccionar el más negativo
Si es Min
Seleccionar el más positivo
Ingresamos la variable X1 a la base
Sacamos la variable X4
Variable que ingresa
Variable 
que sale
Segunda Iteración
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
Cj Salió X4 ingreso X1 a la base
1- Dividimos la fila del pívot por ese valor del pívot
2- Calculamos los nuevos valores de los casilleros
Nuevo B1 
Nuevo B1 = Anterior B1 – A11 * B2 / A21 
Nuevo B1 = 2000 – 2* 800 / 2
Nuevo B1 = 1200
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200
70 X1 400 1 1/2 0 1/2 0
0 X5
ZJ
ZJ - CJ
Iteración 1
Iteración 2
Cj
Segunda Iteración
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
Cj
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 4
70 X1 400 1 1/2 0 1/2 0
0 X5
ZJ
ZJ - CJ
Iteración 1
Iteración 2
Salió X4 ingreso X1 a la base
1- Divimos la fila del pívot por ese valor del pívot
2- Calculamos los nuevos valores de los casilleros
Nuevo B1
Nuevo B1 = Anterior B1 – A11 * B2 / A21 
Nuevo B1 = 2000 – 2* 800 / 2
Nuevo B1 = 1200
Nuevo A12
Nuevo A12 = Anterior A12 – A11 * A 22 / A21 
Nuevo A12 = 5 – 2* 1 / 2
Nuevo A12 = 4
Cj
Segunda Iteración
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 4 1
70 X1 400 1 1/2 0 1/2 0
0 X5
ZJ
ZJ - CJ
Iteración 1
Iteración 2
Salió X4 ingreso X1 a la base
1- Divimos la fila del pívot por ese valor del pívot
2- Calculamos los nuevos valores de los casilleros
Nuevo B1
Nuevo B1 = Anterior B1 – A11 * B2 / A21 
Nuevo B1 = 2000 – 2* 800 / 2
Nuevo B1 = 1200
Nuevo A12 
Nuevo A12 = Anterior A12 – A11 * A 22 / A21 
Nuevo A12 = 5 – 2* 1 / 2
Nuevo A12 = 4
Nuevo A13
Nuevo A13 = Anterior A13 – A11 * A 23 / A21 
Nuevo A13 = 1 – 2* 0 / 2
Nuevo A13 = 1
Repetimos este proceso para todos los casilleros de la tabla
Cj
Cj
Segunda Iteración
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 0 4 1 -1 0
70 X1 400 1 1/2 0 1/2 0
0 X5 100 0 1/2 0 -1/2 1
ZJ
ZJ - CJ
Iteración 1
Iteración 2
Salió X4 ingreso X1 a la base
1- Divimos la fila del pívot por ese valor del pívot
2- Calculamos los nuevos valores de los casilleros
Nuevo B1
Nuevo B1 = Anterior B1 – A11 * B2 / A21 
Nuevo B1 = 2000 – 2* 800 / 2
Nuevo B1 = 1200
Nuevo A12 
Nuevo A12 = Anterior A12 – A11 * A 22 / A21 
Nuevo A12 = 5 – 2* 1 / 2
Nuevo A12 = 4
Nuevo A13
Nuevo A13 = Anterior A13 – A11 * A 23 / A21 
Nuevo A13 = 1 – 2* 0 / 2
Nuevo A13 = 1
Repetimos este proceso para todos los casilleros de la tabla
Cj
Cj
Segunda Iteración
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 0 4 1 -1 0
70 X1 400 1 1/2 0 1/2 0
0 X5 100 0 1/2 0 -1/2 1
ZJ 28000 70 35 0 35 0
ZJ - CJ
Iteración 1
Iteración 2
Salió X4 ingreso X1 a la base
1- Divimos la fila del pívot por ese valor del pívot
2- Calculamos los nuevos valores de los casilleros
3- Calculamos Z 
Cj
Cj
Segunda Iteración
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 0 4 1 -1 0
70 X1 400 1 1/2 0 1/2 0
0 X5 100 0 1/2 0 -1/2 1
ZJ 28000 70 35 0 35 0
ZJ - CJ 0 -5 0 1/2 0
Iteración 1
Iteración 2
Salió X4 ingreso X1 a la base
1- Divimos la fila del pívot por ese valor del pívot
2- Calculamos los nuevos valores de los casilleros
3- Calculamos Z 
4- Calculamos Zj - Cj
Cj
Cj
Segunda Iteración
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 0 4 1 -1 0
70 X1 400 1 1/2 0 1/2 0
0 X5 100 0 1/2 0 -1/2 1
ZJ 28000 70 35 0 35 0
ZJ - CJ 0 -5 0 1/2 0
Iteración 1
Iteración 2
Salió X4 ingreso X1 a la base
1- Divimos la fila del pívot por ese valor del pívot
2- Calculamos los nuevos valores de los casilleros
3- Calculamos Z 
4- Calculamos Zj – Cj
5- Seleccionamos variable que ingresa (más negativa)
Variable que ingresa
Cj
Cj
Segunda Iteración
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 0 4 1 -1 0 300
70 X1 400 1 1/2 0 1/2 0 800
0 X5 100 0 1/2 0 -1/2 1 200
ZJ 28000 70 35 0 35 0
ZJ - CJ 0 -5 0 1/2 0
Iteración 1
Iteración 2
Salió X4 ingreso X1 a la base
1- Divimos la fila del pívot por ese valor del pívot
2- Calculamos los nuevos valores de los casilleros
3- Calculamos Z 
4- Calculamos Zj – Cj
5- Seleccionamos variable que ingresa (más negativa)
6- Seleccionamos variable quesale 
(ϴ más pequeño positivo)
Variable que ingresa
Variable 
que sale
Cj
Cj
Segunda Iteración
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 0 4 1 -1 0 300
70 X1 400 1 1/2 0 1/2 0 800
0 X5 100 0 1/2 0 -1/2 1 200
ZJ 28000 70 35 0 35 0
ZJ - CJ 0 -5 0 1/2 0
Iteración 1
Iteración 2
Salió X4 ingreso X1 a la base
1- Divimos la fila del pívot por ese valor del pívot
2- Calculamos los nuevos valores de los casilleros
3- Calculamos Z 
4- Calculamos Zj – Cj
5- Seleccionamos variable que ingresa (más negativa)
6- Seleccionamos variable que sale 
(ϴ más pequeño positivo)
7- Encontramos el pívot
8- Pasamos a siguiente iteración
Cj
Cj
Tercera Iteración
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3
70 X1
40 X2 200 0 1 0 -1 2
ZJ
ZJ - CJ
Iteración 2
Iteración 3
Salió X5 ingreso X2 a la base
1- Divimos la fila del pívot por ese valor del pívot
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 0 4 1 -1 0 300
70 X1 400 1 1/2 0 1/2 0 800
0 X5 100 0 1/2 0 -1/2 1 200
ZJ 28000 70 35 0 35 0
ZJ - CJ 0 -5 0 1/2 0
** Resolver **
Cj
Cj
Tercera IteraciónIteración 2
Iteración 3
Salió X5 ingreso X2 a la base
1- Divimos la fila del pívot por ese valor del pívot
2- Calculamos los nuevos valores de los casilleros
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 0 4 1 -1 0 300
70 X1 400 1 1/2 0 1/2 0 800
0 X5 100 0 1/2 0 -1/2 1 200
ZJ 28000 70 35 0 35 0
ZJ - CJ 0 -5 0 1/2 0
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 400 0 0 1 3 -8
70 X1 300 1 0 0 1 -1
40 X2 200 0 1 0 -1 2
ZJ
ZJ - CJ
Cj
Cj
Tercera IteraciónIteración 2
Iteración 3
Salió X5 ingreso X2 a la base
1- Divimos la fila del pívot por ese valor del pívot
2- Calculamos los nuevos valores de los casilleros
3- Calculamos Z 
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 0 4 1 -1 0 300
70 X1 400 1 1/2 0 1/2 0 800
0 X5 100 0 1/2 0 -1/2 1 200
ZJ 28000 70 35 0 35 0
ZJ - CJ 0 -5 0 1/2 0
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 400 0 0 1 3 -8
70 X1 300 1 0 0 1 -1
40 X2 200 0 1 0 -1 2
ZJ 29000 70 40 0 30 10
ZJ - CJ
Cj
Cj
Tercera IteraciónIteración 2
Iteración 3
Salió X5 ingreso X2 a la base
1- Divimos la fila del pívot por ese valor del pívot
2- Calculamos los nuevos valores de los casilleros
3- Calculamos Z 
4- Calculamos Zj – Cj
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 0 4 1 -1 0 300
70 X1 400 1 1/2 0 1/2 0 800
0 X5 100 0 1/2 0 -1/2 1 200
ZJ 28000 70 35 0 35 0
ZJ - CJ 0 -5 0 1/2 0
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 400 0 0 1 3 -8
70 X1 300 1 0 0 1 -1
40 X2 200 0 1 0 -1 2
ZJ 29000 70 40 0 30 10
ZJ - CJ 0 0 0 30 10
Todos los Zj – Cj son positivos Llegamos a la solución
Z = 29000
X1 = 300
X2 = 200
X3 = 400
X4 = 0
X5 = 0
Solución Optima
Cj
Cj
Relación Iteración de Método Simplex con Método Gráfico
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
Iteración 1
1
Cj
Relación Iteración de Método Simplex con Método Gráfico
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 2000 2 5 1 0 0 1000
0 X4 800 2 1 0 1 0 400
0 X5 500 1 1 0 0 1 500
ZJ 0 0 0 0 0 0
ZJ - CJ -70 -40 0 0 0
Z
Iteración 2
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 1200 0 4 1 -1 0 300
70 X1 400 1 1/2 0 1/2 0 800
0 X5 100 0 1/2 0 -1/2 1 200
ZJ 28000 70 35 0 35 0
ZJ - CJ 0 -5 0 1/2 0 2
Cj
Relación Iteración de Método Simplex con Método Gráfico
Z
Iteración 3
Z
3
MAX 70 40 0 0 0
Ci Xi Bj X1 X2 X3 X4 X5 ϴ
0 X3 400 0 0 1 3 -8
70 X1 300 1 0 0 1 -1
40 X2 200 0 1 0 -1 2
ZJ 29000 70 40 0 30 10
ZJ - CJ 0 0 0 30 10
Cj
Preguntas
Muchas Gracias