Lösen wir das in Teaming durch Kombinationsoptimierung eingeführte Problem mit einem anderen Modell.
Dieses Problem ist ein Kombinationsoptimierungsproblem, das die Variabilität minimiert. Die Varianz wird im Allgemeinen als Index für den Variationsgrad verwendet, aber da die Varianz durch eine quadratische Funktion dargestellt wird, ist sie schwieriger als das lineare Programmierproblem, das die lineare Funktion minimiert. Daher wird es im Originalartikel als lineares Planungsproblem formuliert, das die Differenz (den Bereich) zwischen dem Maximalwert und dem Minimalwert minimiert.
Andererseits gibt es auch eine Möglichkeit, die mittlere Abweichung anstelle des Bereichs zu minimieren. Daher werden wir in diesem Artikel zunächst die Unterschiede zwischen den Modellen für den Bereich und die mittlere Abweichung vergleichen. Lassen Sie uns abschließend das Beispiel des Problems der Minimierung der mittleren Abweichung mit Python + PuLP lösen.
Daher ist die Grundpolitik der Zielfunktion wie folgt.
$$
\ text {minimieren} \ quad \ sum_ {j = 1} ^ m (\ text {Variation innerhalb des Teams $ j
Sie können auch jede Variation wiegen und ausgleichen.
Wir werden das Problem formulieren. Definieren Sie zunächst die folgenden Variablen.
\begin{align}
n &:Anzahl der Mitglieder\\
m &:Anzahl der Teams\\
l &:Anzahl der Fähigkeiten\\
x_{i,j} &:Zuordnung von Mitglied i zu Team j(\in \{0,1\}) \\
a_{i,k} &:Mitglied i's Skill k Score\\
b_i &:Summe aller Fähigkeiten des Mitglieds i(=\sum_{k=1}^l a_{i,k}) \\
\end{align}
Verwenden Sie die Differenz (den Bereich) zwischen den Maximal- und Minimalwerten als Indikator für Abweichungen und minimieren Sie diese.
Hier,
\begin{align}
y_{j,\min}, y_{j,\max} &:Minimale und maximale Fähigkeiten im Team j\\
z_\min, z_\max &:Minimum und Maximum zwischen Teams
\end{align}
Dann kann es wie folgt als Entfernungsminimierungsproblem formuliert werden.
\begin{align}
\text{minimize} \quad &\sum_{j=1}^m (y_{j \max} -y_{j \min}) + 1.5 (z_\max - z_\min) \tag{1.1}\\
\text{subject to} \quad & y_{j \min} \leq \sum_{i=1}^n a_{i,k} x_{i,j} \leq y_{j \max} &j=1,\ldots,m;\, k=1,\ldots,l \tag{1.2}\\
& z_\min \leq \sum_{i=1}^n b_i x_{i,j} \leq z_\max &j=1,\ldots,m \tag{1.3}\\
&\sum_{j=1}^m x_{i,j} = 1 &i=1,\ldots,n \tag{1.4}\\
& x_{i,j} \in \{0,1\} &i=1,\ldots,n;\, j=1,\ldots,m \tag{1.5}\\
\end{align}
Gleichung (1.4) ist eine Einschränkungsgleichung, die angibt, dass jedes Mitglied zu einem Team gehört. Gemäß dem ursprünglichen Artikel wird das Gewicht von 1,5 auf die Variation zwischen den Teams angewendet. Es hat eine kleine Anzahl von Variablen und kann sehr einfach formuliert werden.
Unter der Annahme, dass $ x_i $ ein Einzelwert und $ \ bar {x} $ sein Durchschnitt ist, können die Varianz und die durchschnittliche Abweichung wie folgt ausgedrückt werden:
Die durchschnittliche Abweichung enthält einen absoluten Wert und wird vermieden, da sie nicht unterscheidbar und schwer zu berechnen ist. Sie kann jedoch leicht entfernt werden, wenn die Zielfunktion des Optimierungsproblems einen absoluten Wert enthält.
Das Umschreiben der Gleichung (0.1) unter Verwendung der durchschnittlichen Abweichung ergibt:
\begin{align}
\text{minimize} \quad &\sum_{j=1}^m \Bigl(\sum_{k=1}^l \Bigl|\sum_{i=1}^n a_{i,k} x_{i,j} - \mu_j \Bigr|\Bigr) + 1.5\sum_{j=1}^m\Bigl|\sum_{i=1}^n b_i x_{i,j} -\nu\Bigr| \tag{2.1}\\
\text{subject to} \quad &\mu_j = \frac{1}{l}\sum_{k=1}^l\sum_{i=1}^n a_{i,k}x_{i,j} &j=1,\ldots,m \tag{2.2}\\
& \nu = \frac{1}{m} \sum_{j=1}^m \sum_{i=1}^n b_i x_{i,j} \tag{2.3}\\
&\sum_{j=1}^m x_{i,j} = 1 &i=1,\ldots,n \tag{2.4}\\
& x_{i,j} \in \{0,1\} &i=1,\ldots,n;\, j=1,\ldots,m \tag{2.5}\\
\end{align}
Ein solches Absolutwertminimierungsproblem kann wie folgt in ein lineares Planungsproblem umgewandelt werden, indem die Hilfsvariablen $ y_ {j, k}, , z_j $ eingeführt werden.
\begin{align}
\text{minimize} \quad &\sum_{j=1}^m \Bigl(\sum_{k=1}^l y_{j,k} + 1.5 z_j\Bigr) \tag{2.6}\\
\text{subject to} \quad & -y_{j,k} \leq \sum_{i=1}^n a_{i,k} x_{i,j} - \mu_j \leq y_{j,k} & j=1,\dots,m;\,k=1,\ldots,l \tag{2.7}\\
& -z_j \leq \sum_{i=1}^n b_i x_{i,j} -\nu \leq z_j & j=1,\ldots,m \tag{2.8}\\
&\mu_j = \frac{1}{l}\sum_{k=1}^l\sum_{i=1}^n a_{i,k}x_{i,j} &j=1,\ldots,m \tag{2.9}\\
& \nu = \frac{1}{m} \sum_{j=1}^m \sum_{i=1}^n b_i x_{i,j} \tag{2.10}\\
&\sum_{j=1}^m x_{i,j} = 1 &i=1,\ldots,n \tag{2.11}\\
& x_{i,j} \in \{0,1\} &i=1,\ldots,n;\, j=1,\ldots,m \tag{2.12}\\
\end{align}
Im Vergleich zum Bereichsminimierungsmodell ist die Anzahl der Variablen größer, was das Modell etwas komplizierter macht.
Lösen wir das Beispiel mit dem PuLP-Paket von Python.
Mit PuLP können Sie einen Solver auswählen, aber hier verwenden wir die Standard-Coin-CBC.
import numpy as np
import pandas as pd
from pulp import *
from ortoolpy import addvar, addvars, addbinvars
#Beispiel
teams = ['A', 'B', 'C']
members = ['P', 'Q', 'R', 'S', 'T', 'U']
skills = ['Controller', 'Promoter', 'Supporter', 'Analyzer']
scores = 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]],
index=members,
columns=skills)
nteams = len(teams) #Anzahl der Teams
nmembers = len(scores.index) #Anzahl der Mitglieder
nskills = len(scores.columns) #Anzahl der Fähigkeitstypen
print(scores)
# Controller Promoter Supporter Analyzer
# 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
Weitere Informationen finden Sie unter Originalartikel.
#Minimieren Sie die durchschnittliche Abweichung
m = LpProblem() #Mathematisches Modell
x = pd.DataFrame(addbinvars(nmembers, nteams), index=members, columns=teams) #Zuweisung
y = pd.DataFrame(addvars(nteams, nskills), index=teams, columns=skills) #Durchschnittliche Abweichung innerhalb des Teams
mu = pd.DataFrame(addvars(nteams), index=teams) #Durchschnitt im Team
z = pd.DataFrame(addvars(nteams), index=teams) #Durchschnittliche Abweichung pro Team
nu = addvar() #Durchschnitt für alle Teams
m.setObjective(lpSum([lpSum(y.loc[j]) + 1.5*z.loc[j] for j in teams])) #Zielfunktion
m.addConstraint(lpSum(np.dot(scores.sum(1), x)) / nteams == nu)
for j in teams:
m.addConstraint(lpDot(scores.sum(1), x[j]) - nu <= z.loc[j])
m.addConstraint(lpDot(scores.sum(1), x[j]) - nu >= -z.loc[j])
m.addConstraint(lpSum(np.dot(x[j], scores)) / nskills == mu.loc[j])
for k in skills:
m.addConstraint(lpDot(scores[k], x[j]) - mu.loc[j] <= y.loc[j,k])
m.addConstraint(lpDot(scores[k], x[j]) - mu.loc[j] >= -y.loc[j,k])
for i in members:
m.addConstraint(lpSum(x.loc[i]) == 1) #Gehören zu einem Team
m.solve() #Lösung
if m.status:
for i, xi in enumerate(np.vectorize(value)(x).tolist()):
print((members[i], teams[xi.index(1)]))
else:
print('Die optimale Lösung konnte nicht erhalten werden.')
#Ergebnis:(Mitglied,Mannschaft)
# ('P', 'B')
# ('Q', 'A')
# ('R', 'A')
# ('S', 'C')
# ('T', 'B')
# ('U', 'C')
Ich habe die gleiche Lösung wie der Originalartikel. Es kam vor, dass sie gleich waren, weil ich ein anderes Modell löste.
Wir haben uns mit der Minimierung der durchschnittlichen Abweichung befasst. Dieses Modell kann beispielsweise bei der Portfoliooptimierung verwendet werden. Bei der Portfoliooptimierung wird die Variation der erwarteten Renditen als Risiko angesehen und als Risikominimierungsproblem formuliert. Zu diesem Zeitpunkt kann die durchschnittliche Abweichung jedoch minimiert werden. Bei ganzzahligen Programmierproblemen (Kombinationsoptimierungsprobleme, diskrete Optimierungsprobleme), bei denen ganze Zahlen in den Entscheidungsvariablen enthalten sind, wird das Problem jedoch mit zunehmendem Umfang des Problems schwierig zu lösen. Das Problem, das ich dieses Mal aufgegriffen habe, bestand nur darin, "20 Personen in 5 Teams aufzuteilen", und es wurde schwierig, es in einer realistischen Zeit auf meinem PC zu lösen (ich kann es nicht lösen, selbst wenn ich es über Nacht lasse). Die Verwendung eines kommerziellen Lösers wie Gurobi oder CPLEX als Löser kann eine erhebliche Verbesserung darstellen, insbesondere in einer Mehrkernumgebung, kann jedoch in großem Maßstab schwierig zu lösen sein. In diesem Fall können Sie das Modell überprüfen oder die ungefähre Lösungsmethode verwenden.
[Fortsetzung] Als ungefähre Lösung für dieses Problem werde ich vorstellen, wie es mit dem Python-Paket simanneal für die Glühmethode gelöst werden kann. Separate Teams durch Kombinationsoptimierung (Backmethode)
Recommended Posts