Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Método de Ramificación Y Acotamiento

No description
by

Andres Velandia Rodriguez

on 17 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Método de Ramificación Y Acotamiento

Método de Ramificación Y Acotamiento

Programación Entera Pura (PEP)

Introducción
Para el Problema de Programación Entera Pura (PEP), existe un número finito de soluciones posibles (no todas son factibles) que pueden representarse mediante un diagrama de árbol. En este método no hace falta enumerar todas las soluciones posibles, ya que se pueden eliminar “ramas dominadas”. Una rama puede eliminarse si puede demostrarse que no contiene una solución factible que sea mejor que una ya obtenida, esto se debe a que siempre las ramas que nacen a partir de un nodo tendrán respuestas menores a este nodo.
Función Objetivo y Restricciones
Pasos
Para solucionar un problema de Programación Entera Pura por método Gráfico se requiere seguir los siguientes pasos:
Programación Entera Pura (PEP)
Investigación de Operaciones II
Grupo 81 – 2013-3
Grupo Interno 1


Andrés Velandia Rodríguez - 20102020102
William Alfredo Linares G. - 20102020052
Juan David Lara Rodríguez - 20102020050

Paso 1
Resolver el problema como si fuera un problema ordinario de Programacion Lineal (relajación de enteros). La solución obtenida se toma como cota o valor máximo y base para el procedimiento de búsqueda de una solución factible.

Paso 2
A partir de la solución de Programación Lineal designar una variable no entera, y ramificar sus dos posibles valores enteros que le preceden y suceden (E1<=A1<=E2) en dos ramas. Este proceso se denomina como acotamiento.

Paso 3
Después de obtener el acotamiento para la variable seleccionada por medio de la ramificación, estos valores corresponderán a nuevas restricciones del problema (respectivamente en cada rama), con los cuales posteriormente se solucionara el problema como si fuera de Programación Lineal.
Paso 4
Analizar si las variables del problema tienen valores enteros en la nueva solucion, si no es asi, se continua con la ramificacion del problema.
Paso 5
Se continua con el proceso de ramificación y acotamiento hasta que se pueda y se selecciona de todas las soluciones óptimas enteras (si existen), la mas óptima y esa sera la respuesta de nuestro problema de Programación Entera Pura.
Paso 6
Si se obtiene una solución entera pura, se termina la ramificación de esa rama y se continua con las demás ramas, si en dado caso la solución óptima No entera de una rama, es menos óptima a una solución entera, no se ramifica más esa rama, puesto que las soluciones óptimas de un nodo ramificado serán siempre menos óptimas que la solución del mismo.
Nota:
Hay que tener en cuenta que en el caso de solucionar los nuevos problemas con las restricciones agregadas, no siempre dará una solución factible, en el caso de que esto pase sencillamente se dice que por esa rama no hay solución factible y se continua con otra rama.
Si al terminar de ramificar y acotar no hay una solución óptima y entera pura, se dice que el problema no tiene solución óptima netamente pura
Full transcript