Hozzárendelési probléma - Assignment problem

A hozzárendelési probléma alapvető kombinációs optimalizálási probléma. Legáltalánosabb formájában a probléma a következő:

A problémapéldány számos ügynököt és számos feladatot tartalmaz . Bármely ügynök hozzárendelhető bármely feladat elvégzéséhez, ami bizonyos költségekkel jár , amelyek az ügynök-feladat hozzárendelésétől függően változhatnak. A lehető legtöbb feladatot kell elvégezni úgy, hogy minden feladathoz legfeljebb egy ügynököt, legfeljebb pedig egy feladatot rendel hozzá, oly módon, hogy a hozzárendelés teljes költsége minimális legyen.

Alternatív megoldásként a probléma leírása gráfelmélettel:

A hozzárendelési probléma áll megállapítás, egy súlyozott páros gráf , a megfelelő egy adott méretű, amelyben a súlyok összege az élek minimális.

Ha az ügynökök és a feladatok száma egyenlő, akkor a problémát kiegyensúlyozott hozzárendelésnek nevezzük . Ellenkező esetben ezt kiegyensúlyozatlan hozzárendelésnek hívják . Ha a hozzárendelés összes költsége minden feladatra megegyezik az egyes ügynökök költségeinek összegével (vagy az egyes feladatok költségeinek összegével, ami ebben az esetben ugyanaz), akkor a problémát lineáris hozzárendelésnek nevezzük . Általánosságban elmondható, hogy ha a hozzárendelési feladatról további képzettség nélkül beszélünk , akkor a lineáris kiegyensúlyozott hozzárendelési feladatra gondolunk.

Példák

Tegyük fel, hogy egy taxitársaságnál három taxi (az ügynökök) áll rendelkezésre, és három ügyfél (a feladatok), amelyeket mielőbb fel akarnak venni. A cég büszke a gyors pickupokra, ezért minden taxi esetében az adott ügyfél felvételének "költsége" attól függ, hogy mennyi idő alatt jut el a taxi az átvételi ponthoz. Ez egy kiegyensúlyozott hozzárendelési probléma. Megoldása a taxik és az ügyfelek bármelyik kombinációja a legkevesebb összköltséget eredményezi.

Tegyük fel, hogy négy taxi áll rendelkezésre, de még mindig csak három ügyfél. Ez egy kiegyensúlyozatlan hozzárendelési probléma. Ennek egyik megoldási módja az, hogy feltalálunk egy negyedik próbabábu feladatot, amelyet talán úgy hívnak, hogy "ülve, semmit sem csinálok", és a hozzárendelt taxi 0 költséggel jár. Ez a problémát kiegyensúlyozott hozzárendelési problémára redukálja, amely a szokásos módon megoldható, és így is a legjobb megoldást adja a problémára.

Hasonló kiigazításokat lehet végrehajtani annak érdekében, hogy több feladatot lehessen engedélyezni, mint ügynököket, olyan feladatokat, amelyekhez több ügynököt kell hozzárendelni (például több ügyfélből álló csoportot, mint amennyi egy taxiban elfér), vagy a nyereség maximalizálása helyett a költségek minimalizálása.

Formális meghatározás

A hozzárendelési probléma (vagy lineáris hozzárendelési probléma ) formális meghatározása az

Mivel két, A és T , azonos méretű, együtt egy súlyfüggvény C : A × T → R . Keresse meg az f : A → T bikciót úgy, hogy a költségfüggvény :

{\ displaystyle \ sum _ {a \ in A} C (a, f (a))}

minimalizálva van.

Általában a súlyfüggvényt négyzet alakú valósértékű C mátrixnak tekintik , így a költségfüggvényt a következőképpen írják le:

{\ displaystyle \ sum _ {a \ in A} C_ {a, f (a)}}

A probléma "lineáris", mert az optimalizálandó költségfüggvény, valamint az összes megkötés csak lineáris kifejezéseket tartalmaz.

Algoritmusok

A hozzárendelési probléma naiv megoldása az összes hozzárendelés ellenőrzése és mindegyik költségének kiszámítása. Ez nagyon hatástalan lehet, mivel n ügynökkel és n feladattal n van ! ( Faktoriális a n ) különböző feladatokat. Szerencsére sok algoritmus létezik a probléma időbeni polinom megoldására n -ben .

