Pouvez-vous résoudre les horaires sportifs?

Problème d'horaire sportif

Ravi de vous rencontrer, tout le monde! J'écrirai l'article d'aujourd'hui. Immédiatement, cette fois, je voudrais écrire sur le problème d'horaire sportif. Prenons le football comme exemple, mais comment décidez-vous d'un programme de football? En regardant la ligue J1, 18 équipes ont un bon équilibre entre domicile et extérieur! Créer un tel planning est en fait le même que le problème d'optimisation! Cette fois, résolvons ce problème de planification en utilisant la pulpe de Python!

Problème de réglage

Planifiez une ligue de 6 équipes et 10 matchs. Par condition, la maison et l'extérieur ne sont pas autorisés trois fois de suite. La maison est 5 fois pour chaque équipe! !! Si la saison d'ouverture est à la maison, la saison de fermeture est loin! !! Et vice versa! !! Nous organiserons cet horaire pour minimiser la distance parcourue par l'équipe.

Tout d'abord, la préparation

python


from pulp import *
import numpy as np
#Réunion d'équipe
team = ["A", "Y", "T","K","O","H"]
print("Ensemble d'équipe I= {:}".format(team))

#Ensemble de clauses
setu = ["1", "2", "3", "4", "5","6","7","8","9","10"]

print("Ensemble de clauses setu= {:}".format(setu))



#distance
cc = [
      [ "H","T","O","Y","K","H","T","O","Y","K"],
      [ "O","H","K","A","T","O","H","K","A","T"],
      [ "K","A","H","O","Y","K","A","H","O","Y"],
      [ "T","O","Y","H","A","T","O","Y","H","A"],
      [ "Y","K","A","T","H","Y","K","A","T","H"],
      [ "A","Y","T","K","O","A","Y","T","K","O"],
     ]

c2 = [
      [ 912,100,528,130,116,912,100,528,130,116],
      [ 488,792,16,130,35,488,792,16,130,35],
      [ 20,100,810,506,35,20,100,810,506,35],
      [ 20,500,16,804,116,20,500,16,804,116],
      [ 488,500,528,506,330,488,500,528,506,330],
      [ 912,792,810,804,330,912,792,810,804,330],
     ]

c={}
for t in team:
    for s in setu:
        c[t,s]=c2[team.index(t)][setu.index(s)]
        
co={}
for t in team:
    for s in setu:
        co[t,s]=cc[team.index(t)][setu.index(s)]
        
print("Match c[t,s]: ")
for t in team:
    for s in setu:
        print("c[{:},{:}] = {:}, ".format(t, s, c[t,s]), end = "")

    print("")
print("")

L'équipe a amené mon équipe préférée de la ligue J1! cc est un cortège d'équipes en compétition, partant de la rangée du haut, dans l'ordre des équipes A, Y, T, K, O, H. Je suppose qu'il y a 10 colonnes dans certaines sections. Mettez les distances dans le tableau de c. En co, mettez l'équipe de combat.

Sujet principal

python



#Déclaration du problème
SportsScheduling = pulp.LpProblem("SportsScheduling", pulp.LpMinimize) #Défini comme le plus petit problème

#Déclaration de variable
x = {}
for t in team:
    for s in setu:
        x[t, s] = pulp.LpVariable("x({:},{:})".format(t,s), 0, 1, pulp.LpInteger )

#Fonction objective
SportsScheduling += pulp.lpSum( c[t,s]*x[t,s]  for t in team for s in setu), "TotalCost"




