programacion entera




Trabajo de apoyo de la unidad 4

Programación Entera



Carlos Alvarado Gonzalez
Raúl Moran Angón


Índice


Introducción y casos de aplicación……………………. 3-6
Ejemplos de métodogomory……………………………..7-14
Ejemplos de método de acotación………………………15- 18
Introducción de aplicaciones.-

Introducción l Programación lineal (método del simplex) variables continuas l Programación entera: restricciónadicional: variables han de ser enteras Caso particular: programación entera binaria (0/1) Programación entera mixta: algunas variables han de ser enteras, otras no. Resolución de problemas deprogramación entera l Enumeración exhaustiva l Relajación lineal (LP relaxation) l Branch and bound (Ramificar y acotar) l Método de los planos de corte (Gomory) Enumeración exhaustiva No es viable,debido a que las soluciones crecen de forma exponencial PEB n variables: 2n posibles soluciones 5 Relajación lineal (I) Consiste en resolver el mismo problema sin las condiciones de variablesenteras Si el óptimo cumple las condiciones de las variables enteras, entonces es óptimo del problema entero 0 1 2 3 4 5 0 1 2 3 4 5 Politopo entero: Todos los ptos extremos son enteros Branchand bound Método de enumeración implícita: divide en problemas menores: ramificación y descarta algunos de ellos: acotación A veces puede usarse como heurístico, si no se exploran todos los nodos.Si se exploran todos sí se garantiza el óptimo. Puede aplicarse tanto a PEB como a PEM

Corte fraccional de Gomory.- Sea una variable xk no entera. Su fila del Simplex será: åÎ = - j N k k kj jx x y x Y f k y f jk son las partes fraccionales de xk e ykj Entonces, el plano de corte correspondiente es: åÎ - £ j N k kj j f f x 0 y la variable de holgura será entera



.Ejemplos de programación






http://www2.ulpgc.es/hege/almacen/download/14/14958/programacion_enter.pdf

http://es.slideshare.net/betzaidaberenicelopezolivares5/programacion-entera-u4...