你如何找到学生在课堂上的最佳分配? [英] How do you find the optimal assignment of pupils in classes?

问题描述

A 级 23 名、B 级 24 名和 C 级 30 名学生需要分配到三个班级.这些类的大小必须几乎完全相同.不同的级别可以混合成一个类，但最好能避免.无论如何，一个班级的一个级别应该有0个学生，或者超过6个.

23 pupils from level A, 24 from level B and 30 from level C need to be assigned into three classes. The classes need to be almost exactly of the same size. Different levels can be mixed into a single class, however it is better if it can be avoided. In any case, there should be either 0 pupils from one level in a class, or more than 6.

你能帮我解决这个组合优化问题吗?下面是一个示例输入和输出.如果你能告诉我如何解决一般问题，就加分！

Can you help me solve this combinatorial optimization problem? Below is a sample input and output. Bonus points if you can show me how to solve the general problem!

输入:

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}

编辑:这里是我非常骇人听闻的、完全没有记录的、半暴力的代码.这很丑陋，但它有效！我很想了解如何编写更优雅的解决方案.

Edit: Here is my very hackish, completely undocumented, semi-bruteforce code. It's ugly, but it works! I'd love to learn how I could write a more elegant solution.

推荐答案

这里的根本困难在于您遇到了一个多目标优化问题.我认为您对三件事感兴趣，可以考虑目标或软约束":

The fundamental difficulty here is that you sort of have a multiobjective optimization problem. You have three things I think you're interested in that you can either consider objectives or "soft constraints":

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

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

Note that I've written an optimization model for this in AMPL. Since you're using Python, there are similar optimization modeling languages for python like PuLP and pyomo that you could use. The model should not be too difficult to translate.

这是一个整数规划模型和一个数据文件，它强调目标 1，同时保持问题(整数)线性.有了这个目标，优化问题就会找到您在示例中给出的相同解决方案.希望您能以此为基础，添加其他限制条件和/或客观条件并获得更好的解决方案.

Here is an integer programming model and a data file that emphasizes objective number 1 while keeping the problem (integer) linear. With this objective, the optimization problem finds the same solution you gave in your example. Hopefully you can build on this and add other constraints and/or objective terms and get better solutions.

目标是最小化最大的类大小.感兴趣的变量是 y[i,j].y[i,j] for i in LEVEL, j in CLASS 是从级别 i 分配到班级 j 的学生人数.它假设您输入了每个班级中每个级别的最少学生人数(如果有分配给该级别).

The objective is to minimize the largest class size. The variable of interest is y[i,j]. y[i,j] for i in LEVEL, j in CLASS is the number of students from level i assigned to class j. It assumes that you have input for the minimum number of students from each level in each class if any are assigned to that level.

目标函数可能不是您想要的，但它是一种尝试均衡线性类大小的方法.我也不保证这是解决问题的最有效方法.该问题可能有更好的自定义算法，但我所要做的就是表达约束和目标，而不是编写算法.它可能足以供您使用.

The objective function may not be what you want, but it is a way of trying to equalize the class sizes which is linear. I also don't promise that this is the most efficient way of solving the problem. There may be a better custom algorithm for the problem, but all I had to do was express the constraints and objective and not write an algorithm. It's probably good enough for your use.

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

Using the solver Gurobi on neos-server.org (you could use lpsolve or another open source optimization solver), I got the solution

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
;

这篇关于你如何找到学生在课堂上的最佳分配?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！