带分组约束的学生-教室科目匹配最优方案技术咨询

问题描述 #

现有31个小组共370名学生，每名学生仅对1门科目（科目1至6）感兴趣。我们有4间教室，每间教室的总容纳人数固定，且各科目可容纳的学生数也固定。需要找到最优分配方案，确保所有学生都能学习自己感兴趣的科目；若无法实现，则返回各教室匹配率最高的方案。

约束条件 #

• 同一小组的所有学生必须被分配到同一教室
• 实际场景中学生数量可达1500人，暴力枚举法不可行

示例数据 #

学生分组数据 #

{
  'G1': [ { '6': 9 }, 9 ],
  'G2': [ { '6': 7 }, 7 ],
  'G3': [ { '1': 1, '2': 1 }, 2 ],
  'G4': [ { '6': 4 }, 4 ],
  'G5': [ { '6': 2 }, 2 ],
  'G6': [ { '1': 1, '6': 5 }, 6 ],
  'G7': [ { '6': 3 }, 3 ],
  'G8': [ { '6': 2 }, 2 ],
  'G9': [ { '1': 2, '2': 1 }, 3 ],
  'G10': [ { '1': 2, '2': 6, '3': 3, '4': 2 }, 13 ],
  'G11': [ { '6': 13 }, 13 ],
  'G12': [ { '4': 1, '6': 8 }, 9 ],
  'G13': [ { '1': 5, '2': 5, '3': 12, '4': 6 }, 28 ],
  'G14': [ { '3': 9, '4': 3, '6': 8 }, 20 ],
  'G15': [ { '2': 4, '3': 10, '4': 2, '6': 3 }, 19 ],
  'G16': [ { '3': 9, '4': 8, '5': 1, '6': 5 }, 23 ],
  'G17': [ { '2': 2, '3': 3, '6': 19 }, 24 ],
  'G18': [ { '1': 2, '2': 1, '3': 3, '4': 11, '5': 2, '6': 2 }, 21 ],
  'G19': [ { '1': 2, '2': 4, '3': 6, '4': 4, '5': 1, '6': 3 }, 20 ],
  'G20': [ { '2': 3, '3': 13, '5': 1, '6': 6 }, 23 ],
  'G21': [ { '1': 1, '2': 2, '3': 11, '4': 1, '6': 10 }, 25 ],
  'G22': [ { '3': 1, '6': 3 }, 4 ],
  'G23': [ { '3': 1, '4': 1 }, 2 ],
  'G24': [ { '6': 6 }, 6 ],
  'G25': [ { '2': 1 }, 1 ],
  'G26': [ { '2': 3, '3': 4, '4': 14, '5': 2, '6': 5 }, 28 ],
  'G27': [ { '1': 3, '2': 2, '3': 3, '5': 3, '6': 12 }, 23 ],
  'G28': [ { '6': 8 }, 8 ],
  'G29': [ { '2': 3, '3': 5, '4': 5, '5': 3, '6': 1 }, 17 ],
  'G30': [ { '2': 2, '3': 1, '6': 1 }, 4 ],
  'G31': [ { '6': 1 }, 1 ]
}

教室配置数据 #

{
      '1B': [ { '3': 9, '4': 19, '5': 1, '6': 71 }, 100 ],
      '1A': [ { '1': 11, '2': 19, '3': 33, '4': 1, '6': 16 }, 80 ],
      '2B': [ { '2': 3, '3': 14, '4': 38, '5': 12, '6': 43 }, 110 ],
      '2A': [ { '1': 8, '2': 18, '3': 38, '6': 16 }, 80 ]
}

可行解决方案思路 #

1. 整数规划建模 #

将问题转化为混合整数线性规划（MILP）模型，适合中小规模场景：

• 决策变量：设x_{g,c}为0-1变量，表示小组g是否分配到教室c
• 目标函数：最大化成功匹配的学生总数（或匹配率）
• 约束条件：
  • 每个小组必须且只能分配到一个教室：sum_{c} x_{g,c} = 1（对所有小组g）
  • 每个教室总人数不超容量：sum_{g} (size_g * x_{g,c}) ≤ total_cap_c（对所有教室c）
  • 每个教室各科目容纳人数不超限额：sum_{g} (subj_s_g * x_{g,c}) ≤ subj_cap_{c,s}（对所有教室c和科目s）
    可使用PuLP、OR-Tools等开源工具，或Gurobi、CPLEX等专业求解器实现。

2. 启发式算法（大规模场景适配） #

当学生数量达1500人时，整数规划效率不足，可采用以下策略：

• 贪心分配：优先处理科目需求集中、规模较大的小组，将其分配到剩余容量最匹配的教室（同时满足总人数和科目限额）
• 局部搜索优化：在初始贪心分配基础上，尝试交换部分小组的教室分配，迭代寻找更优解
• 聚类分组：先将需求相似的小组聚类，再将聚类后的组整体分配到合适教室，缩小问题规模

3. 近似算法 #

针对超大规模问题，可先求解线性规划松弛后的连续解，再通过取整策略得到可行整数解，保证一定的近似比，平衡求解效率和结果质量。

内容的提问来源于stack exchange，提问作者Nguyễn Duy