Método Simplex de programación lineal

Que tanto tiempo me tomo aprender simplex

Aprender la estrategia de simplex fue algo difícil al inicio debido a que tendía a confundirme durante la explicaciones en clases, sin embargo luego de un par de vídeos en YouTube y practicar un par de ejercicios por una semana (antes del examen) logre entender un par de cosas sobre esta estrategia y entendí que no era tan difícil una vez entiendes los pasos a realizar.

Mi entendimiento de porque debemos usar simplex

Primero que nada, el motivo por el que lo utilizamos es cuando en nuestro problema de programación lineal (PPL) existen mas de una variable de decisión, normalmente utilizamos el método gráfico para representar una gráfica de dos dimensiones ya que en nuestro problema presentamos solamente dos variables de decisión .

Sin embargo para este caso, existe mas de dos variables de decisión, por lo que no podríamos representarlo visualmente a menos que hiciéramos una gráfica de tres dimensiones, lo cual tomaría mas tiempo del necesario. También si existen casos en las que haya tres o cuatro o mas variables de decisión, seria imposible para nosotros representarlo gráficamente.

Por eso existe el método simplex, para representar de forma algebraica, problemas de programación lineal que tengan mas de dos variables de decisión.

Cual es la estrategia que entendí

Los primeros pasos para obtener las variables de decisión, función objetivo y restricciones siguen siendo necesarios, luego de eso debemos de implementar unos métodos nuevos.

1. Determinar las variables de decisión 
2. Determinar función objetivo
3. Determinar las restricciones del enunciado y la de signos
4. Convertir el sistema de ecuaciones (que son tanto las restricciones) a forma estándar.
5. Realizar tabloide simplex.
6. Transformar elementos del tabloide simplex realizando una serie de pasos, hasta cumplir una cierta condición.

Los primeros tres pasos ya deberían saberlos ya que los explicamos en el método gráfico, lo que vamos a destacar es como pasar las restricciones a forma estándar, luego con los valores de nuestro sistema de ecuaciones haremos una tabla, e iremos editando por medio de ciertas normas los valores de la tabla, esto se hará hasta cumplir una cierta condición, la información esta ambigua?, si, ya lo explicare a mas detalle.

La forma estándar

Para que el tabloide indique los resultados de forma correcta, debemos pasar los datos del sistema de ecuaciones en forma estándar, que es convertir las ecuaciones de desigualdad en ecuaciones de igualdad (eliminar el mayor igual o menor igual y convertirlos en solo igualdad). 

Debemos integrar dos elementos nuevos los cuales son las variables de holgura y de excedencia a las restricciones, dependiendo del caso de desigualdad, agregaremos una variable de estos tipos.

La variable de holgura se agrega en restricciones de tipo menor igual que (<=) y  se representa con si, donde i establece el numero de la restricción. Esta variable representa la cantidad restantes en la restricción.

Por ejemplo, para una restricción en la que la suma de tiempo para poder preparar unas manzanas y peras no deben ser mayor a 50 horas, y la cantidad de tiempo dedicada a manzanas y peras es 20 horas cada una, la variable de holgura representaría las 10 horas que restantes para ser iguales al segundo miembro (50 horas). Se representa por adición al primer miembro.

20x1 + 20x2 <= 50 (Restricción de desigualdad)

||

20x1 + 20x2 + s1 = 50 (Restricción pasada a forma estándar)

La variable de excedencia se agrega en restricciones de tipo mayor igual que (>=) y  se representa con ei, donde i establece el numero de la restricción. Esta variable representa la cantidad sobrante en la restricción.

Por ejemplo, para la misma restricción en la que la suma de tiempo para poder preparar unas manzanas y peras pero decimos que deben ser mayor o igual a 50 horas, y la cantidad de tiempo dedicada a manzanas y peras es 30 horas cada una, la variable de holgura representaría las 10 horas que sobran para ser iguales al segundo miembro (50 horas). Se representa por sustracción al primer miembro.

30x1 + 30x2 >= 50 (Restricción de desigualdad)

||

30x1 + 30x2 - e1 = 50 (Restricción pasada a forma estándar)

Dependiendo del caso de desigualdad, agregaremos una variable de holgura o excedencia. En resumen

