第 21 章 谁做哪份活

第 21 章　谁做哪份活

这一章要解决什么

上一章的候选是东西，每类挑一件；这一章的候选是"人和活的配对"。变量还是 0-1，可约束变成了两排：每个人手里正好一个活，每个活正好有一个人做。

这种"两排都卡死"的结构，有一个专门的名字，叫指派问题。它看起来只是背包问题换了个说法，其实解的形状完全变了：答案不再是一堆散落的 0 和 1，而是一个置换矩阵——每行每列正好一个 1。

读完这一章，你会知道三件事：为什么解长成那个样子；为什么这一题的线性规划居然会自动给出整数解；以及为什么只要多加一条规矩，它马上就开始交出"半个人"。

21.1　周一早上的分工

五个人的小设计工作室，周一早上，桌上压着五个活。

品牌海报，客户要三稿，周四交；电商详情页，二十屏，图特别多；一条六十秒的短视频，要出镜；一个展台，周五进场，得熬夜；还有一本六十四页的手册，排版最费眼。

五个人：张，来了六年的资深设计师，什么都拿得起来；李，资深，版式是他的强项；王，入职一年，剪片子快；赵，搭建出身，跑现场最熟；陈，实习生刚转正，做手册最细。

活要分下去，一人一个，一个活一个人。分完之后，每份活的"完成成本"不一样——同样的活，交给出身不同的人，工时、外购素材、返工风险都不一样，折成钱就是一个数。

张把这二十个数算了出来，摆在桌上。他没敢按"谁擅长什么就派什么"直接拍，因为去年这么干过一次：两个人都被派了手册，海报没人接，最后张通宵补了两天。

21.2　先把问题说清楚

表 21-1　三个问题与答案

矛盾就一句话：每个人都有一个最想做的活，可五个人的"最想"会撞车。

这就是指派：把一组人一对一地派给一组活。"一对一"三个字是全部难点——它同时管住了行（人）和列（活），任何一边放松，问题都会变成另一个样子。

顺手看一眼，为什么不能"每人挑自己最便宜的"：张最便宜的是手册（300 元），李最便宜的是详情页（300 元），王最便宜的也是详情页（320 元），赵最便宜的是展台（340 元），陈最便宜的是手册（330 元）。五个人挑完，手册被两个人挑中、详情页被两个人挑中，品牌海报和短视频一个人都没有。账面合计 1590 元，看着比什么都便宜，可这张派工单根本发不下去。

21.3　把大白话变成数学

第一步：给人和活编号。

• $p$：人的编号，五个人；现实里就是"张、李、王、赵、陈"这五个人。
• $t$：活的编号，五个活；现实里就是那五份要交的东西。
• $P$、$T$：五个人、五个活各自的集合。

第二步：把成本写成一张表。

• $c_{pt}$：把活 $t$ 交给人 $p$ 的完成成本，单位元。比如 $c_{\text{赵},\text{展台}}=340$，意思是展台交给赵，预估花 340 元。

二十个数字见表 21-2。

表 21-2　五个人做五个活的完成成本

表注：成本＝预估工时 × 内部结算单价 + 必要的外购素材与返工预备金，单位元。

同一批数字画成图，如图 21-1 所示。

图 21-1　成本矩阵：谁做哪个活便宜

这张图告诉你什么：五行是五个人，五列是五个活，格子里的数字就是完成成本，颜色越深越贵。先看两处最浅的格子：赵那一行的展台 340 元，浅得几乎发白——这是全场最"专"的一格，赵做别的都在 550 以上。再看颜色最深的一片：赵那一行整行偏深，说明他除了展台，做别的都贵；张、李、王三行整体偏浅，说明他们的可替代性强。再看手册那一列：300、370、480、590、330，五个人都能做，价格跨度却有两倍多——这种"人人能做、价格差很大"的列，最容易在分工时被抢。这张图先把结构交代清楚了：有人只有一个便宜格子，有人满行都便宜。

第三步：给每一个"配对"设一个变量。

• $x_{pt}$：活 $t$ 交不交给 $p$。取 1 表示交，取 0 表示不交。

二十个变量，每个都是一个 0-1 变量。注意它的下标是两个字母：一个管人、一个管活，这正是指派问题的记号特点。

第四步：写"每人一个活"。

$$\sum _{t\in T}{x}_{pt}=1,p\in P$$

对固定的人 $p$，五个 0-1 变量加起来等于 1，意思是"他手上正好一个活"。

第五步：写"每个活一个人"。

$$\sum _{p\in P}{x}_{pt}=1,t\in T$$

对固定的活 $t$，五个人里正好一个接。

