tecno




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 objetivo en 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ésde 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 se basa 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 lolargo de la cual Z aumenta.
FORMA ESTANDAR DEL MODELO:
Todas las restricciones son ecuaciones con los lados derechos no negativos, en el caso del primal. Las restricciones del tipo ≤ o ≥ se convierten en ecuaciones sumando una variable de holgura (caso ≤) o restando una variable de exceso (caso ≥) en el lado izquierdo de la restricción.
Todas las variables son no negativas, si una variable esirrestricta 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.
La función objetivo es de maximización o minimización.

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 unasolución básica se determina haciendo n-m variables iguales a cero. En general existen n!/ [m!(n-m)!] soluciones básicas posibles.

VARIABLES NO BÁ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 esnegativa entonces la solución será infactible.

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 para evaluación la fila (Cj – Zj) y elige para entrar la variable que del 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.

SOLUCION DEGENERADA:
Si se presenta un empate en la variable que sale de forma repetida, una variable básica tomara valor cero, esto hace que la solución sea degenerada. Lo anterior es debido a la existencia de a lo menos una restricción redundante.

CASO ESPECIALES DEL METODO SIMPLEX:MULTIPLES SOLUCIONES ÓPTIMAS:

Se presenta cuando la función objetivo es paralela a una restricción activa (se satisface como igualdad en la solución optima), en este caso hay infinitas soluciones. Desde el punto de vista práctico permite escoger la solución que mejor se adapte a la situación.

SOLUCIONES NO ACOTADA:

Se presenta cuando el espacio de soluciones no está acotado en la dirección haciadonde aumenta o disminuye la función objetivo, según el modelo sea de maximización o minimización. Si en cualquier iteración los coeficientes de las restricciones de una variable no básica son no positivos, entonces el modelo no está acotado en la dirección de esa variable. Si el coeficiente de la función objetivo es negativo en maximización o positivo en minimización, entonces el valor de la...