8

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，完全无证，半蛮力代码。这很丑陋，但它有效！我很想学习如何编写更优雅的解决方案。

4

1 回答 1

18

这里的基本困难是你有一个多目标优化问题。我认为您对三件事感兴趣，可以考虑目标或“软约束”：

  1. 获得相似的班级规模
  2. 最小化每个班级的级别数
  3. 如果班级中有学生，则班级中有足够多的学生。

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

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

目标是最小化最大的班级规模。感兴趣的变量是 y[i,j]。y[i,j] for i in LEVEL, j in 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
;
于 2013-06-09T22:04:05.147 回答