Los problemas de programación entera surgen con frecuencia cuando los valores de algunas o todas las varibles de decisión deben restringirse a valores enteros. Existen también muchas aplicaciones que necesitan decisiones de sí o no - incluyendo las relaciones combinatorias que se puedan expresar en términos de tales decisiones - que se pueden representar por variables binarias (0-1). Estos problemas son más difçiles de lo que serían sin la restricción de valores enteros, de manera que los algoritmos disponibles para programación entera, en general, son mucho menos eficientes que el método símplex. Los factores que determinan el tiempo de cálculo son el número de variables enteras y la estructura del problema. Para un número fijo de variables enteras, casi siempre es más fácil resolver problemas de PEB que problemas con variables enteras generale, pero agregar variables continuas (PEM) puede no significar un incremento en el tiempo de cálculo. Para problemas especiales de PEB que contienen alguna estructura especial que se puede aprovechar mediante un algoritmo especial, es posible resolver problemas muy grandes (muy por encima de mil variables binarias) en forma rutinaria. Puede ser que otros problemas mucho más pequeños sin estructura especial no e puedan resolver.
En la actualidad es común que se disponga de paquetes de computadora para algoritmos de programación entera en el software de programación matemática. EStos algoritmos casi siempre se basan en la técnica de ramificación y acotamiento o en alguna variación de ésta.
No hay comentarios.:
Publicar un comentario