Poznámky k příkladům pro II. část písemné zkoušky
1. Je dána matice A typu (2, n). Určete všechny báze.
Viz DSO, příklad 2.3.
2. Je dána soustava dvou lineárních rovnic a báze B. Zjistěte odpovídající bázické řešení.
Viz DSO, příklad 2.3.
3. Je dána úloha LP se 2 proměnnými. Graficky určete optimální řešení.
Viz DSO, příklady 2.2, 2.4 ­ 2.8.
4. Je dána simplexová tabulka odpovídající optimálnímu řešení s příznakem existence
dalších optimálních řešení. Určete všechna optimální bázická řešení.
Viz DSO, příklad 3.12.
5. Je dána jedna z dvojice symetricky duálně sdružených úloh. Zkonstruujte k ní úlohu
duální.
Viz DSO, příklad 4.2. V tomto příkladu je jako výchozí zadána maximalizační úloha.
Může být ale také jako výchozí zadána úloha minimalizační.
6. Je dána nelineární funkce f(x) více proměnných a bod x0. Určete směry, v nichž funkce
f(x) v bodě x0 nejrychleji roste a klesá.
Tyto směry se získají pomocí gradientu funkce f(x) (viz DSO, příklad 5.3).
7. Je dána nelineární funkce dvou proměnných ve tvaru polynomu 3. stupně. Určete obor, ve
kterém je daná funkce konvexní.
Konvexnost se ověřuje pomocí Hessovy matice (viz DSO, příklad 5.6, kde se ověřuje
konvexnost funkcí z příkladu 5.3). V uvedeném příkladě se ovšem jedná o polynomy
nejvýše druhého stupně, takže příslušné Hessovy matice jsou konstantní. V případě
polynomu 3. stupně bude Hessova matice záviset na x.
Uvažujme např. funkci . Hessova matice této funkce
vypadá takto:
3
221
2
1 )4(4)( -++= xxxxf x






-
=
2464
42
)(
2
2
x
f x
Aby tato matice byla pozitivně semidefinitní, musejí být všechny hlavní minory
nezáporné. Platí, že 2 > 0. Dále pak musí platit, že 0246 2 -x a
Řešením těchto dvou nerovnic dostaneme, že f(x) je konvexní pro .
.016)246(2 2 --x
3/162 x
8. Je dána úloha NLP. Zjistěte, zda se jedná o úlohu konvexního programování.
Řekneme, že úloha
min {f(x) | gi(x)  0, i = 1, 2, ... , m }
je úlohou konvexního programování právě tehdy, když funkce f(x) a všechny funkce gi(x)
jsou konvexní. Poznamenejme, že pokud by se mezi omezujícími podmínkami vyskytla
rovnice, pak tato rovnice musí být lineární.
Při ověřování konvexnosti musí být úloha nejprve upravena do požadovaného tvaru, tj.
musí být minimalizační, všechny nerovnice musejí být typu  a pravé strany omezujících
podmínek musejí být nulové.
Viz DSO, příklad 5.6. kde je ověřována konvexnost úlohy z příkladu 5.1, která je
v příkladu 5.3 nejprve upravena do požadovaného tvaru.
9. Jsou zadány veličiny dopravní úlohy (vektory a, b a matice C). Sestavte matematický
model.
Viz DSO, příklad 1.19 a podkapitola 7.2. Je třeba prověřit, zda je úloha vyvážená, tj. je-li
součet kapacit dodavatelů roven součtu požadavků odběratelů .
V takovém případě mohou mít všechna vlastní omezení tvar rovnic. Je-li A > B, musejí
mít omezení odpovídající dodavatelům tvar nerovnic typu . Je-li A < B, musejí mít tento
tvar omezení odpovídající odběratelům.

=
=
m
i
iaA
1

=
=
n
j
jbB
1
10. Je dána úloha stochastického LP, kde koeficienty v účelové funkci jsou navzájem
nezávislé náhodné veličiny se zadanými středními hodnotami a rozptyly. Sestavte možné
deterministické ekvivalenty dané úlohy.
Viz DSO, příklady 8.14 a 8.15. Stačí zformulovat pouze příslušné účelové funkce podle
vztahů (8.58) a (8.59) resp. (8.60). Vzhledem k nezávislosti náhodných veličin c1 a c2 pro
kovariance platí 11 = D(c1), 12 = 21 = 0, 22 = D(c2).
11. Je dána úloha dvoukriteriálního LP. Dále jsou dány minimální a maximální hodnoty obou
účelových funkcí a případně také jejich váhy. Sestavte možné jednokriteriální úlohy.
Viz DSO, příklady 8.17 a 8.19. Pokud jsou maximální hodnoty obou účelových funkcí
přibližně stejné, není třeba provádět normalizaci.
12. Úloha vícekriteriálního hodnocení variant je zadána kriteriální maticí a případně také
vahami jednotlivých kritérií. Určete bazální variantu, ideální variantu, dominované a
nedominované varianty a pomocí nějaké vhodné metody také kompromisní variantu.
Viz DSO, příklady 8.20 (ideální a bazální varianta) a 8.21 (nedominované varianty).
Kompromisní variantu je možno jednoduše určit pomocí agregace kritérií nebo
vzdálenosti od ideálního vektoru. Uvažujme např. kriteriální matici
















=
362
599
246
997
486
Y
a vektor vah kritérií (3, 2, 1), přičemž všechna kritéria jsou maximalizační. Ideální
hodnoty všech kritérií jsou stejné (jsou rovny 9) a tedy nemusíme provádět normalizaci.
Při váženém součtu hodnot kritérií podle vzorce

=
p
j
ijj yv
1
kde vj jsou váhy kritérií, dostáváme pro jednotlivé varianty tyto hodnoty: 38, 48, 28, 50,
21. Nejvýhodnější je tedy 4. varianta.
Při počítání vzdálenosti od vektoru ideálních hodnot kritérií podle vzorce

=
-
p
j
ijjj yHv
1
)(
kde Hj jsou ideální hodnoty kritérií, dostáváme pro jednotlivé varianty tyto hodnoty: 16,
6, 26, 4, 33. Nejvýhodnější je tedy opět 4. varianta. která je nejblíže ideální variantě.
Uvedené výpočty stačí ovšem dělat pouze pro nedominované varianty, tj. pro variantu
druhou a čtvrtou.