#Contraintes
for t in team:
    SportsScheduling += x[t,"1"]+x[t,"2"]+x[t,"3"]  >= 1 
    SportsScheduling += x[t,"2"]+x[t,"3"]+x[t,"4"]  >= 1 
    SportsScheduling += x[t,"3"]+x[t,"4"]+x[t,"5"]  >= 1 
    SportsScheduling += x[t,"4"]+x[t,"5"]+x[t,"6"]  >= 1 
    SportsScheduling += x[t,"5"]+x[t,"6"]+x[t,"7"]  >= 1 
    SportsScheduling += x[t,"6"]+x[t,"7"]+x[t,"8"]  >= 1 
    SportsScheduling += x[t,"7"]+x[t,"8"]+x[t,"9"]  >= 1 
    SportsScheduling += x[t,"8"]+x[t,"9"]+x[t,"10"]  >= 1 
    
    SportsScheduling += x[t,"1"]+x[t,"2"]+x[t,"3"]  <= 2 
    SportsScheduling += x[t,"2"]+x[t,"3"]+x[t,"4"]  <= 2 
    SportsScheduling += x[t,"3"]+x[t,"4"]+x[t,"5"]  <= 2 
    SportsScheduling += x[t,"4"]+x[t,"5"]+x[t,"6"]  <= 2
    SportsScheduling += x[t,"5"]+x[t,"6"]+x[t,"7"]  <= 2 
    SportsScheduling += x[t,"6"]+x[t,"7"]+x[t,"8"]  <= 2 
    SportsScheduling += x[t,"7"]+x[t,"8"]+x[t,"9"]  <= 2 
    SportsScheduling += x[t,"8"]+x[t,"9"]+x[t,"10"]  <= 2 
    
#Alignement avec les adversaires
for t in team:
    for s in setu:
        SportsScheduling += x[co[t,s],s]+x[t,s]  == 1 

for t in team:
    SportsScheduling += sum(x[t,s] for s in setu) <= 5
    
for t in team:
     SportsScheduling += x[t,"1"]+x[t,"10"] == 1   
    
SportsScheduling.solve()

Je pense que c'est le plus important. Cela me rend somnolent. .. .. .. Définissez la variable. 0 pour la maison et 1 pour l'extérieur. Vous pouvez obtenir la distance en multipliant la distance précédente par cette variable. La maison ne bouge pas, donc 0. Multipliez par 1 pour vous éloigner.

Par contrainte, si trois matchs consécutifs valent 1 ou plus et 2 ou moins, la maison à l'extérieur ne sera pas trois fois de suite. De plus, par exemple, X jouera contre Y. Dans ce cas, l'un ou l'autre doit être égal à 1 et l'un ou l'autre doit être égal à 0. pour cette raison. Nous avons également mis cette contrainte afin de faire cette correspondance.

5 matchs sur 10 sont à domicile, donc 5 ou moins sont requis. Ajoutez 1 aux clauses d'ouverture et de clôture.

Les conditions sont maintenant réunies! !! !! !! !!

Voyons le résultat!


for t in team:
    for s in setu:
        print("x[{:},{:}] = {:} ".format(t, s, x[t,s]), end = "")
    print("")
print("")

print("La formule en question")
print("--------")
print(SportsScheduling)
print("--------")
print("")




print("Résultat du calcul")
print("")

print("Solution x[i,j]: ")
for t in team:
    for s in setu:
        print("{:},  "
              .format( x[t,s].value()), end="")
    print("")
print("")




Solution x[i,j]: 
0.0,  0.0,  1.0,  1.0,  0.0,  1.0,  1.0,  0.0,  0.0,  1.0,  
1.0,  1.0,  0.0,  0.0,  1.0,  1.0,  0.0,  0.0,  1.0,  0.0,  
0.0,  1.0,  0.0,  1.0,  0.0,  1.0,  0.0,  0.0,  1.0,  1.0,  
1.0,  0.0,  1.0,  0.0,  1.0,  0.0,  0.0,  1.0,  1.0,  0.0,  
0.0,  1.0,  0.0,  0.0,  1.0,  0.0,  1.0,  1.0,  0.0,  1.0,  
1.0,  0.0,  1.0,  1.0,  0.0,  0.0,  1.0,  1.0,  0.0,  0.0,  

............ J'ai pu le faire pour le moment w

Je pense que je peux mieux le construire. Cela semble intéressant car il semble que cela puisse aussi être un problème de minimisation de rupture!

Je voudrais m'attaquer profondément à ce problème à l'avenir!

Merci d'avoir regardé.

Nous continuerons à grandir dans le futur! Puis!

Recommended Posts

Pouvez-vous résoudre les horaires sportifs?
Pouvez-vous supprimer ce fichier?
Filtre de Kalman que vous pouvez comprendre
"Obake" peut être chanté par "you"
Python | Ce que vous pouvez faire avec Python
Programmeur 8e année [Pair ou Impair (pair ou impair)] Pouvez-vous résoudre ce problème de programmation! !!