В этом разделе описан решатель присваивания линейной суммы , специализированный решатель для простой задачи присваивания, который может быть быстрее, чем решатель 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, которая решает задачу присваивания с помощью решателя присваивания линейной суммы.
Импортируйте библиотеки
Код, который импортирует необходимую библиотеку, показан ниже.
Питон
import numpy as np from ortools.graph.python import linear_sum_assignment
С++
#include "ortools/graph/assignment.h" #include <cstdint> #include <numeric> #include <string> #include <vector>
Ява
import com.google.ortools.Loader; import com.google.ortools.graph.LinearSumAssignment; import java.util.stream.IntStream;
С#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Graph;
Определите данные
Следующий код создает данные для программы.
Питон
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()С++
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
}};Ява
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();С#
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 которой представляют собой стоимость выполнения задачи j работником i . Есть четыре работника, соответствующие строкам матрицы, и четыре задачи, соответствующие столбцам.
Создайте решатель
Программа использует решатель линейных задач , специализированный решатель задач о назначениях.
Следующий код создает решатель.
Питон
assignment = linear_sum_assignment.SimpleLinearSumAssignment()
С++
SimpleLinearSumAssignment assignment;
Ява
LinearSumAssignment assignment = new LinearSumAssignment();
С#
LinearSumAssignment assignment = new LinearSumAssignment();
Добавьте ограничения
Следующий код добавляет затраты к решателю путем циклического перебора рабочих и задач.
Питон
assignment.add_arcs_with_cost(start_nodes, end_nodes, arc_costs)
С++
for (int w : all_workers) {
for (int t : all_tasks) {
if (costs[w][t]) {
assignment.AddArcWithCost(w, t, costs[w][t]);
}
}
}Ява
// Add each arc.
for (int w : allWorkers) {
for (int t : allTasks) {
if (costs[w][t] != 0) {
assignment.addArcWithCost(w, t, costs[w][t]);
}
}
}С#
// 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]);
}
}
}Вызов решателя
Следующий код вызывает решатель.
Питон
status = assignment.solve()
С++
SimpleLinearSumAssignment::Status status = assignment.Solve();
Ява
LinearSumAssignment.Status status = assignment.solve();
С#
LinearSumAssignment.Status 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 (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.";
}Ява
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);
}С#
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.
В теории графов набор ребер двудольного графа, который соответствует каждому узлу слева ровно одному узлу справа, называется идеальным паросочетанием .
Вся программа
Вот вся программа.
Питон
"""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()
С++
#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;
}Ява
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() {}
}С#
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}.");
}
}
}Решение, когда работники не могут выполнять все задачи
В предыдущем примере мы предполагали, что все работники могут выполнять все задачи. Но это не всегда так: работник может быть не в состоянии выполнить одну или несколько задач по разным причинам. Однако приведенную выше программу легко изменить, чтобы справиться с этой задачей.
В качестве примера предположим, что рабочий 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
Обратите внимание, что общая стоимость теперь выше, чем для исходной задачи. Это неудивительно, поскольку в исходной задаче оптимальное решение назначило работника 0 задаче 3, а в модифицированной задаче такое назначение не допускается.
Чтобы увидеть, что произойдет, если больше работников не смогут выполнять задачи, вы можете заменить другие записи матрицы затрат на '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 подключены только к двум узлам для задач 0 и 1, невозможно назначить этим исполнителям отдельные задачи.
Теорема о браке
В теории графов есть хорошо известный результат, называемый «Теорема о браке» , который говорит нам, когда именно можно присвоить каждый узел слева отдельному узлу справа в двудольном графе, подобном приведенному выше. Такое присваивание называется идеальным паросочетанием . Вкратце, теорема говорит, что это возможно, если слева нет подмножества узлов (как в предыдущем примере), ребра которого ведут к меньшему набору узлов справа.
Точнее, теорема гласит, что двудольный граф имеет идеальное паросочетание тогда и только тогда, когда для любого подмножества S узлов в левой части графа множество узлов в правой части графа, соединенных ребром узлу в S, по крайней мере, такого же размера, как S.