带约束的班级人员分配最优组合是否有对应的求解算法?
解决方案
这个问题属于典型的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
- 每个班级仅分配给1名老师:对任意班级
- 优化目标:最小化
sum(x[u][c] * 老师u在班级c的排名 * 班级c学生数)
实现代码
可直接使用Python的pulp库求解,步骤如下:
- 安装依赖:
pip install pulp
- 完整求解代码:
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
相关产品推荐
相关产品推荐

