[PYTHON] 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)

• Le même groupe sera dans la même pièce.
• Attribuez du numéro de groupe le plus jeune au numéro de chambre le plus jeune. --Si vous souhaitez placer les groupes a et b (a <b) dans les numéros de pièce c et d respectivement, c <= d doit être satisfait.
• Une salle peut accueillir jusqu'à 63 personnes.

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.

• Comme il est difficile de résoudre le solveur lorsque la valeur maximale est minimisée, c'est une contrainte.

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