EJERCICIO TÍPICO PROGRAMACIÓN ENTERA PURA (P.E.P)
Enviado por miguelrojasfore • 1 de Mayo de 2017 • Apuntes • 612 Palabras (3 Páginas) • 633 Visitas
EJERCICIO TÍPICO PROGRAMACIÓN ENTERA PURA (P.E.P)
Septiembre 01 de 2016
IO 2, Gr 81; Grupo # 2
Estefany Jaramillo Vera 20131020047
Santiago Alfonso Casallas 20132020081
Maddyzeth Ariza Riaño 20132020101
OBJETIVOS:
Resolver un ejercicio de Programación Entero Pura (P.E.P), usando el método de ramificación y acotamiento, con el fin de investigar, entender y aplicar el procedimiento adecuado que brindará una base para abordar problemas de este tipo en la vida real.
CONCEPTOS CLAVES:
Método Grafico: El método gráfico es una forma fácil y rápida para la solución de problemas de Programación Lineal, siempre y cuando el modelo conste de dos variables. Para modelos con tres o más variables, el método gráfico es imposible. Consiste en representar geométricamente las restricciones, condiciones técnicas y función objetivo.
Método de ramificación y acotamiento: El método de Branch and Bound (o Ramificación y Acotamiento), es un algoritmo diseñado para la resolución de modelos de Programación Entera. Su operatoria consiste en linealizar el modelo de Programación Entera, es decir, resolver éste como si fuese un modelo de Programación Lineal y luego generar cotas en caso que al menos una variable de decisión (entera) adopte un valor fraccionario.
El algoritmo genera en forma recursiva cotas (o restricciones adicionales) que favorecen la obtención de valores enteros para las variables de decisión. En este contexto resolver el modelo lineal asociado a un modelo de Programación Entera se conoce frecuentemente como resolver la relajación continua del modelo entero.
Maximizar: Se refiere a la búsqueda del máximo rendimiento. La maximización consiste en aprovechar o explotar todo lo posible ciertos recursos o funciones.
ENUNCIADO:
Maximizar:
Z= 2+ 5[pic 1][pic 2]
Sujeto a:
2 + 3 ≤ 12[pic 3][pic 4]
[pic 5]
[pic 6]
, ≥ 0[pic 7][pic 8]
, Є Z[pic 9][pic 10]
SOLUCIÓN:
Pasos | Procedimiento |
Se resuelve el problema relajado por el método gráfico. De allí obtenemos una solución óptima. Como soluciones se tiene: [pic 11] [pic 12] Z = 18 Debido a que es fraccionario se ramifica con respecto a esta variable.[pic 13] | [pic 14] |
Realizamos nuestra primera ramificación. Como es un fraccionario entre 1 y 2, agregaremos una nueva restricción a nuestro problema, que será .[pic 15][pic 16] La solución a nuestro problema es: [pic 18] Z = 17 Todas nuestras soluciones son enteras, pero debemos realizar las demás ramificaciones para observar si en realidad es la solución óptima. | [pic 19] |
Ramificamos por la derecha, por lo cual le agregamos la nueva restricción ≥ 2. Tenemos como solución:[pic 20] [pic 21] [pic 22] Z = 17.333 Como vemos, aún hay soluciones fraccionarias, por lo cual se realiza una nueva ramificación. Como =8/3 entonces pondremos una nueva restricción , pero en esta caso no hay región factible. Entonces, procedemos a hacer la siguiente rama. | [pic 26] |
Agregamos la nueva restricción y resolvemos por método gráfico. Este nos da como solución: ; [pic 27][pic 28][pic 29] Z = 16. La solución es entera, por lo que termina la ramificación. | [pic 30] |
Aquí podemos observar como fue el proceso de ramificación de una manera más sencilla. Como tenemos dos soluciones enteras, debemos escoger la más adecuada de acuerdo a las condiciones del inicio (maximización, por lo que se escoge el máximo. En nuestro problema, la solución de Z era 18, por lo que en este caso la solución óptima será: ; ; Z = 17[pic 31][pic 32] | [pic 33] |
...