Gurobi Python成本最小化模型无报错但未生成合理解决方案求助

问题概述 #

使用Gurobi Python API开发了包含可变成本与固定成本的生产成本最小化模型，需完成：

• 将任务分配至多个工作站，满足周期时间限制
• 评估2类机器的选用（高可变成本对应高固定成本）
• 任务的分配时长与成本仅关联机器类型，与工作站编号无关

模型运行无报错，但求解结果显示最优目标值为0，显然不符合实际需求，推测约束条件或目标函数存在设置错误。

原代码 #

import gurobipy as gp
from gurobipy import GRB, quicksum

stations = [1,2,3,4]
tasks = ['w01','w02','w03']
durations = {('w01','BTC1'):200,
             ('w02','BTC1'):500,
             ('w03','BTC1'):300,
             ('w01','BTC2'):100,
             ('w02','BTC2'):250,
             ('w03','BTC2'):150 }

successors = {'w01':[],'w02':['w01'],'w03':['w01']}

types = ['BTC1','BTC2']
arcs = [(i,j) for i in tasks for j in types]
arcs2 = [(i,j) for i in stations for j in tasks]
C = 500
C_min = 100

edges, v_cost, f_cost = gp.multidict({
    ('BTC1','w01'): [150,200000],
    ('BTC1','w02'): [200,200000],
    ('BTC1','w03'): [180,200000],
    ('BTC2','w01'): [120,300000],
    ('BTC2','w02'): [160,300000],
    ('BTC2','w03'): [100,300000]
})

m = gp.Model()
y = m.addVars(stations, vtype=GRB.BINARY, name='y')
x = m.addVars(arcs, vtype=GRB.CONTINUOUS, name='x',lb=0,ub=1) # Variable for share of assignment between 0 and 1
a = m.addVars(arcs2, vtype=GRB.CONTINUOUS, name='a',lb=0,ub=1)

# 原任务分配约束
m.addConstrs(quicksum(a[i,j] for j in tasks) == 1 for i in stations)

# 原容量约束
m.addConstrs(quicksum(durations[i,j]*x[i,j] for i in tasks for j in types)
               <= C*y[j] for j in stations) 

# 原最小容量约束
m.addConstrs(quicksum(durations[i,j]*x[i,j] for i in tasks for j in types)
         >= C_min*y[j] for j in stations)

# 原优先级约束
m.addConstrs(quicksum(p*x[k,j] for j in types for p in stations) >= 
             quicksum(p*x[i,j] for j in types for p in stations) 
             for k in tasks for i in successors[k] if k!= 'w01')

m.setObjective(x.prod(v_cost)+y.prod(f_cost), GRB.MINIMIZE)
m.optimize()

求解输出 #

Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (win64)
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 14 rows, 22 columns and 76 nonzeros
Model fingerprint: 0x4cbb069e
Variable types: 18 continuous, 4 integer (4 binary)
Coefficient statistics:
  Matrix range     [1e+00, 5e+02]
  Objective range  [0e+00, 0e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+00]
Presolve removed 11 rows and 16 columns
Presolve time: 0.01s
Presolved: 3 rows, 6 columns, 14 nonzeros
Variable types: 6 continuous, 0 integer (0 binary)

Root relaxation: objective 0.000000e+00, 0 iterations, 0.01 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0       0.0000000    0.00000  0.00%     -    0s

Explored 1 nodes (0 simplex iterations) in 0.12 seconds (0.00 work units)
Thread count was 4 (of 4 available processors)

Solution count 1: 0 

Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%

问题排查与修正点 #

1. 目标函数变量映射完全错误 #

• 可变成本部分：x的变量键为(任务, 机器类型)，但v_cost的键为(机器类型, 任务)，两者顺序完全相反，导致Gurobi无法匹配系数，可变成本被默认视为0。
• 固定成本部分：y是工作站的二进制变量（是否启用），但f_cost的键为(机器类型, 任务)，维度不匹配，固定成本同样被视为0。
• 最终目标函数实际为0，因此求解结果必然是0。

2. 约束条件逻辑错误 #

• 任务分配约束颠倒：原约束要求每个工作站的任务占比之和为1，实际需求应为每个任务在所有工作站的分配占比之和为1，约束逻辑完全相反。
• 容量约束索引混用：C*y[j]中的j是机器类型，但y的索引是工作站编号，索引混用导致约束逻辑混乱；同时未关联a（任务在工作站的分配）和x（任务选用的机器类型），时长计算与工作站启用状态脱节。
• 优先级约束无效：x变量仅关联任务和机器类型，与工作站无关，无法通过p*x[k,j]体现任务的执行工作站，优先级约束完全无效。

3. 变量关联缺失 #

x（任务选用机器类型的占比）与a（任务在工作站的分配占比）之间无约束关联，变量相互独立，模型无法生成有意义的分配方案。

核心修正代码示例 #

# 新增工作站-机器类型绑定变量：z[i,t]表示工作站i选用机器类型t
z = m.addVars(stations, types, vtype=GRB.BINARY, name='z')
# 每个启用的工作站只能选一种机器类型
m.addConstrs(quicksum(z[i,t] for t in types) == y[i] for i in stations)

# 修正成本映射，对齐变量键
v_cost = {
    ('w01','BTC1'):150, ('w02','BTC1'):200, ('w03','BTC1'):180,
    ('w01','BTC2'):120, ('w02','BTC2'):160, ('w03','BTC2'):100
}
f_cost = {
    (1,'BTC1'):200000, (1,'BTC2'):300000,
    (2,'BTC1'):200000, (2,'BTC2'):300000,
    (3,'BTC1'):200000, (3,'BTC2'):300000,
    (4,'BTC1'):200000, (4,'BTC2'):300000
}

# 修正目标函数
m.setObjective(x.prod(v_cost) + z.prod(f_cost), GRB.MINIMIZE)

# 修正任务分配约束：每个任务在所有工作站的分配占比之和为1
m.addConstrs(quicksum(a[i,j] for i in stations) == 1 for j in tasks)

# 修正容量约束：关联任务分配、机器类型与工作站容量
m.addConstrs(quicksum(a[i,j] * quicksum(x[j,t] * durations[j,t] for t in types) for j in tasks) <= C * y[i] for i in stations)
m.addConstrs(quicksum(a[i,j] * quicksum(x[j,t] * durations[j,t] for t in types) for j in tasks) >= C_min * y[i] for i in stations)

# 修正优先级约束：前驱任务的执行工作站编号不大于后继任务
m.addConstrs(quicksum(i * a[i,j_prev] for i in stations) <= quicksum(i * a[i,j_next] for i in stations) 
             for j_next in tasks for j_prev in successors[j_next])

内容的提问来源于stack exchange，提问作者Harun Gül