Metodo simplex

 

El método del simplex fue creado en 1947 por el matemático George Dantzig. Este método es utilizado, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables.

El método del simplex es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

El método está diseñado de manera que la función objetivo no disminuya (o aumente) en un modelo de maximización (o minimización) y generalmente aumentará (o disminuirá) en cada iteración. Pasos para el desarrollo del método simplex:

 

 

 

1. Hallar una solución básica factible inicial.

a. Convertir las desigualdades en igualdades.

b. Igualar la Función Objetivo a cero.

c. Escribir la tabla inicial simplex. (en las columnas aparecerán todas las variables del problema y, en las filas, los

coeficientes de las igualdades obtenidas, una fila para cada restricción y la primera fila con los coeficientes de la función objetivo.

 

2. Prueba de optimidad: determinar si la solución básica factible inicial es óptima, esto ocurre si todos los coeficientes de la ecuación son no negativos (= 0), para el caso de maximización. Si es así, el proceso termina; de otra manera se lleva a cabo otra iteración para obtener la nueva solución básica factible inicial.

 

3. Para escoger la variable de decisión que entra en la base, nos fijamos en la primera fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor

a. Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos.

b. Si en la primera fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la primera fila no haya elementos negativos (para el caso de maximización).

c. La columna de la variable que entra en la base se llama columna pivote

 

4. Para todos los problemas de maximización y minimización, la variable que sale es la variable básica que tiene la razón más pequeña (positiva). Una coincidencia se anula arbitrariamente.

a. Para determinar la razón de cada renglón, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero.

b. Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir.

c. El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, indica la fila de la variable de holgura que sale de la base. Esta fila se llama fila pivote

 

5. En la intersección de la fila pivote y columna pivote se encuentra el elemento pivote.

 

6. Se determina la nueva solución básica factible construyendo una nueva tabla en la forma apropiada de eliminación de Gauss, abajo de la que se tiene. Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a 1, se divide todo el renglón entre el número pivote, entonces Nueva fila del pivote = renglón o fila pivote antigua / número pivote

 

7. Para el resto de las filas: Nueva fila= (Vieja fila) - (Coeficiente de la vieja fila en la columna de la variable entrante) X (Nueva fila del pivote) Ó renglón nuevo = renglón antiguo - ( coeficiente de la columna pivote X renglón pivote nuevo)

 

8. Si en los elementos de la primera fila hay un coeficiente negativo, significa que no hemos llegado todavía a la solución óptima. Entonces se repite el proceso.

 

9. Si todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima. La solución óptima viene dada por el valor de Z en la columna de los valores solución. En la misma columna se puede observar el vértice donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base.

 

 


 

 

 

 

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 enEl 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 + 0S+ 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    
 

Solución de Modelos Lineales con el Método SIMPLEX y el método de de la “M” penalización. 

 
Esbozo de conceptos y aspectos relevantes de la teoría de la solución de Modelos de Programación Lineal 
 
1. El Método Simplex es un procedimiento de cálculo algebráico, iterativo, para resolver Modelos Lineales de 
cualquier tamaño. 
 
2. El algoritmo Simplex requiere que el Modelo Lineal, para ser solucionado, cumpla las condiciones de Forma 
Estándar y Sistema Canónico. 
 
3. La Forma Estándar incluye: 
a) una Función Objetivo a optimizar 
b) lado derecho de las restricciones con valor positivo 
c) variables de decisión no negativas 
d) las restriccionesdeben ser expresadas como igualdades. 
 
4. Para transformar las restricciones en igualdades se deben incorporar las llamadas variables de holgura. 
 
5. Una variable de holgura tiene coeficiente cero en la Función Objetivo. Se suman en restricciones del Tipo ≤ y 
se restan en restricciones del Tipo ≥. En términos matemáticos, expresan la diferencia entre el lado izquierdo y el 
lado derecho de las restricciones. Al igual que las variables de decisión deben ser mayores o iguales a cero. 
 
6. En términos del modelo representan la cantidad de recurso no utilizado con relación a un máximo disponible 
(Parte ociosa de los recursos). 
 
7. Cuando la restricción es de una condición o requerimiento, representan la cantidad de esa condición o 
requerimiento que se obtiene por encima de un mínimo o que se deja de tener con relación a un máximo. 
 
8. El Sistema Canónico en un Modelo Lineal significa que debe existir una variable básica en cada restricción. 
Esto permite obtener una primera solución posible que satisface todas las restricciones. 
 
9. Una variable básica tiene coeficiente 1 positivo en una restricción y no existe en las demás. 
 