第六步：写目标。

$$\sum _{p\in P}\sum _{t\in T}{c}_{pt}{x}_{pt}$$

二十个成本各自乘以"派不派"，加起来就是总成本，要越小越好。

21.4　完整的数学模型

装起来：

KaTeX parse error: Multiple \\tag

十条约束，二十个变量，二十个成本系数。这就是指派问题的标准长相。

为什么解一定是一个置换矩阵。 十条规定一摆，答案的形状就被定死了：把 $x_{pt}$ 排成一个 5×5 的方阵，行是人、列是活。式 (21-1) 要求每行加起来是 1，式 (21-2) 要求每列加起来是 1，式 (21-3) 要求每格只能是 0 或 1。一个 5×5 的方阵，每行每列正好一个 1，这就是置换矩阵——二十个格子里只有五个 1，而且没有任何两个在同一行或同一列。

解的形状由约束决定，不由目标决定。 你就算把二十个成本全改成别的数，答案还是长这样；你就算把"最小化"改成"最大化"，答案也还是长这样。成本只决定"哪五个格子亮"，不决定"亮几个"。

五个人分五个活，全部派法就是五个活的排列，一共 $5!=120$ 种。一百二十种，手算也能算完，但十个人十个活就是三百六十多万种——这也是为什么这类题一定要交给求解器。

顺便说一件反直觉的事：这一题的线性规划，自己就会给出整数解。

把式 (21-3) 换成 $0\le x_{pt}\le 1$，允许"张做半张海报"，会发生什么？对这道题，答案是：什么都不发生，求解器交回来的仍然是五个 1 和十五个 0。

这不是巧合。式 (21-1)、(21-2) 加上 0 到 1 的界，围出来的可行域是一个多面体，它的每一个顶点都是置换矩阵；而线性规划的最优解一定能在顶点上取到。所以"每行每列各一个"这个结构，天然把分数解挡在门外。这个性质有个名字，叫全幺模——矩阵的每个子方阵行列式都是 0、1 或 −1，整数性从结构里白送。

正是因为这个，很多人才会误以为"整数规划就是线性规划加个取整"。21.8 节的第一个实验会把这个错觉打掉：只要在模型里加一条跟"每行每列"无关的规矩，全幺模立刻失效，求解器马上交出"张做半个海报、半个手册"。

再说说匈牙利算法。 它不用枚举，只做两件事：给每一行减一个数、给每一列减一个数，再在 0 上配对。减数为什么不影响答案？因为每个人正好接一个活、每个活正好一个人做，行减一个常数、列减一个常数，任何一套完整分法的总成本都被减掉同一个数，"谁最便宜"的相对关系一点没变。减到矩阵里冒出足够多的 0，就在 0 上像抢座位一样配对；配不上，就调整减数再配。这个思路的直觉一句话就能说完：先把每个人的相对优势抹平，剩下的 0 就是答案。

21.5　用 Python 写出来

分五段看。

第一段：把二十个成本读成字典。

import json
from pathlib import Path

DATA = json.loads((HERE / "数据.json").read_text(encoding="utf-8"))
PEOPLE = [p["key"] for p in DATA["people"]] # 五个人
TASKS = [t["key"] for t in DATA["tasks"]] # 五个活
# 成本矩阵：COST[人][活] 就是一个数
COST = {p["key"]: dict(DATA["cost"][p["key"]]) for p in DATA["people"]}

双重字典比二维数组好读：COST["zhao"]["booth"] 一眼就知道是"赵做展台"，不用记下标顺序。

第二段：建二维的 0-1 变量。

import gurobipy as gp
from gurobipy import GRB

m = gp.Model("assign")
m.Params.OutputFlag = 0
x = m.addVars(PEOPLE, TASKS, lb=0, ub=1, vtype=GRB.BINARY, name="x")

addVars 传两个列表，得到的就是二维变量，变量名自动长成 x[zhang,poster]，对结果时不用猜。

第三段：两排约束，各五条。

for p in PEOPLE: # 每人正好一个活
m.addConstr(gp.quicksum(x[p, t] for t in TASKS) == 1, name=f"person[{p}]")
for t in TASKS: # 每个活正好一个人
m.addConstr(gp.quicksum(x[p, t] for p in PEOPLE) == 1, name=f"task[{t}]")

两段循环只差一个下标的位置：第一段固定人、遍历活；第二段固定活、遍历人。写反了不会报错，但约束的意思就完全变了。

第四段：设目标并求解。

m.setObjective(
gp.quicksum(COST[p][t] * x[p, t] for p in PEOPLE for t in TASKS), GRB.MINIMIZE)
res = solve_both(m, name="021_谁做哪份活")

