Czym jest problem przydziału?

Problem przydziału to klasyczny problem optymalizacji kombinatorycznej: mając zbiór pracowników i zadań, każdy z powiązanym kosztem, znaleźć przyporządkowanie jeden-do-jednego, które minimalizuje całkowity koszt. Pojawia się naturalnie w planowaniu harmonogramów, logistyce, alokacji zasobów i badaniach operacyjnych — w każdej sytuacji, gdzie trzeba dopasować dwie grupy w możliwie najbardziej efektywny sposób.

Problem rozwiązuje się za pomocą algorytmu węgierskiego (zwanego również algorytmem Munkresa), wydajnej metody opracowanej w latach 50. XX wieku. W przeciwieństwie do podejść siłowych, które muszą ocenić każdą permutację, algorytm węgierski znajduje rozwiązanie optymalne w czasie wielomianowym, co czyni go praktycznym nawet dla macierzy o umiarkowanie dużych rozmiarach.

Opis narzędzia

Wprowadź macierz kosztów reprezentującą, ile kosztuje przydzielenie każdego pracownika do każdego zadania, a następnie kliknij Rozwiąż, aby natychmiast znaleźć optymalny przydział. Narzędzie podświetla, które pary pracownik-zadanie minimalizują całkowity koszt i wyświetla wynik w przejrzystej tabeli wraz z optymalnym całkowitym kosztem.

Przykłady

Macierz wejściowa (3 pracownicy × 3 zadania):

Zadanie 1 Zadanie 2 Zadanie 3
Pracownik 1 400 150 400
Pracownik 2 400 450 600
Pracownik 3 300 225 300

Optymalne przydziały:

Pracownik Zadanie Koszt
Pracownik 1 Zadanie 2 150
Pracownik 2 Zadanie 1 400
Pracownik 3 Zadanie 3 300

Całkowity koszt: 850

Funkcje

  • Edytowalna macierz — kliknij dowolną komórkę lub nagłówek kolumny, aby zmienić nazwy pracowników, zadań i kosztów bezpośrednio w tabeli
  • Konfigurowalny rozmiar — obsługuje macierze od 2×2 do 8×8
  • Natychmiastowe wyniki — algorytm węgierski działa w przeglądarce bez komunikacji z serwerem

Jak to działa

Narzędzie używa algorytmu Munkresa (węgierskiego) do optymalnego rozwiązania problemu przydziału. Konstruuje macierz kosztów z Twoich danych wejściowych, stosuje serię kroków redukcji wierszy i kolumn, a następnie iteracyjnie znajduje maksymalne dopasowanie zer, aż do zidentyfikowania kompletnego optymalnego przydziału. Złożoność czasowa wynosi $O(n^3)$, gdzie $n$ to wymiar macierzy.

W przypadku macierzy niekwadratowych (więcej pracowników niż zadań lub odwrotnie) algorytm uzupełnia macierz zerami, aby każdy pracownik i każde zadanie zostały przydzielone.

Wyjaśnienie opcji

  • Liczba pracowników / wierszy — kontroluje, ile wierszy pojawia się w macierzy kosztów (2–8)
  • Liczba zadań / kolumn — kontroluje, ile kolumn pojawia się w macierzy kosztów (2–8)
  • Komórki macierzy kosztów — wprowadź koszt przydzielenia konkretnego pracownika do konkretnego zadania; akceptowana jest dowolna wartość numeryczna

Ograniczenia

  • Rozmiar macierzy jest ograniczony do 8×8 (64 komórki)
  • Algorytm minimalizuje całkowity koszt; aby maksymalizować (np. dla macierzy zysków), zaneguj wartości przed ich wprowadzeniem
  • Nienumeryczne wartości komórek są traktowane jako zero