UBACS Q&A Foro WikiCS
Fecha actual 26 May 2024, 01:48

Todos los horarios son UTC - 3 horas




 Página 1 de 1 [ 4 mensajes ] 
Autor Mensaje
 Asunto: Problema: Dividir clubes en grupos por cercanía geográfica
NotaPublicado: 29 Dic 2014, 21:33 
Vago

Registrado: 29 Dic 2014, 20:54
Mensajes: 1
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


Desconectado
 Perfil  
 
 Asunto: Re: Problema: Dividir clubes en grupos por cercanía geográfi
NotaPublicado: 30 Dic 2014, 03:40 
1er Licenciado
Avatar de Usuario

Registrado: 05 Jul 2008, 14:02
Mensajes: 1166
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?



_________________
Quimey
Desconectado
 Perfil  
 
 Asunto: Re: Problema: Dividir clubes en grupos por cercanía geográfi
NotaPublicado: 30 Dic 2014, 16:20 
1er Licenciado
Avatar de Usuario

Registrado: 05 Jul 2008, 14:02
Mensajes: 1166
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.



_________________
Quimey
Desconectado
 Perfil  
 
Mostrar mensajes previos:  Ordenar por  
 Página 1 de 1 [ 4 mensajes ] 

Todos los horarios son UTC - 3 horas


¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 1 invitado


No puede abrir nuevos temas en este Foro
No puede responder a temas en este Foro
No puede editar sus mensajes en este Foro
No puede borrar sus mensajes en este Foro
No puede enviar adjuntos en este Foro

Buscar:
Saltar a:  

cron