[PYTHON] 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)

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

• Regroupement par optimisation de combinaison
• Regroupement des jeux par optimisation de combinaison

c'est tout