Simplex

INVESTIGACION DE OPERACIONES:

METODO SIMPLEX.
El algoritmo símplex fue descubierto por el matemático norteamericano George Bernard Dantzig en 1947, es una técnica para dar soluciones numéricas a problema de programación lineal. Un problema en su forma estándar se puede representar como:

X, Xs ≥ 0. donde X son las variables de decisión de la forma estándar, Xs son las variables de holgura ode exceso, c contiene los coeficientes de la función objetivo y Z es la variable a ser maximizada o minimizada. El sistema es no determinado, debido a que el número de variables excede el número de ecuaciones. La diferencia entre el número de variables y el número de ecuaciones nos da los grados de libertad asociados con el problema. Cualquier solución, óptima o no, incluirá un número devariables de valor arbitrario. Esta forma permite encontrar la solución factible básica inicial haciendo Xsi = bj

INVESTIGACION DE OPERACIONES:

METODO SIMPLEX.
El método Simplex es un algoritmo iterativo que permite mejorar la solución con cada paso sucesivo. El algoritmo termina cuando no se puede seguir mejorando más la solución. Se parte de una solución básica inicial para la función objetivoen un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore la anterior solución. La búsqueda se hace siempre a través de los lados del polígono de soluciones factibles o de las aristas de la región solución, si el número de variables es mayor. Cómo el número de vértices y de lados o aristas es finito, siempre se podrá encontrar la solución. El método Simplex sebasa en la siguiente propiedad: si la función objetivo Z, no toma su valor máximo en el vértice A, entonces hay una arista o lado que parte de A, a lo largo de la cual Z aumenta.

INVESTIGACION DE OPERACIONES:

METODO SIMPLEX. FORMA ESTANDAR DEL MODELO:
1.- Todas las restricciones son ecuaciones con los lados derechos no negativos, en el caso del primal. Las restricciones del tipo ≤ o ≥ seconvierten en ecuaciones sumando una variable de holgura (caso ≤) o restando una variable de exceso (caso ≥) en el lado izquierdo de la restricción. 2.- Todas las variables son no negativas, si una variable es irrestricta se usa la sustitución Yi = Y ´i – Y´´i. Una variable negativa se hace no negativa multiplicando por -1 a la variable en la función objetivo y las restricciones. 3.- La funciónobjetivo es de maximización o minimización.

INVESTIGACION DE OPERACIONES:

METODO SIMPLEX. SOLUCIÓN BÁSICA:
Una solución básica es aquella que es factible o se encuentra en uno de los vértices de la región solución. Con m ecuaciones y n variables una solución básica se determina haciendo n-m variables iguales a cero. En general existen n!/ [m!(n-m)!] soluciones básicas posibles.

VARIABLES NOBÁSICAS:
Son las n -m variables que hemos hecho igual a cero.

VARIABLES BÁSICAS:
Son m variables restantes diferentes de cero. La solución básica será factible si todos los valores de las variables básicas son no negativos. Si alguna de las variables es negativa entonces la solución será infactible.

INVESTIGACION DE OPERACIONES: CONDICIONES PARA QUE UNA VARIABLE SEA BÁSICA O NO BÁSICA:CONDICIÓN DE OPTIMIDAD: La variable que entra o pasa a ser básica es aquella no básica con el coeficiente más negativo si el problema es de maximización, o más positivo si es de minimización. Si todos los coeficientes de las variables no básicas en Z son no negativos, la solución es óptima en maximización y si son no positivos entonces la solución es óptima en minimización. Otro método utiliza paraevaluación la fila (Cj – Zj) y elige para entrar la variable que de el mayor mejoramiento por unidad a la función objetivo. CONDICIÓN DE FACTIBILIDAD: La variable que sale es la variable básica, con la menor razón(denominador positivo) en la dirección de la variable que entra. Tanto en la condición de optimidad como de factibilidad, los empates se rompen de forma arbitraria.

INVESTIGACION DE...