assignment problem

assignment problem (tsz. assignment problems)

1. (informatika) hozzárendelési feladat

A hozzárendelési probléma egy klasszikus optimalizálási probléma, amelyben adott két halmaz (pl. munkások és feladatok), és célunk az, hogy egyetlen hozzárendelést végezzünk a két halmaz elemei között oly módon, hogy a hozzárendelés teljes költsége minimális legyen (vagy értéke maximális).

Matematikailag a hozzárendelési probléma egy n × n-es mátrixon értelmezhető, ahol minden cella azt mutatja meg, hogy egy adott “személy–feladat” páros költsége mennyi. Ezt a mátrixot költségmátrixnak nevezzük.

• Egy n × n-es költségmátrix: ${\textstyle C=}$, ahol
  • ${\textstyle i}$: munkás sorszáma
  • ${\textstyle j}$: feladat sorszáma
  • ${\textstyle c_{ij}}$: az ${\textstyle i}$-edik munkás ${\textstyle j}$-edik feladathoz történő hozzárendelésének költsége

• Hozzárendelni minden munkához pontosan egy feladatot, és minden feladathoz pontosan egy munkást, úgy hogy az összköltség

$${\displaystyle \sum _{i=1}^{n}c_{i,\pi (i)}}$$

minimális legyen, ahol ${\textstyle \pi }$ a hozzárendelést jelentő permutáció.

• Gyártás: gépkezelők hozzárendelése gyártósorokhoz
• Szállítmányozás: járművek hozzárendelése útvonalakhoz
• Személyzetmenedzsment: dolgozók kiosztása műszakokra
• Kép-felismerés: objektumok párosítása két képkocka között
• Sportversenyek: játékosok párosítása

• A legismertebb és leghatékonyabb módszer négyzetes hozzárendelési problémákra
• Polinomiális időben fut: O(n³)
• Sor- és oszlopnormalizálással, valamint nullák lefedésével működik

• Az LP modellben minden hozzárendelés egy bináris változó
• A célfüggvény minimalizálja az összköltséget

• Minden lehetséges permutáció kipróbálása – O(n!), csak kis méretű problémákra

• Minden lépésben a legkisebb költségű hozzárendelést választja
• Nem garantálja az optimális megoldást

1. Soronként kivonjuk a legkisebb elemet minden sorból.
2. Oszloponként kivonjuk a legkisebb elemet.
3. Lefedjük a nullákat a lehető legkevesebb vonallal.
4. Ha az összes nullát le tudtuk fedni n vonallal, akkor kész vagyunk.
5. Ha nem, akkor a legkisebb nem fedett értéket kivonjuk a nem lefedett elemekből, és hozzáadjuk a kétszeresen fedettekhez.

Ez új nullákat hoz létre, és ismételhetjük az eljárást, amíg nem találunk teljes hozzárendelést.

A változók:

$${\displaystyle x_{ij}={\begin{cases}1,&{\text{ha az }}i{\text{ munkás a }}j{\text{ feladatot kapja}}\\0,&{\text{egyébként}}\end{cases}}}$$

$${\displaystyle \min \sum _{i=1}^{n}\sum _{j=1}^{n}c_{ij}x_{ij}}$$

$${\displaystyle \sum _{j=1}^{n}x_{ij}=1\quad {\text{(minden munkás csak egy feladatot kapjon)}}}$$

$${\displaystyle \sum _{i=1}^{n}x_{ij}=1\quad {\text{(minden feladatot csak egy munkás kapjon)}}}$$

$${\displaystyle x_{ij}\in \{0,1\}}$$

Mi történik, ha a munkások és feladatok száma nem egyenlő?

• Adjunk hozzá „dummy” sorokat vagy oszlopokat nulla költséggel
• Így egy négyzetes mátrixot kapunk, amit a Hungarian algoritmus is kezel

Ha nem költséget minimalizálunk, hanem hasznot maximalizálunk, például:

• Melyik dolgozó végezne el egy feladatot a leghatékonyabban
• Melyik ajánlott film a legjobban illik egy nézőhöz

Ekkor a mátrixból minden értéket negálni vagy normalizálni kell, hogy a maximális probléma átalakítható legyen minimálisra.

• Több munkás egy feladatra: általánosítás (Generalized Assignment Problem)
• Munkásoknak korlátozásaik vannak: tilos bizonyos feladatokat végezni → ezeket nagyon nagy (∞) költséggel adjuk meg
• Időalapú hozzárendelés: feladatok különböző időpontban kezdődnek
• Dinamikus hozzárendelés: valós időben kell dönteni (pl. online rendelés kiszállítás)

• A hozzárendelési probléma NP-teljes általános esetben (pl. kapacitáskorlátokkal, időzítéssel), de az alapeset (n×n mátrix) polinomiális időben megoldható
• Nagy dimenziójú esetekre specializált implementációk szükségesek (pl. GPU, párhuzamosítás)

Tegyük fel, hogy a költségmátrix a következő:

A cél: minden dolgozót úgy hozzárendelni egy feladathoz, hogy az összköltség minimális legyen.

Lehetséges megoldás:

• Dolgozó 1 → Feladat 2 (2)
• Dolgozó 2 → Feladat 1 (6)
• Dolgozó 3 → Feladat 3 (1) Összköltség = 2 + 6 + 1 = 9

A hozzárendelési probléma a gyakorlatban gyakori, formálható és hatékonyan megoldható optimalizálási probléma, amely:

• Egy párosítás a minimális (vagy maximális) összköltség elérése érdekében
• Négyzetes mátrixra épül, de kiterjeszthető általánosabb esetekre is
• A Hungarian algoritmus segítségével gyorsan és pontosan megoldható
• A lineáris programozás módszertanában is kiemelt helyet kap

• assignment problem - Szótár.net (en-hu)
• assignment problem - Sztaki (en-hu)
• assignment problem - Merriam–Webster
• assignment problem - Cambridge
• assignment problem - WordNet
• assignment problem - Яндекс (en-ru)
• assignment problem - Google (en-hu)
• assignment problem - Wikidata
• assignment problem - Wikipédia (angol)