Skripta

VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ
FAKULTA STAVEBNÍ
JIŘÍ NOVOTNÝ
ZÁKLADY
OPERAČNÍHO VÝZKUMU
STUDIJNÍ OPORY PRO STUDIJNÍ PROGRAMY
S KOMBINOVANOU FORMOU STUDIA
Typeset by LATEX2ε
c© Jiří Novotný, Brno 2006
Obsah
ÚVOD 3
Cíle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Požadované znalosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Doba potřebná ke studiu . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Klíčová slova . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1 MODELY V OPERAČNÍM VÝZKUMU 7
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 TEORIE GRAFŮ 11
2.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Některé grafové problémy . . . . . . . . . . . . . . . . . . . . . . 28
2.2.1 Problém čínského listonoše . . . . . . . . . . . . . . . . . . 28
2.2.2 Problém obchodního cestujícího . . . . . . . . . . . . . . . 28
2.2.3 Problém minimální kostry grafu . . . . . . . . . . . . . . 30
2.2.4 Problém nalezení optimálních cest v grafu . . . . . . . . . 31
2.2.5 Problém optimální lokace . . . . . . . . . . . . . . . . . . 32
2.2.6 Problém batohu . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2.7 Problém maximálního toku v síti . . . . . . . . . . . . . . 33
2.2.8 Problém čtyř barev . . . . . . . . . . . . . . . . . . . . . . 35
2.3 Optimalizační grafové algoritmy . . . . . . . . . . . . . . . . . . . 36
2.3.1 Procházení bludištěm . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Konstrukce grafu jedním tahem . . . . . . . . . . . . . . . 38
2.3.3 Hledání minimální kostry . . . . . . . . . . . . . . . . . . . 38
2.3.4 Hledání nejkratší cesty . . . . . . . . . . . . . . . . . . . . 41
2.3.5 Hledání nejdelší cesty . . . . . . . . . . . . . . . . . . . . . 45
2.3.6 Hledání nejširší cesty . . . . . . . . . . . . . . . . . . . . . 48
2.3.7 Hledání nejužší cesty . . . . . . . . . . . . . . . . . . . . . 49
2.3.8 Hledání nejspolehlivější cesty . . . . . . . . . . . . . . . . 50
2.3.9 Hledání nejporuchovější cesty . . . . . . . . . . . . . . . . 50
2.3.10 Hledání maximálního toku v síti . . . . . . . . . . . . . . . 51
2.3.11 Hledání nejkratší okružní cesty . . . . . . . . . . . . . . . 54
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3 ŘÍZENÍ PROJEKTŮ 79
3.1 Konstrukce síťového grafu projektu . . . . . . . . . . . . . . . . . 79
3.2 Metoda CPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
1
3.3 Analýza zdrojů . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.4 Metoda PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4 LINEÁRNÍ PROGRAMOVÁNÍ 117
4.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.2 Typy úloh lineárního programování . . . . . . . . . . . . . . . . . 126
4.3 Simplexová metoda . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.4 Speciální úlohy lineárního programování . . . . . . . . . . . . . . 137
4.4.1 Dopravní problém . . . . . . . . . . . . . . . . . . . . . . . 137
4.4.2 Kontejnerový dopravní problém . . . . . . . . . . . . . . . 142
4.4.3 Obecný distribuční problém . . . . . . . . . . . . . . . . . 143
4.5 Celočíselné programování . . . . . . . . . . . . . . . . . . . . . . . 145
4.5.1 Přiřazovací problém . . . . . . . . . . . . . . . . . . . . . . 147
4.5.2 Úloha o pokrytí . . . . . . . . . . . . . . . . . . . . . . . . 150
4.5.3 Okružní dopravní problém . . . . . . . . . . . . . . . . . . 151
4.5.4 Problém batohu . . . . . . . . . . . . . . . . . . . . . . . . 153
4.6 Optimalizace v MS Excel . . . . . . . . . . . . . . . . . . . . . . . 155
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
5 TEORIE HROMADNÉ OBSLUHY 183
5.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
5.2 Exponenciální modely hromadné obsluhy . . . . . . . . . . . . . . 187
5.2.1 Systém s čekáním a neohraničeným zdrojem požadavků . . 187
5.2.2 Optimalizace v modelech hromadné obsluhy . . . . . . . . 190
5.2.3 Systém bez čekání se ztrátami . . . . . . . . . . . . . . . . 191
5.2.4 Systém s čekáním a ohraničeným zdrojem požadavků . . . 193
5.3 Simulační analýza systémů hromadné obsluhy . . . . . . . . . . . 196
Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
ZÁVĚR 205
Shrnutí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
Autotest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
Zadání individuálních příkladů do cvičení . . . . . . . . . . . . . . . . . 220
Studijní prameny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
Seznam obrázků . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
2
ÚVOD
Prostředky matematického modelování nacházejí stále častější uplatnění v celé
řadě oblastí hospodářské sféry. Velmi časté jsou aplikace v podnikovém manage-
mentu, marketingu, finančním řízení a v logistických studiích. Vzhledem k mož-
nému použití prostředků matematického modelování a k jejich významu by měl
každý student ekonomického směru získat o těchto prostředcích aspoň základní
přehled.
Podívejme se trochu na situaci, před kterou je postaven kdokoli, kdo chce
vnést matematický řád do složitých dějů v ekonomii. Připomeňme hned, že nejde
jen o pasivní formulaci problémů a o vystižení vzájemných vztahů faktorů, které
průběh děje ovlivňují, ale o nalezení optimálního řešení problému za daných pod-
mínek, tedy o aktivní zásah do dění. To druhé ovšem předpokládá umět se také
vypořádat s tím prvním. Oč zde konkrétně jde, to se dá vyložit na spoustě pří-
kladů, z nichž však žádný nepostihne celou šířku problematiky; ale to už je úděl
příkladů. Uveďme jeden za všechny.
Výrobní program podniku, to je záležitost mnoha faktorů, které jeho volbu
omezují. Ta omezení však nikdy nejdou tak daleko, aby neponechala dost místa
na množství variant, ze kterých je možno (a nutno) vybírat. Jde pak o to, vy-
brat mezi existujícími možnostmi tu, která zaručuje plnění daného cíle: dosažení
maximálního zisku nebo minimálních výrobních nákladů, největší úsporu surovin
a energie apod. Toto kriterium však problém neřeší, teprve jej staví. Optimální
řešení je pak výsledkem složitých myšlenkových konstrukcí, které jsou svou po-
vahou matematice vlastní a které současná matematika také nejednou úspěšně
zvládla.
Jak již o tom byla zmínka, pro problémy spojené s hospodářským rozhodová-
ním je charakteristická především ta okolnost, že je nutno vybírat z nepřehledného
množství variant, a při jistých zjednodušeních, která si vynucuje matematické
zpracování problému, jich bývá prokazatelně nekonečně mnoho, takže není prak-
ticky (ani teoreticky) možné vyhodnotit každou z nich zvlášť a vybrat z nich
optimální. Je-li ekonom postaven před takovou úlohu, má k dispozici pouze dvě
možnosti: spolehnout se na zkušenost nebo užít exaktních matematických metod.
Je evidentní, že čím jde o otázku složitější, závisející na velkém počtu parametrů
(což zpravidla znamená významnější), tím nespolehlivější je první metoda.
Operační výzkum (operations research = výzkum operací) se zabývá analýzou
a koordinací provádění operací v rámci nějakého systému. První práce zabývající
se úlohami, metodami a modely, které bychom dnes zařadili do operačního vý-
zkumu, vyšly v roce 1909. Pocházely od dánského matematika Agnera K. Erlanga
a byly zaměřeny na teorii hromadné obsluhy. Na ně navazovaly ve dvacátých le-
3
Operační výzkum
tech 20. století práce různých autorů, kteří aplikovali matematiku na oblast řízení
zásob. Ve třicátých letech 20. století se začíná rozvíjet matematické programo-
vání jako ucelený soubor optimalizačních metod zaměřený na hledání vázaných
extrémůfunkcívíceproměnných(JohnvonNeumann(USA)1937,LeonidV.Kan-
torovič (SSSR) 1939). Metody z těchto prací došly k uplatnění ve vojenském vý-
zkumu britské armády, který prováděla před a během druhé světové války skupina
vědců a technologů zabývajících se rozvojem radaru. Tato skupina poprvé v roce
1940 použila pro svou činnost název operační výzkum. První výsledky operačního
výzkumu byly tehdy uplatněny při plánování protivzdušné obrany Anglie, při vý-
počtech optimálního rozdělení ponorkového loďstva k ochraně lodních konvojů
a optimálního sledu prací při kladení min. Souběžně s tím se rozvíjel operační
výzkum rovněž v USA, po druhé světové válce i v SSSR. Z univerzit a vědec-
kých pracovišť těchto států se šířil do dalších zemí. V poválečném rozvoji byl
používán především uhelnými, ocelářskými, plynárenskými, elektroenergetickými
a dopravními společnostmi.
V současné době se operačního výzkumu využívá například i v řízení státní
správy, řešení vztahu mezi ekonomickým růstem a kvalitou životního prostředí
apod. Dostupnost metod operačního výzkumu roste v posledním období s inten-
zivním používáním osobních počítačů. Vytvářejí se ucelené systémy na podporu
rozhodování. Ty se v průmyslových podnicích aplikují při plánování strategickém
i operativním, ve všech fázích projektového řízení, při řízení výrobních procesů,
v prognózování i při navrhování organizačních struktur a informačních systémů.
Operační výzkum modeluje matematickými prostředky úlohy vznikající při řízení
systémů. Používá k tomu systémového přístupu a komplexního týmu specialistů.
Nejčastější složení takového týmu bývá: vedoucí týmu, operační analytik, mate-
matik nebo statistik, ekonom, programátor, ekolog, právník, zástupce uživatele,
psycholog nebo sociolog. Každá z uvedených profesí bývá zastoupena potřebným
počtem pracovníků. Výsledky analýzy operací, tj. výsledky činnosti týmu, slouží
jako podklad pro rozhodování.
Úkolem tohoto modulu je seznámit čtenáře se základními pojmy a metodami
vybraných disciplín operačního výzkumu. V první kapitole se charakterizuje pod-
stata operačního výzkumu, popisují se fáze při aplikaci operačního výzkumu a kla-
sifikují disciplíny operačního výzkumu. Druhá kapitola je věnována základům teo-
rie grafů a sítí. Je zde zavedena terminologie, formulují se v praxi nejfrekventova-
nější úlohy a předvádí jejich řešení. Řízení projektů a kalendářní plánování prací
je vyčleněno do třetí kapitoly. Čtvrtá kapitola pojednává o lineárním programo-
vání. Rozebírají se obecné, speciální a celočíselné úlohy. Teorii front a hromadné
obsluze je věnována kapitola pátá.
Za každou kapitolou je pro potřeby samostatné práce student˚u připojen sou-
bor otázek a cvičení. Za poslední kapitolou je autotest, na kterém si poslu-
chači kombinovaného studia mohou ověřit zvládnutí problematiky celého modulu.
Ve studijních pramenech jsou v seznamu použité literatury uvedeny nejprve zá-
kladní učebnice, a pak skripta, v seznamu doplňkové studijní literatury sbírky
aplikovaných příkladů a v odkazech na další studijní zdroje a prameny jsou inter-
netové adresy stránek souvisejících s tématem modulu. Pro snadnější orientaci je
na konci zařazen rejstřík pojmů a seznam obrázků.
4
Úvod
Cíle
• Umět vysvětlit význam modelů v operačním výzkumu.
• Znát pojem grafu a některé jejich speciální třídy.
• Umět formulovat vybrané grafové problémy.
• Znát základní optimalizační grafové algoritmy.
• Umět kalendářní plánování prací.
• Znát typy úloh lineárního programování.
• Umět objasnit otázku existence a jednoznačnosti řešení úloh lineárního pro-
gramování.
• Znát význam a interpretaci proměnných v úlohách lineárního programování.
• Umět formulovat dopravní a přiřazovací problém.
• Znát základní metody řešení celočíselného lineárního programování.
• Umět charakterizovat systémy hromadné obsluhy.
• Umět vysvětlit rozdíl mezi analytickým a simulačním řešením systému hro-
madné obsluhy.
• Umět popsat možnosti optimalizace v systémech hromadné obsluhy.
Požadované znalosti
Operační výzkum je dalším modulem z řady studijních opor určených pro po-
sluchače 6. semestru kombinovaného studia na Stavební fakultě Vysokého učení
technického v Brně. Proto je v tomto díle použita co možná nejpřístupnější forma
výkladu, pro jehož pochopení stačí běžné znalosti středoškolské matematiky, zá-
klady vysokoškolské matematiky probírané v 1. ročníku studia a některé partie
z teorie pravděpodobnosti a matematické statistiky vyučované v 5. semestru. Dále
je potřebná píle a určitý stupeň logického myšlení, které je u studentů technického
zaměření samozřejmou nezbytností.
Doba potřebná ke studiu
Jakdlouhosebudete zabývat studiemtohotomodulu,záleží navašichmožnostech
a schopnostech. V prezenčním studiu je problematika modulu probírána v šestém
semestru oboru Management stavebnictví v rozsahu 2 hodiny přednášek a 2 ho-
diny cvičení týdně. Odtud vychází, že by mělo být dostatečné věnovat studiu 78
hodin samostatné práce završené samokontrolou nabytých vědomostí vyřešením
autotestu.
5
Operační výzkum
Klíčová slova
Operační výzkum, modely, teorie grafů, řízení projektů, lineární programování,
celočíselné programování, teorie front (hromadné obsluhy).
6
Kapitola 1
MODELY V OPERAČNÍM
VÝZKUMU
V úvodu bylo řečeno, že operační výzkum se zabývá zkoumáním operací v rámci
nějakéhosystému.Cílemjestanovittakovouúroveňprováděnítěchtooperacínebo
jejich vzájemný vztah, aby bylo zajištěno co nejlepší fungování tohoto systému.
Provádění operací závisí na zdrojích, na provádění jiných operací, na vnějších
činitelech ovlivňujících systém apod. Operační výzkum je tedy prostředek pro
nalezení optimálního řešení daného problému při respektování řady různorodých
omezení, které mají na chod systému vliv. Základním nástrojem operačního vý-
zkumu je matematické modelování, které umožňuje strukturalizaci systému,
specifikaci možných variant stavu systému (často neomezené množství), analýzu
chování systému ve zkráceném čase (reálné procesy trvají měsíce, roky, simulace
na počítači zlomky sekund). S modely lze snadno manipulovat a provádět experi-
menty změnou jejich parametrů při téměř zanedbatelných nákladech ve srovnání
s experimenty s reálným systémem.
Při aplikaci operačního výzkumu na řešení nějakého problému rozlišujeme
několik základních na sebe navazujících fází.
Fáze aplikace operačního výzkumu
1. Definice problému v reálném systému.
2. Jeho ekonomický model.
3. Jeho matematický model.
4. Řešení matematického modelu.
5. Interpretace a verifikace výsledků.
6. Implementace výsledků v reálném systému.
Ad 1. Rozpoznání problému v rámci reálného systému a jeho definice je prv-
ním podstatným krokem. Dále je třeba posoudit jakými prostředky je daný pro-
blém řešitelný a vytvořit tým příslušných odborníků, který se bude na řešení
podílet. Příklad: plánování výrobního programu.
7
Operační výzkum
Ad 2. Formulací ekonomického modelu daného problému se zjednodušuje po-
pis na pouze nejpodstatnější prvky a vazby mezi nimi. Je třeba vyjasnit cíl ana-
lýzy, popsat probíhající procesy a činitele ovlivňující jejich provádění a vzájemné
vztahy mezi procesy, činiteli a cílem anylýzy. Ekonomický model je slovním po-
případě numerickým popisem problému. Příklad: proces – výroba výrobku, činitel
– spotřeba suroviny, cíl – maximalizace zisku.
Ad3. Formulacímatematickéhomodeludanéhoproblémuseformalizujeslovní
popis zavedením funkcí, proměnných, jejich hodnot, rovnic, nerovnic, parametrů
apod. Příklad: procesy – proměnné, činitelé – lineární nerovnice, cíl – účelová
funkce.
Ad 4. Při řešení matematického modelu se používají metody a postupy vytvo-
řené v jednotlivých odvětvích operačního výzkumu. Většina z nich je zabezpečena
kvalitními programovými systémy. Příklad: disciplína – lineární programování,
simplexová metoda.
Ad 5. Interpretace získaných výsledků a jejich ověření včetně posouzení, zda
byl ekonomický a následně matematický model sestaven správně.
Ad 6. Úspěšná implementace výsledků v rámci analyzovaného reálného sys-
tému přispěje ke zlepšení jeho fungování s ohledem na sledovaný a v modelu
definovaný cíl.
Modely operačního výzkumu jsou velmi různorodé a zabývají se rozdílnými
oblastmi. Proto vyvstala potřeba specifických přístupů k řešení jednotlivých tříd
problémů a časem se ustavily relativně samostatné disciplíny (odvětví) operačního
výzkumu.
Matematicképrogramovánísezabývářešenímoptimalizačníchúloh,vekte-
rých se hledá extrém daného kriteria na množině variant určených soustavou
omezujících podmínek. My se budeme v tomto textu zabývat jeho nejpoužívanější
částí tzv. lineárním programováním, které řeší úlohy popsané lineárními funkcemi.
Nelineární programování řeší úlohy popsané nelineárními funkcemi. Optimalizací
úloh, v nichž se vyskytují náhodné veličiny, řeší stochastické programování. Dy-
namické programování se zabývá optimalizací vícestupňových časově návazných
procesů.
Strukturní analýza zkoumá kvantitativní vztahy mezi výrobou a spotřebou
a vztahy mezi jednotlivými odvětvími s cílem zabezpečení jejich proporcionálního
rozvoje. Nehledá optimální řešení, nýbrž bilancuje meziodvětvové vztahy.
Kromě lineárního programování je dále v textu probírána teorie grafů. Ta
zkoumá objekty tvořené body a jejich spojnicemi. Část grafickoanalytických me-
tod řeší topologické problémy v grafech, jejich nejčastější použití je v oblasti
analýzy a řízení projektů a v logistice.
Konečně obsah textu tvoří teorie front (hromadné obsluhy), která umož-
ňuje modelovat systémy, v nichž vznikají požadavky na obsluhu. Cílem je nalézt
takový způsob obsluhy, při kterém jsou jak časové ztráty vzniklé čekáním na ob-
sluhu, tak i ztráty vzniklé prostoji obslužných zařízení minimální.
Mezi další (v textu neprobírané) disciplíny patří teorie her, která se zabývá
řešením konfliktních situací, ve kterých vystupují proti sobě dva nebo více účast-
níků (hráčů). Cílem řešení je nalézt pro účastníky hry optimální strategie, tj.
pravidla jednání a rozhodování v průběhu hry, zaručující nejvýhodnější výsledek.
Teorie zásob tvoří modely řízení zásob, tj. hledá optimální velikost a optimální
8
1. modely
rozložení zásob, a to jak z místního, tak časového hlediska. Teorie obnovy řeší
otázky reprodukce objektů, zařízení a jejich částí, které se amortizují. Cílem je
stanovit optimální způsob jejich oprav, obměn a doplňování, aby činnost systému
nebyla narušena. Vícekriteriální rozhodování se zabývá analýzou rozhodovacích
úloh, v nichž jsou varianty posuzovány podle několika často navzájem protichůd-
ných hodnotících kriterií zároveň. Simulace je napodobování reálných dějů vý-
početním procesem na počítači. Dříve byla simulace považována za východisko
z nouze všude tam, kde nebylo možné nalézt ucelené analytické řešení. Dnes,
zvláště s ohledem na růst operační rychlosti počítačů, se stává velmi efektivní
a pro některé skupiny úloh téměř výlučnou metodou řešení.
Operační výzkum se dá také charakterizovat jako souhrn disciplín zabývajících
se řešením různých tříd rozhodovacích problémů.
CVIČENÍ 1 − Modely
Kontrolní otázky
1. Charakterizujte operační výzkum.
2. Popište fáze při aplikaci operačního výzkumu.
3. Vyjmenujte a charakterizujte disciplíny operačního výzkumu.
4. Objasněte úlohu modelů v operačním výzkumu.
5. Jaká je role počítačů při řešení úloh operačního výzkumu?
9
Operační výzkum
10
Kapitola 2
TEORIE GRAFŮ
2.1 Základní pojmy
Celá řada důležitých skupin optimalizačních a rozhodovacích problémů může být
analyzována pomocí grafické reprezentace dané úlohy. Prameny, z nichž teorie
grafů čerpala, nacházíme už v dávnější minulosti. Obvykle se její počátky spojují
s úlohou o sedmi mostech města Královce známého matematika Leonharda Eu-
lera, který žil v 18. století. 19. století nahroma