Observaciones importantes al utilizar método simplex

Método Simplex

Es un método iterativo que permite ir mejorando la solución en cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución.

Este famosísimo método fue creado en el año de 1947 por el estadounidense George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich, con el ánimo de crear un algoritmo capaz de solucionar problemas de m restricciones y n variables.

¿QUE ES UNA MATRIZ IDENTIDAD?

Una matriz puede definirse como una ordenación rectangular de elementos, (o listado finito de elementos), los cuales pueden ser números reales o complejos, dispuestos en forma de filas y de columnas.

La matriz idéntica o identidad es una matriz cuadrada (que posee el mismo número tanto de columnas como de filas) de orden n que tiene todos los elementos diagonales iguales a uno (1) y todos los demás componentes iguales a cero (0), se denomina matriz idéntica o identidad de orden n, y se denota por:

La importancia de la teoría de matrices en el Método Simplex es fundamental, dado que el algoritmo se basa en dicha teoría para la resolución de sus problemas.

OBSERVACIONES IMPORTANTES AL UTILIZAR MÉTODO SIMPLEX

VARIABLES DE HOLGURA Y EXCESO

El Método Simplex trabaja basándose en ecuaciones y las restricciones iniciales que se modelan mediante programación lineal no lo son, para ello hay que convertir estas inecuaciones en ecuaciones utilizando unas variables denominadas de holgura y exceso relacionadas con el recurso al cual hace referencia la restricción y que en el tabulado final representa el "Slack or surplus" al que hacen referencia los famosos programas de resolución de investigación de operaciones, estas variables adquieren un gran valor en el análisis de sensibilidad y juegan un rol fundamental en la creación de la matriz identidad base del Simplex.

Estas variables suelen estar representadas por la letra "S", se suman si la restricción es de signo "<= " y se restan si la restricción es de signo ">="

Ejemplo:

La empresa jenox se dedica a la fabricación de manteles. Fabrica 2 modelos (redondos y rectangulares). Cada una consume 2 o 3 metros de tela respectivamente, además de ser cortados y cosidos a mano, tarea que lleva una hora para los manteles rectangulares se les debe colocar cuatro esquineros de refuerzo.

Semanalmente se pueden conseguir 600 m2 de tela, 600 esquineros y 500 horas de corte y costura. Los márgenes de ganancia son de $8 para los manteles redondos y $10 para los rectangulares.

Solución:

X1= Cantidad de manteles redondos a fabricar semanalmente

X2= Cantidad de manteles rectangulares a fabricar semanalmente

Maximizar

Z= 8 x1 + 10 x2

Restricciones = 2x1 + 3x2 < 600

4x2 < 600

2x1 + x2 < 500

El primer paso es convertir las desigualdades en igualdades.

2x1 + 3x2 + x3 = 600

4x2 + x4 = 600

2x1 + x2 + x5 = 500

z -8x1 - 10x2 = 0

Para igualar Z a cero debemos pasar los elementos al lado izquierdo de tal forma que se vuelven negativos

 Se denomina variable de holgura a la variable que se debe sumar a uno de los miembros de una restricción para que ambos miembros sean iguales.

X Z X1 X2 S1 S1 S3 CD

S1 0 2 3 1 0 0 600

S2 0 0 4 0 1 0 600

S3 0 2 1 0 0 1 500

Zj 1 -8 -10 0 0 0 0

• La matriz pasa a formar la parte central o estructura de la tabla.

• En la columna “X” se debe colocar las variables básicas (X3, X4, X5)

• En la columna “C” se colocan los coeficientes en el funcional de las variables asociadas a cada fila o columna.

• En la columna “B” se coloca el término independiente de la restricción asociada a cada fila.

En la fila de Z se considera el mayor valor negativo, una vez identificado la columna será nuestro pivote, después dividimos la columna CD con nuestra columna pivote quedando de la siguiente forma.

600/3= 200

600/4= 150

500/1= 500

X Z X1 X2 S1 S2 S3 CD

S1 0 2 3 1 0 0 200

S2 0 0 4 0 1 0 150

S3 0 2 1 0 0 1 500

Zj 1 -8 -10 0 0 0 0

Tomamos el de menor valor y con este encontramos nuestra fila pivote, de tal forma que nuestro elemento pivote es el numero 4.

Como podemos observar la variable que entra seria X2 y la variable que sale S2.

Continuando con el procedimiento se divide toda la fila entre cuatro

0/4=0 0/4= 0 4/4=1 0/4=0 1/4=1/4 0/4= 0 600/4= 150

Fila nueva: 0 0 1 0 ¼ 0 150

Para encontrar la variable se realiza el siguiente procedimiento:

S1

Colocar la fila vieja: 0 2 3 1 0 0 600

El coeficiente de la fila: 3 3 3 3 3 3 3

Fila nueva: 0 0 1 0 1/4 0 150

0 2 0 1 -3/4 0 150

S3

Colocar la fila vieja: 0 2 1 0 0 1 500

El coeficiente de la fila: 1 1 1 1 1 1 1

Fila nueva: 0 0 1 0 1/4 0 150

0 2 0 0 -1/4 0 350

Z

Colocar la fila vieja: 1 -8 -10 0 0 0 0

El coeficiente de la fila: -10 -10 -10 -10 -10 - 10 -10

Fila nueva: 0 0 1 0 1/4 0

...