A végrehajtók minimális számának hozzárendelésének problémája

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2017. augusztus 15-én felülvizsgált verziótól ; az ellenőrzések 6 szerkesztést igényelnek .

Az alkalmazott matematikában a minimális számú teljesítő hozzárendelése egy kombinatorikus optimalizálási feladat alatt értendő, amely általánosítja a halmaz lefedésének problémáját, és megfogalmazásában hasonló a hozzárendelési feladathoz .

Ebben a problémában a dolgozók halmazának mérete nem feltétlenül egyenlő a munkakörök halmazának méretével. Ebben az esetben egy végrehajtó több feladat egyidejű végrehajtására is hozzárendelhető, és minden jobhoz csak egy végrehajtó van hozzárendelve. Minden tevékenység végrehajtására teljes költségvetés áll rendelkezésre, ami a hozzárendelési korlát. Olyan előadóművészek kinevezését kell találni a munka elvégzésére, hogy a munkavégzésben részt vevő előadóművészek száma minimális legyen, és ne haladja meg a teljes műegyüttesre elkülönített költségvetést.

Definíció

n előadó és m állás van . Minden egyes előadópár és mű esetében a munka elvégzésének költsége megadva . A teljes munkacsoport megvalósítására általános költségvetés áll rendelkezésre. A megoldás az U végrehajtók egy részhalmaza, és az U -ból származó végrehajtók hozzárendeléseinek elosztása a munkák között. A döntés akkor fogadható el, ha minden munkára kivitelezőt rendelnek ki, és ennek költsége nem haladja meg a költségvetést . Minimalizálni kell a hozzárendelt előadók számát ( L ). Más szóval, meg kell választani az előadók minimális (teljesítményét tekintve) készletét, akik együtt képesek az összes munkát elvégezni. $w_{i,j}$ $w$ $w$

A probléma úgy oldható meg, hogy két részre osztjuk:

A minimális számú előadó kiválasztása, akik együtt képesek lesznek az összes munkát elvégezni és teljesíteni a költségvetést . Ez a probléma NP-nehéz azóta az NP-teljes halmaz lefedő problémájának általánosítása . $w$
Kinevezés a kiválasztott előadói csoportba munkára.

Matematikailag az előadók minimális számának meghatározásának problémája a következőképpen fogalmazható meg [1] :

minimalizálni

{\displaystyle L=\mid U\mid =\sum _{i=1}^{n}\max _{j=1}^{m}x_{ij))

alá

\sum _{i=1}^{n}\sum _{j=1}^{m}w_{ij}x_{ij}\leq w.

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

;

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

Ebben a beállításban a feladat célfüggvénye nem lineáris, ami nem teszi lehetővé az optimális megoldás közvetlen megtalálását pontos lineáris programozási módszerekkel , beleértve a szimplex módszert is . A feladat azonban linearizálható további változók bevonásával , amelyek a kiválasztási tényt mutatják az előadó csoportjában , . A változókat és a . Ekkor a célfüggvény alakot ölt ${\displaystyle y_{i))$ $én$ $y_{i}\in \{0,1\}\qquad i=1,\ldots ,n$ ${\displaystyle y_{i))$ $x_{ij}$

minimalizálni .

{\displaystyle L=\mid U\mid =\sum _{i=1}^{n}y_{i))

A változók kapcsolata a következő feltétellel adható meg:

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

Hozzávetőleges algoritmusok

A nagy méretű problémák gyors megoldásához célszerű közelítő algoritmusokat használni: a minimális elemek maximális számának algoritmusát (MCME) és a maximális megengedett elemek számának algoritmusát (MCDE) [2] .

Lásd még

Jegyzetek

↑ Kataev A.V., Kataeva T.M., Kozhenko Ya.V. Kataev A. V., Kataeva T. M., Kozhenko Ya. V. A projektcsapat méretének optimalizálása: gazdasági és matematikai eszközök // Versenyképesség a globális világban: közgazdaságtan, tudomány, technológia. 2016. - 8-3 (22) szám. – 101-104
↑ Kataev A.V., Kataeva T.M. Dinamikus partnerhálózaton alapuló projektmenedzsment: monográfia. - Rostov-on-Don - Taganrog: A Déli Szövetségi Egyetem Kiadója, 2017. - 125 p.