10. Las variables de decisión (estructurales) del modelo y las variables de holgura pueden ser 
variables básicas. Cuando ninguna de ellas cumple con la condición de ser básica, se incorpora una variable 
como artificio matemático, para cumplir con el sistema canónico y a esa variable se le llama variable artificial. 
 
11. Una variable artificial debe tener incorporado un coeficiente muy alto en la Función Objetivo, con signo 
negativo en maximización y con signo positivo en minimización. Con esto se logra que el procedimiento 
Simplex las elimine de la solución en las primeras iteraciones. Estas variables deben valer cero en la solución 
óptima del modelo. 
 
12. Una Tabla Simplex es un resumen detallado de toda la información del modelo para trabajar más fácilmente 
con él. La siguiente tabla expresa cómo deben ser recogidos los datos para resolver el problema de programación 
líneal por el Método Simplex. 
Modelo de Tabla Simplex 
 
                      
Procedimiento para la resolución de problemas mediante por el Método Simplex. 
 
FASE I: Preparar el modelo inicial para construir la tabla: 
 
1) Transformar los términos independientes en positivos (multiplicando por -1). 
 
2) Si en alguna restricción, hay un solo proceso que está contenida en  ella sola, lo convertiremos en 
unitario (dividiendo por su coeficiente) y si no lo hago meteré una variable de holgura. 
 
3) En las inecuaciones en las que encontramos ≤ introducimos una variable de holgura sumando.  
 
4) En las inecuaciones en las que encontramos ≥ introducimos una variable de holgura restando y además 
una variable artificial sumando para que en dicha restricción haya un proceso unitario positivo. 
 
5) En las igualdades se introduce una variable artificial sumando si en la misma no existe una variable 
unitaria positiva. 
 
6) En toda restricción debe haber una variable unitaria positiva. 
 
7) Las variables de holgura, a la hora de introducirlas en la función objetivo lo haremos siempre con 
coeficiente cero, y las variables artificiales se  introducen con el  coeficiente –m si estamos 
maximizando 0 m si estamos minimizando. 
 
8) Igualar a cero la función objetivo 
 
FASE II: Construir la tabla y resolver el algoritmo. 
 
Paso 1: Construir la tabla del método Simplex y rellenamos la tabla con los coeficientes. Comprobamos que las 
varibles básicas tienen un coeficiente de 1 en la intersección de su renglón y columna correspondiente y cero en 
los demás renglones incluido la finción objetivo. Si no es así (como en el caso de la existencia de variables 
artificiales, eliminamos el coefiente m del renglón 0 utilizando como pivote la ecuación que incorpora la variable 
artificial)  
 
Paso 2: La S.B.F. es óptima, si y sólo si todos los coeficientes del renglón  (0) son no negativos. De lo contrario 
se debe iterar. En  
 
Paso 3: Si comprobamos que hay coeficientes negativos en el renglón (0), marcamos el mayor en valor absoluto 
y esta será la variable no básica que entra a la base.  
Para determinar la variable básica que sale de la base, marcamos la columna debajo del coeficiente de la variable 
que entra y se le da el nombre columna pivote.  
Aplicamos la prueba del cociente mínimo para determinar cuál es la variable básica que sale. 
a) Elegimos los coeficientes de la columna pivote positivos 
b) Se divide cada coeficiente del lado derecho entre los coeficientes de la columna pivote 
c) Se identifica el renglón con la menor razón 
La variable básica para este renglón es la que sale y se le da el nombre de renglón pivote. La intersección entre la 
columna pivote y el renglón pivote lo denominamos número pivote. El patrón de coeficientes en la columna de la  
variable que entra en la 
d) base, debe quedar como actualmente está el patrón de coeficientes de la variable que sale. 
 
Paso 4: Calculamos los nuevos coeficientes de la matriz:  
a) Coeficientes del renglón de la variable que entra: Dividimos el renglón pivote entre el número pivote y 
el resultado serán los coeficientes del nuevo renglón de la variable que entra. 
b) Coeficientes de los demás renglones :  Dividimos el nuevo renglón de la variable que entra por menos 
el coeficiente del de la variable que entra en el renglón que estamos calculando y al resultado, le 
sumamos el renglón que teníamos inicialmente 
 
Paso 5: Construimos la tabla con los resultados. 
 
Paso 6: En la nueva matriz, comprobamos los coeficientes del renglón cero, si todavía existen coeficientes 
negativos, se sigue iterando, de lo contrario hemos terminado y hallamos la solución óptima. EJEMPLO