Что такое задача о назначениях?

Задача о назначениях — это классическая задача комбинаторной оптимизации: дан набор рабочих и задач, каждая с соответствующей стоимостью, найти взаимно-однозначное соответствие, которое минимизирует общую стоимость. Она естественным образом возникает в планировании, логистике, распределении ресурсов и исследовании операций — в любой ситуации, где нужно сопоставить две группы наиболее эффективным способом.

Задача решается с помощью венгерского алгоритма (также называемого алгоритмом Мункреса), эффективного метода, разработанного в 1950-х годах. В отличие от методов перебора, которые должны оценить каждую перестановку, венгерский алгоритм находит оптимальное решение за полиномиальное время, что делает его практичным даже для матриц среднего размера.

Описание инструмента

Введите матрицу стоимостей, представляющую, сколько стоит назначить каждого рабочего на каждую задачу, затем нажмите Решить, чтобы мгновенно найти оптимальное назначение. Инструмент выделяет пары рабочий-задача, которые минимизируют общую стоимость, и отображает результат в четкой таблице вместе с оптимальной общей стоимостью.

Примеры

Входная матрица (3 рабочих × 3 задачи):

Задача 1 Задача 2 Задача 3
Рабочий 1 400 150 400
Рабочий 2 400 450 600
Рабочий 3 300 225 300

Оптимальные назначения:

Рабочий Задача Стоимость
Рабочий 1 Задача 2 150
Рабочий 2 Задача 1 400
Рабочий 3 Задача 3 300

Общая стоимость: 850

Возможности

  • Редактируемая матрица — нажмите на любую ячейку или заголовок столбца, чтобы переименовать рабочих, задачи и стоимости прямо в таблице
  • Настраиваемый размер — поддерживает матрицы от 2×2 до 8×8
  • Мгновенные результаты — алгоритм Мункреса работает в браузере без обращения к серверу

Как это работает

Инструмент использует алгоритм Мункреса (венгерский алгоритм) для оптимального решения задачи о назначениях. Он строит матрицу стоимостей из ваших входных данных, применяет серию шагов сокращения строк и столбцов и итеративно находит максимальное паросочетание нулей до тех пор, пока не будет определено полное оптимальное назначение. Временная сложность составляет $O(n^3)$, где $n$ — размерность матрицы.

Для неквадратных матриц (больше рабочих, чем задач, или наоборот) алгоритм дополняет матрицу нулями, чтобы каждый рабочий и каждая задача были сопоставлены.

Объяснение параметров

  • Количество рабочих / строк — управляет количеством строк в матрице стоимостей (2–8)
  • Количество задач / столбцов — управляет количеством столбцов в матрице стоимостей (2–8)
  • Ячейки матрицы стоимостей — введите стоимость назначения конкретного рабочего на конкретную задачу; принимается любое числовое значение

Ограничения

  • Размер матрицы ограничен 8×8 (64 ячейки)
  • Алгоритм минимизирует общую стоимость; для максимизации (например, для матриц прибыли) отрицайте значения перед их вводом
  • Нечисловые значения ячеек рассматриваются как нуль