Título:
Modelado de asignación de becas con restricciones sectoriales
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
García Troisi, Diego
Paolini, Liliana
Tassino, Víctor
Paolini, Liliana
Tassino, Víctor
Tutor:
Testuri, Carlos E.
Tipo de documento:
Tesis de grado
Editor:
Palabras clave:
METODO HEURISTICO
METODO EXACTO
PROGRAMACION MATEMATICA ENTERA
RESTRICCIONES SECTORIALES
ASIGNACION DE BECAS
GLPK
CSP
ALGORITMOS EVOLUTIVOS
ALGORITMOS AVIDOS
ALGORITMO GRASP
BUSQUEDA TABU
METODO EXACTO
PROGRAMACION MATEMATICA ENTERA
RESTRICCIONES SECTORIALES
ASIGNACION DE BECAS
GLPK
CSP
ALGORITMOS EVOLUTIVOS
ALGORITMOS AVIDOS
ALGORITMO GRASP
BUSQUEDA TABU
Descriptores:
Año de publicación:
2011
Contenido:
Resumen:
Un mecanismo utilizado como apoyo a estudiantes para su formación es el de subsidio financiero o beca. Diferentes instituciones gestionan fondos destinados al otorgamiento de becas mediante mecanismos concursables por méritos y potencial de los postulantes. Muchas veces las instituciones, además de otorgar las becas basándose en méritos, también establecen subsidios sectoriales entre los postulantes, donde atienden criterios como el de cierta cantidad mínima de becas por tramos de los postulantes según criterios previamente establecidos. Al imponer restricciones sectoriales el problema de asignación de becas se torna difícil de resolver. En este contexto, se modeló el problema y diseñó e implementó dos alternativas de resolución computacional que incluyen restricciones sectoriales, mediante mecanismos exacto y heurístico. Además se evaluarón los resultados de algunas instancias resueltas del problema. La metodología exacta se instrumentó mediante un modelo de programación entera que abstrae los conceptos más relevantes del problema; y su resolución se compuso mediante el mecanismo exacto, que además de aportar su valor en sí mismo, permite obtener cotas para evaluar la heurística. Para la resolución mediante el método heurístico se estudiaron varias alternativas tomando en cuenta métodos obtenidos de la literatura para la creación de heurísticas. En base a estas alternativas se decidió generar una heurística a medida que toma estrategias de los distintos métodos.
Para brindar un entorno de ejecución práctico al problema se realizó el desarrollo de un prototipo de aplicación que encapsula los dos métodos y presenta una interfaz con varias secciones que contienen funcionalidades para generar instancias del problema, ejecutar ambos métodos y realizar mediciones de los resultados. A partir del trabajo realizado se compararon soluciones obtenidas de distintas instancias y ejecuciones mediante ambos métodos. Si bien el tiempo de resolución del método exacto resultó en la mayoría de los casos superior al tiempo requerido por el método heurístico, la ventaja del primer método es que se está seguro de que el resultado es óptimo, mientras que para el método heurístico no se puede asegurar nada sobre la optimalidad de la solución si no conoce cuál es el valor óptimo. Sin embargo, con el método heurístico desarrollado, además de reducir los tiempos se comprobó que en la mayoría de los casos el resultado fue el óptimo o muy cercano a él. Por lo que concluimos que si el problema no es muy crítico en cuanto a la optimalidad de la solución, es recomendable el método heurístico y en caso contrario el exacto.
Para brindar un entorno de ejecución práctico al problema se realizó el desarrollo de un prototipo de aplicación que encapsula los dos métodos y presenta una interfaz con varias secciones que contienen funcionalidades para generar instancias del problema, ejecutar ambos métodos y realizar mediciones de los resultados. A partir del trabajo realizado se compararon soluciones obtenidas de distintas instancias y ejecuciones mediante ambos métodos. Si bien el tiempo de resolución del método exacto resultó en la mayoría de los casos superior al tiempo requerido por el método heurístico, la ventaja del primer método es que se está seguro de que el resultado es óptimo, mientras que para el método heurístico no se puede asegurar nada sobre la optimalidad de la solución si no conoce cuál es el valor óptimo. Sin embargo, con el método heurístico desarrollado, además de reducir los tiempos se comprobó que en la mayoría de los casos el resultado fue el óptimo o muy cercano a él. Por lo que concluimos que si el problema no es muy crítico en cuanto a la optimalidad de la solución, es recomendable el método heurístico y en caso contrario el exacto.
Descripción:
Editorial:
UR. FI-INCO,
EN:
Financiadores:
Citación:
GARCÍA TROISI, D., PAOLINI, L., TASSINO, V. "Modelado de asignación de becas con restricciones sectoriales". Tesis de grado, Universidad de la República (Uruguay). Facultad de Ingeniería. Instituto de Computación, 2011.
Citación:
metadata.cc.license.name:
Documento del Gobiberno:
URI:
http://hdl.handle.net/20.500.12008/3014
ISBN:
e-ISBN:
ISSN:
ISMN:
Otros identificadores:
Título Obtenido:
Ingeniero en Computación
Facultad o Servicio que otorga el Título:
Universidad de la República (Uruguay). Facultad de Ingeniería. Instituto de Computación
Licencia:
Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)
Cobertura geográfica:
Cobertura temporal:
metadata.dc.relation.IsVersionOf:
Clasificación:
Es versión de:
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| tg-dgarcia.pdf | — | 1.63 MB | Adobe PDF |