GRB.MINIMIZE 表示"越小越好"。solve_both 把同一份模型交给 Gurobi 和 COPT 各解一遍，二维变量也会自动镜像过去。

第五段：加一条额外规矩，再放开整数性。

# 规矩：张和李合计承担的成本不超过 650 元
m.addConstr(gp.quicksum(COST[p][t] * x[p, t]
for p in ("zhang", "li") for t in TASKS) <= 650)

把这一条加进去，再把 vtype 从 GRB.BINARY 换成 GRB.CONTINUOUS，就是 21.8 节实验二要看的"半个方案"。一条本来很合理的规矩，能让一个整数模型变成分数模型，这件事值得亲手试一次。

21.6　跑起来，先看输出

在案例目录下执行 python 建模.py：

==================================================================
求解状态： OPTIMAL
最小总成本：1750.00 元
——————————————————————
人 分到的活 成本 他最便宜的是 多花
张 品牌海报 400 手册 +100
李 详情页 300 详情页 +0
王 短视频 380 详情页 +60
赵 展台 340 展台 +0
陈 手册 330 手册 +0
——————————————————————
五份活合计 1750 元
对照 1 每人挑最便宜：账面 1590 元，但 详情页、手册各被两个人挑中，品牌海报、短视频没人接
对照 2 线性松弛 ：1750.00 元，解里没有一个分数——这一行很重要
——————————————————————
实验 1 资深搭配：张和李合计不超过 650 元
整数解 1790 元；线性松弛 1770 元
松弛解：张 做 品牌海报 的份额 0.50
松弛解：张 做 手册 的份额 0.50
松弛解：陈 做 品牌海报 的份额 0.50
松弛解：陈 做 手册 的份额 0.50
——————————————————————
实验 2 赵不能做展台：1750 → 2080 元（+330）
连锁换位 3 人：张(品牌海报→手册)、赵(展台→品牌海报)、陈(手册→展台)
——————————————————————
实验 3 成本上下浮动 5%，重解 200 次：原方案原样出现 192 次
原方案里最不稳的一格：张 做 品牌海报，只留下 96%
双后端核对： Gurobi=OPTIMAL obj=1750.0 t=0.0037s | COPT=OPTIMAL obj=1750.0 t=0.0148s | 偏差=0.00e+00
==================================================================

逐段读。

“最小总成本：1750.00 元”——张做海报，李做详情页，王做短视频，赵做展台，陈做手册。五个活，一千七百五。

“张 品牌海报 400 / 他最便宜的是 手册 300 / +100”——张是全场最能干的人，五份活他报的价都不超过 640 元，最便宜的是手册。可他不能做手册，因为陈做手册只要 330，张做手册是 300，两个人抢同一个活，陈就得去做海报（470 元），一换，总成本反而涨。所以最优解让张这个"多面手"去做海报（400 元），把手册留给陈（330 元）。这两个数加起来是 730 元，反过来是 300 加 470 等于 770 元，差 40 元——分工的道理就在这 40 元里。

“王 短视频 380 / 他最便宜的是 详情页 320 / +60”——王剪片子快，可他最便宜的是详情页。详情页归了李（300 元），王只能去做短视频（380 元），多花 60 元。这 60 元买的是"详情页让给更擅长的人"。

“赵 展台 340 / 赵 展台 +0”——赵一分没让。展台这一格他 340，第二名王要 520，差 180 元，谁都抢不走。这种人叫结构性优势：他在这一格上的领先，超过了任何重排能省下的钱。

“李 +0，陈 +0”——五个人里有三个拿到了自己最便宜的活，两个各让一步，一共多花 160 元。

“对照 1 每人挑最便宜：账面 1590 元”——这个 1590 比 1750 低 160 元，可它不是一套分法：手册被张和陈同时挑中，详情页被李和王同时挑中，品牌海报和短视频空着。"账面更低"和"能执行"是两件事，这也是所有指派问题最容易被直觉骗过去的地方。

“对照 2 线性松弛：1750.00 元，解里没有一个分数”——放开整数性，答案一模一样。21.4 节说过原因：这一题的结构保证松弛解落在置换矩阵上。

21.7　把答案画出来

最终分法如图 21-2 所示。

图 21-2　最终分法：一个 5×5 的置换矩阵

