Problemet med att tilldela det minsta antalet exekutorer

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 15 augusti 2017; kontroller kräver 6 redigeringar .

I tillämpad matematik förstås uppgiften att tilldela ett minsta antal utförare som ett kombinatoriskt optimeringsproblem som generaliserar problemet med att täcka en mängd och liknar uppgiftsproblemet i sin formulering .

I detta problem har uppsättningen arbetare en storlek som inte nödvändigtvis är lika med storleken på uppsättningen jobb. I det här fallet kan en utförare tilldelas att utföra flera jobb samtidigt, och endast en utförare tilldelas varje jobb. Det finns en total budget för genomförandet av alla aktiviteter, vilket är uppdragsbegränsningen. Det är nödvändigt att hitta en sådan utnämning av artister för att utföra arbetet så att antalet artister som är involverade i utförandet av arbetet är minimalt och inte överstiger den budget som tilldelats för hela komplexet av verk.

Definition

Det finns n artister och m jobb. För varje par av utförare och verk anges kostnaden för att utföra arbetet . Det finns en allmän budget för genomförandet av hela komplexet av verk. Lösningen är en delmängd av utförare U och fördelning av uppdrag av utförare från U mellan jobb. Beslutet är godtagbart om utförare tillsätts för alla arbeten och kostnaderna för detta inte överstiger budgeten . Det krävs för att minimera antalet tilldelade artister ( L ). Med andra ord krävs det att man väljer den minsta (i kraftmässiga hänseende) uppsättning artister som tillsammans kan utföra allt arbete. $w_{i,j}$ $w$ $w$

Problemet kan lösas genom att dela upp det i två problem:

Val av minsta antal artister som tillsammans kommer att kunna slutföra allt arbete och klara budgeten . Detta problem är NP-svårt sedan är en generalisering av NP-komplett uppsättning som täcker problemet . $w$
Utnämning i en utvald grupp artister för arbete.

Matematiskt kan problemet med att tilldela det minsta antalet artister formuleras på följande sätt [1] :

minimera

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

föremål för

\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

I den här inställningen är problemets objektiva funktion icke-linjär, vilket inte gör att du direkt kan hitta den optimala lösningen med exakta linjära programmeringsmetoder , inklusive simplexmetoden . Uppgiften kan dock linjäriseras genom att inkludera ytterligare variabler , som visar att urvalet i gruppen av utförare , . Du måste också binda variabler och . Då kommer den objektiva funktionen att ta formen ${\displaystyle y_{i))$ $i$ $y_{i}\in \{0,1\}\qquad i=1,\ldots ,n$ ${\displaystyle y_{i))$ $x_{ij}$

minimera .

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

Kopplingen av variabler kan specificeras av följande villkor:

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

Ungefärliga algoritmer

För att snabbt lösa problem med stora dimensioner är det tillrådligt att använda ungefärliga algoritmer: algoritmen för det maximala antalet minimala element (MCME) och algoritmen för det maximala antalet tillåtna element (MCDE) [2] .

Se även

Anteckningar

↑ Kataev A.V., Kataeva T.M., Kozhenko Ya.V. Kataev A. V., Kataeva T. M., Kozhenko Ya. V. Optimering av projektgruppens storlek: ekonomiska och matematiska verktyg // Konkurrenskraft i den globala världen: ekonomi, vetenskap, teknik. 2016. - Nr 8-3 (22). – s. 101-104
↑ Kataev A.V., Kataeva T.M. Projektledning baserad på ett dynamiskt nätverk av partners: monografi. - Rostov-on-Don - Taganrog: Publishing House of the Southern Federal University, 2017. - 125 sid.