A hozzárendelési probléma a szállítási probléma speciális esete, amely a minimális költségáram problémájának speciális esete, amely viszont egy lineáris program speciális esete . Bár ezen problémák bármelyikét meg lehet oldani a szimplex algoritmus használatával , mindegyik szakterületnek van egy kis megoldási tere, és ezáltal hatékonyabb algoritmusai, amelyek célja a speciális struktúra kihasználása.

Kiegyensúlyozott feladat

A kiegyensúlyozott hozzárendelési feladatban a kétoldalú gráf mindkét része azonos számú csúccsal rendelkezik, amelyeket n jelöl .

A kiegyensúlyozott hozzárendelés egyik első polinomiális idejű algoritmusa a magyar algoritmus volt . Ez egy globális algoritmus - az illeszkedés javításán alapul, a növekvő utak mentén (váltakozó utak a páratlan csúcsok között). Futásidejű összetettsége Fibonacci-halmok használatakor , ahol m élek száma. Jelenleg ez a leggyorsabb futási ideje egy erősen polinomiális algoritmusnak erre a problémára. Ha minden súly egész szám, akkor a futási idő javítható , de a kapott algoritmus csak gyengén polinom. Ha a súlyok egész számok, és a minden súly legfeljebb C (ahol C > 1 jelentése valamilyen egész szám), akkor a problémát meg lehet oldani a gyengén-polinomiális időben egy módon, az ún tömeg skálázás . ${\ displaystyle O (mn+n^{2} \ log n)}$ ${\ displaystyle O (mn+n^{2} \ log \ log n)}$ ${\ displaystyle O (m {\ sqrt {n}} \ log (n \ cdot C))}$

A globális módszerek mellett vannak helyi módszerek, amelyek a helyi frissítések keresésén alapulnak (nem pedig a teljes bővítési útvonalakon). Ezek a módszerek rosszabb aszimptotikus futásidejű garanciákkal rendelkeznek, de a gyakorlatban gyakran jobban működnek. Ezeket az algoritmusokat aukciós algoritmusoknak , push-relabel algoritmusoknak vagy preflow-push algoritmusoknak nevezik . Ezen algoritmusok közül néhány egyenértékűnek bizonyult.

Néhány helyi módszer feltételezi, hogy a gráf tökéletes illeszkedést enged ; ha ez nem így van, akkor ezek a módszerek némelyike örökké tarthat. A probléma megoldásának egyszerű technikai módja az, hogy a bemeneti gráfot kiterjesztjük egy teljes kétoldalú gráfra, nagyon nagy súlyú mesterséges élek hozzáadásával. Ezeknek a súlyoknak meg kell haladniuk az összes meglévő illesztés súlyát, hogy megakadályozzák a mesterséges élek megjelenését a lehetséges megoldásban.

Amint azt Mulmuley, Vazirani és Vazirani is mutatja, a minimális súly tökéletes illeszkedésének problémája kiskorúak megtalálására alakul át a gráf szomszédsági mátrixában . Az elkülönítési lemma segítségével egy minimális súly tökéletes illeszkedése látható egy gráfban, legalább ½ valószínűséggel. Egy n csúcsú gráfhoz időre van szükség . ${\ displaystyle O (\ log ^{2} (n))}$

Kiegyensúlyozatlan feladat

A kiegyensúlyozatlan hozzárendelési feladatban a kétoldalú gráf nagyobb részének n csúcsa van, a kisebbik résznek pedig r < n csúcsa. Van is egy állandó s amely legfeljebb a számossága legfeljebb megfelelő a grafikonon. A cél az, hogy megtaláljuk a minimális költségű megfelelő méretű pontosan s . A leggyakoribb eset az az eset, amikor a gráf egyoldalúan tökéletes egyezést (azaz r méretű egyezést ) ismer el , és s = r .

A kiegyensúlyozatlan hozzárendelés kiegyensúlyozott feladatra redukálható. A naiv redukció az, hogy új csúcsokat kell hozzáadni a kisebb részhez, és össze kell kötni őket a nagyobb részhez a 0 költségű élek segítségével. Ehhez azonban új élekre van szükség . A hatékonyabb redukciót duplázási technikának nevezik . Itt egy új G ' gráf épül fel az eredeti G grafikon két másolatából : egy előremenő Gf és egy visszafelé Gb másolat . A visszamásolt példányt "megfordítják", így G ' mindkét oldalán most n + r csúcs található. A másolatok között kétféle összekötő élt kell hozzáadnunk: ${\ displaystyle nr}$ ${\ displaystyle n (nr)}$

