Método Simplex

 

 

El Método Simplex me parece sencillamente... asombroso! Sé que cuando se está en pregrado los detalles de cálculo y las cantidades de tablas y tablas pueden parecer un tedio impresionante...

...pero es muy diferente cuando se mira desde el impacto que este método matemático ha hecho en la economía mundial.  Muchas veces siendo bastante joven, me quejaba de que a pesar que las matemáticas me fascinaban, no encontraba un uso real de ellas en la vida real. Pues, este método, es uno de los miles de ejemplos, dónde podemos decir, con palabras sencillas, que las matemáticas han cambiado el mundo. No podemos cálcular el bienestar que ha traido a la tierra este muy sencillo pero genial algoritmo. Cuánto tiempo ahorrado! Cuanta materia prima que se dejó de desperdiciar! Cuanto dinero ha generado! Cuando se es un estudiante aveces, en medio de los incontables y tediosos cálculos aritméticos olvidamos lo genial que representa el poder encontrar entre las miles de millones de combinaciones posibles de resolver un problema, cuál es la mejor! Bueno, para eso tenemos la Optimización, y como punta de lanza de ella: la programación matemática!

 

Un Programa  Matemático normalmente tiene el siguiente formato:

 

Maximizar (o Minimizar)  Z  =  f(X1, X2, X3, X..,Xn)

    Sujeto a:

           R1(X1, X2, X3, ...,Xn) <=  B1

           R2(X1, X2, X3, ...,Xn) <=  B2

                             ...

           Rn(X1, X2, X3, ...,Xn) <=  Bn

 

Hay varios métodos para resolver Problemas de Programación Lineal: Simplex (Primal, Dual, Gran M, Dos Fases), Empujar y Halar y el del Punto Interior de Karmakar

 

Simplex Primal:

 

El método Simplex se basa en una premisa supremamente lógica: la solución tiene que encontrarse en un punto extremo del área de soluciones factibles. Claro! Recuerda el método gráfico? Cada restricción que matemáticamente la representabamos como una inecuación  de desiguadad (<=, >=) se representaba graficamante como un área. Cada área estaba delimitada por los ejes y claro, por una recta extrema que resultaba de tomar la desigualdad como una igualdad.  En la gráfica arriba se puede ver una recta extrema por ejemplo la formada por el extremo CD, y el área de soluciones factibles en ABCD.  La solución, ha de estar en alguno de los puntos extremos de ABCD, y nunca DENTRO, pues si estuviera adentro, ya fuera moviendose a la derecha, a izquierda, arriba o abajo, se tendría alguna mejora factible...

... Y si la solución se encuentra en un punto extremo, el problema se reduce a encontrar dichas soluciones extremas y encontrar la forma de iterar de una solución extrema a una mejor, hasta encontrar la óptima... y es eso lo que hace el método Simplex Primal. 

 

De una manera similar a que en el método gráfico la igualdad asociada a cada inecuación representa un extremo del área de soluciones factibles, el método simplex requiere trabajar no con inecuaciones o desigualdades si no con igualdades... para que? para ignorar, si se puede decir así, todas aquellas soluciones en el volumen interno e irse desplazando por los puntos realmente extremos. Cuando convertimos estas inecuaciones en ecuaciones para preparlas para el método, decimos que lo convertimos en El Modelo Estándar; en este modelo, por ejemplo,  en vez de expresar una restricción de la siguiente manera: 

 

Material Usado en el Producto A + Material Usado en el Producto B <=  Material Disponible    decimos:

 

Material Usado en  A + Material Usado en B + Material no usado = Material Disponible.

 

Vemos como para llevar del formato inicial al Modelo Estándar es necesario usar variables adicionales. Estas variables son llamadas Variables de Holgura, y son las que contendran los valores que no sean usados por las restricciones. El método requiere otro tipo de variables, usadas cuando hay restricciones de tipo >= e =, y son llamadas Variables Artificiales. Estas variable no tienen ningun significado físico, si no que son un artificio matemático requerido por el método para estos dos tipos de restricciones.

 

Cuando tengamos restricciones de tipo >= o =, y por lo tanto aparezcan variables artificiales,  será necesario usar una variante del Simplex llamado: Método de la Gran M.  En este tipo de situación también se puede usar el Método de las DOS FASES y más modernamente el Método Empujar y Halar.

 

Cuando ya tenemos el programa lineal en formato de modelo estándar es posible usar el algebra de matrices para encontrar los puntos extremos que hablabamos anteriormente. Tal vez recuerde de sus clases de algebra lineal que para que un sistema de ecuaciones tenga solución única es necesario que el número de variables y el número de ecuaciones fuera igual; pero en nuestro caso, al llevar al formato de modelo estándar añadimos variables tanto de holgura como artificiales haciendo que el número de variables sea mayor que el número de restricciones, por lo que tendremos que para hallar una solución (un punto extremo)  hacer cierto número de estas variables iguales a cero. Para este efecto definimos dos grupos en cada iteración (mencioné que el método simplex es de caracter iterativo?) uno llamado Variables Básicas y otro llamado No básicas. Las variables no básicas son las que le damos valor de cero y las variables básicas son las que usaremos con valor dentro de las iteraciones.

 

