| UBA - CienciaS http://ubacs.com.ar/ubacs/ |
|
| Problema: Dividir clubes en grupos por cercanía geográfica http://ubacs.com.ar/ubacs/viewtopic.php?f=279&t=3271 |
Página 1 de 1 |
| Autor: | hertzu [ 29 Dic 2014, 21:33 ] |
| Asunto: | Problema: Dividir clubes en grupos por cercanía geográfica |
Hola, cómo están? Espero que no caiga mal que mi primer post sea pidiendo una mano con un problema, es algo que se me presentó en la vida real y me propuse resolverlo con matemática y programación antes que hacerlo al tanteo. Un poco de contexto: Se va a empezar una liga deportiva en la zona metropolitana de Buenos Aires. La primera fase será con sistema local-visitante con los clubes divididos en dos grupos A y B (los del grupo A no se enfrentan con los del grupo B). Luego habrá una segunda fase que va a ser una llave de simple eliminación a la que acceden los mejores de cada grupo. El problema es conformar los grupos de manera tal que la suma de desplazamientos sea mínima. No estoy avanzado en la carrera, quizás hay algún concepto clave para este tipo de problemas que me falta. En el secundario tuve algo de Investigación Operativa (maximización, minimización, Método Simplex) y pensé que iba por ese lado. Después investigué el Algoritmo de Dijkstra... Me gustaría poder resolverlo, alguno me orienta un poco? Saludos! Nicolás |
|
| Autor: | Quimey [ 30 Dic 2014, 03:40 ] |
| Asunto: | Re: Problema: Dividir clubes en grupos por cercanía geográfi |
Los dos grupos tienen que tener la misma cantidad de equipos? Seguro que lo podés resolver usando programación lineal entera (es como simplex pero podés agregar la restricción de que algunas variables solo pueden tomar valores enteros). El problema con esto es que puede ser bastante lento si son muchos equipos. Después pienso si hay algo mejor... Cuántos equipos son mas o menos? |
|
| Autor: | Quimey [ 30 Dic 2014, 16:20 ] |
| Asunto: | Re: Problema: Dividir clubes en grupos por cercanía geográfi |
Parecería que tu problema es bastante complicado (http://en.wikipedia.org/wiki/Maximum_cut). Lo que significa que programación lineal entera puede ser una buena opción. |
|
| Página 1 de 1 | Todos los horarios son UTC - 3 horas |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|