Gurobi中两类约束导致LP模型不可行的原因咨询

让我们直接定位你模型不可行的核心原因——第二类序列约束（third_constraint）的逻辑错误导致了矛盾约束，具体分析如下：

变量与约束回顾 #

先明确关键变量：

• g[i,j]：二进制变量，表示工件i在某台机器上优先于j加工
• x[i,r]：二进制变量，表示工件i被分配至机器r

你的三类约束中，问题出在第二类序列约束的写法上：

for i in packages:
    for j in packages:
        if i != j:
            for r in machines:
                model.addConstr(g[i, j] + g[j, i] <= (x[i, r] + x[j, r]) / 2, name = 'third constraint')

核心冲突点 #

假设工件i和j被分配到同一台机器r1（即x[i,r1]=1、x[j,r1]=1）：

1. 针对r1的第一类约束要求：g[i,j]+g[j,i] >= 1+1-1=1
2. 但针对其他机器r2/r3的第二类约束要求：g[i,j]+g[j,i] <= (0+0)/2=0

一边强制g[i,j]+g[j,i]至少为1，另一边强制它最多为0，这是不可调和的矛盾，直接导致模型不可行。

约束逻辑修正 #

你的第二类约束的真实意图应该是：只有当i和j被分配到同一台机器时，g[i,j]和g[j,i]才能有一个为1；若不在同一台机器，两者必须都为0。正确的约束写法应该避免对所有机器遍历添加约束，而是用全局的机器分配判断：

修正方案1（直接乘积形式） #

for i in packages:
    for j in packages:
        if i != j:
            # 只有当i和j在同一台机器时，g[i,j]+g[j,i]才能取1，否则必须为0
            model.addConstr(g[i,j] + g[j,i] <= quicksum(x[i,r] * x[j,r] for r in machines), name='third constraint')

因为x[i,r] * x[j,r]仅当i和j都分配到r时为1，求和后结果为1当且仅当i和j在同一台机器，否则为0。这样约束就准确表达了需求：不同机器的工件之间不能有优先级关系。

修正方案2（大M法，避免二次项） #

如果你的求解器对二次项支持有限，可以用大M法改写为线性约束：

M = 1  # 因为g是二进制变量，M取1足够
for i in packages:
    for j in packages:
        if i != j:
            for r in machines:
                # 若i不在r上，则g[i,j]必须为0
                model.addConstr(g[i,j] <= x[i,r], name='third_constraint_gij')
                # 若j不在r上，则g[i,j]必须为0
                model.addConstr(g[i,j] <= x[j,r], name='third_constraint_gij2')
            # 等价于：g[i,j]只能在i和j同机器时为1

这个线性约束和方案1的逻辑完全一致，且避免了二次变量。

额外验证点 #

移除第二类约束后模型可行但g全为0，是因为此时没有约束强制同机器工件必须有优先级关系，求解器会选择最容易满足的g=0解。修正第二类约束后，同机器的工件会被第一类约束强制g[i,j]+g[j,i]=1，符合你的调度需求。

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