** Vous **, le membre du comité exécutif de la présentation de la recherche de la société, a décidé de créer un programme pour la présentation de la recherche.
[^ 1]: Par exemple, il est possible de calculer avec Word2Vec.
Le problème ci-dessus peut être résolu en utilisant Optimisation de combinaison. Formulons-le.
| Maximiser | $ \ sum_i {Relevance_i x_i} $ | Somme de pertinence des candidats assignés |
| Variables | $ x_i \ in \ {0, 1 \} $ | $ x_i $: $ i $ Sélectionnez le candidat Si |
| $ y_j \ in Integer supérieur ou égal à 0 $ | $ y_j $: $ j $ Nombre de sessions dans la e catégorie m | |
| $ \ sum_ {i \ in F_h} {x_i} = 1 ~ ~ ~ \ forall h \ in H $ | Chaque présentation se voit attribuer exactement un mot-clé td> | |
| $ \ sum_ {i \ in G_k} {x_i} \ le 4 y_j ~ ~ ~ \ forall k \ in C $ | Le nombre de présentations dans chaque catégorie est inférieur au nombre d'images td> |
Cependant, $ H $ est un ensemble de présentateurs, $ F_h $ est un ensemble de candidats pour le présentateur $ h $, $ C $ est un ensemble de catégories et $ G_k $ est un ensemble de candidats pour la catégorie $ k $.
Faisons la table d'application.
python3
import numpy as np, pandas as pd
from pulp import *
np.random.seed(3)
nu = 4 #Nombre de présentations par session
nr = 60 #Nombre de présentateurs
cat = 'Communication Logistique médicale Énergie électrique Génie civil Physique Chimie Algèbre Géométrique Géographie'.split() #Catégorie
ns = nr / nu #Nombre de séances
dat = [(i, j, np.random.rand()) for i in range(nr)
for j in np.random.choice(cat, np.random.randint(1, 3), replace=False)]
dat.extend([(i, 'Tout', -10) for i in range(nr)]) # Toutカテゴリの追加
a = pd.DataFrame(dat, columns=['Présentateur', 'Catégorie', 'Pertinence']) #Candidat
a['vx'] = [LpVariable('vx%d'%i, cat=LpBinary) for i in a.index] #Quelle ligne choisir
print(a[:3])
| Présentateur | Catégorie | Pertinence | vx | |
|---|---|---|---|---|
| 0 | 0 | Physique | 0.207243 | vx0 |
| 1 | 1 | puissance | 0.492636 | vx1 |
| 2 | 1 | organismes | 0.913301 | vx2 |
vx est la colonne qui correspond à la variable $ x $.
Faisons un tableau des catégories.
python3
b = pd.DataFrame(cat, columns=['Nom'])
b['vy'] = [LpVariable('vy%d'%j, cat=LpInteger, lowBound=0) for j in b.index] #Nombre de séances
print(b[:3])
| Nom | vy | |
|---|---|---|
| 0 | Communication | vy0 |
| 1 | Médical | vy1 |
| 2 | Logistique | vy2 |
vy est la colonne qui correspond à la variable $ y $.
Formulez et résolvez pour voir les affectations qui sont devenues des catégories arbitraires.
python3
m = LpProblem(sense=LpMaximize)
m += lpDot(a.Pertinence, a.vx)
m += lpSum(b.vy) == ns #Le nombre total de sessions est égal
for i in range(nr):
m += lpSum(a.vx[a.Présentateur==i]) == 1 # Présentateurは1カテゴリを選ぶ
for _, r in b.iterrows():
m += lpSum(a.vx[a.Catégorie==r.Nom]) <= r.vy * nu #L'annonce est inférieure au nombre d'images
m.solve()
a['rx'] = a.vx.apply(value) #Résultat de l'allocation
b['ry'] = b.vy.apply(value) #Résultat du nombre de sessions
print(a[(a.rx > 0)&(a.Catégorie=='Tout')])
| Présentateur | Catégorie | Pertinence | vx | rx | |
|---|---|---|---|---|---|
| 117 | 26 | facultatif | -10.0 | vx117 | 1.0 |
rx est la colonne qui est le résultat de la variable $ x $. Le présentateur "26" l'a attribué à n'importe quelle catégorie.
Regardons le nombre de présentations pour chaque catégorie.
python3
print(a.Catégorie[(a.rx>0)].value_counts())
| Catégorie | |
|---|---|
| Communication | 12 |
| puissance | 8 |
| Physique | 8 |
| Biologie | 7 |
| Géométrie | 4 |
| Génie civil | 4 |
| Logistique | 4 |
| Médical | 4 |
| Géographie | 4 |
| Chimie | 4 |
| Arbitraire | 1 |
Puisque la catégorie de biologie n'est pas un multiple de 4, le fou 26 sera ici.
c'est tout
Recommended Posts