Otazky_k_casti_II_p2007

ýze citlivosti. Optimální hodnoty duálních proměnných zde tedy představují
ocenění zdrojů z hlediska jejich omezenosti a proto se také nazývají stínovými cenami. Tyto
ceny mohou podnikovému managementu pomoci rozhodnout, zda zvýšit výrobu dodatečným
získáním omezených zdrojů. Jestliže stínová cena jednotky některého zdroje není vyšší než cena,
kterou by bylo nutno vynaložit na dodatečné získání jednotky tohoto zdroje, tak se nevyplatí
zásobu tohoto zdroje zvyšovat.
Nelineární programování
13. Napište definice konvexní funkce a konvexní množiny. Nakreslete příklady konvexních a
nekonvexních funkcí a množin.
Nechť funkce f(x) je definována na konvexní množině K. Řekneme, že f(x) je konvexní funkcí na
K právě tehdy, když pro každé dva body x1, x2 K a libovolné t (0;1) platí
Jestliže pro každé dva body x1, x2 K , x1 ≠ x2 platí ostrá nerovnost, řekneme, že funkce f(x) je na
množině K ryze konvexní. Geometricky vztah (5.5) znamená, že graf funkce leží pod sečnou spojující
body (x1; f(x1)) a (x2; f(x2)).
Konvexní množina
Podmnožinu K vektorového prostoru V nazveme konvexní množinou, jestliže s libovolnými dvěma
body x1 K, x2 K leží v této množině také všechny body
x =t x1 + (1– t) x2
kde 0 < t < 1. Geometricky to znamená, že množina K spolu s libovolnými dvěma různými body
musí obsahovat i úsečku spojující tyto dva body (viz obr. 2.3).
14. Zvolte si nějakou nelineární funkci více proměnných a určete její gradient. Jaké jsou vlastnosti
gradientu?
Gradient
Nechť funkce f(x) má v bodě x0 parciální derivace 1. řádu. Gradientem funkce f(x) v bodě x0
nazýváme vektor
Gradient má následující vlastnosti:
• Gradient f(x0) je kolmý na hladinovou nadplochu f(x) = f(x0) v bodě x0.
• Gradient f(x0) ukazuje směr, ve kterém funkce f(x) v okolí bodu x0 nejrychleji roste (směr
největšího růstu). Směr největšího spádu ukazuje obrácený gradient – f(x0).
• Nechť M = { x | gi (x) ≤ 0 } a nechť pro x0 M platí gi (x0) = 0. Pak gradient gi (x0) je kolmý k
nadploše gi (x0) = 0 a směřuje ven z množiny M.
• Nechť bod xmin M lokálního minima funkce f(x) na množině M je hraničním bodem množiny
M. Pak gradient f(xmin) směřuje dovnitř množiny M.
15. Zvolte si nějakou nelineární funkci více proměnných a určete Hessovu matici této funkce. K
čemu používáme Hessovu matici? Ilustrujte to na zvolené funkci.
Hessova matice
Nechť funkce f(x) má v bodě x0 parciální derivace 2. řádu. Hessovou maticí v bodě x0 nazýváme
matici
Jestliže funkce f(x) má spojité druhé parciální derivace, pak Hessova matice je symetrická.
Jak již bylo uvedeno v odstavci věnovaném konvexním funkcím, Hessova matice je pomůckou pro
ověřování konvexnosti funkcí. Nechť funkce f(x) je definována na konvexní množině M a má zde
spojité parciální derivace 2. řádu. Pak funkce f(x) je
• • konvexní na množině M, jestliže pro všechna x M je Hessova matice pozitivně
semidefinitní,
• • ryze konvexní na množině M, jestliže pro všechna x M je Hessova matice pozitivně
definitní (s případnou výjimkou množiny míry nula, kde je pozitivně semidefinitní).
16. Napište definici úlohy konvexního programování. Jaké má tato úloha vlastnosti?
Řekneme, že úloha
je úlohou konvexního programování právě tehdy, když M je konvexní množina a funkce f(x) je
konvexní na M. Příklady takových úloh ukazují obrázky 5.1 a 5.2. Následující tvrzení umožňuje
rozhodnout, zda je konvexní množina, která je dána nějakými omezujícími podmínkami.
Nechť
Pak množina M je konvexní, jestliže množina X je konvexní a všechny funkce gi(x) jsou konvexní na
X. Poznamenejme, že pokud by se mezi omezujícími podmínkami vyskytla rovnice, pak tato rovnice
musí být lineární.
Vlastnosti úlohy konvexního programování:
• každé lokálně optimální řešení je globálně optimálním řešením,
• je-li množina optimálních řešení neprázdná, je konvexní,
• je-li f(x) ryze konvexní, má úloha nejvýše jedno optimální řešení.
17. Jaké znáte typy metod jednorozměrné optimalizace? Jak mohou být využity ve vícerozměrné
optimalizaci?
• Metody bez použití derivace: Interval zužujeme na základě porovnání hodnot funkce ve dvou
vnitřních bodech x1, x2, x1 < x2 (metoda zlatého řezu, Fibonacciho metoda). Je-li ϕ(x1) < ϕ(x2),
pak interval redukujeme na interval . Je-li ϕ(x1) > ϕ(x2), je výsledkem redukce
interval .
• Metody s použitím derivací: V metodě půlení intervalu se interval redukuje na základě
znaménka 1. derivace ve středu s intervalu . Je-li ϕ´(s) > 0, je výsledkem redukce interval
. Je-li ϕ´(s) < 0, je to interval . Newtonova metoda využívá 2. derivaci pro hledání
kořene rovnice ϕ´(λ) = 0.
• Metody založené na aproximaci: V každém iteračním kroku se provádí kvadratická nebo
kubická interpolace funkce ϕ .
18. Charakterizujte obecný princip vícerozměrných metod hledání volných extrémů funkce více
proměnných. Jak se dá určit směr přechodu k dalšímu řešení?
19. Charakterizujte typy metod pro hledání vázaných extrémů funkce více proměnných.
Metody hledání vázaných extrémů
Metody pro hledání vázaných extrémů můžeme rozdělit do těchto skupin:
• Metody založené na transformaci úlohy hledání vázaného extrému na úlohu hledání volného
extrému:
• − penalizační a bariérové metody
• − metoda využívající Lagrangeovu funkci rozšířenou o kvadratický penalizační člen
• Linearizační metody:
• − metody spočívající v řešení posloupnosti úloh LP, aproximujících danou úlohu NLP
• − metody výběru směru založené na linearizaci
• Metody řešení speciálních úloh:
• − metody kvadratického programování
• − metody separovatelného programování
Celočíselné programování
20. Charakterizujte princip metody sečných nadrovin.
Metody sečných nadrovin
Pro metody sečných nadrovin (metody řezů) je charakteristická počáteční úprava dané celočíselné
úlohy, která spočívá ve „vnoření“ množiny přípustných řešení do nějaké souvislé nadmnožiny (jinými
slovy jde o dočasné zanedbání podmínek celočíselnosti). Na takto získanou spojitou úlohu se pak
aplikuje nějaká vhodná optimalizační metoda. Jestliže optimální řešení upravené úlohy vyhovuje
požadovaným podmínkám celočíselnosti, je vyřešena i původní úloha. V opačném případě se do
spojité úlohy doplní dodatečné lineární omezení, které má tyto vlastnosti:
• není splněno pro optimální neceločíselné řešení,
• je splněno pro libovolné přípustné řešení původního celočíselného problému.
Přidání tohoto omezení odpovídá geometricky zavedení nadroviny, která od množiny přípustných
řešení spojitého problému „odřízne“ optimální neceločíselné řešení, přičemž nedojde ke ztrátě
žádného přípustného řešení celočíselného problému. Postup se opakuje, tj. doplněný spojitý problém
se znovu řeší a splňuje-li získané optimální řešení podmínky celočíselnosti, je výpočet ukončen,
kdežto v opačném případě se přidá další omezení atd.
Původně byly metody sečných nadrovin konstruovány pouze pro lineární úlohy. Z nich
nejznámější jsou Gomoryho metody. Později došlo k rozvoji těchto metod ve směru jejich
rozšíření na některé obecnější úlohy. Použití metod sečných nadrovin může v některých
případech narazit na problémy spojené s nadměrným růstem rozměrnosti úlohy při přidávání
dodatečných omezení a s pomalou konvergencí.
Postup řešení celočíselné úlohy LP (6.11) – (6.14) může být tedy popsán takto:
1. Úlohu (6.11) – (6.13) řešíme simplexovou metodou. Splňuje-li získané optimální řešení podmínky
celočíselnosti, pak postup končí. V opačném případě položíme s = 1 a pokračujeme bodem 2.
2. K soustavě rovnic z poslední simplexové tabulky připojíme rovnici:
kde k je určeno vztahem Rk = max Ri a proměnná xn+s je vázána podmínkou nezápornosti.
3. V rozšířené simplexové tabulce považujeme nově připojený řádek za klíčový a řešíme ji dále
duálně simplexovou metodou. Jestliže je optimální řešení celočíselné, postup končí. V opačném
případě zvětšíme s o jedničku a postup opakujeme od bodu 2.
K popsané metodě řezů ještě na závěr poznamenejme, že růstu rozměrnosti rozšířené úlohy
můžeme zabránit tím, že po vyloučení dodatečné proměnné xn+s z báze vypustíme z řešené
soustavy i příslušné dodatečné omezení.
21. Charakterizujte princip metody větví a mezí a uveďte příklady způsobů větvení a omezování.
Metoda větví a mezí
Metoda větví a mezí (branch and bound) je iterační metoda pro nalezení globálního extrému funkce
f(x) na množině přípustných řešení M. Tato metoda je založena na opakování následujících dvou
operací:
• větvení, při němž se zprvu množina M a později její vybraná podmnožina rozkládá na po dvou
disjunktní podmnožiny (postup rozkladu množiny M je možno znázornit stromovým grafem,
jehož uzly odpovídají jednotlivým podmnožinám),
• omezování, při němž se pro každou podmnožinu získanou předchozí operací určuje dolní (při
minimalizaci) resp. horní (při maximalizaci) mez hodnot funkce f(x) na této podmnožině.
Pro další rozklad se volí podmnožina s nejnižší dolní resp. nejvyšší horní mezí. Cílem je najít takové
přípustné řešení, pro něž hodnota účelové funkce není větší než dolní meze resp. není menší než horní
meze u všech dosud nerozložených podmnožin, neboť takové řešení je optimální.
Všimněme si, že v popisu metody větví a mezí se vůbec neobjevila zmínka o celočíselnosti
proměnných. Znamená to, že použitelnost metody není omezena pouze na úlohy celočíselného
programování.
Metoda větví a mezí je vhodná pro řešení úloh, ve kterých struktura množiny M umožňuje
jednoduchý postup rozkladu a funkce f(x) dovoluje odvodit příslušné dolní nebo horní meze.
Efektivnost postupu závisí na stanovení mezí h(Mk). Příliš hrubé meze mohou způsobit to, že se strom
úlohy příliš „rozroste“. Přesnější meze sice vedou k redukci stromu úlohy, ale z toho plynoucí úspora
může být na druhé straně negována náročností výpočtu těchto mezí. Obecně mohou být meze hodnot
účelové funkce určeny pomocí nějaké heuristické metody. V případě, že metodu větví a mezí
aplikujeme na problém celočíselného programování, je možno příslušné meze získat zanedbáním
podmínek celočíselnosti a použitím nějaké metody „neceločíselné“ optimalizace.
Úlohy síťové optimalizace
22. Napište definici orientovaného grafu a nakreslete příklad. Jaké znáte typy grafů? Uveďte
příklady aplikací.
Orientovaný graf je definován jako dvojice
kde V je množina vrcholů (uzlů) a E je množina orientovaných hran, definovaná jako
podmnožina kartézského součinu V × V, tj.
Orientovaná hrana je tedy uspořádaná dvojice vrcholů e = (v1, v2), kde v1 je počáteční uzel a v2 je
koncový uzel. Příklad orientovaného grafu je ukázán na obr. 7.1, kde kroužky představují vrcholy a
orientované spojnice reprezentují hrany.
Pomocí orientovaného grafu může být modelován např. výrobní systém, kde stroje jsou
reprezentovány pomocí uzlů a orientované hrany odpovídají tokům materiálu, polotovarů a
výrobků. Jiným příkladem je model kanalizační sítě kde hrany představují úseky potrubí
(orientace je dána spádem) a vrcholy odpovídají vpustím a spojovacím uzlům.
Kromě orientovaných grafů ještě existují neorientované a smíšené grafy. Neorientovaný graf je
definován jako dvojice (7.1), kde
přičemž symbol (V nad 2) označuje množinu všech dvouprvkových podmnožin množiny V. Tedy
každá neorientovaná hrana je množina obsahující dva vrcholy, e = {v1, v2}. Neorientovaný graf může
být např. modelem automapy, kde vrcholy jsou obce a hrany jsou úseky silnic mezi obcemi.
Smíšený graf je definován jako dvojice (7.1), kde
Pomocí smíšeného grafu můžeme zobrazit např. síť ulic ve městě, kde vrcholy odpovídají náměstím,
křižovatkám a začátkům a koncům ulic, neorientované hrany představují obousměrné ulice a
orientované hrany ulice jednosměrné.
V dalších podkapitolách se budeme zabývat pouze orientovanými grafy. Neorientované a smíšené
grafy můžeme převést na orientované tak, že každou neorientovanou hranu nahradíme dvojicí
opačně orientovaných hran (viz obr 4.2).
23. Jak je definován tok od zdroje ke spotřebiči? Ilustrujte na příkladě. Charakterizujte možné
způsoby nalezení maximálního toku (stačí slovně).
Podmínka (7.13) říká, že tok hranou musí být nezáporný a nesmí překročit její kapacitu. Podmínka
(7.14) znamená, že pokud uzel není zdroj ani spotřebič, musí být součet toků do něj vstupujících
roven součtu toků z něj vystupujících.

Ford - Fulkersonův algoritmus vychází z nějakého přípustného toku a opakují se v něm dvě fáze. V
prvé fázi se hledá cesta ze zdroje do spotřebiče (bez ohledu na orienta