这张图告诉你什么：深蓝的五格就是最终分法，格子里是这一格的成本；浅灰色的数字是没被选中的配对，看得到但用不上。先数一遍形状：每一行正好一格深蓝，每一列也正好一格深蓝，五格连起来像一条斜线但不完全在一条线上——这就是置换矩阵的样子，也是 21.4 节那十条约束逼出来的形状。再看这五格的数字：400、300、380、340、330，加起来 1750。再看被放弃的格子：张那一行的手册是 300，比 400 还便宜，却是灰的——它不是不好，是被陈以 330 的更低价"占住"了。这张图最想说明的是：最优解不是"每个人都挑自己最便宜的"，而是"五个人合起来最便宜"。

五个人的让步情况，见表 21-3。

表 21-3　五个人的分派与让步

表注："多花"是这个人分到的活与自己最便宜的活之间的差额；五个人合计多花 160 元。

21.8　换个条件，答案会怎样

实验一：不建模，每人挑最便宜的

表 21-4　两种做法的账面成本与可行性

表注：第一行的 1590 是五个人各自最低成本之和，不是任何一套完整分法的成本。两种做法的差额如图 21-3 所示。

图 21-3　五个人：最便宜的活 vs 分到的活

这张图告诉你什么：每个人两根柱子，浅色是这人最便宜的活的成本，深色是实际分到的活的成本，右边写着差额。先看三个"没让"的人——李、赵、陈的深色和浅色一样长，他们拿到了自己最想要的活。再看两个"让了"的人：张让 100 元，王让 60 元，两根柱子一高一低，差额就写在右边。这张图要说的是：一套能执行的分法，代价就是这 160 元；三个人一分没让，两个人各让一步，多出来的 160 元买的不是效率，是"每个活都有人接"。

实验二：加一条"资深搭配"的规矩

工作室还有一条不成文的规矩：重活不能都压在两位资深身上。把它写死：张和李的完成成本合计不超过 650 元。

表 21-5　资深搭配条款下的整数解与松弛解

表注：两个人的成本合计正好卡在 650 元的限额上。

这张表值得停下来看三十秒。

整数解退了一步：为了让张、李两人的成本落到 650 以内，张只能回去做手册（300 元），海报交给陈（470 元），总成本从 1750 涨到 1790。

而线性松弛给出的是另一个东西：张做半张海报、半本手册，陈做另外半张、另外半本。四个 0.5 摆在那里，四个约束全都满足，成本 1770 元——比整数解便宜 20 元，可这套方案没人能执行。

这就是 21.4 节说的那件事的另一半：全幺模是"每行每列各一个"这个结构给的，一旦加进一条不按行、不按列的规矩，结构被破坏，顶点就不再是置换矩阵，分数解立刻出现。整数规划不是"线性规划加取整"，它是一类完全不同的问题——把 1770 取整，得到的东西既不可行，也不最优。

实验三：赵不能做展台

客户方的场地负责人跟赵有过节，这次要求换人。把 $x_{\text{赵},\text{展台}}$ 钉死为 0，再解一次。

表 21-6　赵不能做展台前后的分工

表注：括号里是这一格的完成成本；新方案的五格全部满足每人一个活、每个活一个人。

禁掉一格之后的重排如图 21-4 所示。

图 21-4　禁掉一格之后，三个人跟着动

这张图告诉你什么：左边是原方案，每行开头写着"人·他原来做的活"；右边是赵不能做展台之后的分法，灰虚线是没动的人，橙实线是动了的人。先看灰的两条：李和王原地不动，说明他们的位置很稳。再看橙的三条：张从海报挪到手册（省 100），陈从手册挪到展台（多 170），赵从展台挪到海报（多 260）。这三个人像一个环，被一格封死带着一起转。再看下面两个总价：1750 变成 2080，多 330 元——这就是"一个人少一个选项"的代价。这张图想说的是：指派问题里，动一格从来不是只动一个人，它会沿着行列一路传下去。

实验四：成本估错了会怎样

那二十个成本都是"预估"，估错一点很正常。把每一格乘上一个 0.95 到 1.05 之间的随机数，重解两百次，数一数原方案那五格还在不在。

每一格在两百次重解里的留存情况如图 21-5 所示。

图 21-5　成本上下浮动 5% 之后，每一格还留着多少

这张图告诉你什么：格子里是"这一格仍然出现在最优解里"的比例，橙框圈的是原方案的五格。先看橙框里的五个数：李做详情页 100、赵做展台 100、王做短视频 99、张做海报 96、陈做手册 96——五个都在 96 以上，说明这套分工很结实。再看框外的零星几个：陈做海报 3、张做手册 4、陈做详情页 1，都是个位数，对应的是"张和陈互换"那条几乎打平的边界。这张图要说的是：两百次里原方案原样出现 192 次，剩下 8 次换的也只是那对争抢的格子——估错 5% 动不了这套分法，你可以放心按它派活。

