Simplex: Método de resolución de problemas de programación lineal

Para resolver problemas de programación lineal mucho más complejos, que obviamente, son los más comunes en la realidad, se necesita un algoritmo o método algebráico (ya que es más sencillo representar N cantidad de variables de forma abstracta).

Simplex es uno de estos métodos, que aunque es algebráico tiene raices gráficas (vease el método gráfico). Igualmente vamos a enumerar ciertos conceptos gráficos importantes para entender el método simplex:

1. Las restricciones son lineas rectas: enteder esto es de vital importancia. Las lineas rectas tienen la particularidad de que son predecibles (realmente proporcionales) asi que si hay una relación sencilla entre todos los puntos que conforman la recta.
2. La solución óptima está sobre una de las restricciones: Esto se debe a que los puntos que están sobre las restricciones son los últimos en respetarlas. Más especificamente se puede decir que la solución optima está en la intersección de dos o más restricciones. A estas intersecciones se les llama soluciones factibles en el vértice.
3. Soluciones factibles en el vértice vecinas: son todas aquellas intersecciones unidas por la recta que representa a una restricción.
   

El método simplex es un algoritmo algebráico que reza asi:

Parado en una solución factible en el vertice, voy a buscar soluciones factibles en el vertice vecinas mejores a la actual, recorriendo las restricciones que se intersectan en dicho punto.

NOTA: Aquí se puede leer como el principio del método simplex es completamente gráfico, aunque su implementeación sea algebráica.

Pasos del método SIMPLEX - Versión UNO:

1. Se busca una Solución Factible en el Vértice (SFV) donde comenzar
   
2. Prueba de optimalidad: La SFV actual es óptima si y solo si ninguno de sus vecinos es mejor.
3. Si la SFV actual no es óptima, me muevo al mejor vecino y vuelvo al paso 2.
   
4. Termina el algoritmo.

Aquí tenemos parafraseado el algoritmo algebráico de SIMPLEX. El cuál es un poco más complejo cuando se trata de implementar en computadora.

Pero criticando un poco: para poder correr el algoritmo anterior tenemos que conocer todas las soluciones factibles en el vértice, lo cual implica intersectar todas las restricciones. Esto tiene un costo computacional grande, dependiendo del tamaño del problema, pero al final es un costo. ¿Por qué no aprovechamos un poco el hecho de que las SFV se unen por una recta (restricción)? Basandonos en los conceptos de proporcionalidad de la recta: ¿Por qué no simplemente determinamos cuanto ganamos (o perdemos) al desplazarnos por una de las restrcciones, en vez de tener que determinar la SFV vecina?

Pasos del método SIMPLEX - Versión DOS:

1. Se busca una Solución Factible en el Vértice (SFV) donde comenzar
   
2. Prueba de optimalidad: La SFV actual es óptima si y solo si al desplazarnos por alguna de las restricciones solamente perdemos (desmejoramos el resultado de la función objetivo). Esto es igual a decir que no tiene vecinos mejores.
   
3. Si la SFV actual no es óptima, me muevo por la restricción que me de más ganancia, y determino la SFV vecina adyacente a esa recta.
   
4. Termina el algoritmo.

Lo más importante de resaltar en esta "versión" es que ya no necesitamos saber todas las SFV, sino solamente la actual, y la SFV vecina que esta al otro extremo de la restricción que le de más ganancias a la función objetivo.

En este momento, mi recomendación es ejecutar el algoritmo de SIMPLEX parados en el gráfico de un problema. Si se entiende de este modo, es una garantía el entendimiento de la forma tabular del SIMPLEX (que en definitiva es el que usualmente se implementa en computadoras - aunque esto es una mentirita blanca porque el que se implementa en computadora es el SIMPLEX Revisado)

Precondiciones para la aplicación de SIMPLEX

Ahora, para poder aplicar SIMPLEX, el método debe estar expresado de una forma particular, que enumeramos aquí:

1. La optimización de la función objetivo debe ser para máximizar (MAX Z). Esto hace que la forma de recorrer las SFV siempre sea para aumentar el valor de Z.
   
2. Las restricciones deben estar expresadas en forma de igualdad ( = ). Para poder recorrer las restricciones se deben tener rectas, no inecuaciones.
   
3. El punto inicial debe ser el origen. Eso hace que la SFV inicial sea facil de estimar o detectar, y asi poder comenzar el algoritmo sin cálculos complejos que determinen el punto inicial de búsqueda.

Para poder expresar un problema de PL en esta forma, tenemos que saber transformar los problemas de programación lineal para conseguir una representación equivalente que siga apegado al problema original pero que respete las pre-condiciones de SIMPLEX.

