Tecnologia

Programación entera

Un modelo de Programación Entera (PE) permite abordar aplicaciones donde la solución tiene sentido si una parte o todas las decisiones toman valores restringidos a númerosenteros.
Por ejemplo, consideremos que tenemos el siguiente problema de Programación Lineal:






Si todas las variables restringen sus valores a números enteros, entonces estamos frente aun modelo de Programación Entera (puro). Por el contrario, si al menos algun conjunto de variables no esta acotada a adoptar valores o números enteros, se trata de un modelo de Programación Entera(mixta).
Luego, si consideramos que estamos a un modelo de Programación Entera (puro o mixto) y resolvemos el modelo de Programación Lineal asociado (esto es, admitiendo valores continuos para lasvariables), estaremos obtenido la solución de la Relajación Continua del modelo entero. Para un modelo de maximización, la relajación continua nos proporciona una cota superior del valor óptimo del modelode Programación Entera asociado.
En el caso particular que la Relajación Contínua nos proporcione una solución entera, entonces ésta será también la solución del modelo de Programación Enteraasociado. En caso contrario deberemos utilizar alguna estrategia o algoritmo para obtener la solución del modelo de PE.
Una herramienta eficiente para abordar estos casos es el algoritmo de Branch & Bound.Branch-and-Bound (B&B) es una técnica eficiente para la búsqueda de soluciones donde su objetivo es encontrar no solamente una solución, más si la óptima solución. El algoritmo B&B interactua ycrea un árbol de búsqueda con el problema representado en un nodo, donde este nodo – problema – sufre una descomposición del problema en subproblemas, buscando la falseabilidad de soluciones noóptimas. Casi todas las otras técnicas de búsquedas son distintas del método B&B porque encuentran soluciones no óptimas o soluciones subóptimas. El problema debe ser representado con un grafo de estados,...