Mikä on tehtävänanto-ongelma?

Tehtävänanto-ongelma on klassinen kombinatorinen optimointiongelma: annetaan joukko työntekijöitä ja tehtäviä, joilla jokaisella on siihen liittyvä kustannus, ja etsi yksi-yhteen-vastaavuus, joka minimoi kokonaiskustannukset. Se esiintyy luonnollisesti aikataulutuksessa, logistiikassa, resurssien allokoinnissa ja operaatiotutkimuksessa — missä tahansa tilanteessa, jossa sinun on sovitettava kaksi ryhmää mahdollisimman tehokkaasti.

Ongelma ratkaistaan Unkarilaisen algoritmin avulla (kutsutaan myös Munkres-algoritmiksi), tehokkaalla menetelmällä, joka kehitettiin 1950-luvulla. Toisin kuin raa'at voimamenetelmät, jotka joutuvat arvioimaan jokaisen permutaation, Unkarilainen algoritmi löytää optimaalisen ratkaisun polynomiajassa, mikä tekee siitä käytännöllisen myös kohtuullisen suurille matriiseille.

Työkalun kuvaus

Syötä kustannusmatriisi, joka edustaa, kuinka paljon maksaa kunkin työntekijän määrittäminen kullekin tehtävälle, ja napsauta sitten Ratkaise löytääksesi välittömästi optimaalisen tehtävänannon. Työkalu korostaa, mitkä työntekijä-tehtävä-parit minimoivat kokonaiskustannukset, ja näyttää tuloksen selkeässä taulukossa optimaalisen kokonaiskustannuksen rinnalla.

Esimerkkejä

Syötematriisi (3 työntekijää × 3 tehtävää):

Tehtävä 1 Tehtävä 2 Tehtävä 3
Työntekijä 1 400 150 400
Työntekijä 2 400 450 600
Työntekijä 3 300 225 300

Optimaaliset tehtävännannot:

Työntekijä Tehtävä Kustannus
Työntekijä 1 Tehtävä 2 150
Työntekijä 2 Tehtävä 1 400
Työntekijä 3 Tehtävä 3 300

Kokonaiskustannus: 850

Ominaisuudet

  • Muokattava matriisi — napsauta mitä tahansa solua tai sarakkeen otsikkoa nimetäksesi työntekijät, tehtävät ja kustannukset suoraan taulukossa
  • Säädettävä koko — tukee matriiseja 2×2:sta 8×8:aan
  • Välittömät tulokset — Unkarilainen algoritmi toimii selaimessa ilman palvelimen pyyntöä

Kuinka se toimii

Työkalu käyttää Munkres (Unkarilainen) algoritmia tehtävänanto-ongelman optimaaliseen ratkaisuun. Se muodostaa kustannusmatriisin syötteistäsi, soveltaa sarjan rivi- ja sarakevähennysvaihetta ja iteratiivisesti löytää nollien maksimaalisen vastaavuuden, kunnes täydellinen optimaalinen tehtävänanto on tunnistettu. Aikakompleksisuus on $O(n^3)$, jossa $n$ on matriisin dimensio.

Ei-neliömatriiseille (enemmän työntekijöitä kuin tehtäviä tai päinvastoin) algoritmi täyttää matriisin nollilla niin, että jokainen työntekijä ja jokainen tehtävä on sovitettu.

Vaihtoehdot selitetty

  • Työntekijöiden lukumäärä / rivit — ohjaa, kuinka monta riviä näkyy kustannusmatriisissa (2–8)
  • Tehtävien lukumäärä / sarakkeet — ohjaa, kuinka monta saraketta näkyy kustannusmatriisissa (2–8)
  • Kustannusmatriisin solut — syötä tietyn työntekijän määrittämisen tiettyyn tehtävään liittyvä kustannus; mikä tahansa numeerinen arvo hyväksytään

Rajoitukset

  • Matriisin koko on rajoitettu 8×8:aan (64 solua)
  • Algoritmi minimoi kokonaiskustannukset; maksimoidaksesi (esim. voittomatriiseille), negoi arvot ennen niiden syöttämistä
  • Ei-numeeriset solun arvot käsitellään nollina