Какво е проблемът на назначението?

Проблемът на назначението е класически комбинаторен оптимизационен проблем: дадено множество от работници и задачи, всяка със свързана цена, намерете еденствено съответствие, което минимизира общата цена. Той се появява естествено при планиране, логистика, разпределение на ресурси и оперативни изследвания — всяка ситуация, в която трябва да съответствате две групи по най-ефективния начин.

Проблемът се решава с унгарския алгоритъм (наричан също алгоритъм на Munkres), ефективен метод разработен през 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
  • Незабавни резултати — унгарския алгоритъм работи в браузъра без сървърен обмен

Как работи

Инструментът използва алгоритъма на Munkres (унгарски) за оптимално решаване на проблема на назначението. Той конструира матрица на цените от вашите входни данни, прилага серия от стъпки за редукция на редове и колони, и итеративно намира максимално съответствие на нули, докато се идентифицира пълно оптимално назначение. Времевата сложност е $O(n^3)$, където $n$ е размерът на матрицата.

За неквадратни матрици (повече работници от задачи или обратното), алгоритъмът допълва матрицата с нули, така че всеки работник и всяка задача да бъдат съответствани.

Обяснени опции

  • Брой работници / редове — контролира колко редове се появяват в матрицата на цените (2–8)
  • Брой задачи / колони — контролира колко колони се появяват в матрицата на цените (2–8)
  • Клетки на матрицата на цените — въведете цената на назначаване на конкретен работник на конкретна задача; приемат се всички числови стойности

Ограничения

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