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č

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

 

 

 

 

 

      LÉKAŘSKÁ                       EKONOMICKÁ

          OSTATNÍ                           EKONOMICKÁ 2

          OSTATNÍ 2                        EKONOMICKÁ 3

DOMŮ