如何在Google Apps Script的LinearOptimizationService中设置「每个工人恰好分配一个任务」的约束以求解指派问题

我看到你在尝试用Google Apps Script的LinearOptimizationService实现指派问题，目前的代码已经处理了「每个任务恰好分配给一个工人」的约束，但还没设置「每个工人必须恰好分配一个任务」——其实这个修改非常简单，只需要调整现有约束的上下界就行。

具体修改点 #

你当前针对工人的约束设置的是最多分配一个任务（上下界为0, 1），只需要把这段代码里的约束上下界都改成1，就能强制每个工人必须被分配恰好一个任务：

找到这段代码：

// Each worker is assigned to at most one task.
for (let i = 0; i < costMatrix.length; ++i) {
  constraint = engine.addConstraint(0, 1);
  for (let j = 0; j < costMatrix[0].length; ++j) {
    constraint.setCoefficient(`x${i}${j}`, 1);
  }
}

把engine.addConstraint(0, 1)改成engine.addConstraint(1, 1)即可。

修正后的完整代码 #

function myFunction() { 
  // Create the variables 
  var engine = LinearOptimizationService.createEngine(); 
  const costMatrix = [[7,5,4,8,3] ,[2,5,6,7,1] ,[2,8,9,5,2] ,[2,5,6,7,1] ,[2,8,1,5,9]] 
  const capacities = [1,1,1,1,1] 
  
  // initialize the decision variables 
  x = new Array(costMatrix.length); 
  for (let i=0; i<costMatrix.length; i++){ 
    x[i] = new Array(costMatrix[0].length); 
    for (let j=0; j<costMatrix[0].length; j++){ 
      x[i][j] = engine.addVariable(`x${i}${j}`, 0, 1, LinearOptimizationService.VariableType.INTEGER); 
    } 
  } 
  
  // Updated: Each worker is assigned to exactly one task.
  for (let i = 0; i < costMatrix.length; ++i) { 
    constraint = engine.addConstraint(1, 1); // Changed lower bound from 0 to 1
    for (let j = 0; j < costMatrix[0].length; ++j) { 
      constraint.setCoefficient(`x${i}${j}`, 1); 
    } 
  } 
  
  // Each task is assigned to exactly one worker. 
  for (let j = 0; j < costMatrix[0].length; ++j) { 
    constraint = engine.addConstraint(1, 1); 
    for (let i = 0; i < costMatrix.length; ++i) { 
      constraint.setCoefficient(`x${i}${j}`, 1); 
    } 
  } 
  
  // Set objective coefficients
  for (let i = 0; i < costMatrix.length; ++i) { 
    for (let j = 0; j < costMatrix[0].length; ++j) { 
      engine.setObjectiveCoefficient(`x${i}${j}`, costMatrix[i][j]); 
    } 
  } 
  
  engine.setMinimization() 
  
  // Solve the linear program 
  var solution = engine.solve(30); 
  if (!solution.isValid()) { 
    throw 'No solution ' + solution.getStatus(); 
  } 
  
  Logger.log('ObjectiveValue: ' + solution.getObjectiveValue()); 
  for (let i=0; i<costMatrix.length; i++){ 
    for (let j=0; j<costMatrix[0].length; j++){ 
      Logger.log(`Value of: x${i}${j} ` + solution.getVariableValue(`x${i}${j}`)); 
    } 
  } 
}

为什么这样修改 #

你的场景是标准的指派问题（工人数量和任务数量相等，都是5个），需要满足两个双向约束：

• 每个任务必须恰好分配给一个工人（你已经正确实现）
• 每个工人必须恰好分配一个任务（就是我们修正的部分）

修改后，求解器会找到总成本最小的完美匹配，确保所有工人和任务都被充分分配，不会出现闲置的工人或未被处理的任务。

内容的提问来源于stack exchange，提问作者A. Albinus