顺带说一句，这 8 次里换掉的正是"张做手册、陈做海报"那一对。回看表 21-2 就明白为什么：张做手册 300 加陈做海报 470 是 770，张做海报 400 加陈做手册 330 是 730，只差 40 元，5% 的扰动足够把这个差距抹掉。

顺便说说两个求解器

两个后端的逐项对比，如图 21-6 所示。

图 21-6　Gurobi 与 COPT 的逐项对比

这张图告诉你什么：从上往下逐行对。状态都是 OPTIMAL，最小总成本都是 1750.00，五个人的分工一行一行对下来完全一致：海报归张、详情页归李、短视频归王、展台归赵、手册归陈。唯一不同的是耗时，两边都在几十毫秒。这一章用的是二维变量加两排约束，值得确认的是：两个后端对二维 0-1 变量的处理是一致的，二十个变量镜像过去一个没丢，十条约束也没有变形。

21.9　小结与练习

三句话总结

想一想

动手改一改

把 数据.json 里 chen 做 manual 的成本从 330 改成 380，重跑 python 建模.py。看三件事：最优总成本涨了多少；手册最后落到了谁手里；张和陈的位置有没有互换。再把 forbid 里的 booth 改成 detail，看赵被禁掉一个他本来就做不好的活时，总成本是一动不动还是照样往上涨——这一问的答案，能帮你判断"哪一格才是真正的瓶颈"。

附录　代码与数据

以下为可复现材料，不计入正文字数。运行 建模.py 即可重算正文全部数字；数据.json 是输入，结果.json 是输出。

全文合 24,019 字符（正文 11,592＋代码 7,695＋JSON 4,408），未超 25000 上限

A.1　建模.py（全文）

"""案例 021 · 谁做哪份活

五个人的设计工作室，五个活要分给五个人，一人一个、一个活一个人。
每份活在不同人手里的成本不一样，找出总成本最低的分法——这就是指派问题。

运行：
python 建模.py

输出：终端打印谁做哪个活、每人让了多少步、几种改动的后果，双后端结果写入 结果.json
"""

import json
import math
import random
import sys
from pathlib import Path

HERE = Path(__file__).resolve().parent
sys.path.insert(0, str(HERE.parents[2] / "src"))

import gurobipy as gp
from gurobipy import GRB

from kit import brief, save_result, solve_both

# —————————————————————- 读数据

DATA = json.loads((HERE / "数据.json").read_text(encoding="utf-8"))

PEOPLE = [p["key"] for p in DATA["people"]] # 五个人的代号
PNAME = {p["key"]: p["name"] for p in DATA["people"]}
TASKS = [t["key"] for t in DATA["tasks"]] # 五个活的代号
TNAME = {t["key"]: t["name"] for t in DATA["tasks"]}

COST = {p["key"]: dict(DATA["cost"][p["key"]]) for p in DATA["people"]} # 成本矩阵（元）
CAP = float(DATA["fair_cap"]) # 资深两人合计的成本上限
FORBID = (DATA["forbid"]["person"], DATA["forbid"]["task"])
PERT = DATA["perturb"]

# —————————————————————- 建模

def build(binary=True, forbid=None, cap=None):
"""把"谁做哪个活"翻译成指派问题。

变量：x[p,t] 取 1 表示把活 t 派给人 p，取 0 表示不派（binary=False 时放开成 0–1 连续）
约束：① 每个人正好接一个活 ② 每个活正好由一个人做
目标：五份活的成本合计最小
"""
m = gp.Model("assign")
m.Params.OutputFlag = 0

vtype = GRB.BINARY if binary else GRB.CONTINUOUS
x = m.addVars(PEOPLE, TASKS, lb=0, ub=1, vtype=vtype, name="x")

cons = {}
# 约束①：每个人手里只有一个活
for p in PEOPLE:
cons[f"person[{p}]"] = m.addConstr(
gp.quicksum(x[p, t] for t in TASKS) == 1, name=f"person[{p}]")
# 约束②：每个活只能交给一个人
for t in TASKS:
cons[f"task[{t}]"] = m.addConstr(
gp.quicksum(x[p, t] for p in PEOPLE) == 1, name=f"task[{t}]")

if forbid: # 把某个格子钉死为 0
cons["forbid"] = m.addConstr(x[forbid[0], forbid[1]] == 0, name="forbid")

if cap is not None: # 资深两人合计承担的成本不超过上限
cons["fair"] = m.addConstr(
gp.quicksum(COST[p][t] * x[p, t] for p in ("zhang", "li") for t in TASKS)
<= cap, name="fair")

