Khó khăn cơ bản ở đây là bạn sắp xếp có vấn đề tối ưu hóa đa tính. Bạn có ba điều tôi nghĩ bạn quan tâm ở chỗ bạn có thể xem xét các mục tiêu hoặc "hạn chế mềm":
- Bắt lớp tương tự như kích thước
- Giảm thiểu số lượng mỗi lớp
- Có đủ sinh viên đến từ một cấp trong lớp nếu có bất kỳ học sinh nào trong lớp.
Lưu ý rằng tôi đã viết mô hình tối ưu hóa cho điều này trong AMPL. Vì bạn đang sử dụng Python, có các ngôn ngữ lập mô hình tối ưu hóa tương tự cho python như PuLP và pyomo mà bạn có thể sử dụng. Mô hình không nên quá khó dịch.
Đây là mô hình lập trình số nguyên và tệp dữ liệu nhấn mạnh mục tiêu số 1 trong khi vẫn giữ nguyên tuyến tính (số nguyên). Với mục tiêu này, vấn đề tối ưu hóa tìm ra cùng một giải pháp mà bạn đã đưa ra trong ví dụ của bạn. Hy vọng rằng bạn có thể xây dựng trên điều này và thêm các ràng buộc khác và/hoặc các điều kiện khách quan và có được các giải pháp tốt hơn.
Mục tiêu là giảm thiểu kích thước lớp học lớn nhất. Biến quan tâm là y [i, j]. y [i, j] đối với tôi trong LEVEL, j trong CLASS là số học sinh từ cấp độ i được chỉ định cho lớp j. Nó giả định rằng bạn có đầu vào cho số lượng sinh viên tối thiểu từ mỗi cấp trong mỗi lớp nếu có bất kỳ cấp nào được gán cho cấp đó.
Chức năng mục tiêu có thể không phải là những gì bạn muốn, nhưng đó là cách cố gắng cân bằng kích thước lớp học là tuyến tính. Tôi cũng không hứa rằng đây là cách hiệu quả nhất để giải quyết vấn đề. Có thể có một thuật toán tùy chỉnh tốt hơn cho vấn đề này, nhưng tất cả những gì tôi phải làm là thể hiện những ràng buộc và mục tiêu và không viết một thuật toán. Nó có thể đủ tốt để bạn sử dụng.
Sử dụng trình giải quyết Gurobi trên máy chủ neos.org (bạn có thể sử dụng lpsolve này hay cách khác tối ưu hóa giải mã nguồn mở), tôi có những giải pháp
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
;
mẫu:
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];
tập tin dữ liệu ví dụ của bạn:
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
;
Bạn nói ví dụ đầu ra là "không phải là rất tốt". Có gì sai với nó? Tại sao bất kỳ phân chia 25-26-26 nào khác lại tốt hơn? –
@ jwpat7: như được giải thích trong phần mô tả, nó không phải là rất tốt vì có ba cấp độ trong cả ba lớp học, đó là khó khăn hơn cho giáo viên và tránh tốt nhất. Tuy nhiên, ràng buộc rằng các lớp phải có cùng kích thước thì mạnh hơn so với lớp này. –
Bạn đang giải quyết nó ngay bây giờ như thế nào? Như trong, bạn có đang sử dụng trình giải quyết tối ưu không? Nếu vậy, các ràng buộc và mục tiêu của bạn là gì? – raoulcousins