MÉTODO SIMPLEX invst op

INVESTIGACION DE OPERACIONES










IVAN ANDRES RUIZ BARRERA
JENNIFFER MARCELA CARRERO





FANNY YURLEY HERNANDEZ
INGENIERA INDUSTRIAL




UNIVERSIDAD DE PAMPLONA
INVESTIGACIÓN DE OPERACIONES
VILLA DE ROSARIO- COLOMBIA
2015
1. MÉTODO SIMPLEX
El Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltosmediante el método gráfico sin restricción en el número de variables.
El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que elnúmero de vértices que presenta un poliedro solución es finito siempre se hallará solución.

2. MÉTODO DE LA GRAN M
Este método empieza con la PL en la forma estándar Para cualquier ecuación i que no tiene una holgura, aumentamos una variable artificial R. Entonces esta variable se convierte en parte de la solución básica inicial. Debido a que es una variable artificial al modelo de PL se leasigna una penalidad en la función objetivo, para obligarlas a un nivel cero en una iteración del algoritmo SIMPLEX

Debido a que M es un valor positivo suficientemente grande, la variable R1 se penaliza en la función objetivo utilizando —MR, en el caso de la maximización, y +RM, en la minimización. Debido a esta penalidad El proceso de optimización lógicamente tratara de impulsar R1, al nivel ceroLa forma estándar se obtiene restando un superávit X3 en la segunda restricción y añadiendo una holgura X en la tercera restricción. Por tanto obtenemos

Minimice Z= 4X1 +X2


La primera y segunda ecuación no tiene variables que desempeñen el papel de holguras. Por consiguiente, utilizamos las variables R1 y R2 en estas dos ecuaciones y las penalizamos en la función objetivo con MR1 + MR2. La PLresultante se da como

Minimice Z=4X1 +X2 + MR1 + MR2




En el modelo modificado, ahora podemos utilizar R1, R2 y X4 como la solución básica factible inicial como lo demuestra la siguiente tabla simplex


3. DUALIDAD
La dualidad en programación lineal provee de resultados teóricos interesantes que justifican su uso como herramienta alternativa y complementaria de resolución.
TEOREMA DE DUALIDADDÉBIL: En general, el valor de cualquier solución factible del problema de minimización, provee una cota superior del valor óptimo del problema de maximización. Análogamente, el valor de la función objetivo de cualquier solución factible del problema de maximización es una cota inferior del valor óptimo del problema de minimización.
TEOREMA DE DUALIDAD FUERTE: En el óptimo el valor de la funciónobjetivo del problema primal será igual al valor de la función objetivo del problema dual evaluada en la solución dual óptima. Si el problema primal es no acotado, entonces el dual es infactible. Alternativamente si el problema primal es infactible, entonces el dual es no acotado.
TEOREMA DE HOLGURAS COMPLEMENTARIAS: Una variable en el primal está asociada a una restricción en el dual (y viceversa). Eneste sentido si en el primal existe una variable no básica (valor igual a cero), en el dual la restricción asociado no está activa, es decir, no se cumple en igualdad. Análogamente, si la variable es básica en el primal, la restricción asociada en el dual se cumple en igualdad. Este resultado teórico es útil toda vez que simplifica la forma de obtener la solución óptima dado que como en unproblema lineal la solución óptima (en caso de existir) está en un vértice, esto implica resolver un sistema de ecuaciones (con restricciones de igualdad).

4. VARIABLES
DE ENTREDA: Las condiciones para el aprendizaje comprenden tanto en los factores: externos como los internos. Los factores externos se aplican en 3 entradas: contigüidad, repetición y refuerzo. La contigüidad es un principio clásico...