m.setObjective(
gp.quicksum(COST[p][t] * x[p, t] for p in PEOPLE for t in TASKS), GRB.MINIMIZE)
return m, x, cons

def run(**kw):
"""解一次，返回总成本与"人 -> 活"的对应表。"""
m, x, _ = build(**kw)
m.optimize()
if m.SolCount == 0:
return {"obj": None, "plan": {}}
plan = {p: t for p in PEOPLE for t in TASKS if x[p, t].X > 0.5}
return {"obj": round(float(m.ObjVal), 2), "plan": plan}

def greedy():
"""不看全局，每人各挑自己成本最低的那个活。"""
plan = {p: min(TASKS, key=lambda t: COST[p][t]) for p in PEOPLE}
picked = list(plan.values())
double = [t for t in TASKS if picked.count(t) > 1]
missing = [t for t in TASKS if t not in picked]
return {"plan": plan, "cost": sum(COST[p][plan[p]] for p in PEOPLE),
"double": double, "missing": missing}

def relax_fair():
"""加"资深合计不超 650 元"这条规矩，整数解与线性松弛各解一次。"""
ip = run(cap=CAP)
m, x, _ = build(binary=False, cap=CAP)
m.optimize()
frac = {(p, t): round(float(x[p, t].X), 3) for p in PEOPLE for t in TASKS
if 1e-6 < x[p, t].X < 1 – 1e-6}
return ip, round(float(m.ObjVal), 2), frac

def stability(base_plan):
"""成本上下浮动 5%，重解 200 次，数每个格子留在答案里的次数。"""
rnd = random.Random(PERT["seed"])
keep = {(p, t): 0 for p in PEOPLE for t in TASKS}
same = 0
for _ in range(PERT["reps"]):
saved = {p: dict(COST[p]) for p in PEOPLE}
for p in PEOPLE:
for t in TASKS:
COST[p][t] = round(saved[p][t] * (1 + rnd.uniform(–PERT["pct"], PERT["pct"]) / 100), 2)
res = run()
for (p, t) in res["plan"].items():
keep[(p, t)] += 1
if res["plan"] == base_plan:
same += 1
COST.update({p: dict(saved[p]) for p in PEOPLE}) # 还原
return same, {f"{p}|{t}": round(v / PERT["reps"], 3) for (p, t), v in keep.items()}

# —————————————————————- 运行

def pad(s, n, right=False):
"""按显示宽度补空格：一个汉字占两格，否则终端里对不齐。"""
gap = max(n – sum(2 if ord(c) > 127 else 1 for c in s), 0)
return " " * gap + s if right else s + " " * gap

def main():
m, x, cons = build()
res = solve_both(m, name="021_谁做哪份活")

plan = {p: t for p in PEOPLE for t in TASKS if m.SolCount > 0 and x[p, t].X > 0.5}
total = sum(COST[p][t] for p, t in plan.items())
rowmin = {p: min(TASKS, key=lambda t: COST[p][t]) for p in PEOPLE}

g = greedy()
forbid_res = run(forbid=FORBID)
fair_ip, fair_lp, fair_frac = relax_fair()
same, keep = stability(plan)
lp = run(binary=False)

res["case"] = {
"people": PEOPLE,
"pname": PNAME,
"tasks": TASKS,
"tname": TNAME,
"cost": COST,
"plan": plan,
"total": total,
"perms": math.factorial(len(PEOPLE)),
"gap_to_rowmin": total – sum(COST[p][rowmin[p]] for p in PEOPLE),
"rowmin": rowmin,
"rowmin_total": sum(COST[p][rowmin[p]] for p in PEOPLE),
"greedy": g,
"lp_total": lp["obj"],
"lp_plan": lp["plan"],
"forbid": {"person": FORBID[0], "task": FORBID[1], "obj": forbid_res["obj"],
"plan": forbid_res["plan"], "delta": round(forbid_res["obj"] – total, 2),
"moved": [p for p in PEOPLE if forbid_res["plan"].get(p) != plan[p]]},
"fair": {"cap": CAP, "ip_obj": fair_ip["obj"], "ip_plan": fair_ip["plan"],
"lp_obj": fair_lp, "lp_frac": {f"{p}|{t}": v for (p, t), v in fair_frac.items()}},
"perturb": {"reps": PERT["reps"], "pct": PERT["pct"], "seed": PERT["seed"],
"same_plan": same, "keep": keep},
}
save_result(res, HERE / "结果.json")

