Método símplex para resolver problemas

 El método símplex fue inventado por George Dantzig en 1947, basándose en el algoritmo de Gauss Jordan que permite obtener soluciones para sistemas de ecuaciones con más de una variable. El método símplex consta de tres etapas: en la primera etapa, se abstrae el problema y se convierte en un sistema de ecuaciones que al resolverse determinarán la solución, para ello, se construye una tabla símplex, la cual se convierte en una matriz donde se debe operar siguiendo las reglas del método; en esta etapa, se llevan a cabo iteraciones en cada fila y columna hasta llegar a una solución óptima (esto sucede cuando se obtiene un uno y ceros en las filas pivote); en la última etapa se verifica si en verdad la solución es la más óptima. Si esta solución no es óptima, se continúa con la iteración hasta encontrar una, si ésta existe. Esto es a grandes rasgos, no obstante, cada una de estas etapas tiene sus particularidades.

George Dantzing recibiendo un galardón de ciencias, como puede verse era muy formal.

Procedimiento

Antes de empezar con el procedimiento formal, es necesario dejar asentadas ciertas reglas que se deben tomar en cuenta. Para empezar, hay que dejar claro cómo deben incorporarse las restricciones en las variables de holgura (Hj, aunque algunos autores también las manejan como S1, S2,…, Sn) y las denominadas variables ficticias (Fj):

Restricción	Coeficiente de la variable de holgura	Coeficiente de la variable ficticia
Menor o igual(<=)	+1	0
Igual (=)	0	+1
Mayor o igual (>=)	-1	+1
Aproximadamente (≈)	+1 y -1	0

También es necesario recordar la siguiente ecuación para obtener el renglón índice:

Donde:

Ei_j=Elemento índice de la columna j

C_ij= Elemento del renglón i y la columna j

Co_i= Elemento de la columna objetivo y el renglón i

Ro_j= Elemento del renglón objetivo y la columna j

Otra cosa que debe recordarse es el método Gauss Jordan para reducir una matriz y encontrar soluciones óptimas a problemas algebraicos, ya sea que tengan infinitas soluciones, una solución o ninguna.

Ahora, ilustremos el método paso a paso con el siguiente problema del libro Investigación de operaciones. Programación lineal I de Raymundo Palacios Figueroa (2015, p. 47):

Una fábrica de muebles cualquiera elabora un sofá de tipo A y otro de tipo B en cuatro departamentos distribuidos de la siguiente manera:

Departamento	Tiempo disponible	Tiempo requerido Sofá A	Tiempo requerido Sofá A
Corte	80	1	2
Armado	20	3/4	1/2
Tapicería	50	1	0
Cubiertas	10	0	1

Se quiere saber cuántos sofás del tipo A y cuántos del tipo B se deben fabricar para maximizar las ganancias. El precio de cada sofá A es de 10 pesos y el del sofá B es de 25 pesos por pieza.

Paso 1

Se expresa el problema en su forma estandarizada, incluyendo las variables de holgura. Como se trata de maximizar las ganancias, éstas son positivas (cuando se quiere minimizar, hay que recordar que el signo cambia a negativo). Quedaría de la siguiente forma:

Maximizar Z = 10X + 25Y + 0H₁ + 0H₂

Sujeto a

3/4X + 1/2Y + H₁ = 20 Departamento de Armado

Y + H₂ =10 Departamento de Cubiertas

Paso 2

La información debe simplificarse por medio de una tabla símplex. Cabe señalar que cada autor tiene su propia interpretación de la tabla símplex y que si bien varían en cuanto a diseño y la manera en que se vacía la información, en esencia es la misma tabla símplex con el mismo tipo de datos.

		X(sofá A)	Y(sofá B)	H1	H2	Cantidad en Horas	Contribución
Cj	Mezcla	$10	$25	$0	$0		Res
0	H1	3/4	1/2	1	0	20	20/1/2=40
0	H2	0	1	0	1	10	10/1=10
	Zj	$0	$0	$0	$0	$0
	Cj-Zj	$10	$25	$0	$0

Ok, en la primera columna están los coeficientes básicos, en donde se encuentra la contribución por unidad para las variables de holgura (H1 y H2). Como no hay producción de sofás al inicio, empiezan en cero.

