基于CPLEX使用元组求解简单装配线平衡问题的建模方法

全程不使用冗杂邻接矩阵，所有结构化数据用元组存储，逻辑可直接落地改造，适配新手理解节奏。

1. 基础数据元组定义 #

不需要提前构造二维邻接矩阵，所有数据用一维/二元元组存储即可：

• 工序数据：存为键值对结构，键为工序唯一ID，值为对应工序的加工时长，例如tasks = {1:2, 2:3, 3:5, 4:1, 5:4}，直接遍历所有工序ID就能拿到对应时长。
• 先后约束：存为二元元组列表，每一个元组(a,b)代表工序a必须安排在工序b之前完成，有多少条先后约束就存多少个元组，不存在约束的工序对完全不需要存储，例如先后关系为1在3前、2在3前、3在4和5前，就直接写precedence = [(1,3), (2,3), (3,4), (3,5)]，大规模问题下比邻接矩阵省90%以上的冗余存储。
• 固定参数：直接存标量，cycle_time为给定的生产节拍，max_station为工位数量上限，新手可以直接设为工序总数量（对应每个工位放1道工序的极端可行解，保证模型一定有可行域）。

2. 决策变量定义 #

两类0-1变量即可覆盖需求：

• x[t,s]：0-1变量，当工序t被分配到工位s时取值为1，否则为0。
• y[s]：0-1变量，当工位s被实际启用时取值为1，否则为0。

3. 核心约束编写 #

所有约束直接遍历元组集合生成，不需要做矩阵索引转换：

• 工序唯一分配约束：对每道工序，必须分配到恰好一个工位。对应CPLEX写法：

for t in tasks:
    model.add_constraint(model.sum(x[t, s] for s in range(1, max_station+1)) == 1)

• 生产节拍约束：每个启用工位上的所有工序加工时长总和不能超过给定节拍，未启用的工位不能分配任何工序。对应CPLEX写法：

for s in range(1, max_station+1):
    model.add_constraint(model.sum(tasks[t] * x[t, s] for t in tasks) <= cycle_time * y[s])

• 先后顺序约束：直接遍历存好的先后约束元组列表，要求前序工序所在工位编号小于等于后序工序所在工位编号即可，不需要额外定义工位位置变量，用工位索引加权求和直接得到工序对应工位号。对应CPLEX写法：

for (pre_t, post_t) in precedence:
    pre_station = model.sum(s * x[pre_t, s] for s in range(1, max_station+1))
    post_station = model.sum(s * x[post_t, s] for s in range(1, max_station+1))
    model.add_constraint(pre_station <= post_station)

• 优化目标：最小化启用的工位总数，即model.minimize(model.sum(y[s] for s in range(1, max_station+1)))

4. 新手调试提示 #

• 工位编号从1开始计数，不要从0开始，避免加权计算工位号时0值导致逻辑错误。
• 第一次跑模型前，先打印precedence列表抽3-5条核对先后顺序，避免把前序、后序工序写反。
• 先用10道工序以内的小算例验证逻辑跑通，再替换大规模数据，元组存储的方式在千级工序规模下运行效率明显高于邻接矩阵方案。

内容的提问来源于stack exchange，提问作者Jannik Schneider