Hva er tilordningsproblemet?

Tilordningsproblemet er et klassisk kombinatorisk optimaliseringsproblem: gitt et sett med arbeidere og oppgaver, hver med en tilknyttet kostnad, finn den en-til-en-parringen som minimerer den totale kostnaden. Det oppstår naturlig i planlegging, logistikk, ressursallokering og operasjonsforskning — enhver situasjon der du må matche to grupper på den mest effektive måten mulig.

Problemet løses med Hungarian-algoritmen (også kalt Munkres-algoritmen), en effektiv metode utviklet på 1950-tallet. I motsetning til brute-force-tilnærminger som må evaluere hver permutasjon, finner Hungarian-algoritmen den optimale løsningen i polynomisk tid, noe som gjør den praktisk selv for moderat store matriser.

Verktøybeskrivelse

Skriv inn en kostnadsmatrise som representerer hvor mye det koster å tilordne hver arbeider til hver oppgave, og klikk deretter Løs for å øyeblikkelig finne den optimale tilordningen. Verktøyet fremhever hvilke arbeider-oppgave-par som minimerer den totale kostnaden og viser resultatet i en klar tabell sammen med den optimale totale kostnaden.

Eksempler

Inngangsmatrise (3 arbeidere × 3 oppgaver):

Oppgave 1 Oppgave 2 Oppgave 3
Arbeider 1 400 150 400
Arbeider 2 400 450 600
Arbeider 3 300 225 300

Optimale tilordninger:

Arbeider Oppgave Kostnad
Arbeider 1 Oppgave 2 150
Arbeider 2 Oppgave 1 400
Arbeider 3 Oppgave 3 300

Total kostnad: 850

Funksjoner

  • Redigerbar matrise — klikk på en hvilken som helst celle eller kolonneoverskrift for å gi nytt navn til arbeidere, oppgaver og kostnader direkte i tabellen
  • Konfigurerbar størrelse — støtter matriser fra 2×2 opp til 8×8
  • Øyeblikkelige resultater — Hungarian-algoritmen kjører i nettleseren uten serversamtale

Hvordan det fungerer

Verktøyet bruker Munkres (Hungarian)-algoritmen for å løse tilordningsproblemet optimalt. Det konstruerer en kostnadsmatrise fra dine inndata, bruker en serie rad- og kolonnereduksjonstrinn, og finner iterativt en maksimal matching av nuller til en fullstendig optimal tilordning er identifisert. Tidskompleksiteten er $O(n^3)$, der $n$ er matrisedimensjonen.

For ikke-kvadratiske matriser (flere arbeidere enn oppgaver eller omvendt), fyller algoritmen matrisen med nuller slik at hver arbeider og hver oppgave blir matchet.

Alternativer forklart

  • Antall arbeidere / rader — kontrollerer hvor mange rader som vises i kostnadsmatrisen (2–8)
  • Antall oppgaver / kolonner — kontrollerer hvor mange kolonner som vises i kostnadsmatrisen (2–8)
  • Kostnadsmatriseceller — skriv inn kostnaden for å tilordne en spesifikk arbeider til en spesifikk oppgave; en hvilken som helst numerisk verdi aksepteres

Begrensninger

  • Matrisestørrelse er begrenset til 8×8 (64 celler)
  • Algoritmen minimerer total kostnad; for å maksimere (f.eks. for profittmatriser), negerer du verdiene før du skriver dem inn
  • Ikke-numeriske cellverdier behandles som null