La columna de las variables básicas (X y Y, que otros autores manejan como X1 o X2, no importa, es lo mismo) contienen las variables de la mezcla de productos que se usan para saber la contribución total. Las holguras H1 y H2 representan todo el tiempo que no se usa de cada departamento.

La matriz del cuerpo representa las horas que se requieren para fabricar cada sofá, mientras que la matriz unidad representa los coeficientes de las variables de holgura que se han añadido a las desigualdades originales para convertirlas en ecuaciones. La última fila es para verificar que se pueda mejorar la fórmula.

Paso 3

Este paso se resume en una palabra: iteraciones. Al igual que un algoritmo de programación, se debe identificar el valor menor (a veces es negativo) y comenzar desde ahí a operar, en la tabla del ejemplo anterior se coloreó con gris la columna y la fila pivote.

Para la primera iteración, primero se analiza la contribución neta por unidad (Cj -Zj) y escogemos el mayor valor numérico que permita a la empresa obtener una mayor contribución por unidad/producto. El número es 25, ya que representa la mayor cantidad por unidad de sofá tipo B. De esta manera, la variable que entra en la base es Y. Esto se conoce como prueba de optamilidad.

Paso 4

Hecho lo anterior, se dividen las 20 horas totales con las que cuenta el departamento de armado entre ½ hora que requiere para armar el sofá tipo B. Por otra parte, se dividen las 10 horas totales con las que cuenta el departamento de cubiertas entre la hora que requiere el mismo para llevar a cabo la cubierta del sofá tipo B.

En este paso, como se mencionó anteriormente, se debe elegir la cantidad positiva más pequeña para encontrar la variable no básica de salida, proceso que se conoce como prueba de factibilidad.

Paso 5

Se calculan todos los nuevos valores numéricos de la matriz del cuerpo, la matriz unidad, la contribución de pérdida por unidad y la contribución neta por unidad (Cj – Zj). Entonces, se actualiza la tabla símplex con los nuevos valores:

		X(sofá A)	Y(sofá B)	H1	H2	Cantidad en Horas
Cj	Mezcla	$10	$25	$0	$0
0	H1	3/4	0	1	-1/2	15
0	H2	0	1	0	1	10
	Zj	$0	$25	$0	$25	$250
	Cj-Zj	$10	$0	$0	$25

Después se llevan a cabo las operaciones correspondientes, en este caso, al primer renglón se le restó el segundo multiplicado por 1/2.

Paso 6

Ahora se repite el procedimiento en la fila del sofá A para reducir 3/4 a 1 y obtener la optimilidad y la factibilidad correspondiente. El mayor valor numérico positivo que le permite a la empresa mejorar la contribución por unidad de producto es 10.

Se dividen las 15 horas entre 3/4 de hora que se requieren para el armado del sofá A. Finalmente, se calculan todos los nuevos valores numéricos correspondientes a la matriz del cuerpo, a la matriz unidad, a la contribución de pérdida por unidad (Z) y la contribución neta por unidad (Cj – Zj). La tabla símplex actualizada quedará como sigue:

		X(sofá A)	Y(sofá B)	H1	H2	Cantidad en Horas
Cj	Mezcla	$10	$25	$0	$0
0	H1	1	0	4/3	-2/3	20
0	H2	0	1	0	1	10
	Zj	$10	$25	-$13 1/3	$18 1/3	$450
	Cj-Zj	$10	$0	$13 1/3	$18 1/3

Como puede apreciarse, las variables de entrada ya han sido reducidas a 1, por lo que la iteración termina. Las operaciones que se llevaron a cabo fueron las siguientes: el primer renglón se multiplicó por 4/3, después se calcularon los datos asociados a la contribución por pérdida de unidad, con base en los datos de la tabla; la contribución neta por unidad se calcula también con base en ésta.

Como todos los valores que representan la contribución neta por unidad, toman el valor de cero negativo, por lo que la maximización está completa de $250 a $450 pesos.

Paso 7

Para concluir, se sacan los datos de la tabla y se interpretan para dar el resultado final:

Referencias

Jagdish C. A. y Lardner R. W. (2002). Matemáticas aplicadas a la administración y la economía. Pearson Educación.

Izar Landeta J. M. (2018). Modelos matemáticos para la toma de decisiones. Instituto Mexicano de Contadores Públicos.

Palacios, Figueroa, R. (2017). Investigación de operaciones I. Programación Lineal, Alfaomega, 127-162.