Divisez en équipes par optimisation de combinaison

Qu'est-ce que c'est

Dans l'article de Master Apprentices, "[Résoudre les équipes d'ateliers comme un problème d'optimisation de combinaison](http://odapeth.blogspot.jp/2017/06/ blog-post.html) »a été formulé et résolu.

problème

Je veux diviser ** 6 personnes ** (P, Q, R, S, T, U) en ** 3 équipes ** (A, B, C). Je veux rendre les quatre capacités de communication et leur total ** égal ** autant que possible. Voir l'article original pour plus de détails.

Tableau des scores des capacités de communication

La capacité de communication des six personnes est notée comme suit pour chaque contrôleur, promoteur, supporter et analyseur. Par exemple, la capacité de contrôleur de M. P est de 6 points.

python


import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvars, addbinvars
But= pd.DataFrame([[6,0,1,3],[2,-1,3,5],[2,4,0,0],[3,4,5,0],[0,2,1,4],[2,3,-1,1]],
    columns='Analyseur de support de contrôleur de promoteur'.split(),index=list('PQRSTU'))
Nombre d'équipes,Nombre de membres= 3,But.shape[0]
print(But)
Contrôleur Promoteur Supporteur Analyseur
P 6 0 1 3
Q 2 -1 3 5
R 2 4 0 0
S 3 4 5 0
T 0 2 1 4
U 2 3 -1 1

Formuler et résoudre en Python

Afin de le rendre aussi uniforme que possible, il serait bon que la variation puisse être minimisée, mais si elle est formulée docilement, elle devient non linéaire (quadratique) et difficile à résoudre. Nous avons un petit nombre d'équipes cette fois, alors minimisons la différence entre le maximum et le minimum. Empiriquement, si le nombre de groupes est petit, l'effet est similaire à la dispersion minimale. Ici, le poids de la variation au sein d'une équipe est de 1 et le poids de la variation entre les équipes est de 1,5.

python


m = LpProblem() #Modèle mathématique
x = np.array(addbinvars(Nombre de membres,Nombre d'équipes)) #allocation
y = np.array(addvars(Nombre d'équipes,2)) #Minimum et maximum dans l'équipe
z = addvars(2) #Minimum et maximum entre équipes
m += lpSum(y[:,1]-y[:,0]) + 1.5*(z[1]-z[0]) #Fonction objective
for i in range(Nombre de membres):
    m += lpSum(x[i]) == 1 #Appartiennent à une équipe
for j in range(Nombre d'équipes):
    m += lpDot(But.sum(1),x[:,j]) >= z[0]
    m += lpDot(But.sum(1),x[:,j]) <= z[1]
    for k in range(But.shape[1]):
        m += lpDot(But.iloc[:,k],x[:,j]) >= y[j,0]
        m += lpDot(But.iloc[:,k],x[:,j]) <= y[j,1]
m.solve() #Solution
Résultat x= np.vectorize(value)(x)
print(['ABC'[i] for i in (Résultat x@range(Nombre d'équipes)).astype(int)])
>>>
['C', 'A', 'A', 'B', 'C', 'B']

J'ai eu la même division que l'article original. (Dans l'article original, c'était une solution approximative, mais c'est une solution stricte)

Veuillez noter que la méthode de minimisation de la différence entre le maximum et le minimum est une approche qui n'est pas bonne pour le solveur à usage général utilisé cette fois, de sorte que le temps de calcul augmente fortement à grande échelle. Dans ce cas, il sera plus facile à résoudre si vous le modifiez pour qu'il y ait une pénalité s'il sort d'une certaine plage.

référence

c'est tout

Recommended Posts

Divisez en équipes par optimisation de combinaison
Diviser en équipes par optimisation de combinaison (minimiser l'écart moyen)
Diviser en équipes par optimisation de combinaison (méthode de cuisson)
Optimisation du regroupement par combinaison
Résolution de "cubes en cubes" avec optimisation des combinaisons
Déterminer le programme enregistré par optimisation de combinaison
Penser les menus par l'optimisation des combinaisons
Méthode gagnante des courses de chevaux par optimisation des combinaisons
Utiliser l'optimisation des combinaisons
Décidons le cours de date par optimisation de combinaison
Juger la finition du mahjong par l'optimisation des combinaisons
[Python] Divisez les albums de Switch en dossiers par jeu
Décidons la position du service d'incendie par optimisation combinée
Enquête Star avec optimisation des combinaisons
Jeux de regroupement avec optimisation des combinaisons