MÉTODO SIMPLEX
• Procedimiento general para resolver problemas de programación
lineal.
• Desarrollado por George Dantzig en 1947.
• Es un procedimiento algebraico aunque sus conceptos
fundamentales son geométricos.
• Está basado en un algoritmo o series de pasos donde se evalúan
los criterios de Optimalidad y Factibilidad
• Se pueden usar con 2 o más variables de decisión.
MÉTODO SIMPLEX
Función Objetivo:
Max Z = 5X1 + 4X2
Restricciones:
1. 6X1 + 4X2 <= 24
2. X1 + 2X2 <= 6
3. -X1 + X2 <= 1
4. X2 <= 2
5. X1 ,X2 >= 0
MÉTODO SIMPLEX
Pasos:
1. Transformar la función Z y las restricciones a igualdades e
introducir las variables de holgura o de exceso de acuerdo al
caso de la restricción, estas variables también denominadas no
básicas se determinan en función del número de restricciones
presentes en el modelo:
• En el caso de las restricciones si son <= se convierten en =
pero se introducen variables de holgura o variables básicas
con signo positivo
• En el caso de las restricciones si son >= se convierten en =
MÉTODO SIMPLEX
Pasos:
• pero se introducen variables de exceso o variables básicas
con signo negativo
En nuestro ejemplo base este paso queda de la siguiente forma
Z - 5X1 - 4X2+ 0X3+ 0X4+ 0X5+ 0X6= 0
6X1 + 4X2+X3+ 0X4+ 0X5 + 0X6 = 24
X1 + 2X2+0X3+ X4+ 0X5 + 0X6 = 6
-X1 + X2+0X3+ 0X4+ X5 + 0X6 = 1
0X1+X2+0X3+ 0X4+ 0X5 + X6 = 2
X1,X2,X3,X4,X5,X6 >= 0
MÉTODO SIMPLEX
Pasos:
2. Construir la tabla original de partida del Método Simplex
Básica Z X1 X2 X3 X4 X5 X6 Solución Renglón
Z 1 -5 -4 0 0 0 0 0 Z
X3 0 6 4 1 0 0 0 24 X3
X4 0 1 2 0 1 0 0 6 X4
X5 0 -1 1 0 0 1 0 1 X5
X6 0 0 1 0 0 0 0 2 X6
Variables no básicas (ceros) (X1 y X2)
Variables básicas (X3,X4 ,X5, X6)
MÉTODO SIMPLEX
Pasos:
3. Identificar que Variable sale y cual entra utilizando los
criterios de optimalidad y de factibilidad respectivamente
• Criterio de Optimalidad: Si el problema es de
Maximización la variable no básica que entra es la que
tiene el coeficiente más negativo en el renglón Z, si el
problema es Minimización la variable no básica que
entra es la que tiene el coeficiente más positivo en el
renglón Z. En el caso de que hubiese empates se rompen
en forma arbitraria. Se llega al óptimo en la iteración en
MÉTODO SIMPLEX
Pasos:
• la que todos los coeficientes de las variables no básicas
son positivas (si el problema es Maximización) o son
positivas (si el problema es Minimización).
• Criterio de Factibilidad: Independientemente si el
problema es de maximización y minimización, la variable
de salida es la variable básica asociada con la mínima
razón no negativa (con denominador estrictamente
positivo). Los empates se rompen en forma arbitraria.
MÉTODO SIMPLEX
Pasos:
En nuestro ejemplo base este paso queda de la siguiente forma
Básica Z X1 X2 X3 X4 X5 X6 Solución Renglón
Z 1 -5 -4 0 0 0 0 0 Z
X3 0 6 4 1 0 0 0 24 X3
X4 0 1 2 0 1 0 0 6 X4
X5 0 -1 1 0 0 1 0 1 X5
X6 0 0 1 0 0 0 0 2 X6
MÉTODO SIMPLEX
Pasos:
Por tanto se divide la Solución entre cada coeficiente de la Columna
X1 por ser la variable que entra en este momento por tanto
Básicas Solución X1 Nueva Solución
X3 24 6 24
=4
6
X4 6 1 6
=6
1
X5 1 -1 1
= −1
−1
X6 2 0 2
=∞
0
Pasos: MÉTODO SIMPLEX
En función de este cálculo se desecha los valores negativos y los
indeterminados por no cumplir el criterio de factibilidad, por tanto
queda X3 con 3 y X4 con 6 para aplicar dicho criterio, por tanto se
toma X3 con 3 por ser el valor más pequeño.
Básica Z X1 X2 X3 X4 X5 X6 Solución Renglón
Z 1 -5 -4 0 0 0 0 0 Z
X3 0 6 4 1 0 0 0 24 X3
X4 0 1 2 0 1 0 0 6 X4
X5 0 -1 1 0 0 1 0 1 X5
X6 0 0 1 0 0 0 0 2 X6
Columna Pivote (X1) Variable que entra (X1) Fila Pivote (X3) Variable que sale (X3) Elemento
Pivote: 6
MÉTODO SIMPLEX
Pasos:
Iteración # 1:
Aplicando el Método de Gauss – Jordan para obtener la nueva
solución básica
Básica Z X1 X2 X3 X4 X5 X6 Solución Renglón
Z 1 0 -2/3 5/6 0 0 0 20 Z
X1 0 1 2/3 1/6 0 0 0 4 X1
X4 0 0 4/3 -1/6 1 0 0 2 X4
X5 0 0 5/3 1/6 0 1 0 5 X5
X6 0 0 1 0 0 0 0 2 X6
MÉTODO SIMPLEX
Pasos:
Iteración # 1:
Nueva Fila Pivote (NFP) X1 = Fila Pivote X3 / Elemento Pivote
Básica Z X1 X2 X3 X4 X5 X6 Solución
X1 0/6 6/6 4/6 1/6 0/6 0/6 0/6 24/6
Básica Z X1 X2 X3 X4 X5 X6 Solución
X1 0 1 2/3 1/6 0 0 0 4
MÉTODO SIMPLEX
Pasos:
Nueva Z = Z Anterior + (NFP X1* (-)Coeficiente de la Columna Pivote
X1)
Básica Z X1 X2 X3 X4 X5 X6 Solución
Z 1 -5 -4 0 0 0 0 0
anterior
NFP X1 0*5 1*5 (2/3) *5 (1/6)*5 0*5 0*5 0*5 4*5
Básica Z X1 X2 X3 X4 X5 X6 Solución
Z 1 -5 -4 0 0 0 0 0
anterior +
NFP X1 0 5 10/3 5/6 0 0 0 20
Nueva Z 1 0 -2/3 5/6 0 0 0 20
MÉTODO SIMPLEX
Pasos:
Nueva X4 = X4 Anterior + (NFP X1* (-)Coeficiente de la Columna
Pivote X1 )
Básica Z X1 X2 X3 X4 X5 X6 Solución
X4 0 1 2 0 1 0 0 6
anterior
NFP X1 0*-1 1*-1 (2/3) *-1 (1/6)*-1 0*-1 0*-1 0*-1 4*-1
Básica Z X1 X2 X3 X4 X5 X6 Solución
X4 0 1 2 0 1 0 0 6
anterior +
NFP X1 0 -1 -2/3 -1/6 0 0 0 -4
Nueva 0 0 4/3 -1/6 1 0 0 2
X4
MÉTODO SIMPLEX
Pasos:
Nueva X5 = X5 Anterior + (NFP X1* (-)Coeficiente de la Columna
Pivote X1)
Básica Z X1 X2 X3 X4 X5 X6 Solución
X5 0 -1 1 0 0 1 0 1
anterior
NFP X1 0*1 1*1 (2/3) *1 (1/6)*1 0*1 0*1 0*1 4*1
Básica Z X1 X2 X3 X4 X5 X6 Solución
X5 0 -1 1 0 0 1 0 1
anterior +
NFP X1 0 1 2/3 1/6 0 0 0 4
Nueva 0 0 5/3 1/6 0 1 0 5
X5
MÉTODO SIMPLEX
Pasos:
Nueva X6 = X6 Anterior + (NFP X1* (-)Coeficiente de la Columna
Pivote X1 )
Básica Z X1 X2 X3 X4 X5 X6 Solución
X6 0 0 1 0 0 0 0 2
anterior
NFP X1 0*0 1*0 (2/3) *0 (1/6)*0 0*0 0*0 0*0 4*0
Básica Z X1 X2 X3 X4 X5 X6 Solución
X6 0 0 1 0 0 0 0 2
anterior +
NFP X1 0 0 0 0 0 0 0 0
Nueva 0 0 1 0 0 0 0 2
X6
MÉTODO SIMPLEX
Pasos:
Iteración # 2: Aplicando los criterios de optimalidad y factibilidad
Básica Z X1 X2 X3 X4 X5 X6 Solución Renglón
Z 1 0 -2/3 5/6 0 0 0 20 Z
X1 0 1 2/3 1/6 0 0 0 4 X1
X4 0 0 4/3 -1/6 1 0 0 2 X4
X5 0 0 5/3 1/6 0 1 0 5 X5
X6 0 0 1 0 0 0 0 2 X6
MÉTODO SIMPLEX
Pasos:
Por tanto se divide la Solución entre cada coeficiente de la Columna
X2 por ser la variable que entra en este momento por tanto
Básicas Solución X2 Nueva Solución
X1 4 2/3 4
1 = 12 = 6
2 2
3
X4 2 4/3 2
1 = 6 = 1, 5
4 4
3
X5 5 5/3 5
1 = 15 = 3
5 5
3
X6 2 1 2
= 2
1
MÉTODO SIMPLEX
Pasos:
En función de este cálculo queda X4 con 1,5 por ser el valor más
pequeño.
Básica Z X1 X2 X3 X4 X5 X6 Solución Renglón
Z 1 0 -2/3 5/6 0 0 0 20 Z
X1 0 1 2/3 1/6 0 0 0 4 X1
X4 0 0 4/3 -1/6 1 0 0 2 X4
X5 0 0 5/3 1/6 0 1 0 5 X5
X6 0 0 1 0 0 0 0 2 X6
Columna Pivote (X2) Variable que entra (X2) Fila Pivote (X4) Variable
que sale (X4) Elemento Pivote: 4/3
MÉTODO SIMPLEX
Pasos:
Básica Z X1 X2 X3 X4 X5 X6 Solución Renglón
Z 1 0 0 3/4 1/2 0 0 21 Z
X1 0 1 0 1/4 -1/2 0 0 3 X1
X2 0 0 1 -1/8 3/4 0 0 3/2 X2
X5 0 0 0 3/8 -5/4 1 0 5/2 X5
X6 0 0 0 1/8 -3/4 0 0 1/2 X6
MÉTODO SIMPLEX
Pasos:
Nueva Fila Pivote (NFP) X2 = Fila Pivote X4 / Elemento Pivote
Básica Z X1 X2 X3 X4 X5 X6 Solución
X2 0 0 4 −1 1 0 0 2
1 1 3 6 1 1 1 1
4 4 4 4 4 4 4 4
3 3 3 3 3 3 3 3
Básica Z X1 X2 X3 X4 X5 X6 Solución
X2 0 0 1 -1/8 3/4 0 0 3/2
MÉTODO SIMPLEX
Pasos:
Nueva Z = Z Anterior + (NFP X2* (-)Coeficiente de la Columna Pivote
X2)
Básica Z X1 X2 X3 X4 X5 X6 Solución
Z 1 0 -2/3 5/6 0 0 0 20
anterior
NFP X2 0* 2/3 0* 2/3 1* 2/3 -1/8* 2/3 3/4* 2/3 0* 2/3 0* 2/3 3/2* 2/3
Básica Z X1 X2 X3 X4 X5 X6 Solución
Z 1 0 -2/3 5/6 0 0 0 20
anterior +
NFP X2 0 0 2/3 -1/12 1/2 0 0 1
Nueva Z 1 0 0 3/4 1/2 0 0 21
MÉTODO SIMPLEX
Pasos:
Nueva X1 = X1 Anterior + ((NFP X2* (-)Coeficiente de la Columna
Pivote X2)
Básica Z X1 X2 X3 X4 X5 X6 Solución
X1 0 1 2/3 1/6 0 0 0 4
anterior
NFP X2 0* -2/3 0* -2/3 1* -2/3 -1/8* -2/3 3/4* -2/3 0* -2/3 0* -2/3 3/2* -2/3
Básica Z X1 X2 X3 X4 X5 X6 Solución
X1 0 1 2/3 1/6 0 0 0 4
anterior +
NFP X2 0 0 -2/3 1/12 -1/2 0 0 -1
Nueva 0 1 0 1/4 -1/2 0 0 3
X1
MÉTODO SIMPLEX
Pasos:
Nueva X5 = X5 Anterior + (NFP X2* (-)Coeficiente de la Columna
Pivote X2)
Básica Z X1 X2 X3 X4 X5 X6 Solución
X5 0 0 5/3 1/6 0 1 0 1
anterior
NFP X2 0* -5/3 0* -5/3 1* -5/3 -1/8* -5/3 3/4* -5/3 0* -5/3 0* -5/3 3/2* -5/3
Básica Z X1 X2 X3 X4 X5 X6 Solución
X5 0 0 5/3 1/6 0 1 0 5
anterior +
NFP X2 0 0 -5/3 5/24 -5/4 0 0 -5/2
Nueva 0 0 0 3/8 -5/4 1 0 5/2
X5
MÉTODO SIMPLEX
Pasos:
Nueva X6 = X6 Anterior + (NFP X2* (-)Coeficiente de la Columna
Pivote X2 )
Básica Z X1 X2 X3 X4 X5 X6 Solución
X6 0 0 1 0 0 0 0 2
anterior
NFP X2 0* -1 0* -1 1* -1 -1/8* -1 3/4* -1 0* -1 0* -1 3/2* -1
Básica Z X1 X2 X3 X4 X5 X6 Solución
X6 0 0 1 0 0 0 0 2
anterior +
NFP X2 0 0 -1 1/8 -3/4 0 0 -3/2
Nueva 0 0 0 1/8 -3/4 0 0 1/2
X6
MÉTODO SIMPLEX
Pasos:
Como no hay más valores negativos o en otras palabras hay
solamente valores positivos en la fila de Z se detiene el algoritmo
simplex quedando Z con 21, X1 con 3 y X2 con 1,5.
Básica Z X1 X2 X3 X4 X5 X6 Solución Renglón
Z 1 0 0 3/4 1/2 0 0 21 Z
X1 0 1 0 1/4 -1/2 0 0 3 X1
X2 0 0 1 -1/8 3/4 0 0 3/2 X2
X5 0 0 0 3/8 -5/4 1 0 5/2 X5
X6 0 0 0 1/8 -3/4 0 0 1/2 X6