Investigacion De Operaciones
Páginas: 2 (374 palabras)
Publicado: 7 de octubre de 2012
METODO DE RAMIFICACION Y ACOTAMIENTO (MRA)
El MRA es uno de los métodos mas populares en la solución exacta de problemas de programación entera. El método consiste en ir acotando superior einferiormente el valor de la función objetivo hasta que ambas cotas sean iguales, es decir, se haya llegado al valor óptimo.
Algunas de las muchas preguntas que surgen sobre este método son:
1. ¿Comoseleccionar el subproblema a explorar?
2. De todas las variables que deben ser enteras y que en la relajación resultaron ser fraccionarias ¿sobre cual se ramifica o se hace la partición en subproblemas?3. ¿Afectara el orden de prioridades sobre las variables a ramificar el desempeño del método?
Para cada una de ellas hay respuestas, pero depende de la estructura y de características de cadamodelo. Se puede seleccionar el subproblema que tiene la mejor cota o el que recientemente haya sido introducido en la lista o una combinación de estos. Cada una de estas formas de seleccionar elsubproblema tiene sus ventajas y desventajas dependiendo del modelo y de lo que se busca.
La forma de trabajar del MRA permite tener cierto control sobre algunos de sus parámetros algorítmicos, con el fin deayudar al método a encontrar resultados que sean óptimos y obtenidos en tiempos razonables. Uno de estos parámetros es el de dar o no prioridad a las variables a ramificar.
Este trabajo se enfoca enanalizar si el considerar prioridades sobre las variables a la hora de ramificar afecta la calidad de la solución y el tiempo requerido para encontrarla en el modelo bajo estudio.
ALGORITMO DEGOMORY
Se pretende mostrar una de las versiones de Gomory (Fraccional), existen otros, como son el entero y el mixto.
Paso 1: Resolver el problema primal, si la solución es entera, corresponde ala óptima para el problema de Programación Lineal Entera.
Paso 2: Seleccionar decimales y escoger aquel que tenga la mayor parte fraccionaria tomando las ecuaciones completas.
Pasó 3: Se...
El MRA es uno de los métodos mas populares en la solución exacta de problemas de programación entera. El método consiste en ir acotando superior einferiormente el valor de la función objetivo hasta que ambas cotas sean iguales, es decir, se haya llegado al valor óptimo.
Algunas de las muchas preguntas que surgen sobre este método son:
1. ¿Comoseleccionar el subproblema a explorar?
2. De todas las variables que deben ser enteras y que en la relajación resultaron ser fraccionarias ¿sobre cual se ramifica o se hace la partición en subproblemas?3. ¿Afectara el orden de prioridades sobre las variables a ramificar el desempeño del método?
Para cada una de ellas hay respuestas, pero depende de la estructura y de características de cadamodelo. Se puede seleccionar el subproblema que tiene la mejor cota o el que recientemente haya sido introducido en la lista o una combinación de estos. Cada una de estas formas de seleccionar elsubproblema tiene sus ventajas y desventajas dependiendo del modelo y de lo que se busca.
La forma de trabajar del MRA permite tener cierto control sobre algunos de sus parámetros algorítmicos, con el fin deayudar al método a encontrar resultados que sean óptimos y obtenidos en tiempos razonables. Uno de estos parámetros es el de dar o no prioridad a las variables a ramificar.
Este trabajo se enfoca enanalizar si el considerar prioridades sobre las variables a la hora de ramificar afecta la calidad de la solución y el tiempo requerido para encontrarla en el modelo bajo estudio.
ALGORITMO DEGOMORY
Se pretende mostrar una de las versiones de Gomory (Fraccional), existen otros, como son el entero y el mixto.
Paso 1: Resolver el problema primal, si la solución es entera, corresponde ala óptima para el problema de Programación Lineal Entera.
Paso 2: Seleccionar decimales y escoger aquel que tenga la mayor parte fraccionaria tomando las ecuaciones completas.
Pasó 3: Se...
Leer documento completo
Regístrate para leer el documento completo.