METODO SIMPLEX
(Maximización y Minimización)
Es un procedimiento algebraico que contempla una serie de pasos repetitivos, con los cuales, progresivamente se va encontrando una solución optima (maximizar o minimizar según el caso una función objetivo). El método Simplex puede resolver problemas con cualquier número de variables y restricciones, sin embargo cuando el problema involucra más de 4 variables, la resolución resulta dispendiosa, larga y en estos casos es mejor dejar que un programa para computadores de programación lineal haga los cálculos.
Sin embargo, para poder entender los pasos de la programación lineal, para poder formular las ecuaciones algebraicas usadas en el programa de computación y para poder interpretar los resultados del programa, es necesario seguir manualmente el método simplex un buen número de veces.
PROCEDIMIENTO PARA LA APLICACIÓN DEL METDO SIMPLEX.
La descripción teórica de los pasos para la aplicación del método simples, para la resolución de problemas de maximización o minimización, puede parecer un poco larga y compleja, sin embargo su aplicación resulta muy sencilla en la resolución de los problemas si se lee detalladamente y se sigue el ejercicio que se presenta resuelto EN EL SIGUIENTE ENLACE
http://spreadsheets.google.com/pub?key=pAAIO2lY9BwLtbLjJDqROew1. FORMULAR EL PROBLEMA EN TERMINOS ALGEBRAICOS.
Comprende la formulación de la función objetivo y de las restricciones a que esta sujeta la función, teniendo en cuenta las variables que intervienen en el caso o problema. La función objetivo debe de ser maximizada o minimizada según el planteamiento del problema y considerando las restricciones de las variables
Ejemplo de función objetivo:
Z = 4X1 + 6X2
Z= costo total de producción de la empresa
X1= unidades producidas del articulo A
4= costo de producción de una unidad de articulo A
X2= unidades producidas del articulo B
6= costo de producción de una unidad de articulo B
4X1= costo total de producción del articulo A
6X2= costo total de producción del articulo B
La optimización de esta función consiste en minimizar el costo de producción en la empresa
Ejemplo de restricciones
Para fabricar una unidad de articulo A se requiere 1 unidad de materia prima C y 3 unidades de materia prima D
Para fabricar una unidad de artículo B se requiere 2 unidades de materia prima C y 1 unidad de materia prima D
El proveedor de la materia prima C solo suministra cantidades iguales o mayores a 80 unidades
El proveedor de la materia prima D solo suministra cantidades iguales o mayores a 75 unidades.
Entonces las restricciones quedan Así:
§ Primera restricción: 1X1 + 2X2 > 80 unidades de materia prima C
§ Segunda restricción 3X1 + 1X2 > 75 unidades de materia prima D
X1= unidades producidas del articulo A
X2= unidades producidas del articulo B
1X1= unidades consumidas de materia prima C para el articulo A
2X2= unidades consumidas de materia prima C para el articulo B
3X1= unidades consumidas de materia prima D para el articulo A
1X2= unidades consumidas de materia prima D para el articulo B
2. INTRODUCIR LAS VARIABLES DE HOLGURA O EXCEDENTE (H), LAS VARIABLES ARTIFICIALES (A) EN LAS RESTRICCIONES Y EN LA FUNCION OBJETIVO
2.1. INTRODUCIR LAS VARIABLES DE HOLGURA O EXCEDENTE (H), EN LAS RESTRICCIONES Y EN LA FUNCION OBJETIVO.
Cuando el problema es de maximización se introducen las variables de holgura o excedente en las restricciones y en la función objetivo.
Al introducir las variables de holgura o excedente (H) las desigualdades de las restricciones, se convierten en igualdades. Para cada restricción se agrega una variable de holgura o excedente con coeficiente 1 y para que las otras variables tengan representación en la restricción se escriben pero con coeficiente cero. Habrá tantas variables de holgura o excedente como restricciones existan teniendo en cuenta las reglas. Para agregar estas variables se debe tener en cuenta las siguientes reglas:
§ Se suman cuando la restricción es de tipo menor igual que ( < )
§ Se restan cuando la restricción de de tipo mayor igual que ( > )
§ No se necesitan cuando la restricción es una igualdad (=)
Las variables de holgura o excedente llevaran coeficiente cero en la función objetivo
2.2. INTRODUCIR LAS VARIABLES ARTIFICIALES (A) EN LAS RESTRICCIONES Y EN LA FUNCION OBJETIVO.
Cuando el problema es de minimización, se introducen las variables de holgura o excedente y también las variables artificiales, tanto en las restricciones como en la función objetivo.
Las variables artificiales en los problemas de minimización se agregan o utilizan cuando:
§ Las restricciones son de tipo mayor o igual que ( > )
§ Las restricciones son de tipo igual (=)
Habrá tantas variables artificiales como restricciones existan de tipo > o =
El coeficiente de las variables artificiales en la función objetivo, debe de ser un numero mucho más grande que cualquier otro que intervenga en el problema, positivo si la función se va a minimizar y negativo si la función se va a maximizar
2.3 EJEMPLOS DE INTRODUCCION DE VARIABLES DE HOLGURA O EXCEDENTE Y ARTIFICIALES EN LAS RESTRICCIONES Y EN LA FUNCION OBJETIVO§ Primera restricción con variables de holgura y artificiales en problema de minimización.
1X1 + 2X2 – 1H1 – 0H2 + 1A1 + 0A2 = 80
§ Segunda restricción con variables de holgura y artificiales en problema de minimización.
3X1 + 1X2 – 0H1 – 1H2 + 0A1 + 1A2 = 75
§ Función objetivo con variables de holgura y artificiales en un problema de minimización.
Z = 4X1 + 6X2 + 0H1 + 0H2 +100A1 + 100A2
Para la variable artificial en la función objetivo, tomamos un coeficiente grande, mínimo de 10 veces el valor absoluto del mayor coeficiente de la función objetivo ( en este caso 6x10 = 60) sin embargo tomas un coeficiente mas grande (100)
3. CONSTRUCCION DE LA TABLA DE LA PRIMERA SOLUCION
Para observar la descripción de los pasos………. Se debe consultar el ejercicio aplicado, resuelto en el enlace mencionado anteriormente
§ La parte central de la tabla entre la columna 4 y la penúltima columna contiene toda la información relacionada con las variables y los coeficientes de las variables que intervienen en el planteamiento y solución del problema así:
§ La fila 2 contiene el nombre de las variables originales del problema: X1, X2, X3,….,Xn. Seguidas de las variables de holgura o excedente H1, H2, H3,……., Hn. Seguida de las variables artificiales A1, A2, A3,……, An. Si estas últimas forman parte del planteamiento del problema. Para el ejemplo aplicado mostrado en el enlace o dirección mencionada son: A1, A2; H1, H2; A1, A2.
§ La fila 1 o fila Cj, contiene todos los coeficientes de: las variables originales del problema, las de holgura o excedente y las artificiales que forman parte de la función objetivo, Estos coeficientes no cambian en las siguientes tablas de solución. Para el ejemplo aplicado mostrado en el enlace o dirección mencionado los coeficientes son: 4; 6; 0; 0; 100; 100. Estos coeficientes corresponden según el caso a los beneficios o costos por unidad.
§ De la tercera fila hasta la antepenúltima fila contiene los coeficientes de: las variables originales (X), las de holgura o excedente (H) y las artificiales (A), que forman partes de las restricciones a que esta sujeta la función objetivo. Para el ejemplo aplicado mostrado en el enlace o dirección mencionado son
1; 2; -1; 0; 1; 0 (fila 3)
3; 1; 0; -1; 0; 1 (fila 4 o antepenúltima fila)
§ La primera columna de la tabla encabezada con B, muestra las variables que se eligieron para la tabla de primera solución. Para el ejemplo aplicado mostrado en el enlace o dirección mencionada son A1 y A2.
§ La segunda columna de la tabla encabezada con Ci, muestra los coeficientes de las variables que se eligieron para la tabla de primera solución Para el ejemplo aplicado mostrado en el enlace o dirección mencionada los coeficientes son 100 y 100
§ La tercera columna de la tabla encabezada con Po, muestra las cantidades de cada recurso que hay disponibles y corresponde al coeficiente independiente o termino a la derecha de la igualdad de las ecuaciones de las restricciones. Para el ejemplo aplicado mostrado en el enlace o dirección mencionada los coeficientes independientes son 80 y 75 y estarían representando las cantidades de las materias primas C y D
§ La penúltima fila o fila Zj se refiere al beneficio o costo que se da al introducir en la solución una unidad de las diferentes variables contenidas en esa fila desde la columna 4 hasta la penúltima columna. El Zj se calcula así
Zj= sumatoria (Ci*Cvr).
El subíndice j varía desde la columna 4 hasta la penúltima columna
Ci=coeficientes de las variables de la función objetivo y que además forman parte de la solución de la tabla en cuestión
Cvr= coeficientes de las variables respectivas según las columnas y que forman parte de las restricciones.
El Zj de la tercera columna encabezada con Po y que contiene los coeficientes independientes de las variables de restricción, representa el beneficio total para la solución y se calcula así:
Zj= sumatoria (Ci*Cind). = Z3
Ci= coeficientes de las variables de la función objetivo y que además forman parte de la solución de la tabla en cuestión
Cind= Coeficiente independiente de las restricciones
Para el ejemplo aplicado, mostrado en el enlace o dirección mencionada, calculamos los Zj para las columnas 3, 4 y 5
Zj=Z3= 100*80 + 100*75 = 15,500
Zj=Z4= 100*1 + 100*3 = 400
Zj=Z5= 100*2 + 100*1 =300
§ La ultima fila o fila Cj – Zj. Contiene el beneficio o costo neto por unidad, que se obtiene al introducir a la solución una unidad de esa variable. El beneficio costo neto se halla por la diferencia entre el Cj y el Zj de cada columna. En un problema de maximización cuando todos los resultados de Cj-Zj son cero o negativos es por que se ha llegado a la solución optima. En un problema de minimización cuando todos los resultados de Cj-Zj son cero o positivos es por que se ha llegado ala solución optima.
Para el ejemplo aplicado, mostrado en el enlace o dirección mencionada, calculamos los Cj- Zj para las columnas 4 y 5
Cj – Zj = C4-Z4= 4-400 =-396
Cj – Zj = C5-Z5= 6-300 =-294
Así termina la construcción de la tabla de primera solución, las variables que se habían considerado en esta tabla para la primera solución eran A1 y A2 y se muestran en la columna 1 de la tabla, encabezada con B, el valor que le corresponde a cada variable se toma de la columna 3, encabezada con Po y es A1 = 80 y A2= 75. Las demás variables X1, X2, H1 y H2 no aparecen en esta columna por lo tanto su valor es de cero para cada una, de tal manera que estos resultados se constituyen en la primera solución. Es decir A1=80; A2=75; X1=0; X2=0; H1=0 y H2 = 0
4. DETERMINAR LA VARIABLE QUE DEBE INCORPORARSE A LA SOLUCION
4.1 Problemas de Minimización. Siempre que existan valores negativos en la fila (Cj-Zj), es posible obtener una mejor solución. El menor valor negativo en la fila (Cj-Zj), indica la variable que debe incorporarse y corresponde a la que encabeza la columna que tiene ese menor valor negativo. Para el ejemplo aplicado, mostrado en el enlace o dirección mencionada la variable que se incorpora es X1, por que esta en la columna que contiene el menor valor negativo de la fila (Cj-Zj) y que es -396
4.2 Problemas de Maximización. Siempre que existan valores positivos en la fila (Cj-Zj), es posible obtener una mejor solución. El mayor valor positivo en la fila (Cj-Zj), indica la variable que debe incorporarse y corresponde a la que encabeza la columna que tiene ese mayor valor Positivo.
5. DETERMINAR LA VARIABLE QUE DEBE SALIR DE LA SOLUCION.
En la tabla en cuestión, se divide los coeficientes independientes que forman parte de las restricciones, entre los coeficientes de la variable que debe incorporarse a la solución y que ya ha sido determinada en el paso anterior. Los resultados se colocan en la ultima columna encabezada con F y se elige la fila con el menor resultado obtenido en las divisiones, en el interfecto de esa fila con la columna 1 encabezada con B se encuentra la variable que debe salir de la solución. Para el ejemplo aplicado, mostrado en el enlace o dirección mencionada, el menor valor obtenido en las divisiones es 25,000 y se encuentra en la cuarta fila, en el interfecto de esta fila con la columna 1 se encuentra la variable A2, la cual debe salir de la solución. En resumen la variable que entra o se incorpora a la solución es X1 y la variable que sale de la solución es A2
6. CALCULAR LOS NUEVOS VALORES DE LA FILA PARA LA VARIABLE QUE SE INCORPORA O ENTRA A LA SOLUCION.
Se debe construir la tabla de segunda solución así:
§ En la primera y segunda columna se muestra respectivamente el nombre y los coeficientes de las variables que van e intervenir en la segunda solución. Para el ejemplo aplicado, mostrado en el enlace o dirección mencionada, la variable A1 cuyo coeficiente es 100 proviene de la tabla de primera solución, la variable X1 es la que se incorpora y su coeficientes como se indica en la función objetivo es 4
§ Para calcular los nuevos valores de la fila de la variable que entra o se incorpora a la solución, se dividen los valores de la fila de la variable que sale en la tabla de la primera solución por el elemento interseccional fila-columna de la variable que sale, con la variable que entra localizado en la tabla de la primera solución. Para el ejemplo aplicado, mostrado en el enlace o dirección mencionada, los nuevos valores de la fila de la variable que entra para la tabla de segunda solución son 75/3; 3/3; 1/3; 0/3; -1/3; 0/3 y 1/3
7. MODIFICAR LAS FILAS RESTANTES DE LA TABLA DE PRIMERA SOLUCION, PARA TERMINAR DE CONFORMAR LA TABLA DE LA SEGUNDA SOLUCION.
A cada valor de las filas restantes a modificar en la tabla de la primera solución, séle resta el producto del valor ubicado en la misma fila pero en la columna de la variable que entra, con el valor ya calculado en la nueva fila de la variable según la columna en cuestión en la tabla de la segunda solución. Para el ejemplo aplicado, mostrado en el enlace o dirección mencionada, calculamos los valores para la fila A1 de la tabla de segunda solución con respecto a sus columnas 3, 4, 5, 6 y 7.
Fila A1; Columna 3 55= (80-1*25)
Fila A1; Columna 4 0= (1-1*1)
Fila A1; Columna 5 1.6667= (2-1*0.333)
Fila A1; Columna 6 -1= (-1-1*0)
Fila A1; Columna 7 0.3333= (0-1*(-0.333) etc.
8. TERMINAR LA TABLA DE SEGUNDA SOLUCION Y OBTENER LAS SEGUNDA SOLUCIÓN.
En la tabla de segunda solución se calculan las filas Zj y (Cj-Zj), se toma la segunda solución, y se analiza la fila (Cj-Zj), para saber si existen más soluciones, en caso de existir, se repite en forma análoga el proceso a partir del cuarto paso, cuantas veces se necesite, hasta encontrar la solución óptima. Para el ejemplo aplicado, mostrado en el enlace o dirección mencionada, la segunda solución es: X1=25; X2=0; H1=0; H2=0; A1=55 y A2 = 0.
En el mismo ejercicio la tercera solución se convierte en la optima, ya que todos los valores de (Cj-Zj) son mayores iguales a cero (caso de minimización) y esta solución es: X1=14; X2=33; H1=0; H2=0; A1=0 y A2= 0. y el costo mínimo es 254
Finalmente en la misma hoja de calculo se resuelve el mismo problema por el método Simples, pero previamente convirtiendo el problema de minimización en problema de maximización
