Toteuttajien vähimmäismäärän osoittamisen ongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15. elokuuta 2017 tarkistetusta versiosta . tarkastukset vaativat 6 muokkausta .

Sovelletussa matematiikassa esiintyjien vähimmäismäärän osoittamisen tehtävä ymmärretään kombinatoriseksi optimointitehtäväksi , joka yleistää joukon peittämisongelman ja on muotoilultaan samanlainen kuin osoitustehtävä .

Tässä ongelmassa työntekijöiden joukon koko ei välttämättä ole yhtä suuri kuin työjoukon koko. Tässä tapauksessa suorittaja voidaan määrätä suorittamaan useita töitä samanaikaisesti, ja kullekin työlle on määrätty vain yksi suorittaja. Kaikkien toimintojen toteuttamiseen on varattu kokonaisbudjetti, mikä on toimeksiannon rajoitus. Työn suorittamista varten on löydettävä tällainen esiintyjien nimitys siten, että työn suorittamiseen osallistuvien esiintyjien määrä on minimaalinen eikä ylitä koko teoskompleksille osoitettua budjettia.

Määritelmä

Esiintyjiä on n ja työpaikkoja m . Jokaiselle esiintyjä- ja työparille ilmoitetaan teoksen suorituskustannukset . Koko työkokonaisuuden toteuttamiseen on varattu yleinen budjetti . Ratkaisu on osajoukko toteuttajia U ja U :n suorittajien toimeksiantojen jakautuminen tehtävien kesken. Päätös hyväksytään, jos kaikille töille määrätään toimeksiantajat ja tästä aiheutuvat kustannukset eivät ylitä budjettia . Määrättyjen esiintyjien lukumäärä ( L ) on minimoitava . Toisin sanoen on valittava vähimmäismäärä (voimassa mitattuna) esiintyjiä, jotka yhdessä voivat suorittaa kaiken työn. $w_{i,j}$ $w$ $w$

Ongelma voidaan ratkaista jakamalla se kahteen ongelmaan:

Valitaan vähimmäismäärä esiintyjiä, jotka yhdessä pystyvät suorittamaan kaiken työn ja täyttämään budjetin . Tämä ongelma on NP-vaikea siitä lähtien on yleistys NP-täydestä joukosta, joka kattaa ongelman . $w$
Ajanvaraus valittuun esiintyjäryhmään työhön.

Matemaattisesti esiintyjien vähimmäismäärän osoittamisen ongelma voidaan muotoilla seuraavasti [1] :

minimoida

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

kohteena

\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

Tässä asetuksessa tehtävän tavoitefunktio on epälineaarinen, mikä ei salli optimaalisen ratkaisun löytämistä suoraan käyttämällä tarkkoja lineaarisia ohjelmointimenetelmiä , mukaan lukien simpleksimenetelmä . Tehtävä voidaan kuitenkin linearisoida sisällyttämällä siihen lisämuuttujia , jotka osoittavat valinnan tosiasian esiintyjän ryhmässä , . Sinun on myös sidottava muuttujat ja . Sitten tavoitefunktio saa muodon ${\näyttötyyli y_{i))$ $i$ $y_{i}\in \{0,1\}\qquad i=1,\ldots ,n$ ${\näyttötyyli y_{i))$ $x_{ij}$

minimoida .

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

Muuttujien yhteys voidaan määrittää seuraavalla ehdolla:

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

Likimääräiset algoritmit

Suurikokoisten ongelmien nopeaan ratkaisemiseen on suositeltavaa käyttää likimääräisiä algoritmeja: minimielementtien enimmäismäärän algoritmia (MCME) ja sallitun enimmäismäärän elementtien algoritmia (MCDE) [2] .

Katso myös

Muistiinpanot

↑ Kataev A.V., Kataeva T.M., Kozhenko Ya.V. Kataev A. V., Kataeva T. M., Kozhenko Ya. V. Projektiryhmän koon optimointi: taloudelliset ja matemaattiset työkalut // Kilpailukyky globaalissa maailmassa: taloustiede, tiede, teknologia. 2016. - nro 8-3 (22). – s. 101-104
↑ Kataev A.V., Kataeva T.M. Dynaamiseen kumppaniverkostoon perustuva projektinhallinta: monografia. - Rostov-on-Don - Taganrog: Eteläisen liittovaltion yliopiston kustantaja, 2017. - 125 s.