1. Si la restricción i es >=, se resta una variable de excedencia ei al primer termino y se establece la igualdad.
2. Si la restricción i es <=. se suma una variable de holgura si al primer termino y se establece la igualdad.
3. Si la restricción ya esta en igualdad =, se deja como esta.

El tabloide simplex

El objetivo de esta tabla es determinar de forma directa la mejor solución optima por medio del sistema de ecuaciones en forma estándar. Esto se realiza con los siguientes pasos.

Primero debemos igualar a cero la ecuación en Z, es decir la función objetivo, es sencillo, simplemente despejamos todos los elementos de la función objetivo al lado de z, e igualamos a cero.

max z 3x1 + 2x2

||

z - 3x1 + 2x2 = 0

Lo que sigue es crear una tabla que tenga como se muestra a continuación:

Donde renglón es la fila del sistema de ecuaciones, que va empezando desde cero, el renglón cero representará la función objetivo que despejamos anteriormente (z).

Z Representa la fila que posee el termino de z, se representa con 1 si z exista en i fila o 0 en caso contrario.

x1, x2, x3 representan los coeficientes de las variables de decisión en la fila i.

S1, S2, S3 representan las variables de holgura presentes en el sistema de ecuaciones, cabe destacar que en este caso solo hay variables de holgura pero puede haber casos en los que existan variables de excedencia.

Lado derecho representa el valor derecho de la igualdad, una cosa a destacar es que ese valor representa el elemento de la fila que posee un valor uno (sea en las variables de decisión o las variables de holgura), y se representa haciendo una igualdad, por ejemplo si en la fila 1 hay un valor 1 en S1 y el lado derecho de mi igualdad vale 50, lo represento en la columna Lado derecho de la siguiente forma:

S1 = 50

Cociente se usa como referencia, lo veremos mas adelante.

Antes que nada, no te asustes con la tabla, huele el miedo... una ves que entiendas la metodología lo veras como si fuera una suma de enteros.

El procedimiento

Debes llenar el tabloide con la función objetivo que se igualo a cero y las restricciones en forma estándar. La siguiente imagen provee un sistema de ecuaciones y un tabloide simplex con los valores del sistema.

El objetivo del tabloide, es el de eliminar todos los elementos negativos del renglón cero (o renglón z) cuando es de maximización, y cuando es un caso de minimización, eliminar todos los elementos positivos, quedando solo negativos.

Para ello, es necesario un valor pivote, seleccionaremos el valor negativo con el valor absoluto mas alto, esa sera nuestra columna pivote, seguidamente dividiremos cada valor del lado derecho por el valor respectivo de la columna pivote, y tomaremos el valor pivote de la fila con el resultado mas pequeño.

Ahora que ya tenemos nuestro pivote, debemos de igualar ese valor a uno, eso se hace diviendo todo el renglon por el valor pivote, es decir, si el pivote en el renglón es 5, debo dividir todos los elementos del renglon por 5.

Lo siguiente es igualar los demas elementos de la columna pivote en cero, esto se hace multiplicando el renglon pivote por un valor que sumado en el valor de la columna sea igual a cero. Ejemplo, en mi columna tengo los valores 5 1 y 7, ya habiendo conseguido el pivote y despues de haberlo dividido. Lo que debo hacer es multiplicar el renglón pivote por -7 y sumarselo al renglon que posee el valor 7, asi igualo a cero el 7.

Luego de haber realizado la operacion con todos los renglones, se considera una iteracion, lo que sigue es buscar un nuevo pivote, realizando el mismo procedimiento anteriormente, y luego realizando las operaciones entre renglones para igualar a ceros y uno.

Esto lo hacemos hasta que no haya valores negativos en maximizacion o  valores positivos en minimizacion.

Casos especiales

Como pueden notar, el metodo es muy intuitivo, pero tenemos que observar ciertos casos.

1. En caso de haber restricciones de >=, tendriamos que multiplicar la desigualdad por -1 para asi convertirla en <=, y luego aplicar la forma estandar que conocemos.
2. En caso de haber un =, debemos de aplicar otra metodologia, sea el metodo de la gran M, o dual o dos fases.

Últimos detalles

Lo mas importante es aprender a visualizar el tabloide, ya que existen algunos valores que se pueden escribir sin calcular, como la columna z, la columna del renglon, y cuando obtengamos el pivote, ya sabemos que debemos colocar el valor pivote como 1 y el resto de la columna como cero. Confuso si, pero se puede dominar.