Google OR-Tools : 指定與分配 - 2. Assignment with Teams of Workers

原文連結
跟上篇類似的例子，但這次有六個工人，
我們先將六個工人分為兩個團隊，
每個團隊最多可以執行兩個任務

	任務0	任務1	任務2	任務3
0號工人	90	76	75	70
1號工人	35	85	55	65
2號工人	125	95	90	105
3號工人	45	110	95	115
4號工人	60	105	80	75
5號工人	45	65	110	95

# Step 1: Import the linear solver, or MIP, or cp_model

from ortools.linear_solver import pywraplp

# Step 2: Add the solution printer

此步驟不用

# Step 3: Declare the linear solver, or MIP, or cp_model

  solver = pywraplp.Solver('SolveAssignmentProblemMIP',
                           pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

# Step 4: Create a database and requests

  cost = [[90, 76, 75, 70],
          [35, 85, 55, 65],
          [125, 95, 90, 105],
          [45, 110, 95, 115],
          [60, 105, 80, 75],
          [45, 65, 110, 95]]
  num_workers = len(costs)
  num_tasks = len(cost[0])
  team1 = [0, 2, 4]
  team2 = [1, 3, 5]
  team_max = 2

先將工人分成team1 & 2
team 1 有 0, 2, 4 號工人
team 2 有 1, 3, 5 號工人

# Step 5: Create the variables

  x = {}

  for i in range(num_workers):
    for j in range(num_tasks):
      x[i, j] = solver.BoolVar('x[%i,%i]' % (i, j))

這邊跟上篇有點不一樣，上篇是用solver.IntVar(0, 1, '')
這裡是用solver.BoolVar('x[%i, %j]' % (i, j))
兩者差別在於前一篇需要將每一個 x[i, j] 都給予一個數字（不論是 0 或是 1 ）
這樣之後和cost相乘才可以得出最小值
但這邊不需要，所以用BoolVar就好

# Step 6: Define the constraints

 for i in range(num_workers):
    solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)

每個工人最多只能被指定一項工作：
每一個工人 i 在這麼多項任務j中最多只能有一個是1，其他都要是0
所以 x[i, j] 加總起來要小於等於1

  for j in range(num_tasks):
    solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)

每個任務僅分配給一個工人：
每一項任務 j ，在這些工人 i 中只能有一個人是 1，其他都是0
所以 x[i, j] 加總起來要等於1

  solver.Add(solver.Sum([x[i, j] for i in team1 for j in range(num_tasks)]) <= team_max)
  solver.Add(solver.Sum([x[i, j] for i in team2 for j in range(num_tasks)]) <= team_max)

每個團隊有三個人，每個團隊最多可以執行兩個任務
我們將第一行拆解成下列，team1最多只能有兩個任務

solver.Add(solver.Sum([x[i, j] for i in team1 for j in range(num_tasks)]) <= team_max)
=>  y = （Sum([x[i, j] for i in team1 for j in range(num_tasks)]) <= team_max ）
=>  y1 = x[i, j] for i in team1 for j in range(num_tasks)
=>  task = {}
=>  for i in team1:
      for j in range(num_tasks):
        task.append(x[i, j])

# Step 7: Define the objective

  solver.Minimize(solver.Sum([cost[i][j] * x[i,j] for i in range(num_workers)
                                                  for j in range(num_tasks)]))

上面若覺得太複雜，可以拆解如下：

objective_terms = []
for i in range(num_workers):
    for j in range(num_tasks):
        objective_terms.append(costs[i][j] * x[i, j])
solver.Minimize(solver.Sum(objective_terms))

# Step 8: Create a solver and invoke solve

status = solver.Solve()

# Step 9: Call a printer and display the results

  print('Total cost = ', solver.Objective().Value())
  print()
  for i in range(num_workers):
    for j in range(num_tasks):
      if x[i, j].solution_value() > 0:
        print('Worker %d assigned to task %d.  Cost = %d' % (
              i,
              j,
              cost[i][j]))

最後可以得到下面結果：

Minimum cost assignment:  250.0

Worker 0 assigned to task 2.  Cost = 75
Worker 1 assigned to task 0.  Cost = 35
Worker 4 assigned to task 3.  Cost = 75
Worker 5 assigned to task 1.  Cost = 65

Time =  6  milliseconds