# —————- 终端输出（正文逐行解释这些行）—————-
print("=" * 66)
print("求解状态：", res["gurobi"]["status"])
print(f"最小总成本：{res['gurobi']['obj']:.2f} 元")
print("-" * 66)
print(f" {pad('人', 4)}{pad('分到的活', 8)} 成本 他最便宜的是 多花")
for p in PEOPLE:
t = plan[p]
extra = COST[p][t] – COST[p][rowmin[p]]
print(f" {pad(PNAME[p], 4)}{pad(TNAME[t], 8)} {COST[p][t]:6.0f}"
f" {pad(TNAME[rowmin[p]], 12)} {extra:+5.0f}")
print("-" * 66)
print(f"五份活合计 {total:.0f} 元")
print(f"对照 1 每人挑最便宜：账面 {g['cost']:.0f} 元，"
f"但 {pad('、'.join(TNAME[t] for t in g['double']), 10)}各被两个人挑中，"
f"{'、'.join(TNAME[t] for t in g['missing'])}没人接")
print(f"对照 2 线性松弛 ：{lp['obj']:.2f} 元，解里没有一个分数——这一行很重要")
print("-" * 66)
print(f"实验 1 资深搭配：张和李合计不超过 {CAP:.0f} 元")
print(f" 整数解 {fair_ip['obj']:.0f} 元；线性松弛 {fair_lp:.0f} 元")
for key, v in res["case"]["fair"]["lp_frac"].items():
p, t = key.split("|")
print(f" 松弛解：{PNAME[p]} 做 {TNAME[t]} 的份额 {v:.2f}")
print("-" * 66)
print(f"实验 2 {PNAME[FORBID[0]]}不能做{TNAME[FORBID[1]]}："
f"{total:.0f} → {forbid_res['obj']:.0f} 元（+{forbid_res['obj'] – total:.0f}）")
print(f" 连锁换位 {len(res['case']['forbid']['moved'])} 人："
+ "、".join(f"{PNAME[p]}({TNAME[plan[p]]}→{TNAME[forbid_res['plan'][p]]})"
for p in res["case"]["forbid"]["moved"]))
print("-" * 66)
kk = res["case"]["perturb"]["keep"]
low = min(plan.items(), key=lambda kv: kk[f"{kv[0]}|{kv[1]}"])
print(f"实验 3 成本上下浮动 {PERT['pct']}%，重解 {PERT['reps']} 次："
f"原方案原样出现 {same} 次")
print(f" 原方案里最不稳的一格：{PNAME[low[0]]} 做 {TNAME[low[1]]}，"
f"只留下 {kk[f'{low[0]}|{low[1]}'] * 100:.0f}%")
print("双后端核对：", brief(res))
print("=" * 66)

if __name__ == "__main__":
main()

A.2　数据.json

{"story":{"org":"五个人的小设计工作室","scene":"周一早上，五个活要分给五个人，一人一个","cost_unit":"元"},"people":[{"key":"zhang","name":"张","role":"资深设计师，来了六年"},{"key":"li","name":"李","role":"资深设计师，擅长版式"},{"key":"wang","name":"王","role":"入职一年，剪片子快"},{"key":"zhao","name":"赵","role":"搭建出身，跑现场"},{"key":"chen","name":"陈","role":"实习生转正，做手册细"}],"tasks":[{"key":"poster","name":"品牌海报","note":"客户要三稿，周四交"},{"key":"detail","name":"详情页","note":"二十屏，图多"},{"key":"short","name":"短视频","note":"六十秒，要出镜"},{"key":"booth","name":"展台","note":"周五进场，要熬夜"},{"key":"manual","name":"手册","note":"六十四页，排版细"}],"cost":{"zhang":{"poster":400,"detail":560,"short":590,"booth":640,"manual":300},"li":{"poster":430,"detail":300,"short":500,"booth":580,"manual":370},"wang":{"poster":460,"detail":320,"short":380,"booth":520,"manual":480},"zhao":{"poster":600,"detail":550,"short":620,"booth":340,"manual":590},"chen":{"poster":470,"detail":410,"short":420,"booth":500,"manual":330}},"fair_cap":650,"forbid":{"person":"zhao","task":"booth"},"perturb":{"reps":200,"pct":5,"seed":20261021}}

A.3　结果.json

