•Método Simplex Matricial
•Método Simplex Tabular
•Método Simplex Revisado
Características
Objetivo: Max / Min
Restricciones:
n Variables
m restricciones
Todas las restricciones deben ser: <=
Recursos no negativos
Variables no negativas
Método Simplex
Matricial
Representación Matricial del modelo de PL
Departamento Indice de Producción Capacidad
(Operación) (Horas/Unidad) Productiva
Artículo I Artículo 2 (Horas de Operación /
periodo)
Cortado 10 20 4,000
Troquelado 5 5 1,500
Esmaltado 4 2 800
Utilidad Unit($) 10 15
Formulación Formulación formato estándar
Max Max
Xo= 10X1 +15X2 Xo= 10X1 +15X2 + 0X3 + 0X4 + 0X5
S.A. S.A.
10X1 + 20X2 <=4000 10X1 + 20X2 + X3 = 4000
5X1 + 5X2 <=1500 5X1 + 5X2 +X4 = 1500
4X1 + 2X2 <= 800 4X1 + 2X2 +X5 = 800
Xj >=0 Xj >=0
Maximizar maximizar
Xo = CX Xo=(10,15,0,0,0) X 1
S.A. X2
X3
AX=b X4
X
5
X>0 S.A.
X1
C=(10,15,0,0,0) 10 20 1 0 0 4,000
X2
X1
10 20 1 0 0 5 5 0 1 0 X3
= 1,500
X2 4 2 0 0 1
X4 800
X X3 A 5 5 0 1 0 X
5
X4 4 2 0 0 1
X
5 X1 0
0
X2
4,000
X3
>= 0
b 1,500 X4 0
X 0
5
800
Optimizar
Xo = CBXB + CNXN
S.A.
XB
B, N b
XN
BXB + NXN = b
Donde:
CB= Vector de coeficientes básicos de dimensión 1 x m
CN= Vector de coeficientes no básicos de dimensión 1 x n
B= Base factible de dimensión m x m
XB= Vector de variables básicas de dimensión m x 1
N = Matriz de vectores no básicos de dimensión m x n
XN= vector de variables no básicas de dimensión (n x 1)
b= vector de recursos de dimmensión (m x 1)
Pasos para buscar la Solución Óptima
1) Obtener una solución básica de Inicio
2) Mediante un criterio de mejorabilidad, decide si
la SBF actual es suceptible de mejoría.
1) Si la SBF es inmejorable, entonces concluye
que esta es la óptima
2) Si la SBF es mejorable, entonces prescribe
cómo hacerlo y va al siguiente paso
3) Mediante el criterio de factibilidad, y
considerando lo prescrito en 2.2), diseña una
nueva SBF que necesariamente será factible.
1) Si no logra diseñar una nueva SBF, entonces
concluye que el problema tiene solución
ilimitada
2) De lo contrario vuelve al paso 2
BXB + NXN = b
B-1BXB + B-1NXN = B-1b
IXB + B-1NXN = B-1b
XB = B-1b – B-1NXN
Si en una Solución Básica XN=0
XB= B-1b
Xo= CBXB
Xo = CBXB + CNXN
Xo = CB(B-1b – B-1NXN) + CNXN
Xo = CBB-1b + (CN – CBB-1N) XN
Xo = CBXB + (CN – CBB-1N) XN
n
Xo c B x B c
J 1
J
c B B 1a J x j
n
Xo c B x B x
J 1
j j
w C B B 1 j B 1a j
j c J c B B 1a j j c J c B j
j c J wa j
X k max min
B 1b i
, k i 0, i 1,2,.., m
k i
Maximizar
Xo = 10 X1 + 15X2
S.A.
10X1 + 20 X2 <=4000
5x1 + 5 x2 <=1500
4X1 + 2 X2 <=800
Xj >=0
Formato Estandar
Xo = 10X1 +15X2 + 0 X3 + 0X4 + 0X5
S.A.
10X1 + 20 X2 + X3 =4000
5x1 + 5 x2 + X4 =1500
4X1 + 2 X2 + X5 =800
Xj >=0
1) Encontrar la SBF
B1= (a3, a4, a5)
1 0 0
B1 0 1 0
0 0 1
Cb ( 0 0 0 )
Cn ( 10 15 )
X3
Xb X4
X5
X1
Xn X2
X3 1 0 0 4000 4000
Xb = B b X4 = 0 1 0 x 1500 = 1500
X5 0 0 1 800 800
Xo = Cb Xb Xo= 0 0 0 4000
1500 0
800
X3 4000
SBF X4 = 1500 Xo = 0
X5 800
2 Criterio de Mejorabilidad
w= 0 0 0 1 0 0
0 1 0 0 0 0
0 0 1
°1= 10 - 0 0 0 10
5 10
4
°2= 15 - 0 0 0 20
5 15
2
3) Criterio de factibilidad
1 0 0 20 20
alfa 2 0 1 0 5= 5
0 0 1 2 2
X2 max = Min 4000 1500 800
20 5 2
200 300 400
1) Encontrar la SBF
B1= (a2, a4, a5)
20 0 0
B1 5 1 0
2 0 1
Cb ( 15 0 0)
Cn ( 10 0)
X2
Xb X4
X5
X1
Xn X3
X2 0,05 0 0 4000 200
Xb = B b X4 = -0,25 1 0x 1500 = 500
X5 -0,1 0 1 800 400
Xo= 15 0 0 200
500 3000
400
X2 200
SBF X4 = 500 Xo = 3000
X5 400
2 Criterio de Mejorabilidad
w= 15 0 0 0,05 0 0
-0,25 1 0 0,75 0 0
-0,1 0 1
°1= 10 - 0,75 0 0 10
5 2,5
4
°3 0- 0,75 0 0 1
0 -0,75
0
3)Criterio de factibilidad
0,05 0 0 10 0,5
alfa 1 -0,25 1 0 5= 2,5
-0,1 0 1 4 3
X1 max = Min 200 500 400
0,5 2,5 3
400 200 133
1) Encontrar la SBF
B1= (a2, a4, a1)
20 0 10
B1 5 1 5
2 0 4
Cb ( 15 0 10 )
Cn ( 0 0)
X2
Xb X4
X1
X5
Xn X3
X2 0,067 0 -0,2 4000 133,33
Xb = B b X4 = -0,167 1 -0,8 x 1500 = 166,67
X1 -0,033 0 0,33 800 133,33
Xo= 15 0 10 133,333
166,667 3333,3
133,333
X2 133,3
SBF X4 = 166,7 Xo = 3333,33
X1 133,3
2 Criterio de Mejorabilidad
w= 15 0 10 0,07 0 -0,17
-0,17 1 -0,83 0,667 0 0,83
-0,03 0 0,333
°5= 0- 0,67 0 0,83 0
0 -0,83
1
°3 0- 0,67 0 0,83 1
0 -0,67
0
Minimizar
Xo = -X1 -3X2
S.A.
X1 - 3 X2 <=6
4x1 + 4 x2 <=16
-2X1+2X2<=4
Xj >=0
Formato Estandar
Xo = - X1 -3X2 + 0X3 + 0X4 + 0X5
S.A.
X1 - 3X2 + X3 =6
4X1 + 4X2 + X4 =16
-2X1 + 2 X2 + X5 =4
Xj >=0
1) Encontrar la SBF
B1= (a3, a4, a5)
1 0 0
B1 0 1 0
0 0 1
Cb ( 0 0 0)
Cn ( -1 -3 )
X3
Xb X4
X5
X1
Xn X2
X3 1 0 0 6 6
Xb = B b X4 = 0 1 0x 16 = 16
X5 0 0 1 4 4
Xo = Cb Xb Xo= 0 0 0 6
16 0
4
X3 6
SBF X4 = 16 Xo = 0
X5 4
2 Criterio de Mejorabilidad
w= 0 0 0 1 0 0
0 1 0 0 0 0
0 0 1
°1= -1 - 0 0 0 1
4 -1
-2
°2= -3 - 0 0 0 -3
4 -3
2
3) Criterio de factibilidad
1 0 0 -3 -3
alfa 2 0 1 0 4= 4
0 0 1 2 2
X2 max = Min 6 16 4
-3 4 2
------- 4 2
1) Encontrar la SBF
B1= (a3, a4, a2)
1 0 -3
B1 0 1 4
0 0 2
Cb ( 0 0 -3 )
Cn ( -1 0)
X3
Xb X4
X2
X1
Xn X5
X3 1 0 1,5 6 12
Xb = B b X4 = 0 1 -2 x 16 = 8
X2 0 0 0,5 4 2
Xo= 0 0 -3 12
8 -6
2
X3 12
SBF X4 = 8 Xo = -6
X2 2
2 Criterio de Mejorabilidad
w= 0 0 -3 1 0 1,5
0 1 -2 0 0 -1,5
0 0 0,5
°1= -1 - 0 0 -1,5 1
4 -4
-2
°5 0- 0 0 -1,5 0
0 1,5
1
3)Criterio de factibilidad
1 0 1,5 1 -2
alfa 1 0 1 -2 4= 8
0 0 0,5 -2 -1
X1 max = Min 12 8 2
-2 8 -1
------- 1 -------
1) Encontrar la SBF
B1= (a3, a1, a2)
1 1 -3
B1 0 4 4
0 -2 2
Cb ( 0 -1 -3 )
Cn ( 0 0)
X3
Xb X1
X2
X4
Xn X5
X3 1 0,3 1 6 14
Xb = B b X1 = 0 0,1 -0,3 x 16 = 1
X2 0 0,1 0,25 4 3
Xo= 0 -1 -3 14
1 -10
3
X3 14
SBF X1 = 1 Xo = -10
X2 3
2 Criterio de Mejorabilidad
w= 0 -1 -3 1 0,25 1
0 0,13 -0,25 0 -0,5 -0,5
0 0,13 0,25
°4= 0- 0 -0,5 -0,5 0
1 0,5
0
°5 0- 0 -0,5 -0,5 0
0 0,5
1
Ejemplo de solución ilimitada
Max
Xo= 2X1 + 2X2
S.A.
-3X1 + 2X2 <=6
2X1 – 5X2 <=10
X1, X2 >=0
Max
Xo= 2X1 + 2X2 + 0X3 + 0X4
S.A.
-3X1 + 2X2 + X3 =6
2X1 – 5X2 +X4 =10
xj>=0
Solución Básica Factible Inicial
B1(a3,a4) x3
Cb=(0,0) Xb
1 0 x 4
B1
0 1
x1
Cn=(2,2) Xn
x 2
X 3 1 1 0 6 6
X b B b *
X 4 0 1 10 10
6
Xo CbXb 0,0 0
10
SBF X 3 6
X 4 10 Xo 0
Criterio de Mejorabilidad
w cb B 1
j c j wa j
1 0
w (0,0) (0,0)
0 1
3
1 2 (0,0) 2 X1 Entra
2
2
2 2 (0,0) 2
5
Criterio de Factibilidad
X k max
B 1 i
Min
; k 0
k i
1
1 B a1
1 0 3 3
1
0 1 2 2
10
X 1max Min ; 5
2
Sale X4
Solución Básica Factible
B1(a3,a1) x3
Cb=(0,2) Xb
1 3 x1
B1
0 2
x 4
Cn=(0,2) Xn
x 2
X 3 1 1 1.5 6 21
X b B b *
X1 0 0.5 10 5
21
Xo CbXb 0,2 10
5
SBF X 3 21
X 1 5 Xo 10
Criterio de Mejorabilidad
w cb B 1
j c j wa j
1 1.5
w (0,2) (0,1)
0 0.5
2
2 2 (0,1) 7
5 X2 Entra
0
4 0 (0,1) 0
1
Criterio de Factibilidad
X k max Min
B 1 i
; k 0
k i
1
2 B a2
1 1.5 2 5.5
2
0 0.5
5 2.5
X 2 max Min ; i lim itada
No hay variable de salida
Método Simplex
Tabular
Formato General
Base Xo Xb XN Solución
Renglon 0 Xo 1 0m -(CN – C BB-1N) CBB-1b
Renglón 1
... Xb 0m Im B-1N B-1b
Renglón
m
Representación Tabular del modelo de PL
Departamento Indice de Producción Capacidad Productiva
(Operación) (Horas/Unidad) (Horas de Operación /
Artículo I Artículo 2 periodo)
Cortado 10 20 4,000
Troquelado 5 5 1,500
Esmaltado 4 2 800
Utilidad Unit($) 10 15
Formulación
Max
Xo= 10X1 +15X2 + 0X3 + 0X4 + 0X5
S.A.
10X1 + 20X2 + X3 =4000
5X1 + 5X2 +X4 =1500
4X1 + 2X2 +X5 = 800
Xj >=0
Maximizar
Xo = 10 X1 + 15X2
S.A.
10X1 + 20 X2 <=4000
5x1 + 5 x2 <=1500
4X1 + 2 X2 <=800
Xj >=0
Formato Estandar
Xo = 10X1 +15X2 + 0 X3 + 0X4 + 0X5
S.A.
10X1 + 20 X2 + X3 =4000
5x1 + 5 x2 + X4 =1500
4X1 + 2 X2 + X5 =800
Xj >=0
Modelo
Xo - 10X1 -15X2 - 0 X3 - 0X4 - 0X5 =0
10X1 + 20 X2 + X3 =4000
5x1 + 5 x2 + X4 =1500
4X1 + 2 X2 + X5 =800
Xj >=0
Tabla Inicial
Renglón Base X0 X1 X2 X3 X4 X5 Solución
0 X0 1 -10 -15 0 0 0 0
1 X3 0 10 20 1 0 0 4000 4000/20
2 X4 0 5 5 0 1 0 1500 1500/5
3 X5 0 4 2 0 0 1 800 800/2
Tabla II
Renglón Bas X0 X1 X2 X3 X4 X5 Solución
e
0 X0 1 -5/2 0 ¾ 0 0 3000
1 X2 0 ½ 1 1/20 0 0 200 200/0,5
2 X4 0 5/2 0 -1/4 1 0 500 500/2,5
3 X5 0 3 0 -1/10 0 1 400 400/3
Tabla III
Renglón Bas X0 X1 X2 X3 X4 X5 Solución
e
0 X0 1 0 0 2/3 0 5/6 3333.33
1 X2 0 0 1 1/15 0 -1/6 400/3
2 X4 0 0 0 -1/6 1 -5/6 500/3
3 X1 0 1 0 -1/30 0 1/3 400/3
Minimizar
Xo = -1 X1 -3X2
S.A.
1X1 - 3 X2 <=6
4x1 + 4 x2 <=16
-2X1+2X2<=4
Xj >=0
Formato Estandar
Xo = -1 X1 -3X2 + 0X3 + 0X4 + 0X5
S.A.
1X1 -3 X2 + X3 =6
4x1 + 4 x2 + X4 =16
-2X1 + 2 X2 + X5 =4
Xj >=0
Tabla Inicial
Renglón Base X0 X1 X2 X3 X4 X5 Solución
0 X0 1 1 3 0 0 0 0 0
1 X3 0 1 -3 1 0 0 6 ---
2 X4 0 4 4 0 1 0 16 16/4
3 X5 0 -2 2 0 0 1 4 4/2
Tabla II
Renglón Bas X0 X1 X2 X3 X4 X5 Solución
e
0 X0 1 4 0 0 0 -3/2 -6
1 X3 0 -2 0 1 0 3/2 12 ----
2 X4 0 8 0 0 1 -2 8 1
3 X2 0 -1 1 0 0 1/2 2 ---
Tabla III
Renglón Base X0 X1 X2 X3 X4 X5 Solución
0 X0 1 0 0 0 -1/2 -1/2 -10
1 X3 0 0 0 1 1/4 1 14
2 X1 0 1 0 0 1/8 -1/4 1
3 X2 0 0 1 0 1/8 1/4 3