Problème combinatoire : 10 équipes et 15 jeux — Les-mathematiques.net The most powerful custom community solution in the world

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

Réponses

  • Salut.

    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
  • Bonjour et merci pour ta réponse.
    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
  • J'ai fait quelques petits calculs, mais je trouve que ce que tu veux est impossible avec seulement $10$ équipes.

    Soit, des équipes vont répéter un jeu, soit, des équipes vont se rencontrer plus de deux fois.

    Cordialement
  • Je propose la solution suivante, où les équipes sont numérotées de 0 à 9. Le tableau se lit ainsi : au tour 4, les équipes 9 et 0 s'affrontent au jeu 6.
    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).
               Jeu  1  Jeu  2  Jeu  3  Jeu  4  Jeu  5  Jeu  6  Jeu  7  Jeu  8  Jeu  9  Jeu 10  Jeu 11  Jeu 12  Jeu 13  Jeu 14  Jeu 15 
    Tour  1 :  (6, 2)  (7, 0)  (8, 5)  (4, 3)  ------  ------  ------  ------  ------  ------  ------  ------  ------  (9, 1)  ------ 
    Tour  2 :  ------  (3, 1)  ------  (5, 0)  (4, 2)  ------  (7, 6)  (9, 8)  ------  ------  ------  ------  ------  ------  ------ 
    Tour  3 :  (5, 1)  ------  (7, 6)  ------  ------  (9, 0)  ------  ------  ------  ------  ------  (8, 4)  ------  (3, 2)  ------ 
    Tour  4 :  ------  ------  (3, 2)  ------  (7, 5)  (6, 4)  ------  ------  ------  ------  (8, 0)  ------  ------  ------  (9, 1) 
    Tour  5 :  ------  (6, 2)  (1, 0)  ------  ------  ------  ------  ------  ------  (8, 3)  (5, 4)  ------  (9, 7)  ------  ------ 
    Tour  6 :  (7, 0)  ------  (9, 4)  ------  (8, 1)  ------  ------  (6, 3)  ------  ------  ------  ------  ------  ------  (5, 2) 
    Tour  7 :  ------  (8, 4)  ------  ------  (6, 3)  ------  (5, 0)  (7, 1)  (9, 2)  ------  ------  ------  ------  ------  ------ 
    Tour  8 :  (4, 3)  (9, 5)  ------  ------  ------  ------  (8, 1)  ------  (6, 0)  (7, 2)  ------  ------  ------  ------  ------ 
    Tour  9 :  ------  ------  ------  ------  ------  (7, 1)  ------  (5, 4)  ------  ------  (9, 6)  (3, 0)  (8, 2)  ------  ------ 
    Tour 10 :  ------  ------  ------  ------  (9, 0)  ------  (4, 2)  ------  ------  ------  (7, 3)  (5, 1)  ------  (8, 6)  ------ 
    Tour 11 :  ------  ------  ------  (9, 2)  ------  ------  ------  ------  (7, 4)  (1, 0)  ------  ------  (6, 5)  ------  (8, 3) 
    Tour 12 :  ------  ------  ------  (8, 7)  ------  (5, 3)  ------  ------  ------  ------  (2, 1)  (9, 6)  ------  (4, 0)  ------ 
    Tour 13 :  ------  ------  ------  ------  ------  ------  (9, 3)  ------  (8, 5)  ------  ------  (7, 2)  (4, 1)  ------  (6, 0) 
    Tour 14 :  (9, 8)  ------  ------  ------  ------  ------  ------  (2, 0)  (3, 1)  (6, 4)  ------  ------  ------  (7, 5)  ------ 
    Tour 15 :  ------  ------  ------  (6, 1)  ------  (8, 2)  ------  ------  ------  (9, 5)  ------  ------  (3, 0)  ------  (7, 4) 
    
  • Waouh ! J'ai vérifié, ça marche ! Merci beaucoup !
    Juste par curiosité, quelle est la méthode suivie ?
    Merci beaucoup,
    David
  • L'idée consiste à traduire le problème en un système linéaire gigantesque ($15\times15\times45$ inconnues) dont il faut trouver une solution entière, ce que l'ordinateur sait faire efficacement (quelques secondes).

    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.
  • Merci beaucoup concernant ces précisions ! Juste pour savoir, quel type d'algo est utilisé ? Du Constraint Programming ? Du LP ?
  • Il s'agit bien de programmation linéaire en nombres entiers dont la vache à lait a l'air d'être l'algorithme du simplexe (du moins si on enlève « nombres entiers »). En réalité, je ne sais pas. J'ai utilisé ce module de Sage qui renvoie à un module interactif développé à des fins pédagogiques.
  • Ok super un grand merci pour toutes ces informations très intéressantes ! J'ai essayé d'implémenter ça sous R (lpSolve), mais sans succès. Je dois avoir un problème au niveau des contraintes, à revoir. Si tu as le temps, peux-tu me lister les contraintes que tu as utilisées ?
    Un grand merci en tous cas pour les infos !
    David
  • Voici le code. Ça a l'air indigeste mais il y a plus de commentaires que d'instructions. La syntaxe est en Python mais il est fait pour tourner sur Sage (plate-forme libre de calcul formel et plus).
    # 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)
    
  • Ok merci, je vais regarder ça de plus près, pour trouver où mes contraintes sont trop restrictives. Simple question, pourquoi "à chaque tour au plus 5 jeu occupés à la fois", et non pas exactement 5 ?
  • Pourquoi $\le5$ au lieu de $=5$ ? Je ne sais pas, c'est sans doute indifférent, c'est peut-être une mauvaise idée en principe.
  • D'accord merci.
    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 ?
  • Le diable est dans les détails. Poste ton code à tout hasard ? (Je ne connais pas R donc je risque fort de ne pas savoir quoi faire mais bon.)
  • Voici mon code. C'est un peu difficile de s'y retrouver, surtout si tu ne connais pas R, mais au cas où tu trouves le bug, je serais ravi ! J'ai pas mal étudié les matrices/listes/contraintes que je définis, a priori c'est bon à ce niveau là... Je me demande juste si c'est pas "méthodologiquement" que j'ai mal interprété une contrainte.


    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)
    
    
  • En regardant d'encore plus près, la derniere contrainte (# chaque equipe joue exactement une fois a chaque jeu) me semblait un peu louche. Et en l'enlevant, mon problème admet une solution (en enlevant les autres contraintes toujours pas de solution). Je regarde ça, le problème vient de là à mon avis
  • C'est un peu abscons en effet... En tout cas, dans le paragraphe que tu évoques où « chaque équipe joue exactement une fois a chaque jeu », je ne vois pas trace des variables de jeu ni de tour, ce qui me laisse penser qu'elles jouent le même rôle. Or il faudrait faire une contrainte par jeu, que l'on fixe, et pour chacune sommer sur les tours.
  • J'ai corrigé ça... maintenant ça ne s'arrête pas au bout d'une demie-seconde en me disant qu'il n'y a pas de solution... mais ça tourne depuis des heures sans solution. Peut être qu'utiliser un solveur lp en dimension d = 15*15*45 = 10125 n'est pas une bonne solution ? Sachant que 75 sur les 10125 variables valent 1, peut-être vaut il mieux faire du greedy search jusqu'à ce que les contraintes soient toutes valides (ce qui peut être rapide si elles sont faciles à atteindre, mais infinement long autrement) ?
  • Cela suggère qu'il y a un autre problème (du même genre ?). La résolution sur Sage prend moins de trente secondes :
    Time: CPU 21.42 s, Wall: 21.42 s
    
    Il m'est arrivé très souvent de mouliner indéfiniment pour des problèmes de planning analogues parce qu'il n'est pas facile ou pas possible pour le "solver" de détecter qu'il n'y a pas de solution. C'était presque toujours à cause d'une mauvaise spécification des contraintes.

    Bravo pour la ténacité ! Ça va converger !
  • D'accord c'est peut-être toujours ça qui coince alors ! Je ne m'y connais pas vraiment en programmation linéaire et en simplexe, mais il me semblait qu'effectivement c'était un algo qui passait outre l'augmentation de la dimension !

    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 ;) !
  • Bonjour j'ai quasiment le même problème pour 10 équipes aussi mais 9 ou 10 jeux
    est ce possible de résoudre mon problème?
    merci
  • Peut-être – c'est dimanche, c'est fête ! – mais il faut préciser l'ensemble des règles (combien d'équipes, combien de jeux, combien d'équipe par jeu, combien de tours ?) et des contraintes.
  • 2 équipes par jeu
    et 9 tours je pense
  • En effet, difficile de faire plus de neuf tours s'il y a dix équipes sans que les équipes se rencontrent plusieurs fois. Ceci devrait donner une façon de procéder.
               Jeu 0  Jeu 1  Jeu 2  Jeu 3  Jeu 4  Jeu 5  Jeu 6  Jeu 7  Jeu 8
    Tour 1 :  (9, 8) (3, 2) (5, 0) (7, 6) ------ ------ (4, 1) ------ ------
    Tour 2 :  (4, 2) ------ (3, 1) (8, 5) (7, 0) (9, 6) ------ ------ ------
    Tour 3 :  (6, 1) ------ (9, 7) (4, 0) (8, 2) ------ (5, 3) ------ ------
    Tour 4 :  ------ ------ (8, 4) (9, 3) (5, 1) ------ (6, 0) ------ (7, 2)
    Tour 5 :  ------ (8, 0) ------ (2, 1) (9, 4) ------ ------ (7, 3) (6, 5)
    Tour 6 :  (3, 0) (6, 4) ------ ------ ------ (5, 2) (8, 7) (9, 1) ------
    Tour 7 :  ------ (9, 5) ------ ------ (6, 3) (7, 4) ------ (2, 0) (8, 1)
    Tour 8 :  (7, 5) ------ ------ ------ ------ (1, 0) (9, 2) (8, 6) (4, 3)
    Tour 9 :  ------ (7, 1) (6, 2) ------ ------ (8, 3) ------ (5, 4) (9, 0)
    
    Voilà, c'est 1 bitcoin, service compris.
  • Merci beaucoup vous êtes top!!!
  • Vive la programmation linéaire !
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!