Ple Universidad Católica De Chile
Clase 24 - Programación Entera I
ICS 1102 • Optimización
Prof. Claudio Seebach
-
2do Semestre2006
Programación Entera
• Ventajas de restringir variables a tomar valores enteros
! Más realista
• Desventajas
! Más difícil de modelar ! Puede se mucho más difícil de resolver
•Variables 0-1
! Equivalente a:
0 ! x j ! 1 con x j entero
Prof. Claudio Seebach
ICS 1102 – Optimización / Clase 24
El misterio de programación entera
• Algunos problemas enteros son fáciles! Podemos resolver problemas con millones de variables
• Algunos problemas enteros son difíciles
! Incluso 100 variables puede ser un gran desafío
• Se requiere de conocimientos y experienciapara saber cuál es cuál • Es un área de investigación muy activa
Prof. Claudio Seebach
ICS 1102 – Optimización / Clase 24
Tipos de problemas enteros
• Problema entero puro
! Todas lasvariables son enteras
• Problema entero binario
! Todas las variables deben tomar valores 0 o 1
• Problema entero mixto
! Algunas variables son enteras y otras son continuas
Prof. Claudio SeebachICS 1102 – Optimización / Clase 24
Técnicas para resolver problemas enteros
• Técnicas de enumeración
! Enumeración completa • Lista con todas las soluciones… elegir la mejor ! Branch &bound • Búsqueda implícita de todas las soluciones, pero eliminando inteligentemente muchas de ellas antes de haberlas evaluado
• Técnicas de planos cortantes
! Usar programación lineal (PL) pararesolver problemas enteros, agregando restricciones que eliminan las soluciones fraccionales (o continuas)
Prof. Claudio Seebach
ICS 1102 – Optimización / Clase 24
Ejemplo de Programación EnteraMax z = 5 x1 + 8 x2 s.a. x1 + x2 " 6 5 x1 + 9 x2 " 45 x1 , x2 ! Z 0+
Prof. Claudio Seebach
ICS 1102 – Optimización / Clase 24
Dominio y solución óptima
Max z = 5 x1 + 8 x2 s.a. x1 + x2 "...
Regístrate para leer el documento completo.