Hozzárendelési probléma

A hozzárendelési probléma az egyik alapvető kombinatorikus optimalizálási probléma a matematikai optimalizálás vagy az operációkutatás területén . A probléma az, hogy megtaláljuk az ívek minimális összegét egy súlyozott kétrészes gráfban .

A probléma legáltalánosabb formájában a következőképpen fogalmazódik meg:

Van egy bizonyos számú mű és bizonyos számú előadó . Bármely vállalkozó megbízható bármilyen (de csak egy) munka elvégzésére, de eltérő költségekkel. A munkát úgy kell elosztani, hogy a munka minimális költséggel történjen.

Ha a munkák és az előadók száma azonos, akkor a problémát lineáris hozzárendelési problémának nevezzük . Amikor egy hozzárendelési problémáról beszélünk további feltételek nélkül, általában lineáris hozzárendelési problémát jelentenek .

Algoritmusok és általánosítások

A Magyar Algoritmus egyike azon számos algoritmusnak, amely a lineáris hozzárendelési feladat megoldására szolgál polinomiális időben a jobok számában.

A hozzárendelési probléma a szállítási probléma speciális esete, amely a minimális költségáramlási probléma speciális esete, amely viszont a lineáris programozási probléma speciális esete . E problémák bármelyike megoldható szimplex módszerrel , de minden szakterületnek megvan a maga hatékonyabb algoritmusa a problémastruktúra jellemzői alapján.

Ha a célfüggvényt négyzetekben fejezzük ki, akkor másodfokú hozzárendelési problémáról beszélünk .

Példa

Tegyük fel, hogy egy taxitársaságnak három szabad autója (végrehajtó) és három ügyfele (állása) van, akik mielőbb taxit szeretnének kapni. A cég törődik a taxi ügyfélhez történő átadásának időpontjával, így minden autó esetében a költséget az határozza meg, hogy mennyi idővel éri el az autó az ügyfél által megadott várakozási helyet. A hozzárendelési probléma megoldása a gépek elosztása az ügyfelek között úgy, hogy a teljes költség (teljes várakozási idő) minimális legyen.

A megbízások feladata rugalmasabbá tehető. A fenti példában lehet, hogy nem három, hanem négy ingyenes taxi van, de még mindig van három ügyfél. Egy negyedik fiktív vásárlót nulla költséggel rendelhet hozzá, míg egy autó kiosztása egy fiktív ügyfélhez azt jelenti, hogy „nem csinál semmit”.

Hasonló technika alkalmazható akkor is, ha a megrendelések száma meghaladhatja a rendelkezésre álló autók számát, és az autót több munka elvégzésére is ki lehet rendelni, illetve akkor is, ha a munka több szereplőhöz rendelhető (például ha a megrendelő csoport, amely nem fér el egy taxiban). Célul is kitűzheti a bevétel növelését az ár minimalizálása helyett.

Formális matematikai definíció

A hozzárendelési probléma hivatalos megfogalmazása :

Adott két azonos méretű A és T halmaz , és adott egy C költségfüggvény : A × T → R. Meg kell találni egy f : A → T bijekciót úgy, hogy a célfüggvény :

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

minimális.

Általában a költségfüggvényt valós számokból álló C négyzetmátrixként adják meg, így a célfüggvényt így írhatjuk fel:

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

A problémát "lineárisnak" nevezik, mert mind a célfüggvény, mind a megszorítások csak lineáris kifejezéseket tartalmaznak.

A probléma lineáris programozási problémaként ábrázolható célfüggvénnyel

{\displaystyle \sum _{i\in A}\sum _{j\in T}C(i,j)x_{ij))

és korlátozások

\sum _{j\in T}x_{ij}=1

számára ,

i\in A

\sum _{i\in A}x_{ij}=1

számára ,

j\in T

x_{ij}\geq 0

számára .

i,j\in A,T

A változó egy végrehajtó jobhoz való hozzárendelését jelöli , és 1-et vesz fel, ha a végrehajtó hozzá van rendelve az adott jobhoz, és 0-t egyébként. Ebben a megfogalmazásban a megoldás nem lehet egész szám, de mindig létezik egy optimális megoldás egész értékekkel. Ez a tény a mátrix abszolút unimodularitásából következik . Az első megkötés megköveteli, hogy minden dolgozóhoz pontosan egy feladatot, a másodikhoz pedig egy dolgozót kell hozzárendelni. $x_{ij}$ $én$ $j$

Lásd még

Irodalom

Hemdy A. Taha. 5.4. fejezet A hozzárendelési probléma. // Bevezetés az operációkutatásba. 7. kiadás. Per. angolról. - M . : "Williams" kiadó, 2005.
Wagner G. Függelék 1.2 A hozzárendelési probléma megoldása // Az operációkutatás alapjai. Per. angolról. - M . : "Mir" kiadó, 1972 .. - T. 1.
Akof R., Sasieni M.,. 5. fejezet Elosztási feladatok: Erőforrások hozzárendelése és allokációja // Az operációkutatás alapjai. - M . : "Mir" kiadó, 1971.
Richard A. Brualdi. Kombinatorikus mátrix osztályok . - Cambridge: Cambridge University Press , 2006. - (Matematika és alkalmazásai enciklopédiája). — ISBN 0-521-86565-4 .
Rainer Burkard, M. Dell'Amico, S. Martello. Hozzárendelési problémák (Átdolgozott újranyomtatás). - SIAM, 2012. - ISBN 978-1-61197-222-1 .