Mis on määramise probleem?

Määramise probleem on klassikaline kombinatoorne optimeerimisülesanne: antud töötajate ja ülesannete kogum, millest igaühel on seotud kulu, leida üks-ühele paaritamine, mis minimeerib kogukulud. See esineb loomulikult ajakavade koostamisel, logistikas, ressursside jaotamisel ja operatsioonide uurimisel — igas olukorras, kus peate kahte rühma kõige tõhusamal viisil sobitama.

Probleem lahendatakse Ungari algoritmiga (tuntud ka kui Munkressi algoritm), efektiivne meetod, mis töötati välja 1950. aastatel. Erinevalt jõhkratest lähenemisviisidest, mis peavad hindama iga permutatsiooni, leiab Ungari algoritm optimaalse lahenduse polünoomilises ajas, muutes selle praktiliseks isegi mõõdukalt suurte maatriksite puhul.

Tööriista kirjeldus

Sisestage kulumaatriksi, mis näitab, kui palju maksab iga töötaja igale ülesandele määramine, seejärel klõpsake nupul Lahenda, et leida hetkega optimaalne määramine. Tööriist tõstab esile, millised töötaja-ülesande paarid minimeerivad kogukulud, ja kuvab tulemuse selges tabelis koos optimaalse kogukuluga.

Näited

Sisendmaatriksi (3 töötajat × 3 ülesannet):

Ülesanne 1 Ülesanne 2 Ülesanne 3
Töötaja 1 400 150 400
Töötaja 2 400 450 600
Töötaja 3 300 225 300

Optimaalsed määramised:

Töötaja Ülesanne Kulu
Töötaja 1 Ülesanne 2 150
Töötaja 2 Ülesanne 1 400
Töötaja 3 Ülesanne 3 300

Kogu kulu: 850

Funktsioonid

  • Redigeeritav maatriksi — klõpsake mis tahes lahtril või veeru päisel, et nimetada töötajaid, ülesandeid ja kulusid otse tabelis
  • Konfigureeritav suurus — toetab maatrikseid 2×2 kuni 8×8
  • Hetkelised tulemused — Ungari algoritm töötab brauseris ilma serveriga ühenduseta

Kuidas see toimib

Tööriist kasutab määramise probleemi optimaalseks lahendamiseks Munkressi (Ungari) algoritmi. See konstrueerib kulumaatriksi teie sisendist, rakendab ridade ja veergude vähendamise sammude jada ning iteratiivselt leiab nullide maksimaalse sobituse, kuni täielik optimaalne määramine on tuvastatud. Ajaline keerukus on $O(n^3)$, kus $n$ on maatriksi dimensioon.

Mitteruudukujuliste maatriksite puhul (rohkem töötajaid kui ülesandeid või vastupidi) täidab algoritm maatriksi nullidega nii, et iga töötaja ja iga ülesanne on sobitatud.

Valikud selgitatud

  • Töötajate arv / read — kontrollib, kui palju ridu kulumaatriksis kuvatakse (2–8)
  • Ülesannete arv / veerud — kontrollib, kui palju veerge kulumaatriksis kuvatakse (2–8)
  • Kulumaatriksi lahtrid — sisestage konkreetse töötaja konkreetsele ülesandele määramise kulu; aktsepteeritakse mis tahes numbrilist väärtust

Piirangud

  • Maatriksi suurus on piiratud 8×8-ga (64 lahtrit)
  • Algoritm minimeerib kogukulud; maksimeerimiseks (nt kasummaatriksite puhul) negeeri väärtused enne sisestamist
  • Mittenumbrilised lahtrite väärtused käsitletakse nullina