Wat is het toewijzingsprobleem?

Het toewijzingsprobleem is een klassiek combinatorisch optimalisatieprobleem: gegeven een set werknemers en taken, elk met een bijbehorende kosten, zoek de één-op-één koppeling die de totale kosten minimaliseert. Het komt van nature voor in planning, logistiek, resourcetoewijzing en operationeel onderzoek — elke situatie waarin je twee groepen op de meest efficiënte manier moet matchen.

Het probleem wordt opgelost met het Hongaarse algoritme (ook wel het Munkres-algoritme genoemd), een efficiënte methode ontwikkeld in de jaren 1950. In tegenstelling tot brute-force-benaderingen die elke permutatie moeten evalueren, vindt het Hongaarse algoritme de optimale oplossing in polynomiale tijd, waardoor het praktisch is zelfs voor matig grote matrices.

Hulpprogrammabeschrijving

Voer een kostenmatrix in die aangeeft hoeveel het kost om elke werknemer aan elke taak toe te wijzen, en klik vervolgens op Oplossen om onmiddellijk de optimale toewijzing te vinden. Het hulpprogramma markeert welke werknemer-taak-paren de totale kosten minimaliseren en geeft het resultaat weer in een duidelijke tabel samen met de optimale totale kosten.

Voorbeelden

Invoermatrix (3 werknemers × 3 taken):

Taak 1 Taak 2 Taak 3
Werknemer 1 400 150 400
Werknemer 2 400 450 600
Werknemer 3 300 225 300

Optimale toewijzingen:

Werknemer Taak Kosten
Werknemer 1 Taak 2 150
Werknemer 2 Taak 1 400
Werknemer 3 Taak 3 300

Totale kosten: 850

Functies

  • Bewerkbare matrix — klik op een willekeurige cel of kolomkop om werknemers, taken en kosten rechtstreeks in de tabel te hernoemen
  • Configureerbare grootte — ondersteunt matrices van 2×2 tot 8×8
  • Directe resultaten — het Hongaarse algoritme wordt in de browser uitgevoerd zonder serverronde

Hoe het werkt

Het hulpprogramma gebruikt het Munkres (Hongaarse) algoritme om het toewijzingsprobleem optimaal op te lossen. Het construeert een kostenmatrix uit je invoer, past een reeks rij- en kolomreductiestappen toe, en vindt iteratief een maximale matching van nullen totdat een volledige optimale toewijzing is geïdentificeerd. De tijdcomplexiteit is $O(n^3)$, waarbij $n$ de matrixdimensie is.

Voor niet-vierkante matrices (meer werknemers dan taken of omgekeerd) vult het algoritme de matrix aan met nullen zodat elke werknemer en elke taak wordt gematcht.

Opties uitgelegd

  • Aantal werknemers / rijen — bepaalt hoeveel rijen in de kostenmatrix verschijnen (2–8)
  • Aantal taken / kolommen — bepaalt hoeveel kolommen in de kostenmatrix verschijnen (2–8)
  • Kostenmatrixcellen — voer de kosten in voor het toewijzen van een specifieke werknemer aan een specifieke taak; elke numerieke waarde wordt geaccepteerd

Beperkingen

  • Matrixgrootte is beperkt tot 8×8 (64 cellen)
  • Het algoritme minimaliseert totale kosten; om te maximaliseren (bijvoorbeeld voor winstmatrices), negeer de waarden voordat je ze invoert
  • Niet-numerieke celwaarden worden behandeld als nul