Résolvons le problème introduit dans Association par optimisation de combinaison avec un autre modèle.
Ce problème est un problème d'optimisation de combinaison qui minimise la variabilité. La variance est généralement utilisée comme un indice du degré de variation, mais comme la variance est représentée par une fonction quadratique, elle est plus difficile que le problème de programmation linéaire qui minimise la fonction linéaire. Par conséquent, dans l'article d'origine, il est formulé comme un problème de planification linéaire qui minimise la différence (plage) entre la valeur maximale et la valeur minimale.
D'autre part, il existe également un moyen de minimiser l'écart moyen au lieu de la plage. Par conséquent, dans cet article, nous allons d'abord comparer les différences entre les modèles de plage et d'écart moyen. Enfin, résolvons l'exemple du problème de minimisation de l'écart moyen avec Python + PuLP.
Par conséquent, la politique de base de la fonction objectif est la suivante.
$$
\ text {minimiser} \ quad \ sum_ {j = 1} ^ m (\ text {variation au sein de l'équipe $ j
Vous pouvez également pondérer et équilibrer l'une ou l'autre des variations.
Nous formulerons le problème. Tout d'abord, définissez les variables suivantes.
\begin{align}
n &:Nombre de membres\\
m &:Nombre d'équipes\\
l &:Nombre de compétences\\
x_{i,j} &:Affectation du membre i à l'équipe j(\in \{0,1\}) \\
a_{i,k} &:Score de compétence k du membre I\\
b_i &:Somme de toutes les compétences du membre i(=\sum_{k=1}^l a_{i,k}) \\
\end{align}
Utilisez la différence (plage) entre les valeurs maximale et minimale comme indicateur de variation et minimisez-la.
ici,
\begin{align}
y_{j,\min}, y_{j,\max} &:Compétences minimales et maximales dans l'équipe j\\
z_\min, z_\max &:Minimum et maximum entre équipes
\end{align}
Ensuite, il peut être formulé comme un problème de minimisation de plage comme suit.
\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}
L'équation (1.4) est une équation de contrainte qui indique que chaque membre appartient à une seule équipe. Selon l'article d'origine, le poids de 1,5 est appliqué à la variation entre les équipes. Il comporte un petit nombre de variables et peut être formulé très simplement.
En supposant que $ x_i $ est une valeur individuelle et que $ \ bar {x} $ est sa moyenne, la variance et l'écart moyen peuvent être exprimés comme suit:
L'écart moyen contient une valeur absolue et est évité car non différentiable et difficile à calculer, mais il peut être facilement supprimé si la fonction objectif du problème d'optimisation contient une valeur absolue.
La réécriture de l'équation (0,1) en utilisant l'écart moyen donne:
\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}
Un tel problème de minimisation de valeur absolue peut être transformé en un problème de planification linéaire comme suit en introduisant les variables auxiliaires $ y_ {j, k}, , z_j $.
\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}
Par rapport au modèle de minimisation de plage, le nombre de variables est plus grand, ce qui rend le modèle un peu plus compliqué.
Résolvons l'exemple en utilisant le package PuLP de Python.
PuLP vous permet de sélectionner un solveur, mais ici, nous utiliserons le Coin-CBC par défaut.
import numpy as np
import pandas as pd
from pulp import *
from ortoolpy import addvar, addvars, addbinvars
#exemple
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) #Nombre d'équipes
nmembers = len(scores.index) #Nombre de membres
nskills = len(scores.columns) #Nombre de types de capacités
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
Veuillez vous référer à Article original.
#Minimiser l'écart moyen
m = LpProblem() #Modèle mathématique
x = pd.DataFrame(addbinvars(nmembers, nteams), index=members, columns=teams) #allocation
y = pd.DataFrame(addvars(nteams, nskills), index=teams, columns=skills) #Écart moyen au sein de l'équipe
mu = pd.DataFrame(addvars(nteams), index=teams) #Moyenne au sein de l'équipe
z = pd.DataFrame(addvars(nteams), index=teams) #Écart moyen par équipe
nu = addvar() #Moyenne pour toutes les équipes
m.setObjective(lpSum([lpSum(y.loc[j]) + 1.5*z.loc[j] for j in teams])) #Fonction objective
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) #Appartiennent à une équipe
m.solve() #Solution
if m.status:
for i, xi in enumerate(np.vectorize(value)(x).tolist()):
print((members[i], teams[xi.index(1)]))
else:
print('La solution optimale n'a pas pu être obtenue.')
#résultat:(membre,équipe)
# ('P', 'B')
# ('Q', 'A')
# ('R', 'A')
# ('S', 'C')
# ('T', 'B')
# ('U', 'C')
J'ai eu la même solution que l'article original. Il est arrivé qu'ils étaient les mêmes parce que je résolvais un autre modèle.
Nous avons abordé la question de la minimisation de l'écart moyen. Ce modèle peut être utilisé, par exemple, dans l'optimisation de portefeuille. Dans l'optimisation du portefeuille, la variation des rendements attendus est considérée comme un risque et formulée comme un problème de minimisation du risque, mais à ce moment-là, l'écart moyen peut être minimisé. Cependant, dans le cas de problèmes de programmation d'entiers (problèmes d'optimisation de combinaison, problèmes d'optimisation discrète) dans lesquels des entiers sont inclus dans les variables de décision, le problème devient difficile à résoudre à mesure que l'échelle du problème augmente. Le problème que j'ai abordé cette fois n'était que de "diviser 20 personnes en 5 équipes", et il est devenu difficile de le résoudre en un temps réaliste sur mon PC (je ne peux pas le résoudre même si je le laisse du jour au lendemain). L'utilisation d'un solveur commercial comme Gurobi ou CPLEX comme solveur peut être une amélioration significative, en particulier dans un environnement multicœur, mais cela peut encore être difficile à résoudre à grande échelle. Dans ce cas, vous pouvez revoir le modèle ou utiliser une solution approximative.
[Suite] Comme solution approximative à ce problème, je vais vous présenter comment le résoudre en utilisant le package Python simanneal pour la méthode de recuit. Division des équipes par optimisation des combinaisons (méthode de cuisson)
Recommended Posts