.jpeg)
Para comprender de mejor
manera el método simplex vamos a revisar algunas definiciones.
El método parte de dos
afirmaciones importantes:
El conjunto de posibles soluciones
o conjunto factible de cualquier problema de programación lineal puede
representarse mediante un poliedro convexo.
Si un problema de programación
lineal tiene una solución óptima y finita, ésta estará en un vértice del
poliedro convexo que representa al problema.
El algoritmo simplex parte de
uno de los vértices del poliedro, y verifica si es el óptimo; si no lo es,
busca un nuevo vértice adyacentes que va mejorando el valor de la función
objetivo. Se continúa iterando hasta llegar al vértice que representa la
solución óptima.
En la siguiente imagen vemos
el poliedro que representa la solución factible y cómo realiza el recorrido el
algoritmo simplex:
Pasos del Método Simplex
Los pasos a seguir en el
método simplex son:
- Determinar la función objetivo.
- Definir las restricciones o limitantes.
- Igualar la función objetivo a cero.
- Convertir las inecuaciones en ecuaciones agregando una variable de holgura (h).
- Construir la tabla simplex con los datos de las ecuaciones y la función objetivo.
- Identificar el elemento más negativo de la fila z Max (se llamará columna pivote).
- Se identifica la fila pivote.
- Teniendo la columna y la fila pivote se determinará el elemento pivote.
- Se inicia la reducción de renglones en base al procedimiento de transformaciones elementales, actualizar nuestra matriz realizando las operaciones de Gauss Jordán (Recordar la matriz inversa).
- Al finalizar el procedimiento se comprueba las operaciones utilizando la función objetivo sustituyendo los valores encontrados para cada variable en la tabla simplex
Joyería Mar de Plata ubicada
en el edificio de bomberos voluntarios en Cobán A.V. le encarga a un orfebre
fabricar dos tipos de joyas. La unidad de tipo A se hace con 1g de oro y 1g de
plata y se vende a Q225.00 y la de tipo B se vende a Q270.00 y lleva 1,5g de
oro y 1g de planta. ¿Si solo dispone de 750 g de cada metal cuántas joyas ha de
fabricar de cada tipo para poder tener el máximo beneficio?
1. Determinar la función
objetivo.
Dos variables
X= Unidad tipo A – Q.225.00
Y= Unidad tipo B – Q. 270.00
Zmax = 225x +270y
2. Definir las restricciones o
limitantes.
Construir las inecuaciones con
las restricciones (de la tabla anterior):
3. Igualar la función objetivo a
cero.
Zmax = 225x +
270y
Zmax= -225x –
270y = 0
4. Convertir las inecuaciones en
ecuaciones agregando una variable de holgura (h).
5. Construir la tabla simplex con
los datos de las ecuaciones y la función objetivo.
Ecuaciones
X + 1.5y + h1 = 750
1.5X + y + h2 = 750
Zmax -225 -270 = 0
7. Se
identifica la fila pivote.
- Dividir cada valor de C entre cada valor de la columna pivote (columna seleccionada en el paso 6).
750 ÷
1.5 = 500
750 ÷
1 = 750
- Seleccionar de todas las divisiones el valor más pequeño, el valor más pequeño es 500 (este elemento es el que nos permite seleccionar la fila pivote).
8. Teniendo
la columna y la fila pivote se determinará el elemento pivote. El elemento pivote es el valor que está en
la intersección entre la fila y la columna pivote: 1.5
9. Se inicia la reducción de
renglones en base al procedimiento de transformaciones elementales, actualizar
nuestra matriz realizando las operaciones de Gauss Jordán (recordar la matriz
inversa). El elemento pivote se convierte a uno y todos los elementos
debajo y encima de él deben convertirse a cero.
La fila Zmax posee valores negativos y esto no debe ser así, solo debe poseer valores positivos o ceros, esto quiere decir que vamos a repetir algunos pasos empezando por encontrar el elemento más negativo de la tabla simplex.
Identificar el elemento más negativo de
la fila Zmax (se llamará columna pivote). En este caso es -45
Se identifica la fila pivote.
Dividir cada valor de C entre cada valor
de la columna pivote.
500 ÷ 2/3 = 750
250 ÷ 5/6 = 300
Seleccionar de todas las divisiones el
valor más pequeño, el valor más pequeño es 300 (este elemento es el que nos
permite seleccionar la fila pivote).
Teniendo la columna y la fila pivote se determinará el elemento pivote. El elemento pivote es el valor que está en la intersección entre la fila y la columna pivote: 5/6.
10. Al finalizar el procedimiento se comprueba las operaciones utilizando la función objetivo sustituyendo los valores encontrados para cada variable en la tabla simplex.
Zmax 225(300) + 270 (300)
148,000 = 67,500+81,000
148,500.00 = 148,500.00
Se deben fabricar 300 joyas de cada uno
de los dos tipos.
Necesitan fabricar dé x que son los de tipo
A = 300 joyas.
Y necesitan fabricar dé y que son los de tipo B = 300 joyas.
Para obtener la utilidad máxima de
Q148,500.00
No hay comentarios:
Publicar un comentario