Trasnformando el problema original

1. Transformando un problema de Minimizar en Maximizar. Matemáticamente hablando: Min Z = Max -Z. Esto significa que si multiplicamos ambos lados de la igualdad de la función objetivo cambiamos el sentido de la optimización.
2. Tranformando las restricciones de tipo <= en = . Esto se hace sumando una variable de holgura a la restricción.
3. Trasnformando las restricciones de tipo >= en = . Esto se hace restando una variable de superávit.
4. Haciendo el origen una SFV inicial. Esto ocurre "siempre" cuando las restricciones se expresan de forma de igualdad (=) o desigualdad de mayor e igual que (>=) ya que al hacer las variables de desición cero, las igualdades no se cumplen. Esto se arregla sumando variables artificiales al problema. Esto también es conocido como "aumentando el problema".

NOTA: es importante destacar que cuando se transforma una restricción del tipo (>=) a( =) o ya tenemos simplemente una restricción de igualdad (=), siempre hay que resolver el problema del punto 4 (agregar variables artificiales).

Ejemplo:
Si tenemos un problema original expresado de la forma

Min Z = 4 X1 + 5 X2

Sujeto a:
3 X1 + X2 <= 27
5 X1 + 5 X2 = 6
6 X1 + 4 X2 >= 6

X1 >=0; X2 >=0

Quedaria como:

Max -Z = - 4 X1 - 5 X2 - M X4 - M X6

Sujeto a:
3 X1 + X2 + X3 = 27
5 X1 + 5 X2 + X4 = 6
6 X1 + 4 X2 - X5 + X6 = 6

X1 >=0; X2 >=0 ;X3 >=0; X4 >=0; X5 >=0; X6 >=0

Las variables resaltadas con verde son "variables de holgura", las azules son "variables de superavit" mientras que las rojas son "variables artificiales". Notese que a diferencia de las variables de holgura y superavit, las variables artificiales si afectan a la función objetivo, y se multiplican por una M.

Las variables de holgura y superavit no son mas que un artificio matemático para representar la inecuación, pero al final estas variables son representan una ecuación matemática que depende directamente de las variables de decisión. Mientras que las variables artificiales son elementos que agregamos para que el origen fuera factible, asi que esto si impacta a la función objetivo. Ahora ... ¿como lo impacta? La idea es que el problema original quede intacto por lo cual, convenientemente, tenemos que hacer que en la solución final estas variables artificiales tengan valores iguales a cero, y esto se logra penanlizandolas en la función objetivo (esto se ve a más detalle en el método de la gran M y el método de las dos fases).

SIMPLEX en forma tabular

Obviamente, de lo anterior se pueden derivar varios algoritmos, pero evidentemente esto ya fue realizado, y bastante, hasta que se llegó a una forma tabular del problema (que tampoco es la última versión de este algoritmo).

Para expresar un problema de programación lineal para ser resuelto con SIMPLEX en su forma tabular debemos igualar la función objetivo a cero y armar una tabla como se ve en la primera imágen.

La forma tabular de simplex introduce dos definiciones importantes (en este artículo, más por referencia que conceptualmente):

1. Variables básicas: Son las variables a las cuales el algoritmo le tiene asignado un valor.
2. Variables no básicas: Son las variables que el algoritmo no les asigna ningún valor, pero su valor por defecto es cero (0)
   

NOTA: Esta definición es a fines de explicar el algoritmo, no esta comprendida de conceptos de ningún tipo.

Esta definición nos permitirá separar las variables que son candidatas a entrar (variables no básicas) y cuales son candidatas a salir (variables básicas) en el método.

Pasos para el SIMPLEX en su forma tabular:

1. Prueba de optimalidad: Si en el renglón (0) hay algún valor negativo, tenemos que iterar.
2. Tomamos el valor más negativo del renglón (0) y la columna a la cual pertenece la marcamos como variblen que entra. Esto es lo mismo que decir "variable no básica a ser transformada en variable básica". A esta columna se le llama columna pivote.
   
3. Estudio del conciente mínimo: Estudiamos de la columna pivote a las filas que tengan valores extrictamente positivos. Dividimos su correspondiente en B de la misma fila entre el número de la columna pivote. La fila que genere el cociente mínimo, se considera la variable que sale (También llamada fila pivote)
4. Dividimos la fila pivote entre el número pivote (intersección entre la fila y columna pivote) y generamos la fila para la proxima iteración.
5. A través de eliminación gaussiana, hacemos que todos los elementos de la nueva columna se hagan cero.
6. Volvemos al paso 1.

