Esquemas de enumeración implícita ordenada programación entera

Abstract

El concepto de problema de optimización es intuitivamente fácil de entender, consiste en determinar una alternativa óptima frente al criterio seguido de entre un conjunto de posibilidades. Sin embargo la descripción formal de este problema es algo más compleja. Schrijver (1986) define un problema como subconjunto c * x *, donde es un conjunto finito llamado código y * es el conjunto de secuencias ordenadas de símbolos (elementos del código). El problema de optimización consiste en determinar un elemento x* * fijado z *, o bien decidir que no existe este elemento. A la cadena z se le denomina parámetros del problema o parámetros de entrada y a x* solución. Por Programación Entera se entiende el conjunto de técnicas destinadas a la resolución de problemas de optimización en los que la cadena solución x* representa un vector con componentes enteras. Los problemas de optimización más estudiados dentro de la Programación Entera son los lineales, en ellos los parámetros de entrada se determinan a partir de la cadena (A, b, c) siendo A una matriz de dimensiones mxn, b un vector columna m dimensional y c un vector fila de dimensión n. Para representarlos usaremos la siguiente formulación: minimizar cx sujeto a: Ax b x Existe una gran variedad de problemas reales que admiten la formulación anterior, por indicar algunos ejemplo, podemos citar los problemas de secuenciación de tareas, problemas de planificación como el de localización de tareas, problemas de diseño como el de determinación de recorridos en grafos, problemas estadísticos en el análisis de datos y fiabilidad, o incluso problemas en biolog{u00|