Petr Fiala a kolektiv Operační výzkum - nové trendy
Úvod Kniha je věnována novým trendům v operačním výzkumu, vybraným novým aplikacím, přístupům a metodám. V úvodu jsou stručně popsány obsahy a zaměření jednotlivých kapitol. Nové aplikace v managementu (P. Fiala) Operační výzkum se uplatňuje při řešení řady manažerských problémů. Mezi nejvíce se rozvíjející oblasti v důsledku využití principů operačního výzkumu patří management dodavatelských řetězců, revenue management a kombinatorické aukce. V systémovém pojetí je možno brát firmu za otevřený produkční systém, který vstupy ze svého okolí transformuje na výstupy, které předává zpět svému okolí. Okolí poskytuje také zpětnou vazbu produkčnímu systému. Dodavatelské řetězce směřují za hranice firem a snaží se koordinovat akce a kooperovat při produkci se svými dodavateli a zákazníky a tím optimalizovat chod celého dodavatelského řetězce. Management dodavatelských řetězců (Supply Chain Management) je bouřlivě se vyvíjející disciplína využívající koncepce, které byly vyvinuty v různých jiných disciplínách, včetně operačního výzkumu. Navrhování a řízení dodavatelských řetězců je nyní považováno za vedoucí prvek strategie a za efektivní způsob vytváření hodnoty pro zákazníka a vyvolává značný zájem manažerů a výzkumníků. V současných podmínkách dochází k přechodu od statických dodavatelských řetězců k dynamickým dodavatelským sítím, které se rychle adaptují na nové podmínky. Při modelování a analýze dynamických dodavatelských sítí se uplatňuje řada nástrojů, jejichž těžiště se přesunuje od vyjadřování lineárních vztahů k vyjadřování síťových vztahů a od statických pohledů k dynamickým. Zavedení nových technologií, jako jsou e-obchod, e-aukce, využití softwarových agentů a RFID technologie, má vliv na poskytování rozsáhlých dat v reálném čase a tak mění podmínky pro konstrukci modelů i algoritmů na řešení problémů dynamických dodavatelských sítí. Revenue management získal pozornost jako jedna z nejúspěšnějších aplikací operačního výzkumu. Revenue management se zabývá rozhodnutími, která se týkají řízení poptávky, metodologií a systémy, které je umožňují, s cílem dosáhnout zvýšení příjmů. Revenue management, označovaný také jako management poptávkových řetězců (demand chain management), může být brán jako komplement managementu dodavatelských řetězců (supply chain management), který se věnuje řízení nabídky, s cílem snížení nákladů. Revenue management se týká tří základních kategorií rozhodnutí: strukturální rozhodnutí, cenová rozhodnutí a rozhodnutí o množství. Strukturální rozhodnutí se týkají výběru prodejních forem, použitých segmentačních a diferenciačních mechanismů, podmínek prodeje, vytváření “balíčků” produktů atd. Cenová rozhodnutí se věnují stanovení cen, jak stanovit ceny v rámci kategorií produktu, během času, jak stanovit ceny v průběhu životního cyklu produktu atd. Rozhodnutí o množství se zabývají otázkami přijetí nebo odmítnutí kupní nabídky, alokace výstupu nebo kapacit jednotlivých segmentů, produktů a prodejních kanálů, stažení produktu z trhu s možností pozdějšího prodeje atd. Aukce jsou důležitý tržní mechanismus pro alokaci zboží. Teorie aukcí dosáhla obrovského zájmu jak ze strany ekonomie, tak i z oblasti Internetu. Navrhování aukcí je multidisciplinární zájmem, založeným na přínosech z ekonomie, operačního výzkumu, informatiky a dalších disciplín. Popularita aukcí a požadavky e-obchodu vedly ke zvýšenému zájmu o vyvinutí komplexních modelů obchodování. Při navrhování modelu pro elektronický nákup jsou základem kombinatorické aukce, které umožňují nabídky na kombinaci položek. Kombinatorické aukce vyvolaly v poslední době významný zájem jako automatizovaný mechanismus pro nákup a prodej balíčků zboží. Prokázaly, že jsou velmi užitečné v řadě aplikací e-obchodu. Jsou prezentovány důležité otázky navrhování kombinatorických aukcí. Okružní a rozvozní problémy (J. Fábry) V posledních letech byl zaznamenán obrovský pokrok v oblasti komunikace a informačních technologií. Jedná se především o stále širší používání internetových služeb, rozvoj sítí mobilních operátorů, využití satelitních systémů apod. Současně s tím vznikají vyšší nároky na pružnější reakci firem zajišťujících logistické služby svozu a rozvozu zboží, materiálu či lidí, firem poskytujících kurýrní či opravárenské služby aj. Úspěšnost a atraktivita firmy pro její zákazníky se v dnešní době odvíjejí nejen od ceny či kvality nabízených služeb, ale především od schopnosti flexibilně reagovat na zákazníkovy požadavky. Jedním ze základních distribučních problémů je tzv. okružní dopravní problém, známý spíše jako úloha obchodního cestujícího. Cílem je navštívit předem danou množinu zákazníků, vrátit se do výchozího místa a ujet přitom minimální vzdálenost. V této úloze není zapotřebí uvažovat kapacitu obsluhujícího vozidla, neboť požadavky všech zákazníků mají nulovou či zanedbatelnou velikost. V praktických úlohách jsou u zákazníků velice často zadány časové intervaly, tzv. časová okna, během nichž je nutné zákazníky navštívit. V takovém případě není reálné všechny zákazníky obsloužit během dne jedním vozidlem, ale je nutné využít několik vozidel, která mohou vyjíždět ze stejného místa či z několika nezávislých míst. Více vozidel je nutné využít také v situacích, v nichž mají zákazníci nenulové požadavky a vozidla mají omezenou kapacitu ať již z hlediska nosnosti či objemu. Jedná se o tzv. rozvozní úlohy. Cílem je uspokojit požadavky zákazníků (přivézt zákazníkovi či od něj odvézt určité množství produktu) a minimalizovat celkovou délku všech tras, které vozidla absolvují. I v tomto případě mohou někteří či všichni zákazníci definovat svá časová okna. Speciálním rozvozním problémem je úloha kurýrní služby, v níž jsou zadána místa, ve kterých je zapotřebí vyzvednout zásilku, a místa, kam je zásilku nutné doručit. Distribuční úlohy, které jsou řešeny použitím standardních modelů a metod operačního výzkumu, používají tzv. statický přístup. Informace o všech zákaznících a jejich požadavcích jsou známy předem, tj. před tím, než je úloha předána analytikům k nalezení optimálního řešení. Může se jednat o deterministické či stochastické informace. V reálných situacích však firma musí reagovat i na požadavky, které přicházejí až po nalezení optimálního řešení, v případě okružních a rozvozních úloh optimálních tras. Předmětem tzv. dynamického přístupu se stává rozhodnutí o tom, kdy a kdo (v případě použití více vozidel) nově vzniklý požadavek obslouží. Vzhledem k tomu, že většina podobných úloh patří do celočíselného, resp. bivalentního programování, naráží analytik na problém s výpočetním časem, který má k dispozici pro nalezení optimálního řešení. S rostoucím počtem zákazníků a omezení, která je v problému nutné respektovat, narůstá výpočetní čas neúměrně praktickým požadavkům na rychlou reakci firmy. Proto se v úlohách tohoto typu často používají heuristické a metaheuristické postupy poskytující řešení, které je z hlediska zadaného kritéria velice blízké optimálnímu řešení, a mající tu výhodu, že takové řešení poskytují v podstatě okamžitě, resp. s přípustným zpožděním po vzniku nového požadavku. Modely hodnocení efektivnosti (J. Jablonský) První modely analýzy obalu dat byly formulovány v roce 1978 Charnesem, Cooperem a Rhodesem a dodnes jsou postupně rozvíjeny jako nástroj pro hodnocení efektivnosti a výkonnosti souboru homogenních produkčních jednotek. Tyto modely hodnotí relativní efektivnost souboru jednotek, tj. snaží se konstruovat odhad efektivní hranice na základě informací, které jsou k dispozici v daném datovém souboru. Základní modely analýzy obalu dat rozdělují hodnocené jednotky na efektivní, tj. ty, které leží na efektivní hranici, konstruované daným modelem, a na neefektivní jednotky, které jsou charakterizovány vzdáleností od efektivní hranice. Jedním z problémů, které modely analýzy obalu dat řeší, je tedy uspořádání hodnocených jednotek. V kapitole o modelech analýzy dat se zaměříme samozřejmě i na základní typy modelů, podrobněji se ovšem budeme věnovat modelům, které jsou jejich rozšířením. Jedná se často o modely, které nejsou dosud v české literatuře publikovány. Ve všech případech jsou modely analýzy obalu dat založeny na řešení posloupnosti úloh lineárního programování, které budou postupně formulovány. Budou analyzovány vlastnosti základních DEA modelů s ohledem na transformaci datového souboru (např. invariantnost k posunutí a další změny). Podrobněji se budeme věnovat modelům super efektivnosti, které slouží pro uspořádání hodnocených jednotek, tedy i těch efektivních. Z této kategorie budou formulovány standardní modely, jako je Andersenův a Petersenův model a Toneův model, ale i méně známé modely jako je koncept pesimistické efektivnosti, křížové efektivnosti a model, vycházející z teorie cílového programování. Z dalších modelů se budeme věnovat modelům s intervalovými nebo náhodnými vstupy a výstupy. I v těchto modelech se budeme zabývat možnostmi uspořádání hodnocených jednotek. Kromě formulace jednotlivých modelů analýzy obalu dat bude pozornost věnována popisu základních oblastí aplikací těchto modelů a programovým systémům, které jsou k dispozici pro řešení těchto tříd úloh. Optimalizace ekonomických vztahů (V. Pánková) Tato stať se bude věnovat využití optimalizačních úloh pro formulování klasických ekonomických vztahů s přihlédnutím k možnostem aplikace ekonometrických technik. Jako nezbytný aparát budou pro čtenářské pohodlí nejprve uvedeny věty zavádějící Lagrangeovy multiplikátory, jejich souvislosti s primární a duální úlohou a jejich ekonomická interpretace jako stínových cen. Jako speciální případ bude prezentováno Tobinovo Q, které je poměrem stínové ceny kapitálu v úloze pro optimalizaci investic a tržní hodnoty tohoto kapitálu. Tobinovo Q není v praxi měřitelné a jeho výpočet pomocí ekonometrického přístupu patří do literatury nedávného data. Dále bude ukázáno, že produkční a nákladové funkce mohou tvořit duálně sdružené optimalizační úlohy a lze z nich odvodit poptávkové funkce. Ve všech těchto typech funkcí figurují stejné parametry, avšak různé ekonomické proměnné. Pro ekonometrické odhady těchto parametrů se tak nabízí možnost pracovat s těmi veličinami, které jsou aktuálně k dispozici. Zatímco tyto vztahy patří již ke klasickým, využití mikroekonomických základů pro budování makroekonomických modelů je téma aktuální a dosud nevyčerpané. Bude prezentován model reálného ekonomického cyklu, vycházející z předpokladu maximalizace užitku domácnostmi a maximalizace zisku firmami. Budou také formulovány podmínky rovnováhy tohoto procesu.
Asymptotický celočíselný algoritmus (J. Kalčevová) Řada ekonomických problémů vede v konečném důsledku k úlohám lineárního programování (LP). Řešení takových úloh není algoritmicky složité vzhledem k faktu, že je známá univerzální metoda pro řešení úloh lineárního programování – simplexová metoda. Velká část úloh lineárního programování považuje za optimální řešení takový výsledek, který kromě všech omezení dosahuje nejlepší hodnoty účelové funkce, navíc však má všechny nebo alespoň některé předem známé hodnoty proměnných celočíselné. V takovém případě mluvíme o rozšíření úloh LP o podmínky celočíselnosti na proměnné, a příslušnou úlohu nazýváme úlohou celočíselného lineárního programování (ILP). V ekonomické oblasti existuje mnoho typických úloh ILP, které jsou obecně NP-obtížné, což v důsledku způsobuje, že není znám algoritmus pro nalezení optimálního řešení v polynomiálním čase. Pro hledání celočíselného řešení úlohy LP existují univerzální algoritmy, které ovšem hledají řešení významně pomaleji, než klasická simplexová metoda. Jsou vyvíjeny a zkoumány rychlé algoritmy pro řešení úloh nějakého speciálního tvaru, což je na úkor obecnosti řešené úlohy. Pátá kapitola knihy popisuje algoritmus pro hledání optimálního řešení úlohy celočíselného lineárního programování za předpokladu, že vlastní omezení dodržují podmínku dostatečně velkých pravých stran. Tato podmínka je v textu přesně formulována a je podmínkou postačující. Lze tedy před samotným použitím metody určit, zda nalezené řešení bude zaručeně optimální a zda má tedy smysl úlohu tímto algoritmem řešit. Uvedená podmínka však není podmínkou nutnou, a tak lze popsaným asymptotickým algoritmem řešit s jistou mírou rizika i úlohy, které uvedenou podmínku nesplňují. I při nesplnění této podmínky může uvedený algoritmus poskytnout optimální řešení. V opačném případě však lze tento algoritmus považovat za heuristiku, která rychle najde „relativně dobré“ řešení. Metoda vychází z předpokladu celočíselnosti na všechny koeficienty úlohy, tzn. cenové, strukturní i hodnoty pravých stran. Tento předpoklad lze pro racionální úlohy splnit bez újmy na obecnosti. Celočíselnost koeficientů pak zajistí, že v libovolném celočíselném (a tedy i v optimálním celočíselném) řešení budou hodnoty přídatných proměnných celá čísla. Podobně jako metoda větví a mezí či Gomoryho algoritmus (nástin obou algoritmů je také součástí textu šesté kapitoly) vychází z nalezení optimálního řešení úlohy LP bez podmínek celočíselnosti. Základní myšlenkou tohoto algoritmu je skutečnost, že optimální řešení úlohy ILP je na hranici konvexního polyedru, který tvoří obal všech přípustných celočíselných řešení. Vrcholy tohoto konvexního polyedru jsou pak nutně celočíselná řešení a vrchol, který je v jistém smyslu „nejblíže“ neceločíselnému optimu, je optimálním řešením úlohy ILP. Další postup asymptotického celočíselného algoritmu je tedy založen na myšlence, že hodnoty nezákladních proměnných (které jsou pro neceločíselné optimální řešení nulové) v optimálním celočíselném řešení mohou nabývat i hodnot kladných, ale (vzhledem ke vzdálenosti od neceločíselného optima) pokud možno co nejmenších. Podobně jako u všech řezných metod dojde tedy při praktické aplikaci algoritmu k oříznutí množiny přípustných řešení neceločíselné úlohy tak, aby nebylo odříznuto (a tedy ztraceno) žádné celočíselné řešení. Dodatečným omezením tak dojde k rychlému oříznutí až na hranici konvexního obalu. Uvedená kapitola pak popisuje nejen konstrukci tohoto řezu, ale také následný postup výpočtu až k nalezení optimálního řešení úlohy ILP. Celá kapitola je doplněna o názorné obrázky a modelový příklad pro snadnější pochopení algoritmu i problémů, souvisejících s jeho aplikací. Lenstrův algoritmus (M. Černý) Šestá kapitola je přirozeným pokračováním kapitoly páté. Je především věnována popisu důležitého algoritmu pro řešení problému celočíselné lineární optimalizace (celočíselného programování), který je znám jako Lenstrova metoda. Tento algoritmus má pozoruhodnou teoretickou vlastnost: pracuje v polynomiálním čase, je-li dimenze problému pevná. (Obecně jsou úlohy celočíselné lineární optimalizace NP-těžké, pročež existenci polynomiálního algoritmu nelze očekávat.) Algoritmus se proslavil v teorii celočíselného programování právě díky uvedené vlastnosti; teprve později se začala zkoumat jeho praktická použitelnost. V řadě prací, které budeme citovat, se také užívá při konstrukci heuristik a aproximačních algoritmů. Úvod šesté kapitoly (část 6.1) je věnován zavedení základního značení a formulaci problému celočíselného programování v rozhodovací verzi, v konstruktivní rozhodovací verzi a v optimalizační verzi. Připomeneme zde také základní odhady na velikost zápisu celočíselných bodů v racionálních polyedrech, které jsou nezbytné k formulaci algoritmu a k vyslovení výsledků o jeho výpočetním čase. Vlastní popis Lenstrova algoritmu je podán v částech 6.2 a 6.5. Přitom se užívají tři důležité stavební kameny, kterým jsou věnovány části 6.3, 6.4 a 6.6. Prvním stavebním kamenem je Eukleidův algoritmus a teorie unimodulárních matic (část 6.3), druhým stavebním kamenem je algoritmus známý pod názvem metoda redukce báze (Basis Reduction Method, též LLLalgoritmus či Lenstrův-Lenstrův-Lovászův algoritmus, viz část 6.4) a třetím stavebním kamenem je Goffinova metoda k aproximaci polyedrů pomocí elips (jde o metodu, která k danému omezenému polyedru přibližně najde jeho Löwnerovu- Johnovu elipsu, viz část 6.6). U každého ze studovaných algoritmů podáme argument, že počítá správně, a rovněž prostudujeme odhady na počet iterací.
Simulační metody (M. Dlouhý) Základní myšlenka simulace je vlastně prostá: když nejde problém řešit analyticky, tak napodobíme daný systém pomocí počítačového modelu a poté pozorujeme, co se děje. Můžeme rozlišit čtyři modelové přístupy, které vycházejí z myšlenky simulace: simulaci Monte Carlo, simulaci diskrétních událostí, systémovou dynamiku a multiagentní systémy. Simulací Monte Carlo rozumíme numerické řešení pravděpodobnostních i deterministických úloh pomocí statistického experimentu. Při této metodě je pro experimentování sestrojena pravděpodobnostní úloha, která má shodné řešení s původní úlohou. Řešení takto získané má pravděpodobnostní charakter, jde o statistický odhad, jehož přesnost roste s počtem pokusů. V této metodě obvykle nejsou zahrnuty dynamické interakce. Simulace diskrétních událostí modeluje systémy jako provázanou síť dynamických a statických objektů. Simulovaný čas je sice spojitý, ale změny stavu systému se vyskytují pouze v určitých diskrétních časových okamžicích. Dynamické objekty v simulovaném systému jsou zachyceny jako individuální entity, které mají své charakteristiky (vlastnosti) ovlivňující průchod entity systémem. Cílem je optimalizace studovaného systému za pomocí velmi detailního počítačového modelu. Oproti tomu systémová dynamika zobrazuje systém jako provázanou řadu úrovňových a tokových veličin, jejichž změny mají spojitý charakter. Model se nezabývá detailem, ale klíčovými zpětnými vazbami a jejich vlivem na celkový vývoj systému (např. neomezený růst, pokles, cyklický vývoj). Multiagentní systémy představují počítačové modely pro simulaci interakcí mezi velkými počty autonomních agentů, kteří se chovají podle předem definovaných pravidel. Cílem modelu je hodnocení toho, jak individuální rozhodování velkého počtu agentů ovlivňuje chování systému jako celku. Multiagentní systémy obvykle nenajdeme v tradičních učebnicích simulačního modelování či operačního výzkumu. V tomto textu se budeme zabývat využitím simulace pro analýzu podnikových procesů. Využití je poměrně široké a různorodé, neboť komplikované podnikové systémy, které mají pravděpodobnostní a dynamické chování, jsou spíše pravidlem než výjimkou. Praxe ukázala, že pro modelování podnikových procesů se jako nejvhodnější jeví simulace diskrétních událostí. Simulace diskrétních událostí (diskrétní simulace) je moderním nástrojem pro analýzu komplexních výrobních, zásobovacích, obslužných, komunikačních a dalších podnikových procesů. Simulace je metodou, která pomocí počítačového modelu podnikového procesu umožňuje manažerům předvídat chování systému při změně vnitřních či vnějších podmínek, optimalizovat podnikové procesy vzhledem k zadaným kritériím (zisk, spolehlivost, rychlost dodání), porovnat mezi sebou navrhované alternativy organizace studovaného procesu. Značnou výhodou simulace je fakt, že vše se děje jen v počítačovém modelu, bez nutného zásahu do provozu podniku. Pomocí simulace je možné prozkoumat různé alternativy změn v systému, ověřit dopady a důsledky těchto změn a vybrat takové řešení, které je pro danou situaci nejvhodnější. Simulace jako vědecká i aplikační disciplína úzce souvisí s rozvojem výpočetní techniky, bez níž by nebylo možné rozsáhlé výpočty realizovat. Postupně byly vyvinuty specializované simulační jazyky a produkty, které zjednodušují tvorbu simulačních modelů, provádění simulačních experimentů a analýzu výsledků. Nové počítačové aplikace otevírají pro simulaci nové modelovací možnosti. Formát B5, pevná laminovaná vazba, 240 stran, 288 Kč ISBN 978-80-7431-036-2 |