You need to enable JavaScript to run this app. 带约束的班级人员分配最优组合是否有对应的求解算法?
优惠活动
大模型
产品
解决方案
定价
更多

带约束的班级人员分配最优组合是否有对应的求解算法?

解决方案

这个问题属于典型的0-1整数规划问题,可通过开源求解器完全自动求解,调整约束参数时无需人工介入分配逻辑,直接修改约束数值即可重新计算最优解。

问题建模

先明确核心规则:每个班级必须且仅能分配给1名老师,基于你的需求建模如下:

  • 决策变量:x[u][c]为0-1变量,取值1代表将班级c分配给老师u,0代表不分配
  • 约束条件:
    • 每个班级仅分配给1名老师:对任意班级c,所有老师的x[u][c]之和为1
    • 总学生数T为所有班级学生数之和
    • John覆盖学生数:0.1*T ≤ sum(x['John'][c] * 班级c学生数) ≤ 0.3*T
    • Bob覆盖学生数:sum(x['Bob'][c] * 班级c学生数) ≥ 0.1*T
    • Alice覆盖学生数:sum(x['Alice'][c] * 班级c学生数) ≤ 0.1*T
  • 优化目标:最小化sum(x[u][c] * 老师u在班级c的排名 * 班级c学生数)

实现代码

可直接使用Python的pulp库求解,步骤如下:

  1. 安装依赖:
pip install pulp
  1. 完整求解代码:
import pandas as pd
import pulp

# 原始数据
df = pd.DataFrame({
    'users': ['John', 'Bob', 'Alice', 'John', 'Alice','Bob','Alice','John', 'Bob', 'Alice'], 
    'class': ['Economics','Economics','Economics','Maths','Maths','Physics','Physics','CS','CS','CS'],
    'rank':[2,1,3,1,2,2,1,3,1,2],
    'total_students':[10,10,10,20,20,12,12,30,30,30]
})

# 提取基础配置
teachers = df['users'].unique()
classes = df['class'].unique()
class_student_cnt = df.groupby('class')['total_students'].first().to_dict()
total_student = sum(class_student_cnt.values())
rank_cost_map = df.set_index(['users', 'class'])['rank'].to_dict()

# 初始化最小化问题
problem = pulp.LpProblem("ClassAssignmentProblem", pulp.LpMinimize)

# 定义0-1决策变量
assign = pulp.LpVariable.dicts("assign", (teachers, classes), lowBound=0, upBound=1, cat='Binary')

# 添加优化目标
problem += pulp.lpSum([
    assign[u][c] * rank_cost_map[(u, c)] * class_student_cnt[c]
    for u in teachers for c in classes
])

# 添加约束:每个班级仅分配给一名老师
for c in classes:
    problem += pulp.lpSum([assign[u][c] for u in teachers]) == 1

# 添加占比约束
# John 10%~30%
problem += pulp.lpSum([assign['John'][c] * class_student_cnt[c] for c in classes]) >= 0.1 * total_student
problem += pulp.lpSum([assign['John'][c] * class_student_cnt[c] for c in classes]) <= 0.3 * total_student
# Bob ≥10%
problem += pulp.lpSum([assign['Bob'][c] * class_student_cnt[c] for c in classes]) >= 0.1 * total_student
# Alice ≤10%
problem += pulp.lpSum([assign['Alice'][c] * class_student_cnt[c] for c in classes]) <= 0.1 * total_student

# 求解(关闭日志输出)
problem.solve(pulp.PULP_CBC_CMD(msg=False))

# 输出结果
print("===== 最优分配方案 =====")
for c in classes:
    for u in teachers:
        if pulp.value(assign[u][c]) == 1:
            print(f"班级:{c} → 授课老师:{u}")
print(f"\n最小化目标值(总rank*学生数):{pulp.value(problem.objective)}")
print("\n===== 各老师覆盖学生占比 =====")
for u in teachers:
    cover_stu = sum([pulp.value(assign[u][c]) * class_student_cnt[c] for c in classes])
    print(f"{u}:覆盖{int(cover_stu)}人,占比{round(cover_stu/total_student*100, 2)}%")

你的样例运行结果

===== 最优分配方案 =====
班级:Economics → 授课老师:Bob
班级:Maths → 授课老师:John
班级:Physics → 授课老师:Bob
班级:CS → 授课老师:Bob

最小化目标值(总rank*学生数):84.0

===== 各老师覆盖学生占比 =====
John:覆盖20人,占比27.78%
Bob:覆盖52人,占比72.22%
Alice:覆盖0人,占比0.0%

注:你的样例中所有班级学生数均大于总人数10%(7.2人),因此Alice无法分配到任何班级,符合约束要求。如果后续有更小的班级,模型会自动计算最优分配方案。

后续如果需要调整占比参数,直接修改约束中的比例数值重新运行即可,无需调整其他逻辑。

内容的提问来源于stack exchange,提问作者hidden-layer

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.12 05:33:01