{"name":"021_谁做哪份活","gurobi":{"status":"OPTIMAL","runtime_s":0.0038,"obj":1750.0,"values":{"x[zhang,poster]":1.0,"x[zhang,detail]":–0.0,"x[zhang,short]":–0.0,"x[zhang,booth]":–0.0,"x[zhang,manual]":0.0,"x[li,poster]":–0.0,"x[li,detail]":1.0,"x[li,short]":–0.0,"x[li,booth]":–0.0,"x[li,manual]":–0.0,"x[wang,poster]":–0.0,"x[wang,detail]":0.0,"x[wang,short]":1.0,"x[wang,booth]":–0.0,"x[wang,manual]":–0.0,"x[zhao,poster]":–0.0,"x[zhao,detail]":–0.0,"x[zhao,short]":–0.0,"x[zhao,booth]":1.0,"x[zhao,manual]":–0.0,"x[chen,poster]":–0.0,"x[chen,detail]":–0.0,"x[chen,short]":–0.0,"x[chen,booth]":–0.0,"x[chen,manual]":1.0},"gap":0.0,"nodes":1,"iters":null},"copt":{"status":"OPTIMAL","runtime_s":0.0142,"obj":1750.0,"values":{"x[zhang,poster]":1.0,"x[zhang,detail]":0.0,"x[zhang,short]":0.0,"x[zhang,booth]":0.0,"x[zhang,manual]":0.0,"x[li,poster]":0.0,"x[li,detail]":1.0,"x[li,short]":0.0,"x[li,booth]":0.0,"x[li,manual]":0.0,"x[wang,poster]":0.0,"x[wang,detail]":0.0,"x[wang,short]":1.0,"x[wang,booth]":0.0,"x[wang,manual]":0.0,"x[zhao,poster]":0.0,"x[zhao,detail]":0.0,"x[zhao,short]":0.0,"x[zhao,booth]":1.0,"x[zhao,manual]":0.0,"x[chen,poster]":0.0,"x[chen,detail]":0.0,"x[chen,short]":0.0,"x[chen,booth]":0.0,"x[chen,manual]":1.0},"gap":null},"compare":{"same_status":true,"rel_diff_obj":0.0,"note":""},"case":{"people":["zhang","li","wang","zhao","chen"],"pname":{"zhang":"张","li":"李","wang":"王","zhao":"赵","chen":"陈"},"tasks":["poster","detail","short","booth","manual"],"tname":{"poster":"品牌海报","detail":"详情页","short":"短视频","booth":"展台","manual":"手册"},"cost":{"zhang":{"poster":400,"detail":560,"short":590,"booth":640,"manual":300},"li":{"poster":430,"detail":300,"short":500,"booth":580,"manual":370},"wang":{"poster":460,"detail":320,"short":380,"booth":520,"manual":480},"zhao":{"poster":600,"detail":550,"short":620,"booth":340,"manual":590},"chen":{"poster":470,"detail":410,"short":420,"booth":500,"manual":330}},"plan":{"zhang":"poster","li":"detail","wang":"short","zhao":"booth","chen":"manual"},"total":1750,"perms":120,"gap_to_rowmin":160,"rowmin":{"zhang":"manual","li":"detail","wang":"detail","zhao":"booth","chen":"manual"},"rowmin_total":1590,"greedy":{"plan":{"zhang":"manual","li":"detail","wang":"detail","zhao":"booth","chen":"manual"},"cost":1590,"double":["detail","manual"],"missing":["poster","short"]},"lp_total":1750.0,"lp_plan":{"zhang":"poster","li":"detail","wang":"short","zhao":"booth","chen":"manual"},"forbid":{"person":"zhao","task":"booth","obj":2080.0,"plan":{"zhang":"manual","li":"detail","wang":"short","zhao":"poster","chen":"booth"},"delta":330.0,"moved":["zhang","zhao","chen"]},"fair":{"cap":650.0,"ip_obj":1790.0,"ip_plan":{"zhang":"manual","li":"detail","wang":"short","zhao":"booth","chen":"poster"},"lp_obj":1770.0,"lp_frac":{"zhang|poster":0.5,"zhang|manual":0.5,"chen|poster":0.5,"chen|manual":0.5}},"perturb":{"reps":200,"pct":5,"seed":20261021,"same_plan":192,"keep":{"zhang|poster":0.96,"zhang|detail":0.0,"zhang|short":0.0,"zhang|booth":0.0,"zhang|manual":0.04,"li|poster":0.005,"li|detail":0.995,"li|short":0.0,"li|booth":0.0,"li|manual":0.0,"wang|poster":0.005,"wang|detail":0.005,"wang|short":0.99,"wang|booth":0.0,"wang|manual":0.0,"zhao|poster":0.0,"zhao|detail":0.0,"zhao|short":0.0,"zhao|booth":1.0,"zhao|manual":0.0,"chen|poster":0.03,"chen|detail":0.0,"chen|short":0.01,"chen|booth":0.0,"chen|manual":0.96}}}}