METODOS DE SOLUCION, METODO SIMPLEX

INFORME CAPITULO 4, INVESTIGACIÓN DE OPERACIONES

PROGRAMACIÓN LINEAL

MATEO ANDRÉS SUAREZ

DAVID ALBERTO GARCÍA ARANGO

UNIVERSIDAD DE ANTIOQUIA
SECCIONAL SUROESTE
FACULTAD DE INGENIERÍA
DEPARTAMENTO DE INGENIERÍA INDUSTRIAL
ANDES
2010

MÉTODO SIMPLEX

Se da una breve introducción sobre el método simplex y sobre las diferentes alterativas que hay para su solución

Primero describen el método geométrico como interpretarlo, luego se introducen los términos y conceptos utilizados en el método simplex y se empieza la utilización del mismo, con la forma de formular el  problema, seguido de la forma estándar, las soluciones básicas y la solución óptima, y la adaptación a otros modelos.

Luego de esto se da un abrebocas sobre el análisis de sensibilidad, método simplex revisado y dual.

Por ultimo describen el manejo del método simplex en computadoras y otras alternativas para resolver problemas grandes.

Algebra del método simplex:

Aunque es una forma muy larga y tediosa para la solución de un problema, esta muestra paso a paso toso el procedimiento y nos ayuda a  entender la lógica de los algoritmos

Forma tabular del método siplex.

En este método solo se muestran o se incluyen los datos necesarios como los coeficientes de las variables, los valores del lado derecho de las ecuaciones, y las variables básicas; en este método se hace las operaciones necesarias para que la primera fila quede sin nueros negativos y para hacer que la tabla quede en forma gaussiana. Para esto existen dos métodos; el método de la “M”  o el método de fases.

Rompimiento de empates en el método simplex

Un empate se refiere a dos valores iguales durante el proceso.

            Empate para la vasca entrante.

            En este caso no hay un método definido por lo tanto se puede escoger la variable de forma arbitraria, pues tarde o temprano se llegara a la solución óptima, la diferencia está en el número de it. necesarios para llegar a esta

            Empate para la variable básica que sale: Degeneración

En este caso sí importa cual sale, puesto que generaría variables degeneradas, y esto puede llevar a que el ciclo se repita en forma periódica (ciclo perpetuo).

Aunque existen formas para evitar estos ciclos, estas se ignoran por su escasez, por lo tanto se recomienda romper los empates de forma arbitraria, sin importar el número de variables degeneradas que resulten.

            Cuando no hay variable básica que sale: Z no acotada

Ocurre cuando ninguna variable califica como variable básica que sale (los coeficientes de la columna pivote, excluyendo el renglón 1, son negativos o cero, esto es porque en la prueba de coeficiente mínimo se toman los valores estrictamente positivos), y lo que ocurre es que hay una variable que crece indefinidamente, lo que hace que “Z” haga lo mismo si salirse de la región factible; en este caso se para el proceso y se dice que Z no es acotada o que se ha cometido un error.

Cuando hay soluciones optimas múltiples.

Cualquier problema puede tener as de una solución óptima; cuando esto ocurre es porque hay al menos dos soluciones factibles en el vértice (FEV) óptimas, y toda solución óptima es una combinación lineal de estas soluciones. En consecuencia en la corma aumentada toda solución óptima es una combinación convexa de la solución básica factible óptima.

           

Adaptación a otras formas del modelo

Método de la “M”

Consiste en agregar una “M” a cada variable artificial que se agrega por las restricciones de igualdad; la “M” representa u valor muy grande.

≤ se agrega una variable de holgura para convertirla en igualdad.

≥ se agrega una variable superávit para convertirla en igualdad, además de esta variable, requiere una variable artificial.

= se le agrega una variable artificial ( )

Método de dos fases

Se revisan las restricciones del problema original, introduciendo las variables artificiales según se necesite para obtener una solución BF inicial obvia.

El objetivo de la primera fase es encontrar una solución BF para el problema real, en esta fase se Minimiza:

El objetivo de la fase 2 es encontra ua solucion OPTIMA  para el problema real,  en esta se minimiza el Z del problema original, sujeta a las restricciones, pero eliminando las variables artificiales. Aquí se comienza con la solucion  BF obtinida al final de la fase 1, y se resuelve por el método simplex.

Analisis posóptimo

Consiste en la extracion de errores para despues replantear el problema.
una forma es realizar el método SIMPLEX cada ves que finalice u problema, lo que se convertira en un problema mayor.

El método de reoptimizacion no ofrece una solucion mucho mas eficiente, ulitizando la tabla SIMPLEX final como tabla inicial yluego resolerlos ya sea por el merodo simplex revisado o po el método simplex dual.

            Precios sombra

Mide la tasa a la que Z  puede aumentar si se incrementa (un poco) la cantidad de recursos.

            Método simplex revisado

El método simplex origina revisado consiste en darle tratamiento matricial al método simplex original.

El método simplex revisado utiliza únicamente:

·         Los coeficientes de las variables no basicas en el renglón (0).

·         Los coeficientes de la variable básica entrante en las restricciones.

·         Los coeficientes de las variables basicas actuales en las restricciones.

·         El lado derecho de las ecuaciones.

·         El método simplex revisado utiliza una notación de forma matricial para hallar la solución al problema.

Notación

Maximizar

Z = cx sujeto a Ax ≤ b

Donde c es un vector renglón que representa el coeficiente de las variables en la función objetivo, también llamado vector fila costos:

x vector columna de decisión, b vector columna recursos y 0 vector columna de ceros o vector nulo.

y A es la matriz de coeficientes tecnológicos

            Analisis de sensibilidad

Su proposito principal es identificas los parametros censibles (aquellos que no pueden s¡cambiar sin cambiar la solucion óptima), sirve para deteriminar lo que sucederia al final de la tabla simplex, si le realizaran pequeños cambios a inicio del problema.