[PYTHON] Coordinateur et plan linéaire entier

À partir du coordinateur soumis, j'ai formulé et résolu la combinaison optimale de déjeuners sous forme de plan linéaire entier.

Je l'ai résolu avec un package d'optimisation python appelé PuLP.

Cet article est très facile à comprendre comment utiliser PuLP. http://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17

Exigences

Tout d'abord, passons à l'ajustement.

** ・ Assurez-vous de participer à un horaire par personne ** ** ・ Égalisez le nombre de personnes pour chaque horaire autant que possible **

Faisons de notre mieux pour formuler cela.

Premier, $ P $ = (ensemble de membres) $ D $ = (ensemble de dates) ça ira.

Pour $ p \ dans P, d \ dans D $

\mathrm{hope}[p][d] = \left\{
\begin{array}{ll}
1 & (p devient d ○) \\
0 & (p devient d ×)
\end{array}
\right.

Et décidez de la constante à partir du résultat de M. Ajustement.

Ensuite, définissez les variables.

$ \ mathrm {attend} [p] [d] = (1or0) $ est une variable qui indique si $ p $ participe réellement à $ d $. $ M $ est le nombre maximum de participants pour chaque horaire. En visant à minimiser cela, il est possible d'attribuer un nombre uniforme de personnes à chaque horaire.

Une fois formulé, cela ressemble à ceci.

\begin{align}
\mathrm{min} &\ M \\
\mathrm{s.t} \ &\forall d\in D\ \Sigma_{p \in P}\mathrm{hope}[p][d]\times \mathrm{attend}[p][d] \leq M \\
&\forall p\in P\ \Sigma_{d \in D}\mathrm{hope}[p][d]\times \mathrm{attend}[p][d] = 1

\end{align}

La première formule de la condition de contrainte est que le nombre de participants est M ou moins chaque jour. La deuxième expression de la condition de contrainte est que chaque personne ne doit participer qu'une seule fois.

Faisons ça dur.

code

chousei.py

import pulp

date = ["3/8", "3/9", "3/11", "3/15"]
people = #Mettez une liste de noms de membres ici

_table = [
[1,1,1,1], 
[0,1,0,0],
[1,1,0,0],
[0,1,1,0],
[1,0,0,0],
[1,1,0,1],
[1,0,0,0],
[0,1,0,1],
[0,1,1,0],
[1,1,1,1],
[1,1,1,1],
[1,1,0,0],
[1,0,0,1],
[0,1,1,1],
[0,1,0,0],
[1,1,1,1]] #Écrivez le résultat de M. Ajustement


table = {}
for i,p in enumerate(people):
    table[p] = {}
    for j,d in enumerate(date):
        table[p][d] = _table[i][j]
#Convertir en type de dictionnaire

problem = pulp.LpProblem('chousei', pulp.LpMinimize)
attend = pulp.LpVariable.dicts('attend', (people, date), 0, 1, 'Binary')
M = pulp.LpVariable('M', 0, 1000, 'Integer')
problem += M

for p in people:
    each_people = 0
    for d in date:
        each_people += table[p][d]*attend[p][d]
    problem += each_people == 1

for d in date:
    each_date = 0
    for p in people:
        each_date += table[p][d]*attend[p][d]
    problem += each_date <= M

problem.solve()

for d in date:
    each_date = ''
    for p in people:
        if(table[p][d] == 1　and attend[p][d].value() > 0):
            each_date += p
    print "{}: {}".format(d, each_date)

Amélioration

À ce rythme, il est possible que seuls les anciens aient un horaire fixe, donc je pense que c'est une bonne idée de donner du poids à chaque membre et de minimiser la limite supérieure de la somme des poids pour chaque horaire. .. Je l'expliquerai quand j'en aurai envie.