Jak znaleźć optymalne przydzielenie uczniów na zajęciach?

Question

23 uczniów z poziomu A, 24 z poziomu B i 30 z poziomu C należy przypisać do trzech klas. Klasy muszą być prawie dokładnie tego samego rozmiaru. Różne poziomy można łączyć w jedną klasę, ale lepiej, jeśli można tego uniknąć. W każdym przypadku powinno być albo 0 uczniów z jednego poziomu w klasie, albo więcej niż 6.

Czy możesz mi pomóc rozwiązać ten kombinatoryczny problem optymalizacji? Poniżej znajduje się przykładowe wejście i wyjście. Dodatkowe punkty, jeśli możesz mi pokazać, jak rozwiązać ogólny problem!

wejściowe: (! Nie bardzo dobry)

pupils = { "A" : 23, "B" : 24, "C": 30 } 

Przykâadowa

Class #1 : {'A': 9, 'B': 6, 'C': 10}, 
Class #2 : {'A': 10, 'B': 9, 'C': 7}, 
Class #3 : {'A': 11, 'B': 9, 'C': 6} 

Edit: Here jest moim bardzo hackish, całkowicie nieudokumentowane, kod semi-bruteforce. To brzydkie, ale działa! Chciałbym nauczyć się, jak napisać bardziej eleganckie rozwiązanie.

Answer 1

Podstawową trudność polega na tym, że masz problem z optymalizacją wielu obiektów. Masz trzy rzeczy, myślę, że jesteś zainteresowany, że można albo rozważyć cele i ograniczenia „miękkie”:

1. Pierwsze podobna klasa rozmiarach
2. Minimalizowanie liczby poziomów w klasie
3. Mając wystarczająco dużo studentów z poziom w klasie, jeśli w klasie są uczniowie.

Zauważ, że napisałem model optymalizacji dla tego w AMPL. Ponieważ używasz Pythona, istnieją podobne języki do modelowania optymalizacji dla Pythona, takie jak PuLP i pyomo, których możesz użyć. Model nie powinien być zbyt trudny do przetłumaczenia.

Oto model programowania integer i plik danych, który podkreśla obiektyw numer 1 przy zachowaniu liniowości problemu (liczby całkowitej). W tym celu problem optymalizacji znajduje to samo rozwiązanie, które podałeś w swoim przykładzie. Mam nadzieję, że można na tym oprzeć i dodać inne ograniczenia i/lub warunki obiektywne i uzyskać lepsze rozwiązania.

Celem jest zminimalizowanie największej wielkości klasy. Zmienna zainteresowania to y [i, j]. y [i, j] dla i w POZIOMIE, j w KLASIE to liczba uczniów z poziomu i przypisanych do klasy j. Zakłada on, że masz dane wejściowe dla minimalnej liczby uczniów z każdego poziomu w każdej klasie, jeśli są oni przypisani do tego poziomu.

Funkcja celu może nie być tym, czego potrzebujesz, ale jest to sposób na wyrównanie rozmiarów klas, które są liniowe. Nie obiecuję też, że jest to najskuteczniejszy sposób rozwiązania problemu. Może istnieć lepszy niestandardowy algorytm dla problemu, ale wszystko, co musiałem zrobić, to wyrazić ograniczenia i cel, a nie pisać algorytmu. Jest prawdopodobnie wystarczająco dobry do twojego użytku.

Korzystanie z solver Gurobi na serwerze neos.org (można użyć lpsolve lub inny open source optymalizacji Solver), mam rozwiązanie

y := 
1 1 14 
1 2 9 
1 3 0 
2 1 6 
2 2 0 
2 3 18 
3 1 6 
3 2 16 
3 3 8 
; 

Model:

set LEVEL ordered; 
set CLASS; 

param maxClassSize {CLASS}; 
param minLevelNumberInClass {LEVEL, CLASS}; 
param numInLevel {LEVEL}; 

var z >= 0; 
var y{LEVEL, CLASS} integer, >= 0; 
var x{LEVEL, CLASS} binary; 

#minimize maximum class size 
minimize obj: 
    z; 

subject to allStudentsAssigned {i in LEVEL}: 
    sum {j in CLASS} y[i,j] = numInLevel[i]; 

#z is the largest of all classes sizes 
subject to minMaxZ {j in CLASS}: 
    z >= sum {i in LEVEL} y[i,j]; 

subject to maxClassSizeCon {j in CLASS}: 
    sum {i in LEVEL} y[i,j] <= maxClassSize[j]; 

#xij = 1 if any students from level i are in class j 
subject to defineX {i in LEVEL, j in CLASS}: 
    y[i,j] <= min(numInLevel[i], maxClassSize[j]) * x[i,j]; 

#if any students from level i are assigned to class j, then there is a minimum 
#if x[i,j] = 1, y[i,j] >= minLevelNumberInClass[i,j] 
subject to minLevel {i in LEVEL, j in CLASS}: 
    minLevelNumberInClass[i,j] * x[i,j] <= y[i,j]; 

plik danych dla przykładu:

set LEVEL := 1 2 3; 
set CLASS := 1 2 3; 

param minLevelNumberInClass: 
    1 2 3 := 
1 6 6 6 
2 6 6 6 
3 6 6 6 
; 

param maxClassSize := 
1 77 
2 77 
3 77 
; 

param numInLevel := 
1 23 
2 24 
3 30 
;