Ple Universidad Católica De Chile

Departamento de Ingeniería Industrial y de Sistemas Pontificia 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 "...