Nagy-nagy: a Gf nagyobb részének minden csúcsából adjon hozzá egy nulla költségű élt a Gb megfelelő csúcsához .
Kicsi-kicsi: ha az eredeti gráfnak nincs egyoldalú tökéletes illeszkedése, akkor a Gf kisebb részének minden csúcsából adjon hozzá egy nagyon költséges élt a Gb megfelelő csúcsához .

Összességében legfeljebb új élekre van szükség. A kapott grafikon mindig tökéletesen illeszkedik a mérethez . A minimális költségű tökéletes egyezésnek ebben a grafikonban a minimális költségű maximális számosságú egyezésekből kell állnia Gf és Gb. A fő probléma ezzel a duplázási technikával az, hogy amikor nincs sebességnövekedés . ${\ displaystyle n+r}$ ${\ displaystyle n+r}$ ${\ displaystyle r \ ll n}$

A redukció használata helyett a kiegyensúlyozatlan hozzárendelési probléma megoldható a meglévő algoritmusok közvetlen általánosításával a kiegyensúlyozott hozzárendeléshez. A magyar algoritmus általánosítható a probléma megoldására erősen polinomidőben. Különösen, ha s = r, akkor a futási idő az . Ha a súlyok egész számok, akkor a Thorup módszerrel lehet futási időt kapni . ${\ displaystyle O (ms+s^{2} \ log r)}$ ${\ displaystyle O (mr+r^{2} \ log r)}$ ${\ displaystyle O (ms+s^{2} \ log \ log r)}$

Megoldás lineáris programozással

A hozzárendelési probléma megoldható, ha lineáris programként mutatjuk be . A kényelem érdekében bemutatjuk a maximalizálási problémát. Mindegyik él $(i, j)$ , ahol i A -ban és j T -ben van, súlya van . Minden élhez van egy változó _.A változó 1, ha az él szerepel az illeszkedésben, és 0, különben beállítjuk a tartomány korlátozásait: ${\ texttyle w_ {ij}}$ ${\ displaystyle (i, j)}$ ${\ texttyle x_ {ij}}$

{\ displaystyle 0 \ leq x_ {ij} \ leq 1 {\ text {for}} i, j \ A, T, \,}

{\ displaystyle x_ {ij} \ in \ mathbb {Z} {\ text {for}} i, j \ in A, T.}

A teljes súlya egyezés: . A cél az, hogy megtalálja a maximális súlyú tökéletes egyezést. ${\ displaystyle \ sum _ {(i, j) \ in A \ times T} w_ {ij} x_ {ij}}$

Annak biztosítása érdekében, hogy a változók valóban tökéletes illeszkedést képviseljenek, olyan megszorításokat adunk hozzá, amelyek szerint minden csúcs pontosan egy éle mellett van az illesztésben, azaz

{\ displaystyle \ sum _ {j \ in T} x_ {ij} = 1 {\ text {for}} i \ in A, \, ~~~ \ sum _ {i \ in A} x_ {ij} = 1 {\ text {for}} j \ T, \,}

.

Összességében a következő nagylemezünk van:

{\ displaystyle {\ text {maximize}} ~~ \ sum _ {(i, j) \ in A \ times T} w_ {ij} x_ {ij}}

{\ displaystyle {\ text {subject to}} ~~ \ sum _ {j \ in T} x_ {ij} = 1 {\ text {for}} i \ in A, \, ~~~ \ sum _ {i \ in A} x_ {ij} = 1 {\ text {for}} j \ in T}

{\ displaystyle 0 \ leq x_ {ij} \ leq 1 {\ text {for}} i, j \ A, T, \,}

{\ displaystyle x_ {ij} \ in \ mathbb {Z} {\ text {for}} i, j \ in A, T.}

Ez egy egész lineáris program. Meg tudjuk azonban oldani az integrálási korlátozások nélkül (azaz el kell hagyni az utolsó korlátozást), standard módszerek alkalmazásával a folyamatos lineáris programok megoldására. Míg ez a megfogalmazás töredékes változóértékeket is lehetővé tesz, ebben a speciális esetben az LP mindig optimális megoldást kínál, ahol a változók egész számokat vesznek fel. Ennek az az oka, hogy a frakcionált LP korlátozó mátrixa teljesen unimoduláris - megfelel Hoffman és Gale négy feltételének.

