Simplex

OPTIMIZACIÓN LINEAL Método simplex Solución de modelos lineales con el método simplex. 1. El método simplex es un procedimiento de cálculo algebraico, iterativo, para resolver modelos lineales de cualquier tamaño. 2. El algoritmo simplex requiere que el modelo lineal, para ser solucionado, cumpla las condiciones de forma estándar y sistema canónico. 3. La forma estándar incluye: a) una funciónobjetivo a optimizar, b) lado derecho de las restricciones con valor positivo, c) variables de decisión no negativas y d) las restricciones deben ser expresadas como igualdades. 4. Para transformar las restricciones en igualdades se deben incorporar las llamadas variables de holgura. 5. Una variable de holgura tiene coeficiente cero en la función objetivo. Se suman en restricciones del tipo ≤ y serestan en restricciones del tipo ≥. En términos matemáticos, expresan la diferencia entre el lado izquierdo y el lado derecho de las restricciones. Al igual que las variables de decisión deben ser mayores o iguales a cero. 6. En términos del modelo representan la cantidad de recurso no utilizado con relación a un máximo disponible, o utilizado por encima de un mínimo disponible. Esto es así cuandola restricción es de un recurso disponible. 7. Cuando la restricción es de una condición o requerimiento, representan la cantidad de esa condición o requerimiento que se obtiene por encima de un mínimo o que se deja de tener con relación a un máximo. 8. El sistema canónico en un modelo lineal significa que debe existir una variable básica en cada restricción. Esto permite obtener una primerasolución posible que satisface todas las restricciones. 9. Una variable básica tiene coeficiente 1 positivo en una restricción y no existe en las demás. 10. Las variables de decisión (estructurales) del modelo y las variables de holgura pueden ser variables básicas. Cuando ninguna de ellas cumple con la condición de ser básica, se incorpora una variable como artificio matemático, para cumplir con elsistema canónico y a esa variable se le llama variable artificial. 11. Una variable artificial debe tener incorporado un coeficiente muy alto en la función objetivo, con signo negativo en maximización y con signo positivo en minimización. Con esto se logra que el procedimiento simplex las elimine de la solución en las primeras iteraciones. Estas variables deben valer cero en la solución óptima delmodelo. 12. Una tabla simplex es un resumen detallado de toda la información del modelo, para trabajar más fácilmente con él. 13. El método simplex funciona, en forma general, de la siguiente forma: calcula una solución factible inicial y determina sí esa solución es óptima. Si no lo es, se mueve a un punto extremo adyacente en el conjunto convexo de soluciones factibles, y calcula la nuevasolución en ese punto. De nuevo determina si esa solución es o no óptima; si no lo es, repite el proceso anterior. Así continúa sucesivamente hasta encontrar un punto extremo cuyo valor objetivo no pueda ser mejorado y allí concluye, determinando así que ha encontrado la solución óptima. 14. Para calcular la solución factible inicial le otorga valor cero a las variables que no son básicas y resuelve paralas otras variables básicas. Cada solución factible satisface todas las restricciones. 15. Para determinar si la solución inicial es óptima, calcula los llamados coeficientes relativos de las variables. Estos valores informan en cuanto variaría el objetivo por cada unidad en que se incremente el valor de la variable a la que se refiere ese coeficiente relativo. 16. Si la solución no es óptima, almoverse a otro punto extremo adyacente en el conjunto convexo, el método simplex efectúa un intercambio de una variable básica por una no básica. 17. Para determinar cual variable no básica debe entrar a formar parte de una nueva solución, como variable básica, se utiliza como criterio el seleccionar la variable que

MBA Virginia Haro Sánchez

OPTIMIZACIÓN LINEAL Método simplex mejore en...