20/03/2021
Método Simplex
Algoritmo símplex
Un algoritmo es una secuencia que se caracteriza por tener pasos lógicos que
siempre se realizan en el mismo orden. Por esto es necesario que para aplicar el
algoritmo símplex, siempre se realice en el orden indicado.
Partiendo de un modelo de programación lineal en su forma estándar se realizan
los siguientes pasos:
1
20/03/2021
Paso 1.
Convertir las desigualdades en igualdades al sumarles una variable de holgura hi .
Esta variable representa la cantidad que le falta a la desigualdad para ser igualdad.
Las variables de holgura siempre son positivas. No se incluye la CNN
Paso 2
Escribir la función objetivo como una igualdad a cero sumando las variables de holgura i h con
coeficiente cero y conservando positivo el coeficiente de Zmax , es decir:
2
20/03/2021
Paso 3
Formar la tabla símplex o tabla inicial.
Se construye una tabla como la que se muestra a continuación:
En la primera celda escribimos la etiqueta “Variables básicas”, en la siguiente la etiqueta
“Z”, después de esta celda se escriben los nombres de las variables originales del modelo, seguidas
de las variables de holgura.
En la última celda se coloca la etiqueta “Solución”.
El segundo renglón contiene los coeficientes, correspondientes a cada variable original, de
la función objetivo escrita como se obtuvo en el Paso 2 y con el coeficiente cero para todas las
variables de holgura y la “Solución”.
3
20/03/2021
En la primera columna y a partir del tercer renglón se enlistan verticalmente todas las
variables de holgura empleadas. También a partir del tercer renglón y después de la primera
celda del mismo, se colocan los coeficientes de cada una de las restricciones en la
columna de la variable correspondiente (esto genera los componentes de una matriz identidad
en las variables de holgura).
En la columna solución se colocan los términos independientes y además identificamos un
elemento pivote en la celda en la que se intersectan el renglón de h1 con la columna de h1 . Se
asocia el valor de la columna solución con la variable del mismo renglón de la columna de
variables básicas, esto es h1 = b1 .
4
20/03/2021
De manera similar para todas las variables y para Z:
Z=0
H1= b1
H2=b2
……
Hm=bm
Ésta es la primera solución. Con la tabla inicial símplex asociada al modelo de PL se continúa
para encontrar la solución óptima (si es que existe) o bien se determina que el problema no
tiene solución óptima.
Paso 4. Verificamos si todos los coeficientes asociados al renglón de Z son mayores o
iguales a cero. Si es así, entonces la solución en la tabla es la óptima y el proceso termina. Si no es
así, se continúa.
Paso 5. De los coeficientes del renglón Z se toma el que tenga el mayor valor negativo (número
menor) y se selecciona toda la columna. La variable de esta columna es la que entra al sistema (pasa
a ser básica).
Paso 6. Se divide el término de la columna “Solución” entre el elemento correspondiente de la
columna seleccionada en el punto anterior, y de los resultados de la división se selecciona el menor
valor positivo y todo el renglón asociado a este valor. Ésta es la variable que sale de la base (pasa a
ser no básica). Nota: Las divisiones entre cero o entre números negativos no se toman en cuenta. Si
todas son negativas o indeterminadas el problema no tiene solución y el proceso termina.
5
20/03/2021
Paso 7. La celda que se encuentra en la intersección de la columna con el renglón seleccionado
contiene un elemento al que, por medio de operaciones elementales entre renglones, se
convierte en elemento pivote y los demás elementos de su columna, en ceros; con esto se
obtiene una nueva columna de la matriz identidad.
Paso 8. Se repite el proceso desde el Paso 4 operando sobre matrices hasta obtener todos los
coeficientes del renglón Z, con valores mayores o iguales a cero.
En el siguiente ejemplo se presenta la aplicación del algoritmo del método símplex.
Resolver el siguiente modelo de programación
lineal utilizando el método símplex
6
20/03/2021
Paso 1. Convertir las desigualdades en igualdades al sumarles una variable de holgura i h . Esta
variable representa la cantidad que le falta a la desigualdad para ser igualdad. Las variables de
holgura siempre son positivas.
Paso 2. Escribir la función objetivo como una igualdad a cero sumando las variables de holgura i
h con coeficiente cero y conservando positivo el coeficiente de Zmax , es decir:
7
20/03/2021
Paso 3. Formar la tabla símplex o tabla inicial.
Se construye una tabla como la que se muestra a continuación para este caso:
En la primera celda escribimos la etiqueta “Variables básicas”, en la siguiente la
etiqueta “Z”, después de esta celda se escriben los nombres de las variables originales del
modelo, seguidas de las variables de holgura. En la última celda se coloca la etiqueta
“Solución”. Además, identificamos los renglones de la tabla para realizar operaciones entre
ellos con mayor facilidad.
El segundo renglón contiene los coeficientes, correspondientes a cada variable original,
de la función objetivo escrita como se obtuvo en el Paso 2 y con el coeficiente cero para todas
las variables de holgura y la “Solución”
8
20/03/2021
En la primera columna y a partir del tercer renglón se enlistan verticalmente todas las
variables de holgura empleadas. También a partir del tercer renglón y después de la primera
celda del mismo, se colocan los coeficientes de cada una de las restricciones en la
columna de la variable correspondiente (esto genera los componentes de una matriz identidad
en las variables de holgura).
Identificamos un elemento pivote en la celda en la que se intersectan el renglón de h1 con la
columna de h1 . Se asocia el valor de la columna “Solución” con la variable del mismo renglón de
la columna de variables básicas, esto es h1 = 36 .
De manera similar para todas las variables y para Z:
Ésta es la primera solución.
9
20/03/2021
Con la tabla inicial símplex asociada al modelo de PL se continúa para encontrar la solución óptima
(si es que existe) o bien determinar que el problema no tiene solución óptima.
Paso 4. Verificamos si todos los coeficientes asociados al renglón de Z son mayores o
iguales a cero, si es así, entonces la solución en la tabla es la óptima y el proceso termina. Si no es
así, se continúa.
En este caso existen dos coe cientes negativos asociados al renglón de Z, por lo que se
debe continuar con el proceso.
Paso 5. De los coeficientes del renglón Z se toma el que tenga el mayor valor negativo
(número menor) y se selecciona toda la columna. La variable de esta columna es la que entra al
sistema (pasa a ser básica).
Seleccionamos 2 x como la variable que entra.
10
20/03/2021
Paso 6. Se divide el coeficiente de la columna “Solución” entre el elemento
correspondiente de la columna seleccionada en el punto anterior, y de los resultados de la división
se selecciona el menor valor positivo y todo el renglón asociado a este valor. Ésta es la variable que
sale de la base (pasa a ser no básica). Nota: Las divisiones entre cero o entre números negativos no
se toman en cuenta. Si todas son negativas o indeterminadas, el problema no tiene solución y el
proceso termina.
De la tabla se selecciona el renglón de la restricción tres.
Paso 7. La celda que se encuentra en la intersección de la columna con el renglón seleccionado
contiene un elemento al que, por medio de operaciones elementales entre renglones, se
convierte en elemento pivote y los demás elementos de su columna, en ceros; con esto se
obtiene una nueva columna de la matriz identidad.
11
20/03/2021
La celda con doble marco contiene al que deberá servir como elemento pivote para este
ejemplo y como se tiene un 1 en la celda no es necesario convertirlo. Entonces, la nueva tabla
símplex para el renglón del elemento pivote se escribe como:
Nota que la variable que entra se escribe en el lugar de la variable que sale, x2 en el lugar de h3 ,
para esta tabla, y que lo que se busca es formar una columna con un 1 en el lugar de las
intersecciones, esto es, obtener un elemento pivote y ceros en los demás sitios de la misma
columna. En la parte derecha, fuera de la tabla, se indica la operación que se realizó para
obtener como resultado el nuevo renglón.
Continuamos con el renglón R0 o de la función objetivo:
12
20/03/2021
Para el renglón R1 se tiene la tabla:
Donde se realizó la operación:
13
20/03/2021
Paso 8. Se repite el proceso desde el Paso 4 operando sobre matrices hasta obtener todos los
coeficientes del renglón Z, con valores mayores o iguales a cero. Regresemos al Paso
4. En este caso existe un coeficiente negativo asociado al renglón de Z, por lo que
debe continuar el proceso.
14
20/03/2021
Paso 5. De los coeficientes del renglón Z se toma el que tenga el mayor valor negativo
(número menor) y se selecciona toda la columna. La variable de esta columna es la que entra al
sistema (pasa a ser básica).
Seleccionamos X1 como la variable que entra
Paso 6. Se divide el coeficiente de la columna “Solución” entre el elemento
correspondiente de la columna seleccionada en el punto anterior, y de los resultados de la
división se selecciona el menor valor positivo y todo el renglón asociado a este valor. Ésta es la
variable que sale de la base (pasa a ser no básica). Nota: Las divisiones entre cero o entre
números negativos no se toman en cuenta. Si todas son negativas o indeterminadas, el
problema no tiene solución y el proceso termina.
De la tabla se selecciona el renglón de la restricción uno.
15
20/03/2021
Paso 7. La celda que se encuentra en la intersección de la columna con el renglón seleccionado
contiene un elemento al que, por medio de operaciones elementales entre renglones, se
convierte en elemento pivote y los demás elementos de su columna, en ceros; con esto se
obtiene una nueva columna de la matriz identidad.
La celda con doble marco contiene al elemento que deberá servir como pivote y como se tiene
un 6 en la celda es necesario convertirlo en 1. Entonces, la nueva tabla símplex para el renglón
del elemento pivote se escribe como:
16
20/03/2021
Nota que la variable que entra se escribe en el lugar de la variable que sale, x1 en el lugar de h1 ,
para esta tabla, y que lo que se busca es formar una columna con un 1 en el lugar de las
intersecciones, esto es, obtener un elemento pivote y ceros en los demás sitios de la misma
columna. En la parte derecha, fuera de la tabla, se indica la operación que se realizó para
obtener como resultado el nuevo renglón.
Continuamos con el renglón R0 o de la función objetivo:
17
20/03/2021
Donde no se realizaron operaciones, ya que en la posición correspondiente se tiene un cero,
entonces sólo se reescribe el renglón en la nueva tabla, como se indica en la parte derecha de la
misma.
Paso 8. Se repite el proceso desde el Paso 4 operando sobre matrices hasta obtener todos los
coeficientes del renglón Z con valores mayores o iguales a cero. Como en esta última
tabla, todos los coeficientes de renglón R0 o Z son no negativos, es decir, mayores o
iguales a cero, se ha concluido el proceso.
La última operación por realizar es transferir los valores de la solución de la tabla a las variables
básicas.
18
20/03/2021
Ejercicio:
19
