Metodo simplex Resolución de problemas de Maximización
Enviado por Benecasanova • 16 de Agosto de 2017 • Documentos de Investigación • 3.741 Palabras (15 Páginas) • 193 Visitas
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:
- Resolución de problemas de Maximización
- Resolución de problemas de Minimización
- Análisis de sensibilidad.
- 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]
- 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”
- Dibuja la tabla simplex.
Cj | ||||||
Variables Básicas | [pic 6] | [pic 7] | [pic 8] | [pic 9] | Lado derecho | |
[pic 10] | ||||||
[pic 11] | ||||||
Zj | ||||||
Cj – Zj |
- Coloca los coeficientes de las variables de la función objetivo estándar en el renglón Cj.
Cj | 3 | 2 | 0 | 0 | ||
Variables Básicas | [pic 12] | [pic 13] | [pic 14] | [pic 15] | Lado derecho | |
[pic 16] | ||||||
[pic 17] | ||||||
Zj | ||||||
Cj – Zj |
- Coloca en la columna Cj los coeficientes de las variables básicas de la solución inicial.
Cj | 3 | 2 | 0 | 0 | ||
Variables Básicas | [pic 18] | [pic 19] | [pic 20] | [pic 21] | Lado derecho | |
0 | [pic 22] | |||||
0 | [pic 23] | |||||
Zj | ||||||
Cj – Zj |
- En la parte central de la tabla coloca los coeficientes del conjunto de restricciones, asi como su “lado derecho”.
Cj | 3 | 2 | 0 | 0 | ||
Variables Básicas | [pic 24] | [pic 25] | [pic 26] | [pic 27] | Lado derecho | |
0 | [pic 28] | 1 | 1 | 1 | 0 | 8 |
0 | [pic 29] | 2 | 1 | 0 | 1 | 10 |
Zj | ||||||
Cj – Zj |
- 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.
Cj | 3 | 2 | 0 | 0 | ||
Variables Básicas | [pic 30] | [pic 31] | [pic 32] | [pic 33] | Lado derecho | |
0 | [pic 34] | 1 | 1 | 1 | 0 | 8 |
0 | [pic 35] | 2 | 1 | 0 | 1 | 10 |
Zj | 0 | 0 | 0 | 0 | 0 | |
Cj – Zj |
- Calcula el renglón Cj – Zj, restando la Zj de la Cj correspondiente a cada celda.
Cj | 3 | 2 | 0 | 0 | ||
Variables Básicas | [pic 36] | [pic 37] | [pic 38] | [pic 39] | Lado derecho | |
0 | [pic 40] | 1 | 1 | 1 | 0 | 8 |
0 | [pic 41] | 2 | 1 | 0 | 1 | 10 |
Zj | 0 | 0 | 0 | 0 | 0 | |
Cj – Zj | 3 | 2 | 0 | 0 |
- 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.
...