你如何找到班级中学生的最佳分配？

Question

来自A级的23名学生,B级的24名学生和C级的30名学生需要分为三个班级.类需要几乎完全相同的大小.不同的级别可以混合到一个类中,但是如果可以避免则更好.在任何情况下,一个级别中应该有0个学生,或者超过6个.

你能帮我解决这个组合优化问题吗？以下是输入和输出示例.如果你可以告诉我如何解决一般问题的加分点!

输入:

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

输出示例(不太好!)

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

编辑:这是我非常hackish,完全没有文档的半暴力代码.它太丑了,但它有效!我很想学习如何编写更优雅的解决方案.

Answer 1

这里的根本困难在于你有一个多目标优化问题.你有三件我认为你感兴趣的事情,你可以考虑目标或"软约束":

1. 获得类似的班级规模
2. 最小化每个级别的级别数
3. 如果班上有学生,可以从课堂上有足够的学生.

请注意,我在AMPL中为此编写了一个优化模型.由于您使用的是Python,因此可以使用类似于PuLP和pyomo的优化建模语言.该模型不应该太难翻译.

这是一个整数编程模型和一个数据文件,它强调目标数1,同时保持问题(整数)线性.有了这个目标,优化问题就会找到您在示例中给出的相同解决方案.希望您可以在此基础上增加其他约束和/或客观术语,并获得更好的解决方案.

目标是尽量减少最大的班级规模.感兴趣的变量是y [i,j].y [i,j]对于i在LEVEL中,j在CLASS中是从i级分配给j级的学生人数.它假设您输入了每个班级中每个级别的最小学生人数(如果有的话).

目标函数可能不是您想要的,但它是一种尝试均衡线性类大小的方法.我也不保证这是解决问题的最有效方法.可能有一个更好的自定义算法来解决这个问题,但我所要做的只是表达约束和目标而不是编写算法.这对你的使用来说可能已经足够了.

使用neos-server.org上的求解器Gurobi(你可以使用lpsolve或其他开源优化求解器),我得到了解决方案

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
;

模型:

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];

您的示例的数据文件:

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
;