El problema de asignación generalizado dinámico: modelación y estructura

Abstract

Los problemas de asignación (de ahora en adelante AP, por sus siglas en inglés) han jugado un papel muy importante dentro de la optimización de problemas de la vida real, ya que son múltiples las situaciones que pueden modelarse de este modo. Son muchas las variantes del AP, dependiendo de las características del problema bajo consideración; sin embargo, al pertenecer estas variantes a la clase NP, resulta difícil abordarlos como un problema de optimización (o de valor óptimo), ya que es improbable encontrar la mejor solución en tiempo polinomial; así, en muchas ocasiones, basta con encontrar una respuesta que sea lo "suficientemente cercana al óptimo", en un tiempo de cómputo razonable. En este trabajo se define una nueva variante del AP, denominada Problema de Asignación Generalizado Dinámico (de ahora en adelante DGAP). Se deducen algunas propiedades matemáticas del mismo, que luego son usadas en la elaboración de un algoritmo genético empleado para su solución.