[PYTHON] Gruppierung nach Kombinationsoptimierung

Problem

Es gibt 26 Gruppen, die jeweils aus folgenden Personen bestehen.

python3

import numpy as np
n = 26 #Anzahl der Gruppen
np.random.seed(11)
a = np.random.randint(10, 20, n) #Anzahl der Personen pro Gruppe
for i in range(n):
    print('Gruppe%2d %d Menschen'%(i, a[i]))
>>>
Gruppe 0 19 Personen
Gruppe 1 10 Personen
Gruppe 2 11 Personen
Gruppe 3 17 Personen
Gruppe 4 11 Personen
Gruppe 5 17 Personen
Gruppe 6 12 Personen
Gruppe 7 18 Personen
Gruppe 8 10 Personen
Gruppe 9 10 Personen
Gruppe 10 14 Personen
Gruppe 11 12 Personen
Gruppe 12 11 Personen
Gruppe 13 15 Personen
Gruppe 14 15 Personen
Gruppe 15 17 Personen
Gruppe 16 14 Personen
Gruppe 17 11 Personen
Gruppe 18 18 Personen
Gruppe 19 18 Personen
Gruppe 20 11 Personen
Gruppe 21 13 Personen
Gruppe 22 16 Personen
Gruppe 23 12 Personen
Gruppe 24 12 Personen
Gruppe 25 10 Personen

――26 Teilen Sie die Gruppe in 6 Räume (0, 1, 2, 3, 4, 5). (Mehrere Gruppen in einem Raum)

• Die gleiche Gruppe befindet sich im selben Raum.
• Weisen Sie die jüngste Gruppennummer der jüngsten Zimmernummer zu.
• Wenn Sie die Gruppen a und b (a <b) in die Raumnummern c bzw. d einfügen möchten, muss c <= d erfüllt sein.
• Ein Zimmer bietet Platz für bis zu 63 Personen.

Wo soll ich die Gruppe aufteilen?

Versuchen Sie mit Python zu lösen

Formulieren und lösen Sie ein Problem der Kombinationsoptimierung.

python3

from pulp import *
limit = 63 #Raumkapazität
m = LpProblem() #Mathematisches Modell
#Anzahl der Räume bis zu dieser Gruppe
x = [LpVariable('x%d'%i, lowBound=a[i], upBound=limit) for i in range(n)]
#Gibt an, ob der Raum in vordere und hintere Gruppen unterteilt werden soll
y = [LpVariable('y%d'%i, cat=LpBinary) for i in range(n-1)]
m += lpSum(x) #Zielfunktion
m += lpSum(y) <= 6-1 #Anzahl der Räume=6 oder weniger(Die Pause ist 6-1)
for i in range(n-1):
    m += x[i+1] >= x[i] + a[i+1] - limit * y[i] #Fügen Sie die Anzahl der Personen im selben Raum hinzu
m.solve() #Lösung
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]

――Wenn die Dispersion das Minimum ist, wird sie nichtlinear und schwer zu lösen.

• Da es schwierig ist, den Löser zu lösen, wenn der Maximalwert minimiert ist, ist dies eine Einschränkung.

Ich habe mich auf CodeIQ bezogen. [Im täglichen Leben verborgene Optimierungsprobleme] Algorithmus, der die Prüflinge so gleichmäßig wie möglich dem Prüfungsort zuordnet

das ist alles