如何用Google cp_model构建学生任务均衡分配的目标函数？

要实现让每个学生分配的任务数量尽可能均衡的目标，我们可以通过引入辅助变量的方式，在OR-Tools的CP-SAT模型中实现最小化「最大任务数-最小任务数」的目标。以下是修改后的完整代码：

import math
from ortools.sat.python import cp_model

students = [0,1,2,3,4]
tasks = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

model = cp_model.CpModel()
max_task = math.ceil(len(tasks)/len(students))

x = {}
for student in students:
    for task in tasks:
        x[(student ,task)] = model.NewBoolVar(f'student_{student}_task_{task}')

# 约束：每个任务必须分配给恰好一名学生
for task in tasks:
    model.Add(sum(x[student ,task] for student in students) == 1)

# 定义每个学生的任务数变量
task_count = {}
for student in students:
    count = sum(x[(student, task)] for task in tasks)
    task_count[student] = model.NewIntVar(1, max_task, f'task_count_{student}')
    model.Add(task_count[student] == count)

# 定义最大任务数和最小任务数变量
max_count = model.NewIntVar(1, max_task, 'max_count')
min_count = model.NewIntVar(1, max_task, 'min_count')

# 添加约束：max_count 是所有学生任务数的最大值
for student in students:
    model.Add(task_count[student] <= max_count)

# 添加约束：min_count 是所有学生任务数的最小值
for student in students:
    model.Add(task_count[student] >= min_count)

# 设置目标函数：最小化 最大任务数 - 最小任务数
model.Minimize(max_count - min_count)

solver = cp_model.CpSolver()
status = solver.Solve(model)
print(f"求解状态: {solver.StatusName(status)}")

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    # 输出每个学生的任务数
    for student in students:
        print(f"学生 {student} 分配到 {solver.Value(task_count[student])} 项任务")
    # 输出具体分配情况
    print("\n具体分配：")
    for student in students:
        assigned_tasks = [task for task in tasks if solver.Value(x[(student, task)]) == 1]
        print(f"学生 {student}: {assigned_tasks}")
else:
    print("未找到可行解。")

关键修改说明： #

1. 任务数变量定义：新增task_count字典，存储每个学生被分配的任务数，类型为整数变量，范围限制在1到预先计算的max_task之间（和你原有的约束一致）。
2. 最大/最小任务数变量：引入max_count和min_count两个整数变量，分别表示所有学生任务数的最大值和最小值。
3. 约束补充：通过model.Add(task_count[student] <= max_count)确保max_count不小于任何学生的任务数；通过model.Add(task_count[student] >= min_count)确保min_count不大于任何学生的任务数。
4. 目标函数设置：直接将max_count - min_count作为目标，设置为最小化，这样就能实现任务数尽可能均衡的需求。
5. 输出修正：修复了你原代码中遍历分配结果时的变量错误，现在能正确输出每个学生的任务分配情况。

后续如果需要添加「特定学生不能承接特定任务」的约束，只需在定义x变量后，对对应的(student, task)对添加model.Add(x[(student, task)] == 0)即可，不会影响均衡目标的实现。

内容的提问来源于stack exchange，提问作者Gabriel Choo