En cada iteración se define la base y usando el método de Gauss-Jordan se encuentra el valor del punto extremo. Para mejorar la solución encontrada es necesario desplazarse a otro punto modificando la base: Sacando una variable de ella y metiendo otra. Por lógica vamos a escoger para la variable que entra aquella que mejore en mayor proporción a la función objetivo y para salir escogermos aquella variable que más restrinja el modelo.  A la intersección entre la columna de la variable que entra y la de la fila de la variable que sale, lo llamamos pivote. Debemos convertir por operaciones entre filas y columnas a este pivote en 1 y basandonos en este pivote se aplica gauss-jordan para convertir en cero los demás miembros de la columna.  En cada iteración se hace una verificación de optimalidad, se pregunta si hemos llegado al óptimo: Si ya ninguna variable que entre va a majorar más el resultado, si es así hemos terminado, de lo contrario, hacemos una nueva iteración. En esta verificación también se examina la factibilidad del problema, tal vez se encuentre con que el problema no está acotado, o que tenga infinito número de soluciones

 

Ejemplo

 

Resolver:

 

Max Z = 18.5X1 + 20 X

        Sujeto a:

0.05X1 + 0.05X2 <= 1100

0.05X1 + 0.1X2  <= 1800

0.1 X1 + 0.05 X2 <= 2000

 C.N.N.(Condición de No Negatividad)

 

1. Convertir al Modelo  Estándar:

 

Cada restricción debe ser convertida de inecuación a una igualdad, agregando variables como se requiera. Con las restricciones de tipo <=, es supremamente fácil. Simplemente se agrega una en cada restricción con coeficiente 1 en la misma restricción y con coeficiente cero en la función objetivo. Por ejemplo:

 

0.05X1 + 0.05 X2 <= 1100  queda:

0.05X1 + 0.05 X2 + S1 = 1100

 

La primera restricción se puede leer como que 0.05 por las unidades de X1 más 0.05 por las unidades de X2, no puede exceder a 1100, pero lo mismo da decir que 0.05 por las unidades de X1 más 0.05 por las unidades de X2, más lo que sobre guardado en S1 sea totalmente igual a 1100.  De esta forma se agregan tres variables, una por cada restricción y queda como se ve abajo. Para el caso de restricciones del tipo mayor o igual, se verá en el ejemplo de minimización

 

Max Z = 18.5X1 + 20 X2 + 0S1 + 0S2 + 0S3

        Sujeto a:

0.05X1 + 0.05X2  +  S1                               = 1100

0.05X1 + 0.1X2                  +  S                 =  1800

0.1 X1 + 0.05 X2                              + S3     = 2000

 C.N.N.(Condición de No Negatividad)

 

2. Escribir en formato de Tabla Simplex

 

Si lo escribimos como una matriz, indicando los nombres de las variables en negro queda asi:


 

  X1 X2 S1 S2 S3  
Max Z 18.5 20 0 0 0 RHS
R1 0.05 0.05 1 0 0 1,100
R2 0.05 0.1 0 1 0 1,800
R3 0.1 0.05 0 0 1 2,000

 

Dónde X1, X2 son las variables de decisión, S1, S2 y S3 son las variables de Holgura (Se suelen llamar con S, por que en inglés se  escribe Surplus). R1, R2, R3 son las restricciones y RHS son las disponibilidades de las restricciones, se llama así por que significa Right Hand Side, como lo encontraran en los textos gringos, "el lado derecho". 

 

Para facilitar el procesoiterativo se construyen tablas. Hay muchos formatos de tablas Simplex, que significan exactamente lo mismo. Lo importante es entender que significa cada cosa, y lo demás ya vendrá por añadidura. En la primera fila (fondo negro), colocamos los coeficientes de la función objetivo (18.5,20,0,0,0) y los títulos de las demás columnas. 

 

Recuerda que le dije anteriormente, que había que definir un número de variables que ivan a tomar el valor de cero? Las No Básicas, para poder resolver el sistema de ecuaciones de manera única. Entonces como tenemos 3 restricciones y 5 variables hay que dejar 2 como No Básicas o sea iguales a cero. Siempre se escoge las de holgura (S1, S2, S3)  para estar en la base en el inicio y dejamos las variables de decisión como no básicas. Fijemonos en la tabla siguiente que no las colocamos en la columna de la base.

 

En la primera columna vamos a colocar los coeficientes de las variables de la base. (Los coeficientes que tienen en la función objetivo). En la segunda columna como ya dijimos anteriormente, los nombres de las variables que tenemos actualmente en la base. De la tercera columna en adelante copiamos los coeficientes de las restricciones, luego en la columna RHS, colocamos cuanto tenemos de disponibilidad de las restricciones, lo que los gringos llaman "lado derecho" o RHS. La última columna vamos llamarla theta, más adelante la explico.

 

