Vad är tilldelningsproblemet?

Tilldelningsproblemet är ett klassiskt kombinatoriskt optimeringsproblem: givet en uppsättning arbetare och uppgifter, var och en med en associerad kostnad, hitta den en-till-en-parning som minimerar den totala kostnaden. Det förekommer naturligt inom schemaläggning, logistik, resursallokering och operationsforskning — vilken situation som helst där du behöver matcha två grupper på det mest effektiva sättet möjligt.

Problemet löses med Ungersk algoritm (även kallad Munkres-algoritm), en effektiv metod utvecklad på 1950-talet. Till skillnad från brute-force-metoder som måste utvärdera varje permutation, hittar den ungerska algoritmen den optimala lösningen på polynomtid, vilket gör den praktisk även för måttligt stora matriser.

Verktygsbeskrivning

Ange en kostnadsmatris som representerar hur mycket det kostar att tilldela varje arbetare till varje uppgift, klicka sedan på Lös för att omedelbar hitta den optimala tilldelningen. Verktyget markerar vilka arbetare-uppgift-par som minimerar den totala kostnaden och visar resultatet i en tydlig tabell tillsammans med den optimala totala kostnaden.

Exempel

Indatamatris (3 arbetare × 3 uppgifter):

Uppgift 1 Uppgift 2 Uppgift 3
Arbetare 1 400 150 400
Arbetare 2 400 450 600
Arbetare 3 300 225 300

Optimala tilldelningar:

Arbetare Uppgift Kostnad
Arbetare 1 Uppgift 2 150
Arbetare 2 Uppgift 1 400
Arbetare 3 Uppgift 3 300

Total kostnad: 850

Funktioner

  • Redigerbar matris — klicka på valfri cell eller kolumnrubrik för att byta namn på arbetare, uppgifter och kostnader direkt i tabellen
  • Konfigurerbar storlek — stöder matriser från 2×2 upp till 8×8
  • Omedelbara resultat — Munkres-algoritmen körs i webbläsaren utan serverrundresa

Hur det fungerar

Verktyget använder Munkres (Ungersk) algoritm för att lösa tilldelningsproblemet optimalt. Det konstruerar en kostnadsmatris från dina inmatningar, tillämpar en serie rad- och kolumnreduktionssteg, och hittar iterativt en maximal matchning av nollor tills en fullständig optimal tilldelning identifieras. Tidskomplexiteten är $O(n^3)$, där $n$ är matrisstorlek.

För icke-kvadratiska matriser (fler arbetare än uppgifter eller vice versa) fyller algoritmen matrisen med nollor så att varje arbetare och varje uppgift matchas.

Alternativ förklarade

  • Antal arbetare / rader — styr hur många rader som visas i kostnadsmatrisen (2–8)
  • Antal uppgifter / kolumner — styr hur många kolumner som visas i kostnadsmatrisen (2–8)
  • Kostnadsmatrixceller — ange kostnaden för att tilldela en specifik arbetare till en specifik uppgift; alla numeriska värden accepteras

Begränsningar

  • Matrisstorlek är begränsad till 8×8 (64 celler)
  • Algoritmen minimerar total kostnad; för att maximera (t.ex. för vinstmatriser), negera värdena innan du anger dem
  • Icke-numeriska cellvärden behandlas som noll