Optimisation du regroupement par combinaison

problème

Il y a 26 groupes, chacun composé des personnes suivantes.

python3


import numpy as np
n = 26 #Nombre de groupes
np.random.seed(11)
a = np.random.randint(10, 20, n) #Nombre de personnes par groupe
for i in range(n):
    print('groupe%2d %d personnes'%(i, a[i]))
>>>
Groupe 0 19 personnes
Groupe 1 10 personnes
Groupe 2 11 personnes
Groupe 3 17 personnes
Groupe 4 11 personnes
Groupe 5 17 personnes
Groupe 6 12 personnes
Groupe 7 18 personnes
Groupe 8 10 personnes
Groupe 9 10 personnes
Groupe 10 14 personnes
Groupe 11 12 personnes
Groupe 12 11 personnes
Groupe 13 15 personnes
Groupe 14 15 personnes
Groupe 15 17 personnes
Groupe 16 14 personnes
Groupe 17 11 personnes
Groupe 18 18 personnes
Groupe 19 18 personnes
Groupe 20 11 personnes
Groupe 21 13 personnes
Groupe 22 16 personnes
Groupe 23 12 personnes
Groupe 24 12 personnes
Groupe 25 10 personnes

――26 Divisez le groupe en 6 pièces (0, 1, 2, 3, 4, 5). (Plusieurs groupes dans une pièce)

Où dois-je diviser le groupe?

Essayez de résoudre avec Python

Formulez et résolvez un problème d'optimisation de combinaison.

python3


from pulp import *
limit = 63 #Capacité de la salle
m = LpProblem() #Modèle mathématique
#Nombre de chambres jusqu'à ce groupe
x = [LpVariable('x%d'%i, lowBound=a[i], upBound=limit) for i in range(n)]
#S'il faut diviser la pièce en groupes avant et arrière
y = [LpVariable('y%d'%i, cat=LpBinary) for i in range(n-1)]
m += lpSum(x) #Fonction objective
m += lpSum(y) <= 6-1 #nombre de pièces=6 ou moins(La pause est de 6-1)
for i in range(n-1):
    m += x[i+1] >= x[i] + a[i+1] - limit * y[i] #Ajouter le nombre de personnes dans la même pièce
m.solve() #Solution
print(LpStatus[m.status])
print([int(value(x[i])) for i in range(n) if i==n-1 or value(y[i])])
>>>
Optimal
[57, 58, 57, 61, 58, 63]

――Si la dispersion est minimale, elle devient non linéaire et difficile à résoudre.

J'ai fait référence à CodeIQ. [Problèmes d'optimisation cachés dans la vie quotidienne] Algorithme qui répartit le plus uniformément possible les candidats au lieu d'examen

c'est tout

Recommended Posts

Optimisation du regroupement par combinaison
Jeux de regroupement avec optimisation des combinaisons
Résolution de "cubes en cubes" avec optimisation des combinaisons
Déterminer le programme enregistré par optimisation de combinaison
Divisez en équipes par optimisation de combinaison
Penser les menus par l'optimisation des combinaisons
Utiliser l'optimisation des combinaisons
Méthode gagnante des courses de chevaux par optimisation des combinaisons
Décidons le cours de date par optimisation de combinaison
Minimisez le nombre de polissages en optimisant la combinaison
Juger la finition du mahjong par l'optimisation des combinaisons
Diviser en équipes par optimisation de combinaison (minimiser l'écart moyen)
Diviser en équipes par optimisation de combinaison (méthode de cuisson)
Enquête Star avec optimisation des combinaisons
Optimisation combinée avec recuit quantique
Décidons la conférence de PyCon JP 2016 par optimisation de combinaison
Décidons la position du service d'incendie par optimisation combinée
Résolvez le problème des 4 couleurs grâce à l'optimisation des combinaisons
Allez voir les baleines avec l'optimisation des combinaisons
Paver la route avec l'optimisation des combinaisons
La puissance des solveurs d'optimisation combinée
Pensez à la transformation Janken par l'optimisation
Méthode de planification des expériences et optimisation des combinaisons
Optimisation SVM par la méthode de l'ensemble actif
Résolution de la théorie des jeux avec l'optimisation des combinaisons
Techniques d'optimisation combinées vues dans les puzzles
Explication du modèle d'optimisation de la production par Python
Résolution des problèmes de planification des infirmières grâce à l'optimisation des combinaisons
Trouver l'itinéraire des patrouilleurs en optimisant