3. Definir la variable que entra.

 

Observemos un momento la tabla abajo; definamos dos filas adicionales. La fila Z y la fila Cj-Zj. En la fila Z vamos a colocar la suma del producto de los coeficientes de las variables que hay actualmente en la base por los coeficientes actuales en el área de las restricciones. Hagamos el ejemplo para el   primero: 0x0.05 + 0x0.05+ 0x0.1 = 0 y lo colocamos en seguida de la z. Para la columna siguiente será: 0x0.05+0x0.1+0x0.05 = 0. y así para las demás columnas hasta llegar a la columna RHS.  Fijemonos, que he puesto una celda en esta fila de color azul  más oscuro. En esta celda nos dirá el valor de la función objetivo, a medida que vamos iterando. Ahí debe quedar el mejor valor de Z cuando hayamos terminado.

 

En la fila Cj - Zj vamos a hacer la siguiente resta: De la fila de coeficientes de la función objetivo (la que está de fondo negro), restemos  la fila que acabamos de calcular.  para la primera: 18.5 - 0 = 18.5, para la segunda 20-0 = 0  y así. Esta fila es importante por que nos dice lo siguiente: qué tanto contribuye una variable si se mete en la función objetivo. X1 contribuiría con 18.5 y X2 contribuiría con 20, etc. Cómo queremos hallar el máximo valor, lo que nos interesa es incluir la variable que más contribuya, o sea la que mayor valor tenga en esta fila.En este caso, por supuesto, gana X2 con 20.  X2 no está en la base, entonces la marcamos para entrar, fijése que abajo le pusimos: "entra".

 

 

4. Definir la variable que sale



 

Coef Base 18.5 20 0 0 0 RHS Theta  
0 S1 0.05 0.05 1 0 0 1,100 22,000  
0 S2 0.05 0.1 0 1 0 1,800 18,000 Sale
0 S3 0.1 0.05 0 0 1 2,000 40,000  
  Z 0 0 0 0 0 0    
  Cj- Zj 18.5 20 0 0 0      
      Entra            

 

La variable que sale de la base es la que más restringe el crecimiento de la función objetivo y para ello sacamos un "ratio", es decir una división entre el RHS (la disponibilidad) y la columna de la variable que entra, esta queda en la columna que llamamos Theta. Para la primera fila queda: 1100/0.05 = 22,000. Luego de esta columna escogemos el menor valor que sea diferente de cero o de algún valor negativo.  

 

5. Iteración: Gauss-Jordan.

 

Recuerda de sus estudios de algebra lineal el tema de la eliminación gaussiana? No? Pues debería pegarle una revisada al tema y volver aquí. Si no, será dificil que entienda la siguiente parte. 

 

Una vez definida la variable que entra y la variable que sale, la intersección nos define la celda pivote.  La celda pivote es la que se tomará como base para hacer toda la iteración de gauss-jordan. En la tabla el pivote lo he colocado en fondo verde. Debemos, con base en operaciones entre filas, convertir la celda pivote en 1, y con base en ella convertir a las demás celdas en la misma columna en ceros. Entonces:

 

a. Convertir el pivote en 1: Para ello dividamos toda la fila en el valor del pivote.

0.05/0.1= 0.5

0.1/0.1=1

0/0.1=0

1/0.1=10

 

... los resultados los copiamos reemplazando la fila que contenia el pivote.

 

b. Convertir las demas celdas de la columna pivote en ceros.

 

0.5*(0.05*-1)+0.05 =0.025 

1*(0.05*-1)+0.05 = 0

0*(0.05*-1) + 1= 1 ... y lo mismo para la tercera fila

 

Reemplazamos S2 por X2 con su respectivo coeficiente y repetimos el paso 3 y 4. 

 

Coef Base 18.5 20 0 0 0 RHS Theta  
0 S1 0.025 0 1 -0.5 0 200 8,000 Sale
20 X2 0.5 1 0 10 0 18,000 36,000  
0 S3 0.075 0 0 -0.5 1 1,100 14,667  
  Z 10 20 0 200 0 360,000    
  Cj- Zj 8.5 0 0 -200 0      
    Entra              

 

Repetir hasta que no se llegue al óptimo. Cómo lo sabemos? Cuando al evaluar si hay una variable que entrando mejore el resultado, es decir que la fila Cj - Zj tenga algun valor positivo, aún será posible mejorar la solución, si no hay ningún valor mayor que cero, significa que hemos llegado al óptimo, como se muestra en la siguiente y última tabla. 

 

Coef Base 18.5 20 0 0 0 RHS Theta
19 X1 1 0 40 -20 0 8,000  
20 X2 0 1 -20 20 0 14,000  
0 S3 0 0 -3 1 1 500  
  Z 18.5 20 340 30 0 428,000  
  Cj- Zj 0 0 -340 -30 0    

Contenido :

Social