Metodo simplex Resolución de problemas de Maximización

Tema:

Método Simplex

En el tema anterior, se vieron ejemplos de programación lineal que contenían dos variables de decisión.  Con sólo dos variables es posible utilizar un método gráfico. Se trazó la región factible y luego se buscó el punto de esquina óptimo y la utilidad o costo correspondiente.  Sin embargo la mayoría de los problemas de la vida real implican más de dos variables y por lo tanto son demasiado grandes para resolverlos mediante el procedimiento de solución gráfico simple.  Los problemas que se deben enfrentar en el mundo de los negocios y el gobierno pueden tener docenas, cientos e incluso miles de variables.  Se necesita un método más poderoso que el gráfico, por lo que se deberá usar un método llamado simplex.

¿En qué consiste el método simplex?

Se examina cada uno de los puntos de esquina del poliedro n-dimensional, pues la teoría sostiene que la solución óptima se encuentra en alguno de ellos. Examina los puntos de esquina en forma iteractiva hasta que se llega a la solución óptima.

La temática se abordará de la siguiente forma:

1. Resolución de problemas de Maximización
2. Resolución de problemas de Minimización
3. Análisis de sensibilidad.
4. Modelo dual.

Subtema:

Resolución de problemas de Maximización

Uso de restricciones con el signo [pic 2]

A continuación se explica el formato de la tabla simplex utilizando el libro “Métodos Cuantitativos para los negocios” de Barry Render, para resolver problemas de programación lineal con el método simplex, para esto se desarrollará un ejemplo.

Resolver el siguiente problema de programación lineal (PL), utilizando el método simplex:

[pic 3]

1. Replantea las desigualdades de la forma estándar, esto es incluyendo variables de holgura en cada restricción, para el caso <= . Las variables de holgura representan recursos no utilizados, como maquinaria, mano de obra, dinero, espacio de almacenamiento o cualquier número de recursos semejantes.

[pic 4][pic 5]

En la función objetivo también se agregan las variables de holgura, pero con coeficientes “0”

1. Dibuja la tabla simplex.

1. Coloca los coeficientes de las variables de la función objetivo estándar en el renglón Cj.

1. Coloca en la columna Cj los coeficientes de las variables básicas de la solución inicial.

1. En la parte central de la tabla coloca los coeficientes del conjunto de restricciones, asi como su “lado derecho”.

1. Calcula el renglón Zj, multiplicando los coeficientes de la columna Cj por el valor correspondiente a los coeficientes de la parte central, y se suman. Por ejemplo para obtener el valor 0, en el renglón Zj de la columna x1, se hizo la siguiente operación: (0)(1)+(0)(2)=0.

1. Calcula el renglón Cj – Zj, restando la Zj de la Cj correspondiente a cada celda.

1. Verifica el criterio de optimalidad, esto es, que en el renglón Cj – Zj aparezcan:

• Para maximizar = ceros o números negativos
• Para minimizar = ceros o números positivos

Si no se cumple el criterio de optimalidad, se deberá hacer otra Iteracción, para intercambiar una variable básica por una no básica.

Para el caso de nuestro ejemplo, todas las celdas de la fila Cj – Zj deberían ser ceros o números negativos, como no se cumple se deberá hacer otra iteracción.

...