Įvadas
Atliekant šį tyrimą buvo iškeltas tikslas apibrėžti kiekvieną iš tinklo modelių, pradedant nuo pagrindinių sąvokų, tokių kaip mazgo apibrėžimas, kurios yra tinklo modelyje naudojamos viršūnės, lankas, kuris galėtų būti kiekvieno tinklo mazgo rodyklė arba jungtis, taip pat svarstymai, kurių reikia imtis norint suprasti tinklo struktūrą, pavyzdžiui, arkos nurodytos kryptys gali būti tiesioginės ar netiesioginės.
Kai suprantame tinklus sudarančių dalių terminologiją, tęsiame tai, kas būtų kiekvienas iš modelių, pirmasis galėtų būti mazgo arko dažnio matrica, tai būtų lentelė, vaizduojanti tinkle esantį modelį, medžio technika. minimalus išsiplėtimas, žingsniai, kurių reikia laikytis norint jį atlikti, maksimalaus srauto technika, techniniai žingsniai, trumpiausio maršruto technika ir kiti tinklo modeliai, kokie būtų, transportavimo problemos, trumpiausio kelio problemos, kritinis tinklo projekto planavimo kelias, mažiausių išlaidų srautas, tinklo modelių jautrumo analizė, pardavėjų kelionių problema, taip pat naudojant keletą pavyzdžių, kad problemos būtų aiškesnės.
Visos šios temos dokumente paaiškintos išsamiau ir geriau suprantamai.
Tinklo modeliai
Tinklo modelis yra įvairių pajėgumų perkrovimo modelis, kuris gali būti įvairių formų, pavyzdžiui, trumpiausio maršruto ir maksimalaus bei minimalaus srauto modelis, minimalaus pasiekimo medžio problema, kritinio kelio metodas. kitos finansinio ir gamybos planavimo programos.
Pagrindinė perkrovimo modelio, turinčio pajėgumus, savybė yra ta, kad tai yra tinklas, kuriame pasiūlymai pateikiami konkrečiuose kilmės taškuose, poreikiai konkrečiuose paskirties taškuose ir gabenimo alternatyvos yra siūlomi per tarpinius mazgus, taigi kurie eina maršrutais su apibrėžtomis galimybėmis iš kilmės į paskirties vietą.
Tinklo terminologija
Tinklą sudaro mazgų rinkinys, sujungtas lankais (arba šakomis). Tinklo apibūdinimo žymėjimas yra (N, A), kur N yra mazgų rinkinys, o A yra lankų rinkinys.
N = {1, 2, 3, 4, 5}
A = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5) }
Žemiau yra tinklo ir jo pagrindinių komponentų schema.
Technologinio tinklo modeliai
Kas yra mazgas?
Paprastai jis vadinamas viršūne arba tašku. Paprastai jį vaizduoja apskritimas. Transporto tinkluose tai turėtų būti miestai arba miestai žemėlapyje.
Kas yra arka?
Paprastai jis vadinamas kraštu arba rodykle. Tai gali būti tiesioginė ar netiesioginė. Galva yra kelionės tikslas, o uodega - kilmė. Galva ir uodega yra mazgai, kurie gali būti tiek ištakose, tiek galuose. Transporto tinkluose lankai gali būti keliai, upės navigacijos kanalai ar lėktuvo skrydžio schemos. Lankai suteikia galimybę sujungti mazgus. Vienpusę gatvę galima pavaizduoti lanku, o dvipusę gatvę - be krypčių ar dviem lankais, nukreipiančiais į priešingas puses. Tinkle su n mazgais gali būti tiek daug lankų, kiek n! / = n (n-1) / 2. Jei tikslinės, šis skaičius gali padvigubėti.Šis milžiniškas galimų lankų skaičius yra viena iš priežasčių, kodėl egzistuoja specialūs algoritmų sprendimai tam tikroms tinklo problemoms.
Tinklo mazge paprastai rasite skaičių su teigiamu arba neigiamu ženklu, kuris žymi mazgo tiekimą (+) ir paklausą arba reikalavimus (-).
Maršrutas yra lankų, jungiančių du skirtingus mazgus, rinkinys, einantis per kitus tinklo mazgus. Pavyzdžiui, 1 paveiksle, lankai (1,2), (2,3), (3,4) ir (4,5) sudaro kelią tarp 1 ir 5 mazgų. Kelias sudaro kilpą arba kilpa, jei per kitus mazgus prijungiate mazgą prie savęs. 6.1 paveiksle lankai (2,3), (3,4) ir (4,2) sudaro ciklą.
Svarbios pastabos:
- Vienos krypties strėlės / linijos yra tiesioginiai lankai. Linijos, kurių srautas nukreiptas į abi puses, yra netiesioginiai lankai. Tinklas, turintis tik tiesioginius lankus, yra tiesioginis tinklas. Tinklas, turintis lankus abiem kryptimis, yra netiesioginis tinklas. Tiesioginis kelias nuo mazgo i iki j yra sujungtų lankų seka, todėl yra įmanoma srautas, einantis per tą kelią. Netiesioginis kelias nuo mazgo i iki j yra sujungtų lankų seka, kurios kryptis yra i ir atvirkščiai Kelias, kuris prasideda ir baigiasi tame pačiame mazge, yra kilpa.Jei tinkle yra bent vienas tiesioginis kelias tarp 2 mazgų, sakoma, kad jie yra sujungti. Norėdami nustatyti, kuris iš tinklo maršrutų bus pasirinktas, turime atsižvelgti į sąnaudas ir pajėgumus maršrutų trasoje.
Tinklo modelių 1 versija
Mazgas - lanko dažnio matrica
Tai yra lentelė, kurioje pateikiami apribojimų duomenys tinklo modelyje. Kiekvienas tinklo lankas atitinka lentelės stulpelį. Kiekvienas tinklo mazgas atitinka lentelės eilutę. Stulpeliuose yra tik du įrašai be nulio: +1 ir -1.
Technologinio tinklo modeliai
Pakėlę linijinio programavimo modelį, turime rasti sprendimą, kuris linijinį programavimą, mes turime rasti sprendimą, kuris optimizuoja objekto funkciją.
- Norėdami rasti optimalų sprendimą, galime naudoti kai kurias linijinio programavimo programas, tokias kaip SOLVER ar LINDO.
Uždarymas
- Tinklo piešimo terminija ir procedūra padės pritaikyti optimizavimo modelius, nes žiūrint į 3 iliustraciją yra daug lengviau nustatyti trumpiausią ar ilgiausią kelią ir pan.
2 tinklo modelio versija
Minimali aprėpiamo medžio technika
Šis medis susieja tinklo mazgus, naudodamas mažiausią jungiamųjų atšakų ilgį. Dažnai naudojamasi tiesiant kelius, kurie jungia miestus arba tiesiogiai, arba kurie eina per kitus miestelius. Mažiausiai apimantis medžio sprendimas suteikia kelio sistemos dizainą.
Žingsniai Minimali įtempimo medžio technika
- Pasirinkite bet kurį tinklo mazgą. Prijunkite šį mazgą prie artimiausio mazgo, kuris sumažina bendrą atstumą. Atsižvelgiant į visus dabar prijungtus mazgus, suraskite ir prijunkite artimiausią nesusietą mazgą. Jei artimiausio mazgo ryšys yra, pasirinkti vieną savavališkai. Ryšys rodo, kad gali būti daugiau nei vienas optimalus sprendimas. Kartokite trečiąjį veiksmą, kol visi mazgai bus sujungti.
Pavyzdys
Roxie LaMothe, kuriam priklauso didelis arklių veisimo ūkis netoli Orlando, planuoja įrengti vandens sistemą, jungiančią visas arklides ir tvartus. Patalpų vieta ir atstumai tarp jų pavaizduoti kitame paveiksle. Roxie turi nustatyti pigiausią vandens tiekimo į kiekvieną įrenginį būdą.
Technologinio tinklo modeliai
Didžiausio srauto technika
- Didžiausio srauto technika lemia tai, kas gali tekėti tinklu.
4 smailės tekėjimo technikos žingsniai
- Pasirinkę bet kurį kelią nuo pradžios (originalo) iki pabaigos (tikslo), pasirinkite kelią. Jei nėra srauto kelio, tada buvo pasiektas optimalus sprendimas. Raskite kelio lanką su mažiausiu įmanomu srauto pajėgumu. Tai parodo maksimalią papildomą talpą, kuri gali būti paskirta šiam keliui. Kiekvienam šio kelio mazgui sumažinkite srauto pajėgumą srauto kryptimi suma C. Kiekvienam šio kelio mazgui padidinkite talpą. srautas priešinga kryptimi pagal C kiekį.
Pakartokite šiuos veiksmus, kol nebeįmanoma padidinti srauto.
Pavyzdys
Naftos perdirbimo įmonė „PetroChem“, įsikūrusi Misisipės upėje į pietus nuo Baton Ružo, Luizianoje, projektuoja naują gamyklą dyzeliniam kurui gaminti. 5 paveiksle parodytas pagrindinių perdirbimo centrų tinklas kartu su esamu srauto greičiu. Vadovybė norėtų nustatyti maksimalų kuro kiekį, kuris gali tekėti per gamyklą nuo 1 mazgo iki 7 mazgo.
Technologinio tinklo modeliai
Trumpiausio kelio technika
Ši problema nustato trumpiausią kelią tarp šaltinio ir paskirties transporto tinkle.
Trumpiausio kelio technikos žingsniai
- Raskite mazgą, artimiausią kilmei. Įrašykite atstumą į langelį, esantį šalia mazgo. Raskite artimiausią mazgą, esantį kilmei (augalui), ir nurodykite atstumą į langelį šalia mazgo. Kai kuriais atvejais, norint surasti artimiausią mazgą, teks peržiūrėti kelis kelius - pakartokite procesą, kol apvažiuosite visą tinklą. Paskutinis atstumas galiniame mazge bus trumpiausio kelio atstumas. Atminkite, kad atstumas, esantis laukelyje šalia kiekvieno mazgo, yra trumpiausias kelias į šį mazgą. Šie atstumai naudojami kaip tarpiniai rezultatai norint surasti kitą artimiausią mazgą.
Pavyzdys:
„RentCar“ plėtoja savo automobilių parko pakeitimo politiką 4 metų planavimo laikotarpiu. Kiekvienų metų pradžioje automobilis keičiamas arba eksploatuojamas dar vienerius metus. Automobilis turėtų būti eksploatuojamas nuo 1 iki 3 metų. Šioje lentelėje pateikiamos pakeitimo išlaidos atsižvelgiant į automobilio įsigijimo metus ir eksploatavimo metus.
Technologinio tinklo modeliai
Problemą galima apibūdinti kaip tinklą, kuriame mazgai nuo 1 iki 5 reiškia 1–5 metų pradžią. Arkai iš 1 mazgo (1 metai) gali pasiekti 2, 3 ir 4 mazgus, nes automobilis gali būti eksploatuojamas nuo 1 iki 3 metų. Lankai iš kitų mazgų gali būti aiškinami vienodai. Kiekvienos arkos ilgis yra lygus pakeitimo kainai. Problemos sprendimas yra lygiavertis trumpiausio kelio tarp 1 ir 5 mazgų nustatymui.
6 paveiksle parodytas gautas tinklas. Naudojant TORA, 2 trumpiausias kelias yra 1 S3 S5.
Sprendime nurodoma, kad 1 metų pradžioje įsigytą automobilį (1 mazgas) reikia pakeisti po 2 metų 3 metų pradžioje (3 mazgas). Pakaitinis automobilis bus eksploatuojamas iki 4 metų pabaigos. Bendros šios pakeitimo politikos išlaidos yra 12 500 USD.
(= 5400 USD + 7100 USD).
Technologinio tinklo modeliai
3 tinklo modelio versija
Tinklo modelių tipai
Tinklo optimizavimo problemų šeimą sudaro šie modelių prototipai: Paskyrimo problemos, kritinis kelias, maksimalus srautas, trumpiausias kelias, transportavimas ir minimalios srautų sąnaudos. Problemos lengvai nustatomos naudojant tinklo lankus ir mazgus.
Transportavimo problemos
Transporto modeliai vaidina svarbų vaidmenį logistikos valdyme ir tiekimo grandinėje, siekiant sumažinti sąnaudas ir pagerinti paslaugas. Todėl tikslas yra rasti ekonomiškiausią prekių gabenimo būdą. Platintojas, turintis „m“ sandėlius, kuriuose yra tiekiamų produktų, privalo juos nusiųsti į geografiškai išskaidytus mažmeninės prekybos centrus, kurių kiekvienas turi tam tikrą klientų poreikį, kurie turi būti padengti. Tikslas yra nustatyti kuo mažesnes gabenimo sąnaudas, atsižvelgiant į transportavimo vienetus iš i-ojo sandėlio ir prekybos tinklo „j th“, kuris yra Cij.
Trumpiausios kelio problemos
Problema yra geriausias būdas pereiti tinklą, kad būtų galima rasti pigiausią įmanomą kelią iš vienos kilmės vietos į nurodytą vietą. Tarkime, kad tam tikrame tinkle yra m mazgai ir n lankai (briaunos) ir kaina Cij, susijusi su kiekvienu tinklo lanku (iaj). Formaliai trumpiausio kelio (CC) problema yra rasti trumpiausią kelią (mažiausią kainą) nuo pradžios mazgo 1 iki pabaigos mazgo m. Kelio kaina yra kiekvieno nuvažiuoto lanko išlaidų suma. Apibrėžkite dvejetainius kintamuosius Xij, kur Xij = 1, jei lankas (iaj) yra ant CC, o Xij = 0 kitu atveju. Yra du specialūs mazgai, vadinami šaltiniu ir tikslu. Tikslas yra rasti trumpiausią kelią tarp kilmės ir kelionės tikslo.
Kritinis kelias tinklo projekto planavime
Sėkmingas ambicingo projekto valdymas, nesvarbu, ar tai būtų statyba, transportavimas, ar finansai, priklauso nuo kruopštaus įvairių užduočių koordinavimo ir planavimo. Kritinio kelio (arba kelio) metodu (CCM) bandoma išanalizuoti projekto planavimą. Tai leidžia geriau kontroliuoti ir įvertinti projektą. Pavyzdžiui, norime sužinoti, kiek laiko truks projektas? Kada bus galima pradėti tam tikrą užduotį? Jei užduotis nebus atlikta laiku, Ar likusi projekto dalis bus atidėta?
Kokias užduotis reikia paspartinti (efektyviai), kad projektas būtų baigtas anksčiau?
Minimalių sąnaudų srauto problema
Visos aukščiau išvardytos tinklo problemos yra ypatingos minimalaus išlaidų srauto problemos atvejai. Kaip ir didžiausio srauto problema, ji nagrinėja srautus tinkluose, kuriuose yra galimybių. Kaip ir trumpiausio kelio problema, čia atsižvelgiama į srauto į arką kainą. Kaip ir transportavimo problema, ji leidžia keliais atvejais kilti iš kelių vietų. Todėl visos šios problemos gali būti vertinamos kaip ypatingi minimalaus išlaidų srauto problemos atvejai. Problema yra sumažinti visas sąnaudas atsižvelgiant į tai, ar yra tam tikrų mazgų, ir dėl viršutinio srauto per kiekvieną lanką sujungimo.
Tinklo modelių jautrumo analizė
Klasikinę tinklo optimizavimo problemos šeimą sudaro šie modelio prototipai: paskirstymas, kritinis kelias, maksimalus srautas, trumpiausias kelias ir transportas. Nors gerai žinoma, kad šios rūšies problemos gali būti modeliuojamos kaip linijinis programavimas, paprastai jos niekada nebūna daromos. Dėl tinklo modelių neefektyvaus ir santykinio sudėtingumo (pirminių, dvigubų ir kitų variantų) tinklo problema ši problema sprendžiama vienu iš daugiau nei 400 specialiųjų algoritmų. Tai sukelia daug sunkumų. Algoritmų sprendimai nėra vieningi ir kiekvienas algoritmas naudoja skirtingą strategiją, norėdamas ištirti specialią konkrečios problemos struktūrą. Be to, nedideli problemos variantai, pavyzdžiui, pridedant atskirą apribojimą ar kelis indeksus,sunaikina specialią struktūrą ir verčia algoritmą paleisti iš naujo. Be to, iš šių algoritmų gaunami veiksmingi sprendimai už menką gudrumą, nes galutinis šių algoritmų sprendimas neturi pakankamai informacijos jautrumo analizei atlikti.
Pardavėjo kelionių problema
Pardavėjas privalo aplankyti 1, 2,.. N miestus, o jo kelionė prasideda ir baigiasi gimtajame mieste. Tegul Cij yra kelionės į miestą ir miestą j kaina, kuri yra nurodyta. Problema yra nustatyti optimalų kelionės per miestus užsakymą taip, kad išlaidos būtų kuo mažesnės. Srauto maksimizavimas yra tipinė „Operations Research“ problema, kuriai taikoma daugybė programų, pavyzdžiui, kelių srautas mieste, kanalizacijos tinklas, kompiuterių tinklas ir kt.
išvada
Apibendrinant galima pasakyti, kad lankai yra kiekvieno tinklo mazgų jungtys, šie modeliai gali turėti tiesioginį ar netiesioginį adresą, kad kiekviename tinkle gali būti kelios jungtys, kurios sujungia kelis mazgus ir taip sukuria maršrutus kiekviename tinkle. tinkle yra ciklų, jungiančių mazgus už pradinio kelio.
Modeliai gali būti pavaizduoti tinklo programomis. Antrosios versijos modeliai, tokie kaip mažiausio įtempimo medžio technika, naudojami tais atvejais, kai atstumai yra maži arba maži, maksimalus srauto metodas nustato, kiek yra daugiausiai, kas gali tekėti. Tinkle trumpiausio kelio technika padeda mums nustatyti trumpiausią kelią nuo kilmės mazgo ir transporto kelio.
Tinklo modeliai yra bendrai naudojami tam tikruose darbo aspektuose ir jų dėka mes galime išspręsti problemas, ir jie gali būti kuriami skirtingose srityse palengvinant jiems tinkamiausius maršrutus.
Tikimės, kad šis straipsnis yra labai naudingas ir jame pateiktos sąvokos yra aiškiai paaiškintos.
Nuorodos
- Hillier, F., Lieberman, G. (2006). Įvadas į operacijų tyrimus. (8-asis leidimas) Meksika. McGraw Hill. ISBN 970-10-5621-3Oc, F, (2010), Tinklų modeliai - tyrimo operacijos, gauta iš http://www.slideshare.net/FreddOc/modelos-de-redes-investigacin-de-operacionesTaha, HA (2012), Operacijų tyrimas, (9-asis leidimas), Meksika, „Pearson Education“. ISBN: 978-607-32-0796-6 Raffo, E. (1990), Operacijų tyrimas, Lima, Raffo Lecca Editores, bibliotekos kodas: 658.4034 / T16
