MÉTODO SIMPLEX
UNIVERSIDAD DE EL SALVADOR
FACULTAD MULTIDISCIPLINARIA DE OCCIDENTE
DEPARTAMENTO DE MATEMÁTICA
Ejemplo de
Simplex:
Maximizar Z = f(x1,x2) = 3x1 + 2x2
Sujeto a: 2x1 + x2 ≤ 18
2x1 + 3x2 ≤ 42
3x1 + x2 ≤ 24
x 1 ≥ 0 , x2 ≥ 0
1. Convertir las desigualdades
en igualdades:
Se introduce una variable de holgura por cada una de las
restricciones, este caso s1, s2, s3 para convertirlas en
igualdades y formar el sistema de ecuaciones estandar.
Usando en simplex el siguiente criterio:
Signo: Introducir
≤ sn
FORMA ESTÁNDAR:
2x1 + x2 + s1 = 18
2x1 + 3x2 + s2 = 42
3x1 + x2 + s3 = 24
2. Igualar la función objetivo a cero:
Z - 3 x1 - 2 x2 = 0
3. Escribir la tabla inicial simplex:
En las columnas aparecerán todas las variables
del problema y en las filas, los coeficientes de las
igualdades obtenidas, una fila para cada
restricción:
Tabla Inicial
Variable de Variable de Solución
decisión holgura
X1 X2 S1 S2 S3
S1 2 1 1 0 0 18
S2 2 3 0 1 0 42
S3 3 1 0 0 1 24
Z -3 -2 0 0 0 0
4. Encontrar la variable de decisión que entra y la variable de
holgura que sale.
A. Para escoger la variable de decisión que entra, (FLECHA
ROJA PARTE SUPERIOR), observamos la última fila, la cual
muestra los coeficientes de la función objetivo y escogemos la
variable con el coeficiente más negativo.
En este caso, la variable x1 de coeficiente - 3.
Si existiesen dos o más coeficientes iguales que cumplan la
condición anterior, entonces se elige cualquiera de ellos. Si en
la última fila no existiese coeficiente negativo, significa que se
ha alcanzado la solución óptima. La columna de la variable que
entra se llama columna pivote.
B. Para encontrar la variable de holgura que tiene que
salir, se divide cada término de la última columna
(valores solución) por el término correspondiente de la
columna pivote, siempre que estos últimos sean
mayores que cero.
Si hubiese algún elemento menor o igual que cero no
se hace dicho cociente. En el caso de que todos los
elementos fuesen menores o iguales a cero, entonces
tendríamos una solución no acotada y el proceso
termina.
El término de la columna pivote que en la división
anterior dé lugar al menor cociente positivo, es el 3, ya
que 8 es el menor cociente, e indica la fila de la
variable de holgura que sale de la base, S3. Esta fila
se llama fila pivote.
Iteración 1
Variable de Variable de
Solución Operación
decisión holgura
X1 X2 S1 S2 S3
18
S1 2 1 1 0 0 18 =9
2
42
S2 2 3 0 1 0 42 = 21
2
24
S3 3 1 0 0 1 24 =8
3
Z -3 -2 0 0 0 0
C. En la intersección de la fila y columna pivote tenemos el
elemento pivote operacional, que es 3, este indica que
la variable de decisión X1 entra y la variable de holgura
S3 sale.
5. Encontrar los coeficientes para la nueva tabla de simplex.
Los nuevos coeficientes de la fila pivote se obtienen
dividiendo todos los coeficientes de la fila por el pivote
operacional “3”, este se debe convertir en 1.
A continuación mediante operaciones de fila y columnas
hacemos ceros los restantes términos de la columna
pivote, con lo que obtenemos los nuevos coeficientes de
las otras filas incluyendo los de la función objetivo Z.
Resultado de Iteración No. 1
Variable de
Variable de holgura Solución Operación
decisión
X1 X2 S1 S2 S3
1 2
S1 0 1 0 − 2 f(S1) – 2 f(X1)
3 3
7 2
S2 0 0 1 − 26 f(S2) – 2 f(X1)
3 3
1 1 1
X1 1 0 0 − 8 X1
3 3 3
Z 0 -1 0 0 1 24 f(Z) + 3 f(X1)
Como en los elementos de la última fila hay un número negativo,
significa que no hemos llegado a la solución óptima. Hay que repetir el
proceso:
A. La variable que entra es x2, por ser la columna pivote que
corresponde al coeficiente -1
B. Para calcular la variable que sale o la fila pivote, dividimos los
términos de la columna solución entre los términos de la nueva
columna pivote:
Como el menor cociente positivo es 6, tenemos que la fila pivote y
la variable de holgura que sale es S1.
1
C. El elemento pivote, que ahora hay que hacer 1, es 3.
Y se opera de forma análoga a la interación anterior.
Iteración No. 2
Variable de
Variable de holgura Solución Operación
decisión
X1 X2 S1 S2 S3
1 2 2
=6
S1 0 1 0 − 2 1
3 3 3
7 2 26
=
78
S2 0 0 1 − 26 7
7
3 3 3
1 1 8
= 24
X1 1 0 0 − 8 1
3 3 3
Z 0 -1 0 0 1 24
Resultado de Iteración No. 2
Variable de
Variable de holgura Solución Operación
decisión
X1 X2 S1 S2 S3
X2 0 1 3 0 -2 6 3X2
7
S2 0 0 -7 0 4 12 f(S2) – f(X2)
3
1
X1 1 0 -1 0 1 6 f(X1) – f(X2)
3
Z 0 0 3 0 -1 30 f(Z) + f(X2)
Como en los elementos de la última fila hay uno negativo, -1, significa que no
hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
A. La variable que entra S3, por ser la variable que corresponde al
coeficiente -1
B. Para calcular la variable que sale, dividimos los términos de la
última columna entre los términos correspondientes de la nueva
columna pivote:
6 12 6
= −3; =3; =6
−2 4 1
y como el menor cociente positivo es 3, tenemos que la variable de
holgura que sale es S2.
C. El elemento pivote, que ahora hay que hacer 1, es 4.
Iteración No. 3
Variable de
Variable de holgura Solución Operación
decisión
X1 X2 S1 S2 S3
No se toma
X2 0 1 3 0 -2 6 por ser
negativo
12
S2 0 0 -7 0 4 12 =3
4
6
X1 1 0 -1 0 1 6 =6
1
Z 0 0 3 0 -1 30
Resultado de Iteración No. 3
Variable de
Variable de holgura Solución Operación
decisión
X1 X2 S1 S2 S3
1
X2 0 1 − 0 0 12 f(X2) + 2 f(S3)
2
7 1
S3 0 0 − 0 1 3 S3
4 4
3
X1 1 0 − 0 0 3 f(X1) – f(S3)
4
5
Z 0 0 0 0 33 f(Z) + f(S3)
4
Tabla Final
Variable de
Variable de holgura Solución
decisión
X1 X2 S1 S2 S3
1
X2 0 1 − 0 0 12
2
7
S3 0 0 − 0 1 3
4
3
X1 1 0 − 0 0 3
4
5
Z 0 0 0 0 33
4
Como todos los coeficientes de la fila de la
función objetivo son positivos, hemos llegado a
la solución óptima.
Los solución óptima viene dada por el valor
de Z en la columna de los valores solución, en
nuestro caso: 33.
