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. TECH__MASTER_3月ランチ会___調整さん_と_pandas_get_dummies_—_pandas_0_19_2_documentation.png

** ・ 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.

Recommended Posts

Coordinateur et plan linéaire entier
Programmation linéaire avec PuLP
Programmation avec Python et Tkinter
division des nombres réels python (/) et division des nombres entiers (//)
Programmation linéaire + pratique de la pulpe
Méthode de programmation linéaire par méthode de marqueur de voiture
Liste des solveurs et modélisateurs de conception linéaire (LP) disponibles en Python
[Introduction à Python3 Jour 1] Programmation et Python
Faites la programmation Let et Let's One-Line
Avec les types de données algébriques et la programmation orientée objet