Otazky_k_casti_II_p2007

ci hran), pomocí níž je možno
tok zvýšit. Přitom se jistým způsobem označují uzly grafu. Ve druhé fázi se na nalezené cestě
provádějí změny toku (na hranách orientovaných směrem ke spotřebiči se tok zvyšuje a na opačně
orientovaných hranách se snižuje). Pokud v prvé fázi nelze požadovanou cestu najít, algoritmus
končí, přičemž množina označených uzlů a množina neoznačených uzlů určují minimální řez.
24. Vysvětlete pojmy cesta a vzdálenost v orientovaném hranově ohodnoceném grafu. Ilustrujte na
příkladě. Charakterizujte možné způsoby nalezení nejkratší cesty (stačí slovně).
Cesta je sled, ve kterém se neopakuje žádný uzel.
Orientovaná cesta je cesta, v níž všechny hrany mají shodnou orientaci.
Jedná se o úlohu lineárního bivalentního (nula-jedničkového) programování. Jestliže nahradíme
podmínky xij ∈ {0, 1} podmínkami nezápornosti a prvou rovnici vynásobíme (–1), dostáváme
následující úlohu normálního lineárního programování.

Složité rozhodovací úlohy
25. Charakterizujte úlohu dynamického programování a naznačte způsob jejího řešení. Uveďte
příklady aplikací.
Dynamické programování se zabývá optimalizací dynamických úloh, které je možno formulovat také
jako úlohy řízení procesů probíhajících v čase. Dynamické programování je však použitelné i pro
takové problémy, v nichž čas explicitně nevystupuje a může být do nich uměle zaveden.
Přístupy dynamického programování využívají aparát rekurentních funkcionálních vztahů a
opírají se přitom o tzv. princip optimality, jehož autorem je Richard Bellman. Aplikace těchto
přístupů vyžaduje zpravidla náročnější přípravu než aplikace metod matematického
programování, neboť neexistuje žádný dostatečně obecný algoritmus k řešení některé třídy
problémů dynamického programování. Tedy přístupy dynamického programování v sobě zahrnují
nejen vytvoření matematického modelu, ale také konstrukci výpočetní procedury k jeho řešení.
Získaný algoritmus přitom podstatně závisí na struktuře řešeného problému.
Příklady aplikací dynamického programování
• Plánování výroby a zásob. Je třeba pro každou etapu plánovacího období určit, jaké množství
výrobku vyrobit a jaké uskladnit pro budoucí použití, aby byla splněna poptávka po výrobku a
byly minimalizovány seřizovací, výrobní a skladovací náklady.
• Obnova zařízení. Zařízení postupně zastarává a zisk z jeho použití se postupně snižuje. Je třeba
určit, kdy je nevhodnější pořídit nové zařízení.
• Rozdělování zdrojů. Je dáno omezené množství nějakého ekonomického zdroje a několik
možných způsobů použití s různým přínosem. Je třeba dané množství rozdělit tak, aby byl
maximalizován celkový přínos.
26. Charakterizujte úlohu stochastického programování. Jaké jsou možnosti vytvoření
deterministického ekvivalentu této úlohy? Uveďte příklady aplikací.
Příklady aplikací stochastického programování
• Plánování výroby při neurčité poptávce. Je třeba pro každou etapu plánovacího období určit,
jaké množství výrobku vyrobit a jaké uskladnit pro budoucí použití, aby byly minimalizovány
náklady, přičemž poptávky po výrobku v jednotlivých obdobích jsou náhodné veličiny.
• Dopravní problém s neurčitou poptávkou. Je třeba určit takový plán přepravy, při němž budou
celkové náklady na přepravu minimální, přičemž dopravní náklady a kapacity dodavatelů jsou
konstantní, ale požadavky odběratelů jsou náhodné veličiny.
• Optimalizace portfolia. Je třeba stanovit skladbu portfolia cenných papírů tak, aby se
maximalizoval výnos portfolia, přičemž výnosy jednotlivých aktiv jsou náhodné veličiny.
Za řešení úlohy stochastického programování (8.15) se považuje řešení deterministického
ekvivalentu této úlohy, který je definován tak, aby byla z původní úlohy korektně odstraněna
náhodnost. Při konstrukci deterministického ekvivalentu je nutné stanovit, co budeme považovat
za přípustné řešení a co budeme považovat za optimální řešení.
Pokud musíme určit jednorázové řešení (rozhodnutí), které se po získání novějších informací
nemůže měnit, hovoříme o jednostupňových úlohách stochastického programování. Jestliže
řešení můžeme upravovat na základě postupně se objevujících nových informací, jde o
vícestupňové úlohy stochastického programování. Ve vícestupňových úlohách se proces
rozhodování může rozvíjet podle jednoho ze dvou následujících řetězců:
27. Charakterizujte úlohy vícekriteriálního rozhodování a uveďte příklady aplikací. Na příkladě
vysvětlete pojmy dominovaného a nedominovaného řešení.
Problém vícekriteriálního rozhodování lze charakterizovat takto: je dána nějaká množina možných
variant (rozhodnutí, řešení) a máme vybrat variantu, která je co možná nejlepší vzhledem k dané
množině kritérií (hledisek, charakteristik).
Typy kritérií
Kritéria uvažovaná ve vícekriteriálním rozhodování bývají obvykle konfliktní. Mohou se mezi nimi
vyskytnout jak kritéria kvantitativní (kardinální), tak kritéria kvalitativní (ordinální). V případě
současného výskytu kvalitativních i kvantitativních kritérií se provádí přechod k jednomu typu
kritérií, buď ke kvalitativním nebo ke kvantitativním.
Kvantitativní kritéria umožňují pro každou variantu stanovit hodnoty kritérií. Tato kritéria
bývají často nesouměřitelná v důsledku vyjádření v různých jednotkách. U některých metod pro
řešení vícekriteriálních úloh je třeba tuto nesouměřitelnost odstranit určitou normalizací (např.
přechodem k ukazatelům, které vyjadřují procenta plnění původních ukazatelů).
Kvalitativní kritéria dovolují pouze stanovit, zda je nějaká varianta podle určitého kritéria lepší či
horší než jiná, nebo zda jsou podle tohoto kritéria obě srovnávané varianty rovnocenné.
Příklady úloh vícekriteriálního rozhodování
• Výběr zařízení pro použití ve výrobě. Kritéria: cena, výkon, spolehlivost, provozní náklady.
• Výběr zakázek pro výrobu v daném období. Kritéria: velikost tržeb, procento pokrytí režie,
posílení pozice na trhu, udržení stavu zaměstnanců.
• Výběr projektu na výstavbu nějakého zařízení. Kritéria: investiční náklady, provozní náklady,
vliv na životní prostředí, možnost budoucího rozšíření.
• Hodnocení bonity bankovních klientů. Kritéria: finanční situace (zadluženost), vyrovnanost
potřeb a zdrojů, možnosti reprodukce firmy, efektivnost hospodaření firmy, ukazatele obratu.
Typy vícekriteriálních úloh:
Množina přípustných variant může být vymezena buď explicitně výčtem těchto variant, nebo
implicitně nějakou soustavou podmínek. Úlohy s explicitně vymezenými variantami nazýváme
úlohami vícekriteriálního hodnocení variant. Jsou-li přípustné varianty dány implicitně systémem
podmínek a všechna kritéria jsou kvantitativní, jedná se o úlohy vícekriteriálního programování
(úlohy vektorové optimalizace).
• Úlohy vícekriteriálního hodnocení variant (přípustné varianty jsou vymezeny explicitně).
• Úlohy vícekriteriálního programování (přípustné varianty jsou vymezeny implicitně soustavou
podmínek a všechna kritéria jsou kvantitativní).
Dominovaná a nedominovaná řešení
Je jasné, že jen velmi zřídka můžeme najít variantu, která by byla skutečně nejlepší z hlediska
každého zadaného kritéria, a že se tedy většinou musíme spokojit s nějakým kompromisem. Je
přirozené za kompromisní považovat takovou variantu, k níž neexistuje žádná varianta,která by
byla lepší alespoň v jednom kritériu a v žádném nebyla horší. Takto vymezená kompromisní varianta
se nazývá efektivní, nedominovaná nebo paretovsky optimální. Nedominovanost resp. paretovská
optimalita tedy znamená takový stav, kdy žádné kritérium nemůže být zlepšeno, aniž by došlo ke
zhoršení nějakého jiného kritéria.
28. Popište možnosti řešení úloh vícekriteriálního rozhodování.
Metody vícekriteriálního programování
Tyto metody jsou v podstatě založeny na jednorázovém nebo opakovaném použití metod
jednokriteriální optimalizace. Podle toho, zda a kdy jsou k dispozici nějaké doplňující informace o
rozhodovatelových preferencích, lze specifikovat následující případy:
• jsou k dispozici apriorní informace o preferencích rozhodovatele,
• doplňující informace o preferencích rozhodovatele jsou zadávány až v průběhu řešení úlohy
• žádné doplňující informace o preferencích rozhodovatele nejsou k dispozici
Jestliže jsou předem k dispozici informace o preferencích rozhodovatele, pak lze danou úlohu převést
na úlohu jednokriteriální optimalizace resp. na posloupnost takových úloh. Těmito informacemi
mohou být váhy kritérií, pořadí důležitosti kritérií nebo požadované (ideální) hodnoty kritérií. Podle
charakteru informací o preferencích rozhodovatele rozlišujeme tyto metody:
• metody agregace kritérií
• metody lexikografické optimalizace
• metody minimalizace vzdálenosti od ideálního vektoru
Jsou-li doplňující informace o preferencích rozhodovatele jsou zadávány až v průběhu řešení úlohy,
jedná o tzv. interaktivní metody, které spočívají na dialogu mezi rozhodovatelem a řešitelem (tím je
obvykle počítač), při nichž se střídají dvě fáze – fáze výpočetní a fáze rozhodovací. Výpočetní fáze je
prováděna řešitelem a jejím výstupem je jedno nebo více provizorních řešení úlohy a případně nějaké
další informace důležité pro rozhodovatele. Při výpočtu provizorního řešení se obvykle používá
princip agregace kritérií nebo princip minimalizace vzdálenosti od ideálního bodu. V rozhodovací
fázi rozhodovatel posoudí předložené provizorní řešení a jestliže je dosud nepokládá za vyhovující,
poskytne řešiteli informace o svých preferencích. Na jejich podkladě pak může řešitel stanovit nové
provizorní řešení, které bude rozhodovateli více vyhovovat. Interaktivní metody můžeme členit
následovně:
• Metody založené na informacích o mírách substituce. Míra substituce mezi i-tým a j-tým
kritériem udává, jaké zhoršení i-tého kritéria kompenzuje zlepšení j-tého kritéria o jednu
jednotku. Tyto metody jsou vhodné jen pro úlohy, v nichž se rozhodovací proměnné mění spojitě.
• Metody založené na informacích o úrovních kritérií. Rozhodovatel posuzuje úrovně jednotlivých
kritérií dosažené v provizorním řešení a zadává pro další krok nové mezní hodnoty kritérií. Tyto
metody lze použít i pro celočíselné úlohy.
• Postupy založené na výběru z množiny generovaných provizorních řešení. Řešitel předloží
rozhodovateli několik provizorních řešení, z nichž rozhodovatel vybere nejlepší variantu. Z této
informace pak řešitel vychází při generování dalších přípustných řešení.
Nejsou-li žádné doplňující informace o preferencích rozhodovatele k dispozici, jde o úlohu
nalezení množiny všech nedominovaných variant, což je úloha dosti náročná (tuto množinu
můžeme zkoumat např. metodami parametrického programování). Rozhodovatel nakonec ale
stejně musí vybrat jednu variantu, což je komplikováno tím, že množina všech nedominovaných
variant je obvykle dost rozsáhlá a nebo dokonce nekonečná. Navíc také může mít složitou
strukturu. Například i když všechny funkce v úloze (8.62) jsou lineární, tak množina všech
nedominovaných řešení může být nekonvexní (to ilustruje obr. 8.2, kde množina
nedominovaných řešení je tvořena lomenou čarou BCD).
29. Napište definici hry v normálním tvaru. Jaké znáte typy her? Uveďte příklady aplikací.
Teorie her se zabývá modelováním konfliktních rozhodovacích situací. Tyto situace můžeme členit
takto:
• antagonistické hry (co jedni hráči ztrácejí, ostatní získávají) a neantagonistické hry (mohou
existovat rozhodnutí výhodná pro všechny účastníky a jsou případně možné i kooperace mezi
hráči)
• hry s přenosnou výhrou (je možné přerozdělení výhry po ukončení hry) a hry s nepřenosnou
výhrou
• hry s úplnou informací (hráči mají před každým tahem přesnou informaci o dosavadním průběhu
hry) a hry s neúplnou informací
• konečné hry (všichni hráči mají konečně mnoho strategií) a nekonečné hry
• hry s inteligentními protihráči a hry s neinteligentními protihráči (neinteligentní protihráč
reprezentuje náhodný proces)
Příklady aplikací teorie her
• Soutěž firem o zakázky na n trzích. Předpokládá se, že získané zakázky se dělí v poměru
vynaložených prostředků na propagaci.
• Optimální úrovně výroby při oligopolu. Oligopolem se rozumí trh, na kterém se n výrobců
snaží prodat jeden druh výrobků případně výrobky vzájemně zastupitelné.
• Výběr způsobu kontroly jakosti výrobků. Protihráčem je náhodný proces, způsobující výskyt
zmetků.
30. Napište definici maticové hry. Jak ji můžeme řešit? Ilustrujte na příkladě.