RESOLUCIÓN EXACTA DEL MODELO DEL MÁXIMO PROMEDIO PARA EL PROBLEMA DE LA DISPERSIÓN MÁXIMA

Abstract

El problema de la dispersión equitativa, o de la dispersión máxima consiste en que dado un conjunto de nodos y una función de "distancias" entre estos nodos, se trata de escoger un subconjunto de ellos de tal manera que este sea lo más "diverso" posible, en términos de alguna métrica considerada, aquí se resuelve un problema denominado MÁXIMO PROMEDIO en el cual el número de elementos a seleccionar también es una variable de decisión. Otros modelos han sido extensamente estudiados por otros autores: Martí y Duarte, Glover, Prokopyev y Resende y Martí. En este artículo se estudia el modelo del MÁXIMO PROMEDIO (MAXMEAN), que en general es un problema difícil de optimización combinatoria, del tipo Strongly NP-hard. También se estudia la utilización del modelo MAXSUM para la resolución del MAXMEAN, y se determina un procedimiento exacto más eficiente para resolverlo. Para comprobar los modelos se desarrollaron instancias de prueba aleatorias para diferentes tamaños del problema. Todos los problemas en su formulación como modelos de programación matemática MIP o MIQCP fueron implementados en GAMS y resueltos con CPLEX 12.0 y con CONOPT3.