Ez közvetlenül is bizonyítható. Legyen x a töredékes LP optimális megoldása, legyen az össztömege, és legyen a nem integrál változók száma. Ha végeztünk. Egyébként van egy törtváltozó, mondjuk . Mivel a szomszédos változók összege 1, ami egész számban, a j ₂ mellett egy másik változónak kell lennie , mondjuk tört értékkel . Hasonló megfontolások i ₃ , ott kell lennie egy másik változó szomszédos i ₃ egy frakcionális érték, mondjuk . Hasonló megfontolások alapján egyik csúcsról a másikra haladunk, töredékértékekkel gyűjtjük az éleket. Mivel a gráf véges, valamikor szükségünk van egy ciklusra. Az általánosság elvesztése nélkül feltételezhetjük, hogy a ciklus az i ₁ csúcson ér véget , tehát a ciklus utolsó törtváltozója . Tehát az élek száma a ciklusban 2 m - ennek párosnak kell lennie, mivel a grafikon kétoldalú. ${\ displaystyle w (x)}$ ${\ displaystyle k (x)}$ ${\ displaystyle k (x) = 0}$ ${\ xt {text_stílus {i_ {1}, j_ {2}}}$ ${\ displaystyle j_ {2}}$ ${\ xt {text_stílus {i_ {3}, j_ {2}}}$ ${\ texttyle x_ {i_ {3}, j_ {4}}}$ ${\ xtípus {i_ {1}, j_ {2m}}}$

Tegyük fel, hogy a ciklus összes páros változójához hozzáadunk egy bizonyos konstans e -t, és eltávolítjuk ugyanazt az e konstansot a ciklus összes páratlan változójából. Minden ilyen e esetén az egyes csúcsok közelében lévő változók összege változatlan marad (1), így a csúcskorlátok továbbra is teljesülnek. Ezenkívül, ha e elég kicsi, akkor minden változó 0 és 1 között marad, így a tartományi korlátok is teljesülnek. Könnyű megtalálni a legnagyobb e -t, amely fenntartja a tartományi korlátokat: vagy a legkisebb különbség a páratlan változó és a 0 között, vagy a legkisebb különbség a páros változó és az 1 között. Most eggyel kevesebb törtváltozóval rendelkezünk, tehát k ( x ) csökken 1. a cél érték ugyanaz, mert különben tudtuk növelni úgy, hogy kijelöli e , hogy pozitív vagy negatív, ellentétben azzal a feltevéssel, hogy maximális.

A ciklus-eltávolítási folyamat megismétlésével legfeljebb n lépés után olyan megoldáshoz jutunk, amelyben minden változó integrál.

Más módszerek és közelítő algoritmusok

A hozzárendelési problémára más megközelítések is léteznek, ezeket Duan és Pettie áttekinti (lásd II. Táblázat). Munkájuk egy hozzávetőleges algoritmust javasol a hozzárendelési problémához (és az általánosabb maximális súly -illesztési feladathoz ), amely lineáris időben fut minden rögzített hiba esetén.

Általánosítás

Ha gráfelméleti feladatként fogalmazzuk meg, a hozzárendelési probléma kiterjeszthető a kétoldalú gráfokról az önkényes gráfokra. A megfelelő probléma találni egy megfelelő , egy súlyozott gráf , ahol a súlyok összege maximalizálva van, az úgynevezett maximális súlya megfelelő probléma .

Lásd még

Hivatkozások és további olvasmányok

Brualdi, Richard A. (2006). Kombinatorikus mátrixosztályok . A matematika enciklopédiája és alkalmazásai. 108 . Cambridge: Cambridge University Press . ISBN 978-0-521-86565-4. Zbl 1106.05001 .
Burkard, Rainer ; M. Dell'Amico; S. Martello (2012). Hozzárendelési problémák (Felülvizsgált újranyomtatás) . SZIÁM. ISBN 978-1-61197-222-1.
Bertsekas, Dimitri (1998). Hálózatoptimalizálás: Folyamatos és diszkrét modellek . Athena Scientific. ISBN 978-1-886529-02-1.

Languages

In other projects