Làm thế nào để bạn tìm thấy sự phân bổ tối ưu của học sinh trong lớp học?

Question

23 học sinh từ trình độ A, 24 từ cấp độ B và 30 từ cấp độ C cần được phân thành ba lớp. Các lớp cần phải gần như chính xác với cùng một kích thước. Các cấp độ khác nhau có thể được trộn lẫn vào một lớp duy nhất, tuy nhiên tốt hơn nếu có thể tránh được. Trong mọi trường hợp, phải có 0 học sinh từ một cấp trong một lớp, hoặc nhiều hơn 6.

Bạn có thể giúp tôi giải quyết vấn đề tối ưu hóa tổ hợp này không? Dưới đây là một đầu vào và đầu ra mẫu. Điểm thưởng nếu bạn có thể chỉ cho tôi cách giải quyết vấn đề chung!

Input: (! Không phải là rất tốt)

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

Ví dụ đầu ra

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

Sửa: Here rất hackish, hoàn toàn không có giấy tờ, mã bán bruteforce tôi. Nó xấu xí, nhưng nó hoạt động! Tôi rất muốn tìm hiểu làm thế nào tôi có thể viết một giải pháp thanh lịch hơn.

Answer 1

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":

1. Bắt lớp tương tự như kích thước
2. Giảm thiểu số lượng mỗi lớp
3. 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 
;