无法使用ILOG CPLEX Optimizer求解指派问题求助

这个指派问题来自Google OR-Tools的示例场景，其他框架甚至Excel Solver都能完成求解，但使用ILOG CPLEX求解时出现错误：DOcplexException: Model<Assignemnt_Problem> did not solve successfully。

用户在Jupyter Notebook中的代码如下：

import cplex
import docplex.mp
from docplex.mp.model import Model
import numpy as np
assignment_model = Model(name='Assignemnt_Problem', log_output=True)
costs = np.array([[90,80,75,70],
  [35,85,55,65],
  [125,95,90,95],
  [45,110,95,115],
  [50,100,90,100]])
x = assignment_model.binary_var_matrix(costs.shape[0], costs.shape[1], name="a")
assignment_model.add_constraints((sum(x[i,j] for i in range (costs.shape[0])) <=1 
                              for j in range (costs.shape[1])), names ="workers")
assignment_model.add_constraints((sum(x[i,j] for j in range (costs.shape[1])) ==1 
                              for i in range (costs.shape[0])), names ="tasks")
obj_fn = sum(x[i,j]*costs[i,j] for i in range (costs.shape[0]) for j in range(costs.shape[1]))
assignment_model.set_objective('min', obj_fn)
assignment_model.print_information()
assignment_model.solve()
print('Optimization is done. Objective Function Value: %.2f' % assignment_model.objective_value)

错误原因 #

模型约束存在冲突：

• 任务约束要求每个工人（共5个）必须分配到1个任务（sum(x[i,j] for j...) ==1）
• 工人约束要求每个任务最多被1个工人承担（sum(x[i,j] for i...) <=1）
  但数据中任务只有4个，无法满足5个工人各分配一个任务的要求，导致模型不可行，因此求解失败。

修正方案 #

根据实际需求选择以下两种方案之一：

方案1：允许部分工人不分配任务

将工人的任务分配约束从==1改为<=1，即允许工人可以不被分配任务：

# 修改后的任务约束
assignment_model.add_constraints((sum(x[i,j] for j in range (costs.shape[1])) <=1 
                                  for i in range (costs.shape[0])), names ="tasks")

方案2：增加任务数量

确保任务数量≥工人数量（至少5个任务），这样每个工人都能分配到唯一任务，同时每个任务最多被一个工人承担，约束不再冲突。

修正后重新运行代码，即可正常求解得到最优解。

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