Általános hozzárendelési probléma

Az alkalmazott matematikában az általánosított hozzárendelési probléma alatt kombinatorikus optimalizálási feladatot értünk , amely a hozzárendelési probléma általánosítása , amelyben a teljesítők halmazának mérete nem feltétlenül egyenlő a munkák halmazának méretével. Ebben az esetben az előadó bármilyen munka elvégzésére kijelölhető (nem feltétlenül egy műre, mint a hozzárendelési feladatnál). Amikor egy végrehajtót rendel a munka elvégzéséhez, két értéket kell beállítani - a költségeket és a bevételeket. Minden előadónak van egy bizonyos költségvetése, így az összes költség összege nem haladhatja meg ezt a költségvetést. A bevétel maximalizálása érdekében meg kell találni az előadóművészek ilyen megbízását a munka elvégzésére.

Különleges alkalmak

Abban az esetben, ha az előadók költségvetése és az összes munkaköltség 1, a probléma a maximális illeszkedési problémává válik .

Ha az árak és a bevételek az összes munkakörre azonosak, a probléma multiplikatív hátizsákká csökken .

Ha csak egy ügynök van, a probléma a hátizsák problémájává válik .

Definíció

n állás és m előadó van . Minden előadónak van költségvetése . Minden egyes előadó- és munkapárra megadják a jövedelmet és a súlyt . A megoldás az U munkák egy részhalmaza, és az U munkák elosztása az előadók között. A döntés akkor fogadható el, ha az előadóművész megbízott munkájának költsége nem haladja meg a költségvetést . A döntésből származó bevétel a munkavégző összes megoszlása összes bevételének összege. ${\displaystyle x_{1},\dots ,x_{n))$ ${\displaystyle b_{1},\dots ,b_{m))$ $kettős}$ $w_{i}$ $kettős}$ $x_{j}$ $p_{i,j}$ $w_{i,j}$ $kettős}$ $w_{i}$

Matematikailag az általánosított hozzárendelési probléma a következőképpen fogalmazható meg:

maximalizálni

\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.

alá tartozó ;

\sum _{j=1}^{n}w_{ij}x_{ij}\leq w_{i}\qquad i=1,\ldots ,m

\sum _{i=1}^{m}x_{ij}\leq 1\qquad j=1,\ldots ,n

;

x_{ij}\in \{0,1\}\qquad i=1,\ldots ,m,\quad j=1,\ldots ,n

;

Az általános hozzárendelési probléma NP-nehéz , sőt APX-nehéz .

Fleischer, Gomans, Mirokni és Sviridenko egy kombinatorikus lokális keresési algoritmust javasoltak közelítéssel és egy lineáris programozáson alapuló algoritmust közelítéssel [1] . $(2+\varepszilon )$ $({\frac {e}{e-1))+\varepsilon )$

A közelítés az általánosított hozzárendelési probléma legismertebb közelítése. $({\frac {e}{e-1}}+\epsilon )$

Greedy Approximation Algorithm

A hozzárendelési probléma -közelítési algoritmus segítségével az általánosított hozzárendelési problémára a maradék jövedelem fogalmát használó mohó algoritmus módjára ( ) -közelítést készíthetünk. Az algoritmus iteratív módon létrehoz egy előzetes sorozatot, amelyben az iteráció során munkát kell kiosztania az előadónak . Az előadóra vonatkozó választás később módosítható, amikor más előadóknak adnak ki munkát. A műből fennmaradó bevétel az előadó számára , ha a művet nem adják át más előadónak, és - ha a művet az előadónak adják . $\alpha$ $\alpha +1$ $j$ $b_{j}$ $b_{j}$ $x_{i}$ $b_{j}$ $p_{{ij}}$ $x_{i}$ $p_{ij}$ ${\displaystyle p_{ik))$ $b_{k}$

Formálisan:

Használja a vektort az előválasztáshoz és ebben a vektorban $T$

T[i]=j

azt jelenti, hogy a műhöz hozzá kell rendelni egy végrehajtót ,

x_{i}

b_{j}

T[i]=-1

azt jelenti, hogy senkit sem osztottak ki a feladatra.

x_{i}

Az iterációnként fennmaradó bevételt jelöli , ahol $j$ $P_{j}$

{\displaystyle P_{j}[i]=p_{ij))

ha nincs kiválasztva munka (azaz )

x_{i}

T[i]=-1

{\displaystyle P_{j}[i]=p_{ij}-p_{ik))

, ha a művet állítólag az előadónak kell adni (azaz ).

x_{i}

b_{k}

T[i]=k

Tehát az algoritmus így néz ki:

Hozzárendelt kezdeti értékek mindenkinek

T[i]=-1

i=1\ldots n

Mindenki számára tegye a következőket:

j=1...m

Egy közelítő algoritmust használnak a maradványjövedelem függvény segítségével a vállalkozó munkaelosztásának meghatározására . A kiválasztott művek fel vannak tüntetve .

b_{j}

P_{j}

S_j

Használatával javítva , azaz mindenre .

T

S_j

T[i]=j

{\displaystyle i\in S_{j))

ciklus vége

Lásd még

Hozzárendelési probléma

Jegyzetek

↑ L. Fleischer, MX Goemans, VS Mirrokni és M. Sviridenko. Szoros közelítő algoritmusok a maximális általános hozzárendelési problémákhoz. A SODA'06-ban: Proc

Linkek

Reuven Cohen, Liran Katzir és Danny Raz, "An Efficient Approximation for the Generalized Assignment Problem" , Information Processing Letters, Vol. 100, 4. szám, pp. 162–166, 2006. november.
Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni és Maxim Sviridenko, "Szűk közelítési algoritmusok maximális általános kiosztási problémákhoz" , SODA 2006, pp. 611–620.
Hans Kellerer, Ulrich Pferschy, David Pisinger, Knapsack Problems , 2005. Springer Verlag ISBN 3-540-40286-1