In dem Artikel von Master's Apprentices heißt es: [Lösen von Workshop-Teaming als Problem der Kombinationsoptimierung](http://odapeth.blogspot.jp/2017/06/ blog-post.html) ”wurde formuliert und gelöst.
Ich möchte ** 6 Personen ** (P, Q, R, S, T, U) in ** 3 Teams ** (A, B, C) aufteilen. Ich möchte die vier Kommunikationsfähigkeiten und ihre Gesamtzahl ** gleichmäßig ** so weit wie möglich machen. Einzelheiten finden Sie im Originalartikel.
Die Kommunikationsfähigkeit der sechs Personen wird für jeden Controller, Promotor, Unterstützer und Analysator wie folgt bewertet. Zum Beispiel beträgt die Controller-Fähigkeit von Herrn P 6 Punkte.
python
import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvars, addbinvars
Ergebnis= 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='Controller Promotor Supporter Analyzer'.split(),index=list('PQRSTU'))
Anzahl der Teams,Anzahl der Mitglieder= 3,Ergebnis.shape[0]
print(Ergebnis)
| Controller | Promoter | Unterstützer | Analysator | |
|---|---|---|---|---|
| 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 |
Um es so einheitlich wie möglich zu machen, wäre es gut, wenn die Variation minimiert werden könnte, aber wenn sie gehorsam formuliert wird, wird sie nichtlinear (quadratisch) und schwer zu lösen. Wir haben diesmal eine kleine Anzahl von Teams, also lasst uns den Unterschied zwischen dem Maximum und dem Minimum minimieren. Wenn die Anzahl der Gruppen gering ist, ähnelt der Effekt empirisch der minimalen Dispersion. Hier beträgt das Variationsgewicht innerhalb eines Teams 1 und das Variationsgewicht zwischen Teams 1,5.
python
m = LpProblem() #Mathematisches Modell
x = np.array(addbinvars(Anzahl der Mitglieder,Anzahl der Teams)) #Zuweisung
y = np.array(addvars(Anzahl der Teams,2)) #Minimum und Maximum im Team
z = addvars(2) #Minimum und Maximum zwischen Teams
m += lpSum(y[:,1]-y[:,0]) + 1.5*(z[1]-z[0]) #Zielfunktion
for i in range(Anzahl der Mitglieder):
m += lpSum(x[i]) == 1 #Gehören zu einem Team
for j in range(Anzahl der Teams):
m += lpDot(Ergebnis.sum(1),x[:,j]) >= z[0]
m += lpDot(Ergebnis.sum(1),x[:,j]) <= z[1]
for k in range(Ergebnis.shape[1]):
m += lpDot(Ergebnis.iloc[:,k],x[:,j]) >= y[j,0]
m += lpDot(Ergebnis.iloc[:,k],x[:,j]) <= y[j,1]
m.solve() #Lösung
Ergebnis x= np.vectorize(value)(x)
print(['ABC'[i] for i in (Ergebnis x@range(Anzahl der Teams)).astype(int)])
>>>
['C', 'A', 'A', 'B', 'C', 'B']
Ich habe die gleiche Aufteilung wie der Originalartikel. (Im ursprünglichen Artikel war es eine ungefähre Lösung, aber dies ist eine strenge Lösung)
Bitte beachten Sie, dass die Methode zur Minimierung der Differenz zwischen dem Maximum und dem Minimum ein Ansatz ist, der für den diesmal verwendeten Allzwecklöser nicht geeignet ist, sodass die Berechnungszeit in großem Maßstab stark zunimmt. In diesem Fall ist es einfacher zu lösen, wenn Sie es so ändern, dass es eine Strafe gibt, wenn es außerhalb eines bestimmten Bereichs liegt.
Referenz
das ist alles
Recommended Posts