DESARROLLO DE UN PROGRAMA PARA RESOLVER EL PROBLEMA DE ASIGNACIÓN 3-DIMENSIONAL A TRAVÉS DE UN ALGORITMO GENÉTICO

Abstract

En el presente trabajo se desarrolla un programa para resolver el problema en el cual dados tres (3) conjuntos disjuntos, cada uno conteniendo n elementos, y dado el costo de toda tripleta conteniendo un elemento de cada conjunto, se desea computar n tripletas disjuntas minimizando la suma de los costos. Este problema es conocido como el problema de asignación 3-dimensional y es NP-duro en el sentido fuerte. Para su resolución, se diseñó y analizó una metaheurística denominada Algoritmo Genético, la cual es un método de búsqueda en el que las soluciones al problema son capaces de reproducirse entre sí, generándose nuevas soluciones cada vez más próximas al óptimo.