[PYTHON] Résolution des problèmes de planification des infirmières grâce à l'optimisation des combinaisons

Qu'est-ce que c'est

"Résolution du problème de planification des infirmières (optimisation des équipes) avec un algorithme génétique" à [Optimisation de combinaison](http://qiita.com/ J'ai essayé de le résoudre avec SaitoTsutomu / items / bfbf4c185ed7004b5721).

Lire le tableau (demande de quart, etc.)

python

import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvars, addbinvars
from io import StringIO

a = pd.read_table(StringIO("""\
journée\t mois\t mois\t mois\t feu\t feu\t feu\t eau\t eau\t eau\t arbre\t arbre\t arbre\t or\t or\t or\t sol\t sol\t sol\t jour\t jour\t jour
Fuseau horaire\t matin\t midi\t nuit\t matin\t midi\t nuit\t matin\t midi\t nuit\t matin\t midi\t nuit\t matin\t midi\t nuit\t matin\t midi\t nuit\t matin\t midi\t nuit
Nombre de personnes requis\t2\t3\t3\t2\t3\t3\t2\t3\t3\t1\t2\t2\t2\t3\t3\t2\t4\t4\t2\t4\t4
Employé 0\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t
Employé 1\t○\t○\t○\t\t\t\t○\t○\t○\t\t\t\t○\t○\t○\t\t\t\t\t\t
Employé 2\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t○\t○\t○\t○\t○\t○
Employé 3\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○
Employé 4\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○
Employé 5\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t\t\t\t\t\t
Employé 6\t\t\t\t\t\t\t\t\t\t\t\t\t○\t○\t○\t○\t○\t○\t○\t○\t○
Employé 7\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t
Employé 8\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○\t\t\t○
Employé 9\t\t\t\t\t\t\t\t\t\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○\t○""")).T
a,a.columns = a.iloc[1:],a.iloc[0].tolist()
a.Nombre de personnes requis= a.Nombre de personnes requis.astype(int)
a.iloc[:,2:] = ~a.iloc[:,2:].isnull()
a.insert(0, 'journée', a.index.str[0])
a.reset_index(drop=True, inplace=True)
a = a.iloc[:,list(range(3,a.shape[1]))+[0,1,2]]
print(a[:3]) #Affichage des 3 premières lignes

Résoudre avec Python

"V ..." comme l'allocation V est une variable.

python

Cadre N,N employé= a.shape[0],a.shape[1]-3
Employé L= list(range(N employé))
Administrateur L= [3,5,9] #Le directeur est l'employé 3, 5, 9
C Différence du nombre de personnes requis= 10
C pas désiré= 100
C nombre minimum d'images= 1
C pénurie d'administrateurs= 100
C 1 jour 2 images= 10
m = LpProblem() #Modèle mathématique
Allocation en V= np.array(addbinvars(Cadre N,N employé))
a['V Différence du nombre de personnes requis'] = addvars(Cadre N)
V nombre minimum d'images= addvars(N employé)
a['Pénurie d'administrateurs V'] = addvars(Cadre N)
V 1 jour 2 images= addvars(N employé)
m += (C Différence du nombre de personnes requis* lpSum(a.V Différence du nombre de personnes requis)
    +C pas désiré* lpSum(a.apply(lambda r: lpDot(1-r[Employé L],Allocation en V[r.name]), 1))
    +C nombre minimum d'images* lpSum(V nombre minimum d'images)
    +C pénurie d'administrateurs* lpSum(a.Pénurie d'administrateurs V)
    +C 1 jour 2 images* lpSum(V 1 jour 2 images)) #Fonction objective
for _,r in a.iterrows():
    m += r.V Différence du nombre de personnes requis>=  (lpSum(Allocation en V[r.name]) - r.Nombre de personnes requis)
    m += r.V Différence du nombre de personnes requis>= -(lpSum(Allocation en V[r.name]) - r.Nombre de personnes requis)
    m += lpSum(Allocation en V[r.name,Administrateur L]) + r.Pénurie d'administrateurs V>= 1
for j,n in enumerate((a.iloc[:,Employé L].sum(0)+1)//2):
    m += lpSum(Allocation en V[:,j]) +V nombre minimum d'images[j] >= n #Plus de la moitié d'espoir
for _,v in a.groupby('journée'):
    for j in range(N employé):
        m += lpSum(Allocation en V[v.index,j]) -V 1 jour 2 images[j] <= 2 #Jusqu'à 2 images par jour
%time m.solve()
Résultat R= np.vectorize(value)(Allocation en V).astype(int)
a['résultat'] = [''.join(i*j for i,j in zip(r,a.columns)) for r in Rrésultat]
print('Fonction objective', value(m.objective))
print(a[['journée','Fuseau horaire','résultat']])

production

CPU times: user 7.45 ms, sys: 4.23 ms, total: 11.7 ms
Wall time: 22.8 ms
Fonction objectif 0.0
Résultat du fuseau horaire de jour
0 mois employé le matin 1 employé 5
Janvier midi Employé 3 Employé 5 Employé 7
Nuit de février Employé 1 Employé 3 Employé 4
3 Mar matin Employé 0 Employé 3
4 Mar midi Employé 3 Employé 5 Employé 7
5 Mar soir Employé 4 Employé 5 Employé 8
6 Mer matin Employé 0 Employé 5
7 Mercredi Déjeuner Employé 1 Employé 3 Employé 5
8 Mercredi soir Employé 3 Employé 4 Employé 8
9 Jeudi matin Employé 3
10 Jeudi midi Employé 5 Employé 7
11 Jeudi soir Employé 8 Employé 9
12 ven matin Employé 1 Employé 5
13 Ven Déjeuner Employé 1 Employé 7 Employé 9
14 vendredi soir Employé 5 Employé 6 Employé 8
15 sam matin Employé 0 Employé 3
16 Sam midi Employé 2 Employé 6 Employé 7 Employé 9
17 Sam Night Employé 3 Employé 4 Employé 6 Employé 9
18e matin Employé 0 Employé 9
19 midi Employé 2 Employé 3 Employé 6 Employé 9
20e nuit Employé 2 Employé 3 Employé 4 Employé 6

――Le temps de calcul était de 23 millisecondes et la solution optimale exacte a été obtenue. --La fonction objectif (somme des pénalités) est de 0 $, donc toutes les conditions sont remplies.

c'est tout

référence

• Optimisation de la combinaison - Problème typique - Problème de planification du travail