operačná a systémová analýza

  • Published on
    22-Nov-2014

  • View
    3.470

  • Download
    5

Embed Size (px)

Transcript

<p>DeterministickmetdyoperanejanalzyJaromr Mca, Bohu LeitnerObsah3OBSAHPredhovor .................................................................................................. 51. Predmet operan analza...................................................................... 7Literatra................................................................................................... 122. Riadenie a rozhodovanie ........................................................................ 13 2.1 Zkladn schma riadenia.................................................................. 13 2.2 Informcia v systme riadenia ........................................................... 16 2.3 Rozhodovanie v systme riadenia...................................................... 18 2.4 Rozdelenie metd rozhodovania........................................................ 19 2.4.1 Empirick metdy rozhodovania ............................................ 20 2.4.2 Exaktn metdy rozhodovania................................................ 21 2.4.3 Heuristick metdy rozhodovania........................................... 21 Literatra.................................................................................................. 323. Zkladn postupy a metdy optimalizcie............................................. 33 3.1 Von extrmy funkci ...................................................................... 34 3.2 Viazan extrmy funkci.................................................................... 37 3.3 Zkladn pojmy varianho potu ..................................................... 39 Cvienia ................................................................................................... 41 Literatra.................................................................................................. 414. Linerne programovanie ........................................................................ 42 4.1 Prklady jednoduchch loh linerneho programovania .................... 44 4.2 Grafick rieenie loh linerneho programovania.............................. 51 Cvienia ................................................................................................... 57 Literatra.................................................................................................. 595. Simplexov algoritmus ............................................................................ 60 5.1 Kanonick tvar lohy linerneho programovania .............................. 60 5.2 Vlastn simplexov algoritmus ......................................................... 63 5.3 Dvojfzov simplexov algoritmus ................................................... 69 5.4 Dualita loh linerneho programovania ............................................. 72 5.5 Celoseln linerne programovanie .................................................. 75 5.5.1 Grafick rieenie lohy celoselnho programovania ............ 76 5.5.2 Metda Branch and Bound.................................................. 77 5.5.3 Gomoryho algoritmus ............................................................. 804 5.6 Analza citlivosti v lohch linerneho programovania..................... 83 Cvienia ................................................................................................... 88 Literatra.................................................................................................. 906. Distribun problmy.............................................................................. 91 6.1 Dopravn loha ................................................................................. 91 6.1.1 Formulcia a matematick model dopravnej lohy................. 916.1.2 Urenie vchodiskovho bzickho rieeniadopravnej lohy...................................................................... 96 6.1.2.1 Metda severozpadnho rohu (MSZR) ..................... 97 6.1.2.2 Metda indexov (MI) ............................................... 98 6.1.2.3 Vogelova aproximan metda (VAM)...................... 99 6.1.3 Kritrium optima a iteran pravy v dopravnej lohe............ 101 6.1.4 Nevyrovnan loha a degenerovan bzick rieenie.............. 106 6.1.5 Viacrozmern dopravn loha ................................................ 110 6.1.6 Optimlne rozmiestovanie zdrojov ...................................... 116 6.4.7 Zveren poznmky k dopravnej lohe ................................. 119 6.2 Priraovacia loha ............................................................................ 1216.2.1 Rieenie priraovacej lohy pre maximlnu hodnotuelovej funkcie ..................................................................... 126 6.3 Zveren poznmky k distribunm lohm.................................... 128 Cvienia ................................................................................................... 128 Literatra.................................................................................................. 1297. Zklady terie grafov.............................................................................. 130 7.1 Minimlna kostra grafu ..................................................................... 135 7.2 Minimlne cesty v grafoch ................................................................ 137 7.2.1 Matematick model lohy minimlnej cesty........................... 144 7.3 Optimlne toky v sieach................................................................... 145 7.4 Minimlna okrun cesta v grafe ....................................................... 149 Cvienia ................................................................................................... 152 Literatra.................................................................................................. 1548. Zklady sieovej analzy ........................................................................ 155 8.1 Metda kritickej cesty (CPM)............................................................ 156 8.2 Metda CPM-GE............................................................................... 169 Cvienia ................................................................................................... 176 Literatra.................................................................................................. 178 ZVER.................................................................................................... 179Predhovor5PREDHOVORRozumn lovek sa prispsob svojmu okoliu.Nerozumn sa sna prispsobi okolie sebe.Preto vetok pokrok zvis od nerozumnch ud.G. B. SHAWPredkladan uebnica Operan analza I bola spracovan akozkladn vyuovac text pre rovnomenn predmet v tudijnom odboreObianska bezpenos. Vychdza z niekokoronch sksenost z prednok acvien v predmetoch podobnho zamerania na Fakulte pecilneho ininierstva,priom je doplnen o niektor najnovie poznatky a metdy.V uebnici s zaraden predovetkm deterministick modely a metdyoperanej analzy, priom hlavn draz je poloen na tvorbu matematickchmodelov. Z metd rieenia s pragmaticky a bez dkazov uvdzan ibanajdleitejie a najpouvanejie algoritmy, pretoe pri dnenom rozrenvpotovej techniky a komernch programovch produktov z uvedenej oblastimaj rozhodujci vznam predovetkm sprvna matematick formulcialohy, kvalifikovan prprava vstupnch dajov, vber vhodnej metdy rieeniaspolu s posdenm rieitenosti a kvalifikovan interpretcia zskanchvsledkov. Vlastn vpoet prakticky ubovolne rozsiahlych loh pritomprebieha na primerane vkonnej vpotovej technike.Text uebnice je rozdelen do smich kapitol.V 1.kapitole je strune definovan predmet operanej analzy a uvedennajdleitejie etapy jej vvoja, prehad vyuvanch metd a schematickpostupy tvorby matematickch modelov najrozrenejch problmov.2.kapitola uvdza zkladn schmu riadenia. Obsahuje rozbor zkladnhocyklu riadenia, v ktorom je pozornos venovan najm rozhodovaniu a jehoOperan analza I6metdam. Detailnejie s rozpracovan najm postupy pri multikriterilnom(viackriterilnom) rozhodovan a postupy vyuvajce rozhodovacie tabuky.3.kapitola obsahuje strun shrn metd a problmov optimlnehorozhodovania, so zameranm na lokalizciu a skmanie vonch i viazanchextrmov funkci a problematiku varianho potu.4.kapitola je venovan zkladom linerneho programovania. Obsahujezkladn problmy, ktor mono popsa sstavami linernych nerovnc a naprkladoch grafickho rieenia jednoduchch loh definuje zkladn pojmy.5.kapitola sa zaober rieenm loh linerneho programovania s vyuitmsimplexovho algoritmu. Strune je uveden dvojfzov simplexov algoritmus,dualita loh linerneho programovania ako aj citlivos linernych modelov.6.kapitola je venovan formulcii a rieeniu dopravnch a priraovacchloh, pri ktorch s uveden monosti rieenia s vyuitm simplexovhoalgoritmu i pecilne algoritmy - metda potencilov, maarsk metda a ichniektor aplikcie a rozrenia.7.kapitola uvdza zkladn pojmy a metdy terie grafov, kde s rieenproblmy svisiace s hadanm minimlnych ciest a minimlnych okrunchciest v grafoch, urovanm minimlnej kostry grafu a optimlneho toku v sieti.8.kapitola ukazuje vyuitie terie grafov pri zkladnej lohe sieovejanalzy - metde kritickej cesty (CPM ) a jej modifikcii metde CPM - GE.Na zver kadej kapitoly s uveden jednoduch prklady k precvieniupreberanej problematiky a rozhodujce literrne zdroje, z ktorch autori erpali.alie odkazy na iastkov problmy s vinou uveden priamo v nich.Zverom predhovoru si autori uebnice povauj za mil povinnospoakova recenzentom predkladanho textu akademikovi NorbertoviSzuttorovi, akademikovi Ladislavovi Skvovi a docentke Eve Slamkovej zacenn pripomienky a podnety k jeho skvalitneniu a sasne by radi poiadali opripomienky a alie nmety i jeho budcich itateov. Autori.Predmet Operacnej analzy71. PREDMET OPERANEJ ANALZYKona mzes doviest k rieke, aleaz ked ho presvedcis, aby plval na chrbte, nieco si dokzal.HARTLEYHO PRV ZKON U rznych autorov je mozn njst rzne defincie predmetu operacnanalza, prpadne operacn vskum (z anglickho Operational Research prp.Operations Research v americkej anglictine) v zvislosti na tom, akej oblastijej vyuzitia sa ten ktor autor vo svojich prcach venuje.Z hladiska celu zaradenia predmetu Operacn analza do studijnho plnustudijnch odborov zabezpecovanch Fakultou specilneho inzinierstva(bvalou Vojenskou fakultou) Zilinskej univerzity by bolo mozn definovatoperan analzu ako shrn oblast, kde sa vyuvaj modern vedeckmetdy k rieeniu komplexu problmov vznikajcich pri riaden zloitchvrobnch, ekonomickch, administratvnych, vojenskch a inch systmovzloench z kolektvov ud, techniky a materilnych prostriedkov.Predmetom operacnej analzy je vzdy zostavenie vedeckho modeluskmanho systmu, ktor obsahuje meranie a vyhodnocovanie takch faktorovako s zisk, nklady, sanca, riziko a umoznuje porovnvat vsledkyalternatvnych riesen, stratgi riadenia prpadne zskava optimlne riesenia zpohladu rznych hodnotiacich kritri.Ako je zrejm z prdavnho mena operan vlastn vznik vedeckejdisciplny operacn analza je priamo spojen s uplatnenm metd exaktnhovedeckho hodnotenia problmov a zskaniu podkladov pre kvalifikovanrozhodovanie pri riaden vojenskch operci v priebehu 2.svetovej vojny.Operacn analza I8Spja sa najcastejsie s menom profesora P.M.S. Blacketta, ktor spolu sosvojm tmom vedcov a technikov bol britskou vldou poveren riesit problmyriadenia a rozhodovania spojen s nasadzovanm novch zbranovch systmov azariaden v priebehu rozhodujcich operci 2.svetovej vojny. Uveden skupinasledovala a hodnotila viac taktickch situci, v ktorch niektor zbrane azariadenia neboli vyuzvan s optimlnou cinnostou. Pritom sa zistilo, zepodstatne lepsieho cinku mozno dosiahnut casto len po exaktnom vedeckomzhodnoten vsetkch faktorov ich nasadenia.Ako jeden z prvch klasickch prkladov jednoduchho vyuzitia toho,comu sa niekedy u ns hovor jednoduch sedliacky rozum pri rozhodovan,bol nvrh na zmenu nastavenia hlbky vbuchu u hlbinnch bmb pouzvanchproti ponorkm. Tieto bomby mali pvodne nastaven hlbku vbuchu cca 50 mpod hladinou, co bolo zalozen na predpoklade, ze ponorka mze vidiettociace lietadlo v priemere 2 minty pred tokom a za ten cas je schopn saponorit asi do hlbky 50 m. Takze hlbinn bomba vybuchujca v tejto hlbke, bymala mat pre ponorku znicujci cinok. Tto stratgia ale nebola spesn,pretoze cinnost tokov na ponorky bola v praxi hodnoten ako velmi nzka.Pvodn poziadavka na lepsie riesenie preto znela vyvint zapalovac bmb,ktor bude reagovat nie na hlbku, ale na blzkost ponorky.Detailnm sledovanm nespesnho toku a jeho jednoduchou analzoubolo ale zisten, ze cel pvodn stratgia m zsadn chybu. A sce, ak osdkaponorky zbadala tociace lietadlo a vcas sa s nou ponorila, posdka lietadlanevedela, kde presne m zhodit bomby, a preto cinnost tokov bola velminzka. Na druhej strane, pokial ponorka tociace lietadlo nezbadala a zostala nahladine, explzie v hlbke 50 m ponorke neuskodili, pretoze polomer nicenia uhlbinnch bmb bol priblizne 6,5 m. Na zklade tchto zisten bolo doporucenzmenit nastavenie zapalovacov hlbinnch bmb z 50 m na 8 m a nariaditposdkam lietadiel nebombardovat ponorky, ktor sa ponorili skr ako pred polmintou.Ked boli tieto doporucenia realizovan, zistilo sa, ze cinnost leteckchtokov proti ponorkm sa zvsila viac ako dvojnsobne, takze vvoj zapalovacareagujceho na blzkost ponorky sa ukzal ako nepotrebn. Tieto vsledkypotvrdili i spravodajsk sluzby nepriatela, ktor po prvom nasaden novejstratgie referovali o tom, ze britsk armda musela zrejme vyvint novucinnejsie hlbinn bomby, pretoze straty nemeckch ponoriek sa zrazu zvsilina viac ako dvojnsobok.Predmet Operacnej analzy9Podobnmi, aj ked postupne zlozitejsmi metdami boli este v priebehuvojny riesen aj niektor dalsie lohy svisiace hlavne s : optimlnym nasadenm batri protileteckej obrany, optimlnym zostavenm lodnch konvojov, logistickm zabezpecenm invznych vojsk, plnovanm zlozenia, vyuzitia a zabezpecenia bombardovacch zvzova mnoho dalsch.Po vojne, ked sa vedeck skupina okolo prof. Blacketta rozisla do rznychoblast, zacali sa metdy vyvinut pvodne pre vojensk cely aplikovat i vdalsch oblastiach ako v priemysle, doprave, zdravotnctve apod., pricom sazacali vo vyvjajcej sa vedeckej disciplne vyuzvat i poznatky publikovanpred vojnou. Z mnohch vedcov, ktor sa na rozvoji novej vedy podielaliuvedieme pre zaujmavost aspon niektorch : v r. 1916 publikoval Lanchester prcu zaoberajcu sa vyjadrenm bojovejcinnosti m...</p>