Problème combinatoire : 10 équipes et 15 jeux
Bonjour à tous,
J'ai un petit problème combinatoire que je n'arrive pas à résoudre. Si jamais quelqu'un a une idée de la solution, ou d'un algorithme capable de la découvrir, je serais très intéressé...
10 équipes s'affrontent, autour de 15 jeux différents. Pour chaque jeu, deux équipes s'affrontent simultanément (donc simultanément, 5 jeux/15 sont occupés).
J'aimerais obtenir une solution telle que :
-Chaque équipe ait joué exactement une fois à chaque jeu
-Deux équipes aient joué au moins une fois l'une contre l'autre, au plus deux fois
La première condition fait qu'il faut exactement 15 parties, ce qui est compatible avec la 2ème condition. Cependant, je n'arrive pas à savoir comment organiser le "calendrier des rencontres" pour obtenir une telle solution, si elle existe bien entendu.
Si jamais quelqu'un a une idée, je serais ravi !
Merci d'avance,
David
J'ai un petit problème combinatoire que je n'arrive pas à résoudre. Si jamais quelqu'un a une idée de la solution, ou d'un algorithme capable de la découvrir, je serais très intéressé...
10 équipes s'affrontent, autour de 15 jeux différents. Pour chaque jeu, deux équipes s'affrontent simultanément (donc simultanément, 5 jeux/15 sont occupés).
J'aimerais obtenir une solution telle que :
-Chaque équipe ait joué exactement une fois à chaque jeu
-Deux équipes aient joué au moins une fois l'une contre l'autre, au plus deux fois
La première condition fait qu'il faut exactement 15 parties, ce qui est compatible avec la 2ème condition. Cependant, je n'arrive pas à savoir comment organiser le "calendrier des rencontres" pour obtenir une telle solution, si elle existe bien entendu.
Si jamais quelqu'un a une idée, je serais ravi !
Merci d'avance,
David
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
La deuxième condition ne peut pas se réaliser en $15$ parties, car $\binom{10}{2} = 45\gt 15$.
Je pense alors que tes deux conditions sont incompatibles.
Babacar
Cordialement
Je me suis mal exprimé. Par "partie" j'entends "journée" dans un championnat de foot par exemple. Appelons cela un "tour". Dans mon cas, comme tu le dis la deuxième condition stipule qu'il faut au moins 9 tours pour que chaque équipe ait joué contre une autre (45/5). Au delà de 18 tours, des équipes auront nécessairement joué plus de deux fois l'une contre l'autre.
Le but est de trouver 15 tours tels que deux équipes aient joué une ou deux fois l'une contre l'autre, et que chacune ait joué exactement une fois à chaque jeu.
David
Soit, des équipes vont répéter un jeu, soit, des équipes vont se rencontrer plus de deux fois.
Cordialement
Il serait prudent de vérifier par sondage aléatoire qu'elle satisfait aux contraintes.
En fichiers attachés, ce tableau et les listes par équipes (ce sont des fichiers .txt renommés en .tex).
Juste par curiosité, quelle est la méthode suivie ?
Merci beaucoup,
David
Plus précisément, on définit une inconnue A[t,j,p] par triplet (t,j,p) où t est un numéro de tour, j un numéro de jeu et p un numéro de paire (parmi les $\frac{10\times9}{2}$ paires existantes) : elle vaut 1 si la paire p se rencontre au tour t à l'épreuve du jeu j. Les contraintes s'expriment par des équations et des inéquations linéaires. Par exemple, pour dire qu'à un tour t, il y a au plus une paire pour chaque jeu j, il suffit d'écrire que la somme des A[t,j,p] (sur toutes les paires p) est $\le1$.
Voir ici pour un programme explicite d'un problème analogue.
Un grand merci en tous cas pour les infos !
David
# numérotation des paires paires = [(i,j) for i in range(10) for j in range(i)] print paires # sortie (tronquée) : [(1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), etc. # repérage des paires qui contiennent une équipe donnée D = [[l for l in range(len(paires)) if k in paires[l]] for k in range(10)] # exemple print D[0] # sortie : [0, 1, 3, 6, 10, 15, 21, 28, 36] # sens : les paires d'indice 0, 1, 3, 6, etc. contiennent un 0, pas les autres # on en vient au fait # déclaration d'un problème pb = MixedIntegerLinearProgram() # déclaration d'un tableau d'inconnues à valeurs dans {0,1} # sens : A[t,j,p] = 1 ssi au tour t, les deux équipes de la paire p s'affrontent au jeu j A = pb.new_variable(binary=True) # quelques constantes : nb d'équipes, de tours, de jeux, de paires E, T, J, P = 15, 15, 45 for t in range(T): for j in range(J): # à chaque tour et sur chaque jeu, # au plus une paire d'équipes en train de s'affronter pb.add_constraint(add(A[t,j,p] for p in range(P))<=1) for e in range(10): # à chaque tour, une équipe joue au plus à un jeu pb.add_constraint(add(A[t,j,p] for j in range(J) for p in D[e])<=1) # à chaque tour, au plus 5 jeu occupés à la fois (sans doute impliqué par le précédent ?) pb.add_constraint(add(A[t,j,p] for j in range(J) for p in range(P))<=5) for e in range(10): for j in range(J): # chaque équipe joue exactement une fois à chaque jeu pb.add_constraint(add(A[t,j,p] for p in D[e] for t in range(T))==1) for p in range(P): # chaque paire d'équipe se rencontre au moins une fois et au plus deux fois pb.add_constraint(add(A[t,j,p] for t in range(T) for j in range(J))>=1) pb.add_constraint(add(A[t,j,p] for t in range(T) for j in range(J))<=2) # il n'y a plus qu'à résoudre pb.solve() A = pb.get_values(A)J'ai revu mon code, j'ai trouvé des bugs que j'ai corrigés, mais ça ne fonctionne toujours pas, aucune solution n'est trouvée, le problème semble trop contraint.
J'ai implémenté les contraintes suivantes :
- A chaque tour, chaque jeu est occupé au plus une fois
- A chaque tour, 5 jeux sont occupés (j'ai également essayé avec <=)
- Deux équipes se rencontrent soit une fois, soit deux fois
- Chaque équipe joue exactement une fois à chaque jeu
- Au total, il y a 75 rencontres.
Même en enlevant certaines contraintes, il n'y a pas de solution. Vois-tu une erreur dans mes contraintes ?
library(lpSolve) # parametres n.jeux<-15 n.tours<-15 n.equipes<-10 n.paires<-n.equipes*(n.equipes-1)/2 d<-n.jeux*n.tours*n.paires # DEFINITION ET REMPLISSAGE DES MATRICES paire2equipe<-matrix(0,n.paires,2) indexation<-matrix(0,d,3) # la ligne i de paire2equipe correspond # aux deux equipes (dans 1,n.equipes) de la paire i cpt<-1 for (i in 1:(n.equipes-1)){ for (j in (i+1):n.equipes){ paire2equipe[cpt,]<-c(i,j) cpt<-cpt+1 } } # chaque ligne de indexation correspond # a un tour, un jeu et une paire cpt<-1 for (i in 1:n.tours){ for (j in 1:n.jeux){ for (k in 1:n.paires){ indexation[cpt,]<-c(i,j,k) cpt<-cpt+1 } } } # LISTES POUR FAIRE LE LIEN AVEC LA MATRICE INDEXATION # double liste pour faire le lien avec la matrice indexation # la premiere liste contient un tour i # la deuxieme liste contient, pour le tour i considere, le jeu j # les 45 fois (n.paires) ou apparaissent le tour i et le jeu j sont dans la liste tour.jeu.constant<-vector("list",n.tours) for (i in 1:n.tours){ tour.jeu.constant[[i]]<-vector("list",n.jeux) for (j in 1:n.jeux){ tour.jeu.constant[[i]][[j]]<-which(indexation[,1]==i & indexation[,2]==j) } } # liste qui contient les indices de indexation correspondant au meme tour tour.constant<-vector("list",n.tours) for (i in 1:n.tours){ tour.constant[[i]]<-which(indexation[,1]==i) } # liste qui contient les indices de indexation correspondant au meme match paire.constante<-vector("list",n.paires) for (i in 1:n.paires) paire.constante[[i]]<-which(indexation[,3]==i) # liste qui contient les indices de indexation correspondant a une equipe donnee equipe.constante<-vector("list",n.equipes) for (i in 1:n.equipes){ dans.paire<-which(paire2equipe[,1]==i | paire2equipe[,2]==i) equipe.constante[[i]]<-which(indexation[,3]%in%dans.paire) } # DEFINITION DES CONTRAINTES # a chaque tour, chaque jeu est occupe au plus une fois contrainte.un.jeu.par.tour<-matrix(0,n.tours*n.jeux,d) for (i in 1:(n.tours*n.jeux)){ div<-(i-1)%/%n.jeux+1 reste<-(i-1)%%n.jeux+1 contrainte.un.jeu.par.tour[i,tour.jeu.constant[[div]][[reste]]]<-1 } rhs.un.jeu.par.tour<-rep(1,n.tours*n.jeux) dir.un.jeu.par.tour<-rep("<=",n.tours*n.jeux) # a chaque tour, 5 jeux sont occupes contrainte.chaque.tour<-matrix(0,n.tours,d) for (i in 1:n.tours) contrainte.chaque.tour[i,tour.constant[[i]]]<-1 rhs.chaque.tour<-rep(5,n.tours) dir.chaque.tour<-rep("==",n.tours) # on retrouve soit une fois, soit deux fois chaque paire contrainte.rencontres.entre.paires<-matrix(0,2*n.paires,d) for (i in 1:n.paires) contrainte.rencontres.entre.paires[c(i,i+n.paires),paire.constante[[i]]]<-1 rhs.rencontres.entre.paires<-c(rep(1,n.paires),rep(2,n.paires)) dir.rencontres.entre.paires<-c(rep(">=",n.paires),rep("<=",n.paires)) # chaque equipe joue exactement une fois a chaque jeu contrainte.chaque.equipe.chaque.jeu<-matrix(0,n.equipes,d) for (i in 1:n.equipes) contrainte.chaque.equipe.chaque.jeu[i,equipe.constante[[i]]]<-1 rhs.chaque.equipe<-rep(1,n.equipes) dir.chaque.equipe<-rep("==",n.equipes) # Programme LP a resoudre # On concatene les matrices, directions et rhs de contraintes # Ajout de la contrainte "il y a 75 rencontres en tout" const.mat<-do.call(rbind,list(contrainte.un.jeu.par.tour,contrainte.chaque.tour,contrainte.rencontres.entre.paires,contrainte.chaque.equipe.chaque.jeu,matrix(1,1,d))) const.dir<-c(dir.un.jeu.par.tour,dir.chaque.tour,dir.rencontres.entre.paires,dir.chaque.equipe,"==") const.rhs<-c(rhs.un.jeu.par.tour,rhs.chaque.tour,rhs.rencontres.entre.paires,rhs.chaque.equipe,n.tours*n.equipes/2) sol<-lp(direction="min",objective.in=rep(1,d),const.mat=const.mat,const.dir=const.dir,const.rhs=const.rhs,all.bin=TRUE)Bravo pour la ténacité ! Ça va converger !
Merci, c'est le côté matheux qui m'emporte : j'aurais pu me contenter de ta solution, mais j'ai voulu apprendre, comprendre, et réussir à le faire tourner par moi-même ! Mais avant tout, un grand merci à toi, pour tes réponses et conseils
est ce possible de résoudre mon problème?
merci
et 9 tours je pense