Teoretická otázka č. 11 K čemu slouží analýza citlivosti báze vhledem ke složkám vektoru pravých stran? Popište rámcově způsob jejího provedení.
Přehled některý možných zkouškových otázek z EMMI.
Bodování zkouškového testu: • Teorie 40 bodů: 4x 10 • Příklady 60 bodů: 15+20+25 • Bonifikace 20 bodů • Celkem 120 bodů: 100+20
Teoretická otázka č. 12 Uveďte princip řešení dvoustupňové dopravní úlohy jako úlohy jednostupňové. Co je to úloha o optimálním dimenzování meziskladů? Teoretická otázka č. 13 Popište modifikaci Vogelovy aproximační metody pro řešení okružních dopravních problémů.
Teoretická otázka č. 1 Volně charakterizujte pojmy „optimální řešení“, „alternativní řešení“ a „suboptimální řešení“ v úlohách lineárního programování. Jak se existence těchto řešení pozná ve výsledné simplexové tabulce? Teoretická otázka č. 2 Jaký je reálný význam ohodnocení hran v metodě CPM?
Teoretická otázka č. 14 Co je to systém? Jaký je význam v procesu systémového modelování? Teoretická otázka č. 15 Popište účel, princip a postup provedení testu optimality v simplexové tabulce. Teoretická otázka č. 16 Co je to Dantzigův uzavřený obvod? K čemu slouží při řešení modelu jednostupňové dopravní úlohy?
Teoretická otázka č. 3 Proč mají umělé proměnné prohibitivní sazbu? Jaké hodnoty tato sazba obvykle má?
Teoretická otázka č. 17 Kde a k čemu se používá Mayerova metoda? Stručně popište její princip.
Teoretická otázka č. 4 Jak se pozná degenerace v simplexové tabulce a v grafickém řešení?
Příklad na lineární programování č. 1 Zemědělský podnik má k dispozici 100 ha orné půdy, 600 hodin živé práce při jarní pracovní špičce a 500 hodin živé práce při sklizni. Určete strukturu plodin A, B, C, D, při které podnik dosahuje maximálního zisku.
Teoretická otázka č. 5 Popište princip (ne algoritmus) hledání nejkratší cesty mezi dvěma zadanými uzly grafu. Teoretická otázka č. 6 Uveďte a stručně popište komponenty modelů lineárního programování.
A jaro (hod./ha) sklizeň (hod./ha) zisk Kč
Teoretická otázka č. 7 Uveďte dvě základní podmínky pro aplikovatelnost simplexového algoritmu. Jaký je jejich význam, proč je jejich splnění nutné? Teoretická otázka č. 8 Stručně popište princip metody severozápadního rohu v modelu jednostupňové dopravní úlohy. K čemu se tato metoda používá, jak dobré výsledky poskytuje?
a) b) c) d)
Teoretická otázka č. 9 Popište princip informovaného prohledávání grafů. Uveďte a stručně popište vybranou metodu informovaného prohledávání grafu. Teoretická otázka č. 10 Popište postup převodu modelu z nerovnicového do rovníkového tvaru. Proč tento krok při řešení modelu lineárního programování provádíme?
-1-
10 30
B 10 30
C 25 40
D 5 30
Sestavte model lineárního programování. Napište výchozí simplexovou tabulku. Proveďte 1 krok výpočtu simplexovým algoritmem. Uveďte hodnoty všech proměnných po prvním kroku výpočtu a hodnotu účelové funkce.
Příklad na lineární programování č. 2 Výrobce televizorů potřebuje sestavit výrobní program tak, aby jeho zisk byl maximální. Každý televizor potřebuje čas na kompletaci a testování (viz. tabulka). K dispozici je celkem 200 obrazovek, 2000 hodin na kompletaci a 500 hodin na testování. Sport 8 2 40
Čas na kompletaci hod/kus Čas na testování hod/kus Zisk 5/kus
Standard 10 2 60
Turist 12 4 80
Super 15 5 100
Příklad na lineární programování č. 3 Je dáno výchozí řešení maximalizační úlohy LP. a) Najděte klíčový prvek. b) Vypočítejte optimální řešení simplexovým algoritmem. c) Napište hodnoty všech proměnných a účelové fce pro optimální řešení.
0 0 0
x4 x5 x6
10 x2 15 4 3
16 x3 12 8 3
0 x4 1 0 0
0 x5 0 1 0
Spotřeba surovin v kg/balení Pšenice Kukuřice Vitamínový doplňěk 0 x6 0 0 1
b 360 400 500
Sestavte model lineárního programování. Napište výchozí simplexovou tabulku. Proveďte 1 krok výpočtu simplexovým algoritmem Z tohoto řešení určete a interpretujte hodnoty všech proměnných a hodnotu účelové funkce.
Směs Opti-Fit (balíček) 1 4 1
17
22
0
0
0
0
-100
x1
x2
d1
d2
d3
d4
p4
1
0
d1
3
1
0
b 60
d2
2
4
0
d3
0
1
-100
p4
1
0
-117
-22
0
0
zj-cj
(5 b.) (5 b.) (10 b) (5 b)
Směs Džngar (balíček) 3 2 ---
Je dána výchozí a výsledná simplexová tabulka modelu lineárního programování pro tento problém:
Omega
Příklad na lineární programování č. 4 Betonárka vyrábí dva druhy betonových směsí: kameninu zpevněnou cementem KSC1 a výplňový beton B5. Na výrobu každé směsi jsou potřeba tři základní suroviny: cement, kamenivo a voda. Zatímco voda je pro betonárku neomezený zdroj, cementu je možno pro denní produkci využít nejvýše 80 t a kameniva 50 t. Další suroviny a zdroje jsou k dispozici v neomezeném množství. Na jeden kubík směsi KSC1 se spotřebuje 0,2 t cementu a 0,5 t kameniva, na jeden kubík směsi B5 se spotřebuje 0,4 t cementu a 0,3 t kameniva. Betonu B5 je třeba denně vyrobit nejméně 20 m3. Určete výrobní program maximalizující zisk betonárky v případě, že zisk kubíku KSC1 je 300 Kč a z jednoho kubíku směsi B5 400 Kč. a) b) c) d)
(15 b.)
Příklad na lineární programování č. 6 Obchodník s krmivem pro domácí mazlíčky připravuje vlastní krmné směsi pro křečky. K dispozici je maximálně 60 kg pšenice, 30 kg kukuřice a 16 kg vitamínových doplňků. Směsi Džungar je třeba připravit alespoň 10 balení. Prodejní cena za jeden balíček směsi Džungar je 17,- Kč a za směs OptiFit 22,- Kč. Obchodník maximalizuje tržby za prodané balíčky krmných směsí.
a) Sestavte model lineárního programování. b) Napište výchozí simplexovou tabulku.
9 x1 18 6 5
Příklad na lineární programování č. 5 Sestavte duální model k následujícímu modelu lineárního programování 2x1 + 5x2 – 3x3 ≤ 15 x2 + 4x3 = 10 x1 + 2x2 ≤ 12 4x1 + 2x3 ≥ 5 z = 2x1 + x2 +3x3 … MIN x1 ≥ 0; x2 ≥ 0; x3 … bez omezení (s.l.)
1
30 1
16 -1
1
10
0
100
0
-1000
0
d1
0
-5
1
-1,5
0
0
0
15
0
d4
0
2
0
0,5
0
1
-1
5
0
d3
0
1
0
0
1
0
0
16
17
x1
1
2
0
0,5
0
0
0
15
0
12
0
8,5
0
0
100
255
zj-cj
a) Uveďte definici všech proměnných (i doplňkových a pomocných) ve formátu: proměnná – název proměnné – jednotky (např. x8…spotřeba paliva (l/100 km)). (5 b.) b) Který zdroj (pšenice, kukuřice, vitamíny) je plně vyčerpán? Jak by se změnilo řešení a hodnota ÚF, kdybychom dokázali sehnat další 2 kg tohoto zdroje za 4 Kč/kg? (10 b.) -2-
c) Zákazník nutně potřebuje pro svoje křečky 2 balíčky směsi Opti-Fit a nabízí nám cenu 32 Kč/bal. Lze mu v rámci stávající struktury řešení vyhovět? Pokud ano, vyplatí se nám to? Své odpovědi zdůvodněte příslušnými výpočty. (10 b.)
Dopravní úloha č. 3 Jednostupňová dopravní úloha a) Najděte výchozí řešení jednostupňové dopravní úlohy indexovou metodou. b) Proveďte test optima. c) Rozhodněte, zda je řešení optimální.
Příklad na lineární programování č. 7 Rodinné zahradnictví pěstuje okrasné rostliny. K dispozici má maximálně 100 m2 záhonových ploch. Plánuje prodej okrasných rostlin a k dispozici má semena begónií, hlazenců, jiřinek, cínií a petunií. Plošná náročnost begónií je 25 rostlin/m2, hlazenců a jiřinek shodně 40 rostlin/m2, cinií je 90 rostlin/m2 a petunií 125 rostlin/m2. Rozhoduje se, na kolika m2 má kterou rostlinu pěstovat, aby maximalizovala své tržby, když za jednu rostlinu begonií utrží 40,- Kč, hlazenců 30,- Kč, cinií 40,Kč a petunií 20,- Kč. Přičemž po zkušenosti z minulého roku, kdy šly na odbyt hlavně petunie, begónie a jiřinky, chce tyto tři rostliny pěstovat alespoň na 50 m2. a) Sestavte model lineárního programování. b) Vyřešte tento model graficky pomocí vhodného zobrazení. c) Z výsledku grafického řešení odvoďte, na jakých výměrách pěstovat jednotlivé druhy květin a jaké budou očekávané tržby.
Elektrárny E1 25
E2
E3
ai
E4
7
6
10
Důl D1
3 4
5
9
13
Důl D2
4 13
(10 b.) (10 b.)
15
14
21
Důl D3
9 8
(5b.)
20
24
31
Důl D4
18
Dopravní úloha č. 1 Kapacity dodavatelů: D1 150 D2 120 D3 90 D4 50
Požadavky spotřebitelů: S1 30 S2 50 S3 50 S4 90
Vzdálenosti: S1 D1 5 D2 6 D3 4 D4 5
S2 6 7 6 6
S3 8 7 6 3
S4 2 4 1 8
bj
Kouty Blazov Miletice Kostelec
Dopravní úloha č. 2 Je třeba přesunout stroje z míst A, B, C, D na místa E, F, G, H. Navrhněte plán přesunu tak, aby celková ujetá vzdálenost bylo co nejmenší. E 12 15 6 21
F 24 18 7 16
G 8 35 8 6
5
7
20
Dopravní úloha č. 4 Okružní dopravní úloha a) Najděte řešení Vogelovou aproximační metodou. b) Napište celou trasu a spočítejte její celkovou délku.
Řešte tuto dopravní úlohu: Úkoly: a) Proveďte vyvážení úlohy, pokud je potřeba. b) Najděte výchozí řešení libovolnou metodou a napište, kterou. c) Odstraňte degeneraci, pokud je potřeba. d) Proveďte test optima tohoto výchozího řešení. e) Pokud řešení není optimální, sestrojte Dantzigův uzavřený obvod. f) Určete hodnotu, která se bude po obvodu přesouvat. g) Napište nové řešení.
A B C D
15
H 5 2 4 26 -3-
Kouty x 24 8 5
Blazov 24 x 35 2
Miletice 8 35 x 4
Kostelec 5 2 4 x
a) Najděte optimální plán přejezdů minimalizující celkovou ujetou vzdálenost. Kolik km se celkem najezdí? (12 b.) b) Existuje alternativní řešení problému? Pokud ano, najděte jej. (3 b.)
Dopravní úloha č. 5
S1
S2 12
D1
S3 20
110
S4 37
ai
17
35 80
53 40
D2
90
9 D3
14
34
15
21
39
60 0
a) b) c) d)
45 100
40 0
0
D FIKT
170
190
70
ve Zdechovicích ve Žlebech v Žehušicích V Moravanech
Základna Pardubice 26 13 35 16
Základna Přelouč 8 8 17 33
D2
20
1
3
120 140
1
1
Základna Chrudim 32 22 35 16
100 100 100
ai
50
1
150
90
1
110
2
120
140
Je tato úloha vyvážená? Je aktuální řešení degenerované? Nalezněte optimální řešení této úlohy. Vypočtěte hodnotu účelové funkce optimálního řešení V optimálním řešení si vyberte dvě obsazená pole a dvě neobsazená pole a určete jejich propustnost.
Tygr Ptakopysk Lemur Varan Sojka
(2 b.) (10 b.) (2 b.) (6 b.)
Dopravní úloha č. 6 Nehodové jednotky energetické společnosti zajišťují na Pardubicku po větrné smršti obnovení dodávek elektrického proudu do domácností. Budou pracovat do pozdních hodin a na noc se musí vrátit na domovské základny, tak aby na každé základně byla právě jedna jednotka v pohotovosti na příští den. Navrhněte, kam by se která jednotka měla vrátit, aby přejezdy byly co nejkratší. Jednotka:
D1
120
Je tato úloha vyvážená? Je aktuální řešení degenerované? Nalezněte optimální řešení této úlohy. Vypočtěte hodnotu účelové funkce optimálního řešení . Proveďte analýzu perspektivy všech neobsazených tras.
S3 2
(2 b.) (10 b.) (2 b.) (6 b.)
Dopravní úloha č. 8 Chovatel se rozhodl rozšířit svůj chov a pořídil si 5 nových zvířat. Bohužel už mu zbývá jen 5 posledních chovných prostor a musí do nich zvířata rozdělit. Náklady na chov se podle jednotlivých zvířat liší, jsou v tabulce (tis. Kč/měs.).
0 70
110
a) b) c) d)
110
S2 2
D3 bj
42
110
D4
bj
S1
220
110 11
Dopravní úloha č. 7 Je dána jednostupňová dopravní úloha a její řešení.
60
Skleněné terárium 24 13 20 25 3
Venkovní klec 28 16 16 24 2
Uzavíratelná bouda 26 15 15 24 1
Otevřená bouda 25 13 15 23 0,5
Ohrádka do dvorku 20 11 10 22 0,5
a) Upravte zadání, abyste vyloučili, že se tygr bude tísnit ve skleněném teráriu a sojka uletí z otevřeného prostoru (terárium je uzavíratelné). (5 b.) b) Nalezněte nákladové optimální prostory pro jednotlivá zvířata. (15 b.)
Základna Čáslav 18 34 10 49 -4-
Projekt je zadán následujícím grafem.
a) b) c) d)
Správně očíslujte uzly. Řešte úlohu metodou CPM. Vyznačte kritickou cestu a její délku. Spočtěte Celkovou rezervu tučně vyznačené činnosti.
-5-
