本部分介绍了线性和赋值求解器，一种专用的 可以解决简单的分配问题，这比 MIP 或 CP-SAT 求解器。然而，MIP 和 CP-SAT 求解器可以 更广泛的问题，因此在大多数情况下是最佳选择。
费用矩阵
工作器和任务的费用如下表所示。
| 工作器 | 任务 0 | 任务 1 | 任务 2 | 任务 3 |
|---|---|---|---|---|
| 0 | 90 | 76 | 75 | 70 |
| 1 | 35 | 85 | 55 | 65 |
| 2 | 125 | 95 | 90 | 105 |
| 3 | 45 | 110 | 95 | 115 |
以下部分介绍了一个 Python 程序，可用于处理作业， 计算问题。
导入库
导入所需库的代码如下所示。
Python
import numpy as np from ortools.graph.python import linear_sum_assignment
C++
#include "ortools/graph/assignment.h" #include <cstdint> #include <numeric> #include <string> #include <vector>
Java
import com.google.ortools.Loader; import com.google.ortools.graph.LinearSumAssignment; import java.util.stream.IntStream;
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Graph;
定义数据
以下代码会为程序创建数据。
Python
costs = np.array(
[
[90, 76, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 105],
[45, 110, 95, 115],
]
)
# Let's transform this into 3 parallel vectors (start_nodes, end_nodes,
# arc_costs)
end_nodes_unraveled, start_nodes_unraveled = np.meshgrid(
np.arange(costs.shape[1]), np.arange(costs.shape[0])
)
start_nodes = start_nodes_unraveled.ravel()
end_nodes = end_nodes_unraveled.ravel()
arc_costs = costs.ravel()C++
const int num_workers = 4; std::vector<int> all_workers(num_workers); std::iota(all_workers.begin(), all_workers.end(), 0); const int num_tasks = 4; std::vector<int> all_tasks(num_tasks); std::iota(all_tasks.begin(), all_tasks.end(), 0); const std::vector<std::vector<int>> costs = {{ {{90, 76, 75, 70}}, // Worker 0 {{35, 85, 55, 65}}, // Worker 1 {{125, 95, 90, 105}}, // Worker 2 {{45, 110, 95, 115}}, // Worker 3 }};
Java
final int[][] costs = {
{90, 76, 75, 70},
{35, 85, 55, 65},
{125, 95, 90, 105},
{45, 110, 95, 115},
};
final int numWorkers = 4;
final int numTasks = 4;
final int[] allWorkers = IntStream.range(0, numWorkers).toArray();
final int[] allTasks = IntStream.range(0, numTasks).toArray();C#
int[,] costs = {
{ 90, 76, 75, 70 },
{ 35, 85, 55, 65 },
{ 125, 95, 90, 105 },
{ 45, 110, 95, 115 },
};
int numWorkers = 4;
int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray();
int numTasks = 4;
int[] allTasks = Enumerable.Range(0, numTasks).ToArray();该数组是成本矩阵，其 i、j 条目是工作器 i 的成本 以执行任务 j。有四个 worker，分别与 矩阵，以及四个任务（与各列相对应）。
创建求解器
该程序使用 线性分配求解器 用于解决作业问题的专业求解器。
以下代码将创建求解器。
Python
assignment = linear_sum_assignment.SimpleLinearSumAssignment()
C++
SimpleLinearSumAssignment assignment;
Java
LinearSumAssignment assignment = new LinearSumAssignment();
C#
LinearSumAssignment assignment = new LinearSumAssignment();
添加约束条件
以下代码通过循环遍历 worker 来增加求解器的开销， 任务。
Python
assignment.add_arcs_with_cost(start_nodes, end_nodes, arc_costs)
C++
for (int w : all_workers) { for (int t : all_tasks) { if (costs[w][t]) { assignment.AddArcWithCost(w, t, costs[w][t]); } } }
Java
// Add each arc. for (int w : allWorkers) { for (int t : allTasks) { if (costs[w][t] != 0) { assignment.addArcWithCost(w, t, costs[w][t]); } } }
C#
// Add each arc. foreach (int w in allWorkers) { foreach (int t in allTasks) { if (costs[w, t] != 0) { assignment.AddArcWithCost(w, t, costs[w, t]); } } }
调用求解器
以下代码会调用求解器。
Python
status = assignment.solve()
C++
SimpleLinearSumAssignment::Status status = assignment.Solve();
Java
LinearSumAssignment.Status status = assignment.solve();
C#
LinearSumAssignment.Status status = assignment.Solve();
显示结果
以下代码显示了该解决方案。
Python
if status == assignment.OPTIMAL: print(f"Total cost = {assignment.optimal_cost()}\n") for i in range(0, assignment.num_nodes()): print( f"Worker {i} assigned to task {assignment.right_mate(i)}." + f" Cost = {assignment.assignment_cost(i)}" ) elif status == assignment.INFEASIBLE: print("No assignment is possible.") elif status == assignment.POSSIBLE_OVERFLOW: print("Some input costs are too large and may cause an integer overflow.")
C++
if (status == SimpleLinearSumAssignment::OPTIMAL) { LOG(INFO) << "Total cost: " << assignment.OptimalCost(); for (int worker : all_workers) { LOG(INFO) << "Worker " << std::to_string(worker) << " assigned to task " << std::to_string(assignment.RightMate(worker)) << ". Cost: " << std::to_string(assignment.AssignmentCost(worker)) << "."; } } else { LOG(INFO) << "Solving the linear assignment problem failed."; }
Java
if (status == LinearSumAssignment.Status.OPTIMAL) { System.out.println("Total cost: " + assignment.getOptimalCost()); for (int worker : allWorkers) { System.out.println("Worker " + worker + " assigned to task " + assignment.getRightMate(worker) + ". Cost: " + assignment.getAssignmentCost(worker)); } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); }
C#
if (status == LinearSumAssignment.Status.OPTIMAL) { Console.WriteLine($"Total cost: {assignment.OptimalCost()}."); foreach (int worker in allWorkers) { Console.WriteLine($"Worker {worker} assigned to task {assignment.RightMate(worker)}. " + $"Cost: {assignment.AssignmentCost(worker)}."); } } else { Console.WriteLine("Solving the linear assignment problem failed."); Console.WriteLine($"Solver status: {status}."); }
以下输出显示了工作器给任务的最佳分配。
Total cost = 265 Worker 0 assigned to task 3. Cost = 70 Worker 1 assigned to task 2. Cost = 55 Worker 2 assigned to task 1. Cost = 95 Worker 3 assigned to task 0. Cost = 45 Time = 0.000147 seconds
下图以虚线表示该解法。通过 虚线边旁的数字是它们的费用 此分配的总等待时间是以下两项费用的总和： 也就是 265
在图形理论中，两部分图中的一组边与 右侧只有一个节点的情况称为完美匹配。
整个计划
以下是整个计划。
Python
"""Solve assignment problem using linear assignment solver.""" import numpy as np from ortools.graph.python import linear_sum_assignment def main(): """Linear Sum Assignment example.""" assignment = linear_sum_assignment.SimpleLinearSumAssignment() costs = np.array( [ [90, 76, 75, 70], [35, 85, 55, 65], [125, 95, 90, 105], [45, 110, 95, 115], ] ) # Let's transform this into 3 parallel vectors (start_nodes, end_nodes, # arc_costs) end_nodes_unraveled, start_nodes_unraveled = np.meshgrid( np.arange(costs.shape[1]), np.arange(costs.shape[0]) ) start_nodes = start_nodes_unraveled.ravel() end_nodes = end_nodes_unraveled.ravel() arc_costs = costs.ravel() assignment.add_arcs_with_cost(start_nodes, end_nodes, arc_costs) status = assignment.solve() if status == assignment.OPTIMAL: print(f"Total cost = {assignment.optimal_cost()}\n") for i in range(0, assignment.num_nodes()): print( f"Worker {i} assigned to task {assignment.right_mate(i)}." + f" Cost = {assignment.assignment_cost(i)}" ) elif status == assignment.INFEASIBLE: print("No assignment is possible.") elif status == assignment.POSSIBLE_OVERFLOW: print("Some input costs are too large and may cause an integer overflow.") if __name__ == "__main__": main()
C++
#include "ortools/graph/assignment.h" #include <cstdint> #include <numeric> #include <string> #include <vector> namespace operations_research { // Simple Linear Sum Assignment Problem (LSAP). void AssignmentLinearSumAssignment() { SimpleLinearSumAssignment assignment; const int num_workers = 4; std::vector<int> all_workers(num_workers); std::iota(all_workers.begin(), all_workers.end(), 0); const int num_tasks = 4; std::vector<int> all_tasks(num_tasks); std::iota(all_tasks.begin(), all_tasks.end(), 0); const std::vector<std::vector<int>> costs = {{ {{90, 76, 75, 70}}, // Worker 0 {{35, 85, 55, 65}}, // Worker 1 {{125, 95, 90, 105}}, // Worker 2 {{45, 110, 95, 115}}, // Worker 3 }}; for (int w : all_workers) { for (int t : all_tasks) { if (costs[w][t]) { assignment.AddArcWithCost(w, t, costs[w][t]); } } } SimpleLinearSumAssignment::Status status = assignment.Solve(); if (status == SimpleLinearSumAssignment::OPTIMAL) { LOG(INFO) << "Total cost: " << assignment.OptimalCost(); for (int worker : all_workers) { LOG(INFO) << "Worker " << std::to_string(worker) << " assigned to task " << std::to_string(assignment.RightMate(worker)) << ". Cost: " << std::to_string(assignment.AssignmentCost(worker)) << "."; } } else { LOG(INFO) << "Solving the linear assignment problem failed."; } } } // namespace operations_research int main() { operations_research::AssignmentLinearSumAssignment(); return EXIT_SUCCESS; }
Java
package com.google.ortools.graph.samples; import com.google.ortools.Loader; import com.google.ortools.graph.LinearSumAssignment; import java.util.stream.IntStream; /** Minimal Linear Sum Assignment problem. */ public class AssignmentLinearSumAssignment { public static void main(String[] args) { Loader.loadNativeLibraries(); LinearSumAssignment assignment = new LinearSumAssignment(); final int[][] costs = { {90, 76, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 105}, {45, 110, 95, 115}, }; final int numWorkers = 4; final int numTasks = 4; final int[] allWorkers = IntStream.range(0, numWorkers).toArray(); final int[] allTasks = IntStream.range(0, numTasks).toArray(); // Add each arc. for (int w : allWorkers) { for (int t : allTasks) { if (costs[w][t] != 0) { assignment.addArcWithCost(w, t, costs[w][t]); } } } LinearSumAssignment.Status status = assignment.solve(); if (status == LinearSumAssignment.Status.OPTIMAL) { System.out.println("Total cost: " + assignment.getOptimalCost()); for (int worker : allWorkers) { System.out.println("Worker " + worker + " assigned to task " + assignment.getRightMate(worker) + ". Cost: " + assignment.getAssignmentCost(worker)); } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); } } private AssignmentLinearSumAssignment() {} }
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Graph; public class AssignmentLinearSumAssignment { static void Main() { LinearSumAssignment assignment = new LinearSumAssignment(); int[,] costs = { { 90, 76, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 105 }, { 45, 110, 95, 115 }, }; int numWorkers = 4; int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray(); int numTasks = 4; int[] allTasks = Enumerable.Range(0, numTasks).ToArray(); // Add each arc. foreach (int w in allWorkers) { foreach (int t in allTasks) { if (costs[w, t] != 0) { assignment.AddArcWithCost(w, t, costs[w, t]); } } } LinearSumAssignment.Status status = assignment.Solve(); if (status == LinearSumAssignment.Status.OPTIMAL) { Console.WriteLine($"Total cost: {assignment.OptimalCost()}."); foreach (int worker in allWorkers) { Console.WriteLine($"Worker {worker} assigned to task {assignment.RightMate(worker)}. " + $"Cost: {assignment.AssignmentCost(worker)}."); } } else { Console.WriteLine("Solving the linear assignment problem failed."); Console.WriteLine($"Solver status: {status}."); } } }
工作器无法执行所有任务时的解决方案
在前面的示例中，我们假设所有 worker 都可以执行所有任务。但是 但实际情况并非总是如此 - 工作器可能无法执行一个或多个任务 。不过，可以轻松修改上述程序来处理 这个。
例如，假设工作器 0 无法执行任务 3。要修改 进行以下更改：
- 将费用矩阵的条目 0、3 更改为字符串
'NA'。（任何字符串均可。）cost = [[90, 76, 75, 'NA'], [35, 85, 55, 65], [125, 95, 90, 105], [45, 110, 95, 115]] - 在为求解器分配开销的代码部分中，添加以下代码行
if cost[worker][task] != 'NA':，如下所示。for worker in range(0, rows): for task in range(0, cols): if cost[worker][task] != 'NA': assignment.AddArcWithCost(worker, task, cost[worker][task])
'NA'的任何边 添加到求解器中。
进行这些更改并运行修改后的代码后，您会看到以下内容 输出：
Total cost = 276 Worker 0 assigned to task 1. Cost = 76 Worker 1 assigned to task 3. Cost = 65 Worker 2 assigned to task 2. Cost = 90 Worker 3 assigned to task 0. Cost = 45
请注意，现在的总费用比原始问题的费用高。 这并不奇怪，因为在原始问题中， 向任务 3 分配了工作器 0，而在已修改的问题中，分配 不允许。
要了解当更多工作器无法执行任务时会发生什么情况，您可以将
'NA' 为成本矩阵中的更多条目，以表示
无法执行某些任务：
cost = [[90, 76, 'NA', 'NA'],
[35, 85, 'NA', 'NA'],
[125, 95, 'NA','NA'],
[45, 110, 95, 115]]这次运行程序时，得到的结果是否定的：
No assignment is possible.
这意味着无法将工作器分配给任务，
执行不同的任务。您可以通过查看图表了解
问题（没有与 'NA' 的值相对应的边）
计算。
由于这三个工作器的节点 0、1 和 2 仅连接到 节点，则无法为这些节点分配不同的任务 worker。
婚姻定理
图理论中有一个众所周知的结果，叫做 婚姻定理， 它告诉我们何时可以 将左侧的每个节点分配到 上面所示的两部分图中位于右边的点。此类作业 称为完美匹配。简而言之，该定理表明 如果左侧没有节点子集（如上例中的节点一样） ），其边缘通向右侧较小的一组节点。
更准确地说，该定理表明两部分图有一个完美匹配 当且仅当对于图谱左侧的节点的任何子集 S 时， 图表右侧的一组节点，这些节点通过一条边连接到 节点至少和 S 一样大。