―― Un tournoi sportif se tiendra dans ** 8 pays **. Supposons que vous jouiez à 4 jeux pendant 7 jours. ――Il est supposé que vous connaissez le classement de popularité de la réputation précédente. ―― Autant que possible, essayez de faire correspondre la paire populaire en seconde période et créez un programme qui vous mettra mal à l'aise jusqu'à la fin.
Résolvons ce problème avec Optimisation de combinaison.
Soit les variables 0-1 variables qui représentent «choisir et choisir» la combinaison pour le pays 1, le pays 2 et le jour.
Aussi, le "poids du match un jour (k) avec deux pays (i, j)" correspondant à la variable est le suivant. En maximisant la somme de ces pondérations, les «correspondances entre les pays ayant un classement inférieur» seront priorisées.
| Maximiser | $ \ sum_i {weight _i x_i} $ | somme des poids |
| Variables | $ x_i \ in \ {0, 1 \} ~ ~ \ forall i \ in Candidate $ | Sélection de ce candidat td> |
| Contraintes | $ \ sum_ {i \ in j, k paires ~~~~~} {x_i} = 1 ~ ~ \ forall j, k \ in \ mbox {country} $ | Un dans la même paire |
| $ \ sum_ {i \ in Day k y compris le pays j ~~~~~~~~~~~~~} {x_i} = 1 ~ ~ \ forall j \ in \ mbox {Country }, \ forall k \ in \ mbox {day} $ | Le même jour, un |
Commencez par créer un tableau de combinaisons.
python3
import pandas as pd
from itertools import combinations, product
from pulp import *
ss = 'Italie Pays-Bas Japon Corée Thaïlande République dominicaine Pérou Kazakhstan'.split()
rnk = {s:(i+1) for i, s in enumerate(ss)} #Nom du pays → classement
a = pd.DataFrame([(i, j, k, 2**k/rnk[i]/rnk[j]) for i, j in combinations(ss, 2)
for k in range(7)], columns='Pays 1 Pays 2 jours Poids'.split())
a[:3]
>>>
Pays 1 Pays 2 jours Poids
0 Italie Pays-Bas 0 0.5
1 Italie Pays-Bas 1 1.0
2 Italie Pays-Bas 2 2.0
Formulons et résolvons-le.
python3
m = LpProblem(sense=LpMaximize) #Modèle mathématique
a['Var'] = [LpVariable('v%d'%i, cat=LpBinary) for i in a.index] #variable
m += lpDot(a.poids, a.Var) #Fonction objective
for _, b in a.groupby(['Pays 1', 'Pays 2']):
m += lpSum(b.Var) == 1 #Un dans le même groupe
for s, i in product(ss, range(7)):
#Le même pays, un le même jour
m += lpSum(a.query('(Pays 1=="{0}" |Pays 2=="{0}") &journée=={1}'.format(s, i)).Var) == 1
m.solve() #Solution
a['Val'] = a.Var.apply(value) #résultat
#afficher
for i, b in a.groupby('journée'):
print(i+1, 'journée')
for _, r in b[b.Val > 0].iterrows():
print(' %*s - %s'%(8-len(r.Pays 1), r.Pays 1, r.Pays 2))
>>>
Premier jour
Italie-Kazakhstan
Pays-Bas-Pérou
Japon-République Dominicaine
Corée-Thaïlande
le 2ème jour
Italie-Pérou
Pays-Bas-Kazakhstan
Japon-Thaïlande
Corée-République Dominicaine
Troisième jour
Italie-République Dominicaine
Pays-Bas-Thaïlande
Japon-Kazakhstan
Corée-Pérou
Jour 4
Italie-Thaïlande
Pays-Bas-République Dominicaine
Japon-Pérou
Corée-Kazakhstan
Jour 5
Italie-Corée
Pays-Bas-Japon
Thaïlande-Kazakhstan
République Dominicaine-Pérou
Jour 6
Italie-Japon
Pays-Bas-Corée
Thaïlande-Pérou
République Dominicaine-Kazakhstan
Jour 7
Italie-Pays-Bas
Japon-Corée
Thaïlande-République Dominicaine
Pérou-Kazakhstan
Le programme de chaque jour était sorti.
Une autre méthode peut être une combinaison de différences de force dans la première moitié et une combinaison de différences de force concurrentielle dans la seconde moitié.
Temporairement, je lance mon dernier article sur Python sur Arukas.
c'est tout
Recommended Posts