广义指派问题

广义指派问题（generalized assignment problem，GAP）把每项任务完整指派给一个执行者，既考虑指派成本，也限制每位执行者的资源总量。同一项任务换人执行时，成本与资源消耗都可能改变。普通一人一任务的指派只是其中一个特殊情形；广义模型允许一人承担多项任务，但不能超过可用工时、预算或设备容量。

两位执行者A、B各有四小时。三项任务对A的工时需求依次为三、二、二小时，成本为一、二、三百元；对B的工时为二、三、二小时，成本为二、一、四百元。逐项选最便宜的人会把任务一、三给A，A需要五小时，超过容量。任务之间通过共同的资源上限耦合，不能各自单独决定。

指派与容量的联合模型

令任务为 $i=1,\dots ,n$，执行者为 $j=1,\dots ,m$；$a_{ji}\ge 0$ 表示工时，$b_j\ge 0$ 表示可用工时，$c_{ji}$ 表示成本，$x_{ji}$ 为是否指派的二元变量： $$\begin{array}{cc}min& \sum _j\sum _i{c}_{ji}{x}_{ji},\\ \sum _j{x}_{ji}& =1(i=1,\dots ,n),\\ \sum _i{a}_{ji}{x}_{ji}& \le b_j(j=1,\dots ,m).\end{array}$$ 同一列的和等于一，保证任务不被漏掉或分给两人；每一行则累计对应执行者的实际消耗。若把所有 $a_{ji}$ 都误写成与人无关的 $a_i$，就删除了人员效率的差异。

三任务的完整最优性检验

只需枚举交给A的任务子集，B承担其余部分。A全不接时，B工时七超限；A全接时也需七。A只接任务一、二、三时，B剩余工时分别为五、四、五，仅中间一种可行，其成本为 $2+2+4=8$。A接两项时，$\{1,2\}$ 和 $\{1,3\}$ 工时都是五，超限；只有 $\{2,3\}$ 工时四可行，B只接任务一需二小时，成本为 $2+3+2=7$。因此全部八种指派中仅两种可行，最优成本七百元。

箭头表示任务归属。每个执行者旁列工时，底部单独汇总成本，避免把两个不同单位的数相加。

小实例精确程序

以下把每个任务的执行者编号列成一个长度 $n$ 的向量，枚举全部 $m^n$ 种指派。输入成本和工时均按执行者逐行给出，返回总成本与每个任务的执行者编号；若不可行，返回无穷与 None。

Python 3

from itertools import product
import math

def generalized_assignment(costs, resources, capacities):
    c, a, b = tuple(map(tuple,costs)), tuple(map(tuple,resources)), tuple(capacities)
    m = len(c)
    if not m or len(a) != m or len(b) != m:
        raise ValueError("matching nonempty worker data required")
    n = len(c[0])
    if any(len(row) != n for row in c+a):
        raise ValueError("matching rectangular matrices required")
    if any(not math.isfinite(x) for row in c for x in row):
        raise ValueError("finite costs required")
    if any(not math.isfinite(x) or x < 0 for row in a for x in row):
        raise ValueError("nonnegative finite resource use required")
    if any(not math.isfinite(x) or x < 0 for x in b):
        raise ValueError("nonnegative finite capacities required")
    best, assignment = math.inf, None
    for worker in product(range(m), repeat=n):
        load = [0] * m
        for i,j in enumerate(worker):
            load[j] += a[j][i]
        if any(load[j] > b[j] for j in range(m)):
            continue
        value = sum(c[j][i] for i,j in enumerate(worker))
        if value < best:
            best, assignment = value, worker
    return best, assignment

print(generalized_assignment([[1,2,3],[2,1,4]], [[3,2,2],[2,3,2]], [4,4]))
# (7, (1, 0, 0))

枚举过程中每个任务始终恰有一个归属，容量检查与模型逐行一致；所有归属向量都被覆盖，因此最小可行成本就是全局最优。时间为 $O((n+m)m^n)$，除输入外保存当前归属和载荷需 $O(n+m)$ 空间。它用于教学核对，小型精确枚举的保证不能被误解成大规模高效算法。

变式。 将A的容量从四降为三，原七百元方案超限，只剩A接任务二、B接任务一和三的八百元方案。如果B容量也降为三，前述两种方案都不合法，且减容量不可能产生新的方案，所以问题不可行。任务不允许拆分是这里的关键：把它放宽成分数分配，既改变了业务含义，也可能大幅降低数学最优值。