Resolver problemas de Programacion Lineal gráficamente

Los problemas de la vida real planteados en forma matemática con ecuaciones lineales puede ser resuleto de varias formas, pero una de las mas intuitivas es a través de rectas en un sistema cartesiano. El hecho de que todas las ecuaciones representen una linea recta nos hace ver que el método gráfico es un acercamiento sencillo a la busqueda de soluciones de este tipo, y como veremos mas adelante, es la base de otros métodos mucho mas eficientes y menos limitados.

El Método Gráfico

Tomando en cuenta el problema prototipo, imagínese que dibujamos un plano cartesiano de dos dimensiones donde el eje de las abcisas representa la variable de decisión X1 (lotes de producto uno) y el eje de las ordenadas representa la variable de decision X2 (lotes de producto dos). Con esto tenemos un plano donde un punto representa una combinación de lotes de producto uno y dos. Asi con lo hecho hasta ahora, podemos dibujar un punto en cualquier lado del plano ya que cualquier punto es válido, ya que no hay restricciones.

Pero el problema prototipo si tiene restricciones, y lo bueno (y obligatorio) es que son inecuaciones lineales cuya representación gráfica es una recta limítrofe de la cual el punto no puede pasar. Ahora con esta nueva consideración tenemos que no todos los puntos del plano son válidos, sino son considerados soluciones factibles solo aquellos que respeten las fronteras impuestas por las restricciones. Veamos como quedarian expresadas de forma grafica las restricciones del problema prototipo (Ver gráfico).

Como lo ven, la intersección de las restricciones y el área que limitan han formado una región totalmente limitada, donde se encuentran todos los puntos (combinaciones de productos uno y dos) que respetan todas las restricciones, lo que se conoce como soluciones factibles. Al conjunto de soluciones factibles, que forman un área en el plano cartesiano (amarilla) se le conoce como región factible. Es dentro de esta region factible donde se encuentra la solución optima a nuestro problema (la combinación de lotes de productos uno y dos que no violen las restricciones de capacidad productiva de las tres plantas). Pero intuitivamente ¿dónde puede estar la solución óptima?

Razonando un poco, se puede notar que los puntos óptimos son los mas extremos, lo que están mas cercas de romper las reglas, los que están al borde de violar las restricciones: Si lo vemos en el caso de la fabrica de vidrios, es obvio pensar que la combinación de lotes óptimo estará utilizando al máximo la capacidad de las fábricas ¿cierto? No tiene mucho sentido que lleguemos a una conclusión donde se desperdicie capacidad productiva.

Aunque aqui parafraseamos una conclusión, esto esta demostrado: Las soluciones óptimas a un problema de programacion lineal se encuentra SOBRE alguna de las rectas que representan a las restricciones.

Entonces, ahora lo que se necesita saber es CÓMO se comporta la función objetivo a los cambios de X1 y X2. Para esto tenemos que dibujar una recta que represente a la función objetivo dandole un valor arbitrario a Z. En el gráfico, se puede ver dibujada la recta de la función objetivo para Z = 10. Luego, siempre paralelo a la recta que acabamos de dibujar, nos alejamos de la función objetivo hasta toparnos con el punto más extremo de la región factible. Con este método, encontramos el punto (2,6) que da como resultado un Z = 36.

¿Qué significa lo que acabamos de hacer?

La función objetivo es una linea recta que a medida que cambian los valores de sus variables (X1 y X2) se desplaza en el mapa, manteniendo siempre la misma pendiente (rectas paralelas). Esta condición hace que se respete las relaciones establecidas en la función objetivo. Para el ejemplo prototipo, la función objetivo representa las reglas en las cuales se combinan los productos 1 y 2 para generar ganancias.

Ahora, si tomamos cualquier punto sobre la recta que representa a la función objetivo vamos a conseguir una combinacion de X1 y X2 válida, pero que quizá no respete las restricciones, o quizá las respete demasiado. Es aqui donde tenemos que conseguir el punto de la región factible más alejado del origen (porque estamos maximizando) que se cruze con una paralela de la función objetivo.

Mezclando estos dos conceptos obtendremos la combinacion de X1 y X2 (productos) que combinados producen una ganancia como lo indica la función objetivo y además respeta las restricciones.

Conclusión

Este es un método sencillo de resolución de problemas de programacion lineal (PL), pero también es el más limitado. La limitación más importante es la cantidad de variables de decisión: ya que no se puede representar gráficamente ningún elemento que tenga más de tres dimenciones, los problemas de programacion lineal con cuatro (4) o más variables de decisión no se pueden resolver ccon este metodo.