Vypracované okruhy

ak, že nejdříve určíme nejmenší (při maximalizaci)/ největší (při minimalizaci) koeficient v účelové funkci. Sloupec, kde se tento koeficient nachází je tkz. „klíčový sloupec“ a proměnná, která je nad tímto sloupcem je tkz. „vstupující proměnná“ Klíčový řádek zjistíme podle nejmenšího kladného poměru pravé strany každé rovnice (poslední sloupec v matici) a příslušného koeficientu z „klíčového sloupce“. Řádek, u kterého je poměr nejmenší (ale kladný) je klíčový řádek. Základní proměnná u klíčového řádku je tkz. „vystupující proměnná“ Prvek, který se nalézá v průniku klíčového sloupce a klíčového řádku se jmenuje „klíčový prvek“. V klíčovém sloupci nahradíme všechny koeficienty až na klíčový prvek za nuly. Klíčový prvek nahradíme jedničkou. Všechny řádky matice potom přepočteme tak, aby odpovídaly klíčovému sloupci (pomocí ekvivalentních úprav a klíčového řádku). Nakonec před maticí nahradíme vystupující proměnnou za proměnnou vstupující. Struktura základních proměnných se nám tudíž změnila, proměnné „nad maticí“ se nemění. Tento postup opakujeme, dokud všechny koeficienty v účelové fci. nejsou nezáporné (maximalizace) nebo nekladné (minimalizace). (dokud nedosáhneme optimálního řešení)
Jednofázová simplexová metoda může mít několik možných zakončení. Jedno optimální řešení, několik alternativních optimálních řešení a neomezenou hodnotu účelové fce. Jedno optimální řešení je indikováno tím, že všechny koeficienty v účelové fci jsou nenulové (nekladné), alternativní řešení je indikováno tím, že alespoň jeden koeficient u nezákladní proměnné (proměnné která není „vypsána“ před maticí) je roven nule. Úloha má neomezenou hodnotu řešení, pokud v průběhu výpočtu nelze vybrat klíčový řádek (všechny koeficienty v klíčovém sloupci jsou nekladné).
23.
Je-li matice singulární (obsahuje lineární závislost), převedeme ji na regulární tím, že vyškrtneme jednu z podmínek. Hodnost matice bude odpovídat.
24. Co nám signalizuje, když v případě maximalizační úlohy jsou v kriteriálním řádku záporné hodnoty? Co tedy musíme provést?
Řešení není optimální. Účelovou funkci můžeme ještě zlepšit. Optimální bude tehdy když v kriteriálním řádku budou pouze nuly nebo kladné hodnoty.
V řádku optima najdeme největší zápornou hodnotu v absolutní hodnotě a tím získáme proměnnou, kterou zařadíme do báze.
test optima Zj –Cj = CTXB * α j - Cj
Pak pomocí testu přípustnosti nalezneme proměnnou, kterou z báze vyřadíme, tedy proměnou, která má hodnotu testu přípustnosti nejmenší. Takto postupujeme dokud nebude řešení optimální, tedy do té doby než budou v kriteriállním řádku pouze nuly nebo kladné hodnoty.
test přípustnosti Ωkmin = βi / αikpro všechny αik > 0
27. Co znamená systém cestní sítě mezi dodavateli a odběrateli v dopravní úloze?
Okružní dopravní problém
→ konečná množina míst a vzdáleností,spotřeba času nebo náklady, sazby pro spojení každé dvojice míst. Hledáme takovou posloupnost míst (spojení), ve které se každé místo objeví právě jednou a součet ohodnocení jednotlivých spojení v této posloupnosti je minimální
Základní dva typy okružních dopravních problémů se liší charakterem cestní sítě.
Problém s úplnou cestní sítí – ve kterém existuje mezi libovolnými dvěmi místa místy přímé spojení.
Problém s neúplnou sítí cest – ve kterém nelze realizovat v libovolném směru přímé spojení každé dvojice míst (bez nutného projetí místem dalším).
29. Co nám signalizuje, když v případě minimalizační úlohy jsou v kriteriálním řádku kladné hodnoty? Co tedy musíme provést?
Řešení není dosud optimální. Najdeme tedy největší kladnou hodnotu a tím získáme proměnnou, kterou zařadíme do báze. Potom pomocí testu přípustnosti získáme proměnnou, kterou zařadíme do báze. Dále určíme klíčový prvek… Celý proces opakujeme, dokud v kriteriálním řádku nebudou pouze nulové nebo záporné hodnoty.
30. Jaké jsou podmínky přípustnosti řešení?
všechny vektory x, které vyhovují soustavě omezujících podmínek Ax = b a jsou nezáporné, vytváření množinu přípustných řešení
báze B nesmí obsahovat pomocnou proměnnou
31. Jaké znáte metody, jak nalézt výchozí základní řešení v dopravní úloze?
Existuje několik metod, jak nalézt výchozí základní řešení:
1. metoda severozápadního rohu (NWC)
2. indexová metoda – vzestupná, sestupná, kombinovaná
3. habrova frekvenční – aproximatická metoda, rychle konverguje do řešení v blízkosti optima
4.VAM – přibližná řešení, která nejsou špatná
a další…
Otázka 32. „Definujte postup při testu přípustnosti.“
Test přípustnosti Ωk min
Má 3 funkce:
1, V algoritmu zajišťuje, aby nové řešení zůstalo primárně přípustné, tedy nezáporné.
2, Určuje nově vyřazovanou proměnnou, v každém interačním kroku dochází k vyřazení proměnné a zařazení nové proměnné, cyklus se opakuje, dokud Zj – Cj ukazuje možnost zlepšit hodnotu účelové funkce. Po konečném kroku dostaneme optimální řešení – pokud ho tedy úloha má.
3, určuje maximální možný interval zařazení nové proměnné do báze : 0 ( x1 ( H
Mohou nastat dva problémy:
1, Zacyklování – může nastat, pokud matice není regulární
2, Degenerované řešení – stav, kdy v bázi je zařazena jedna nebo více proměnných s nulovou hodnotou
K výpočtu užíváme vzorec (kmin = (i / (ik .
Nejdříve testem optima zjistím proměnnou s maximální zápornou hodnotou v kriteriálním řádku. Proměnná s touto hodnotou vstupuje do báze.
Nyní testem přípustnosti zjistím proměnnou, která z báze vypadne. Test přípustnosti probíhá tak, že vektor pravých stran vydělíme koeficienty vstupující proměnné. Vypadne ta proměnná, u které je výsledná hodnota podílu nejmenší.
Musí být splněna podmínka nezápornosti, pravá strana musí být nula nebo kladná.
33. Proč maďarská metoda se nazývá maďarská?
Maďarská metoda se používá k řešení přiřazovacího problému. Zjednodušeně lze algoritmus této metody popsat těmito kroky:
redukce matice sazeb
výběr nezávislých nul
kontrola správnosti výběru nezávislých nul
sekundární redukce matice sazeb
postup opakujeme (kroky 2, 3, popř. 4) dokud nenajdeme m nezávislých nul – z tohoto neustálého opakování vzniká tedy název této metody – Maďarská metoda
Optimálního řešení dosáhneme, pokud jsme vybrali m nezávislých nul.
34. Definujte postup při testu optimality
určeno výchozí bazické nedegenerované řešení
řešíme rovnici cij = ui + vj pro všechna obsazená políčka (xij > 0), vypočítaná řádková čísla ui a sloupcová čísla vj zapíšeme do tabulky
pro všechna volná políčka (xij = 0) vypočítáme součty duálních proměnných a zapisujeme je do levého dolního rohu příslušného políčka zij = ui + vj
řešení je optimální, platí-li pro všechna volná políčka ui + vj ≤ cij. Je-li ui + vj = cij, existuje další alternativní optimální řešení. Během výpočtu si upravíme ui + vj ≤ cij na tvar zij - cij ≤ 0, pak pro všechna volná políčka spočítáme tvar zij – cij
řešení není optimální existuje-li alespoň jedno políčko, kde je rozdíl zij – cij > 0
je-li více políček s kladným rozdílem zij – cij, vybereme to políčko, které má maximální rozdíl a to budeme nově obsazovat
Sj
Di
zij – cij ≥ 0 cij
zij = ui + vj
35) Kdy vznikne alternativní optimální řešení?
Alternativní řešení – když je alespoň jeden z koeficientů u nezákladních proměnných roven nule
Optimální řešení – takové řešení, kterým přechodem na jiné přípustné řešení už není možné zvýšit hodnotu účelové fce, může být jediné nebo alternativní
Alternativní optimální řešení – řešení,které zařazením proměnné zj – cj = 0 do báze vyvolá kvantitativní změnu řešení, ale hodnota účelové fce je stejná, jen řešení je jiné ( zisk a náklady se nemění )
36. Co to je matice transformace B -1 ?
Matici transformace B -1 nalezneme v těch sloupcích výsledné simplexové tabulky, v nichž ve výchozí simplexové tabulce byly jednotkové vektory výchozí báze.
Příklad:
Výchozí simplexová tabulka

cB
xB
30
30
40
30
0
0
0
b
x1
x2
x3
x4
x5
x6
x7
0
x5
1
1
1
1
1
0
0
100
0
x6
0
10
0
5
0
1
0
600
0
x7
10
0
25
0
0
01500zk - ck-30-30-40-300000
Výsledná simplexová tabulka

30x43/510110-1/25800x6-3500-511/520040x32/5010001/2520zk - ck40003002/53200
Matice transformace B -1



B -1 =






37.
Graf: uspořádaná dvojice, která se skládá z množiny uzlů(vrcholů) a množiny hran.
Orientovaný graf je graf, který má hrany orientované.
Orientovaná hrana: uspořádaná dvojice uzlů, tj. je určeno jejich pořadí, hrana má definován směr od prvého uzlu- počátečního uzlu hrany ke druhému- koncovému uzlu hrany, průchod hranou je umožněn pouze v tomto směru, nikoliv v opačném.
V grafickém vyjádření se pro orientované hrany používají orientované úseky či oblouky opatřené šipkami.
Síť(síťový graf) je orientovaný souvislý nezáporně ohodnocený graf, který má právě jeden vstup a právě jeden výstup.
Orientace grafu- každému uzlu musíme přiřadit nějakou hodnotu (pořadové číslo).
U malých grafů se používá metoda škrtací.
U velkých grafů se používá Ford - Fulkersonova metoda
Ui < Uj – každá cesta musí vystupovat z uzlu, který má nižší pořadové číslo než uzel do kterého vstupuje. Pro uzly stejného řádu platí pravidlo libovolného pořadí.

38. Co rozumíte pod pojmem suboptimální řešení?
Rozborem výsledné simplexové tabulky rozumíme soubor analýz vlivu různých změn na výsledné řešení.
Ke změnám ve výchozích údajích modelu může dojít v důsledku vzájemných vlivů modelovaného systému a jeho okolí nebo v důsledku působení náhodných činitelů. Cílem rozboru je získání potřebných dodatečných informací o daném systému.
Suboptimálním řešením rozumíme takový vektor řešení, který dostaneme z vektoru obecného řešení volbou určitého kladného čísla za alespoň jednu nezákladní strukturní proměnnou. Hodnota účelové funkce se oproti původní optimální vždy zhorší, tj. při maximalizaci se zmenší, při minimalizaci se zvětší.
Řešení zůstane přípustné v dané bázi, jestliže jednotlivá nezákladní strukturní proměnná Xk splňuje podmínku:
0 intenzita obsluhy - schopnost kanálu obsluhy obsloužit za zvolenou časovou jednotku daný počet zákazníků
Charakteristiky uzlu obsluhy
1) Počet paralelně zapojených kanálů
jeden kanál
více kanálů
Pozn.: Jestliže větší počet pracovníků představující uzel obsluhy pracuje společně na jednom požadavku, jedná se o jednokanálový systém
2) Doba obsluhy
deterministická (pevně daná)
náhodná
Systém hromadné obsluhy (SHO)
s jednofázovou obsluhou (pouze jeden uzel obsluhy)
s vícefázovou obsluhou (několik uzlů obsluhy uspořádaných seriově nebo v nějaké síťové struktuře)
Struktura SHO
134. Proveďte rozlišení mezi cyklickými a acyklickými modely teorie hromadné obsluhy
Uzavřený systém (cyklický): zdroj obsluhuje konečný počet jednotek. Podstatná vlastnost uzavřeného systému: jednotky se vracejí po ukončení obsluhy zpět do zdroje.
Otevřený systém (acyklický): zdroj obsahuje nekonečně mnoho jednotek. Podstatná vlastnost uzavřeného systému: jednotky se nevracejí po ukončení obsluhy zpět do zdroje.
135.
Pro reseni uloh linearniho programovani symplexovou metodou se k reseni pouzivaji:- Veta o zmene baze- Dantzinguv test optimality (spolu s Dantzingovou vetou)
136.
Základní struktura jednoduchého jednokanálového systému front: Příjezdy (vstupy) představují požadavky na použití zařízení. Jednotky (zákazníci) vstupují do systému z určitého zdroje možných příchodů (příjezdů). Když je obsluhující zařízení již obsazeno, příchozí jednotka  čeká ve frontě, dokud kapacita obsluhujícího zařízení není k dispozici.
137. Co znamená zkratka EMM?
EMM je zkratka pro předmět Ekonomicko-matematické metody.
Posláním a základním cílem tohoto předmětu je vytvořit základní poznatkovou bázi pro potřeby tvorby kvantifikovaného pojetí rozhodovacích prostorů s využitím ekonomicko-matematických metod v analytickém i syntetickém pojetí pro potřeby podnikatelských a administrativně-správních činností a operací.
Studenti se v tomto předmětu seznámí s vybranými matematickými metodami se zřetelem na komplexní testování daných problémů. Pozornost je zaměřena na využívání moderních počítačových technologií, zejména na tabulkové procesory.
Zdroj: http://wwwold.pef.czu.cz/KOSA/
138. Jaký je rozdíl mezi marginálními (změnovými, přírustkovými) koeficienty v simplexové metodě a průměrovými koeficienty strukturální analýzy (v obou případech Aij)?
Část A)
Simplexová metoda vychází s Gauss-Jordanovy metody úplné eliminace, kde základem jsou
proměnné x1….xm
Proměnná = jednotkové změnové zobrazení j-tého procesu. Má předem neznámý rozměr (rozsah) j-tého procesu 0 menší nebo rovno než xj, které je menší nebo rovno H (=horní
hranice)
Poměrově/přípustkové proměnné ∆/∆

Jedny ze 6 typů proměnných u Simplexové metody.
(∆Xij / ∆Xj) = Aij - Jedná se o jednotkové změnové zobrazení j-tého procesu
Část B) Principy strukturální analýzy:
Průměrové chování systémů:
- čím jsou tyto úlohy zvláštní:
1) na rozdíl od jiných úloh řeší problém jako celek (systémový přístup)
2) hlavním nástrojem je inverzní matice tzv. úplných toků
zajímá nás pouze podnik – vstupy x výstupy – kolik vyrobím, za kolik prodám a jaké mám náklady
A[aij] = matice technicko-ekonomických koeficientů
tvořena prvky aij
= množství celkové produkce plynoucí z i-tého dodavatelského odvětví na jednotku celkové hrubé produkce j-tého spotřebitelského odvětví
L=(E-A)
E – jednotková matice
A[aij] = matice technicko-ekonomických koeficientů

139. Markovovská matice
Markovovská matice malého modelu teorie front je matice pravděpodobností přechodu Markovova řetězce T, je čtvercová, a jsou v ní zapsány pravděpodobnosti přechodu pij .
Jednotlivé vazby v uzavřeném systému jsou oceněny prvky ∂ij-hodnota pravděpodobnosti možné realizace dané vazby. Součet pravděpodobností výstupů se musí rovnat 1.∑∂ij=1.
j
i
1
2
3
1
0,1
0,3
0,6
2
0,2
0,4
0,4
3
0,1
0,7
0,2
140. Jaký je rozdíl mezi náhodností a nahodilostí ve stochastických procesech s využitím distribuční funkce?
Základní simulační principy dokáží v celku dobře zachytit stochastičnost procesu-stochastický proces=vliv náhody. Dokáží zobrazit tok reálného času.
Náhodnost
Nahodilost
Hranice mezi nimi nejsou exaktní-přesné
Je rozdíl zda zkoumáme náhodnost a nahodilost na velkých souborech
Náhodný jev = jev, který má proměnlivé parametrické charakteristiky.
Trojí průběh normálního rozdělení
x
nahodilé I‘ náhodné jevy nahodilé
Spodní hranice Horní hranice
3 odlišné distribuční funkce(F1-F3) náhodné proměnné dle Gaussova rozdělení, může ale nastat zvláštní případ(F4)-v úzkém intervalu nabývá 1-jev deterministický
I‘-zde všechny funkce nabývají hodnot až 99%(oseknutý definiční obor).
Každý děj lze popsat dle libovolného počtu proměnných P1 až Pk.
Reálné proměnné musí mít větší, než nulovou hodnotu. Každá proměnná má reálný základ(doba činnosti, minimální spotřeba faktorů, ekonomické nápady apod.).K tomuto základu provádíme nějakou stochastickou opravu.
141 – Co je to jednotková matice?
Matice – uspořádaná soustava m x n reálných čísel uspořádaných do m řádků a n sloupců.
Jednotková matice - čtvercová matice, která má všechny prvky na hlavní diagonále rovny 1 a 0 na ostatních místech
- je ortogonální, tvoří nám bázi m- dimenzionálního vektorového prostoru
- jednotková matice je speciálním případem diagonální matice
- značíme ji En.

142. Z čeho vychází Simplexová metoda
Simplexová metoda vychází s Gauss-Jordanovy metody úplné eliminace, kde základem jsou
proměnné x1….xm.
proměnná = jednotkové změnové zobrazení j-tého procesu. Má předem neznámý rozměr (rozsah) j-tého procesu 0 menší nebo rovno xj, které je menší nebo rovno H (=horní
hranice).
143.
Deterministický proces
založen na stálosti (neměnnosti) všech parametrů modelu, které v průběhu výpočtu považujeme za konstanty
ke každému rozhodnutí můžeme jednoznačně přiřadit funkční hodnotu, kdy podle typu kritéria nacházíme funkční minimum nebo maximum
Stochastický proces
náhodný proces, děj, jev, veličina
tuto náhodou veličinu můžeme chápat jako funkční hodnotu funkce y = f (x), kdy funkční hodnota y je pevná hodnota argumentu, x není určena pevným číslem, ale je to náhodná veličina
náhodná veličina = stochastický proces
Fuzzy proces
fuzzy znamená rozptýlené, neurčité, mlhavé
neznáme hranice, prvky a vazby mezi nimi
144. Definujte úlohu generátoru pseudonáhodných veličin ve stochastickém simulačním modelu
Každý děj můžeme popsat pomocí libovolného konečného počtu proměnných P1…Pk. Reálné proměnní musí mít větší než nulovou hodnotu. každá proměnná má reálný základ (R) – doba činnosti, ekonomické náklady, min. spotřeba faktoru…K tomuto základu provádíme stochastickou opravu reálného základu. V PC programech to nazýváme Generátor pseudonáhodných veličin (GPNV). GPNV tedy realizuje opravu endogenní proměnné modelu.
Zdroj náhodných veličin – tabulka náhodných čísel (vydala NASA)
Atomová superrelace (jen 4 ve světě)
Dokonale vyvážené fyzikální pokusy
analogové převody
Generátor generuje pseudonáhodné veličiny, jsou základem všech typů simulací, rozlišujeme jich 10 – 12.
Náhodný jev – jev, který má proměnlivé parametrické charakteristiky
Nejdříve si musíme položit tři otázky:
zda v daném simulačním cyklu (t+Δt) náhodný jev vznikne či ne.
pokud ne, přestává nás to zajímat
pokud ano, zajímá nás jeho reálný rozměr dimenze
rozměr dimenze – Jaký bude mít náhodný jev rozměr?
V jakém okamžiku náhodný jev nastane?
1. fáze algoritmu generátoru – hledá odpověď, zda je jev nastane či ne (1.otázka)
Je sestrojen hypotetický interval s hranicemi 0;1. Nad tímto intervalem je zavedeno rovnoměrné rozdělení – všechny hodnoty mají stejnou ppst výskytu.
střední hodnota intervalu – 0,5
Zavedeme eukleidovskou metriku (vzdálenost dvou bodů)
vytvoříme subinterval a nazveme ho subinterval ppsti náhodného jevu
Generátor pseudonáhodných veličin
0 0,5 0,600 0,60326 1
2. fáze algoritmu generátoru – rozměr dimenze (2. otázka)
- náhodný jev jako délka zkoušky
2. otázka-rozměr dimenze
-náhodný jev je délka u zkoušky
0 t min 15min 20min 45min 1hod x-časová délka
1
x λ
0,5
0
fáze algoritmu generátoru – V jakém okamžiku náhodný jev nastane?(3.otázka)
Přístupy:
exponenciální – pokud náhodný jev dosud nenastal, tak ppst, že nastane stále roste
M1- λ-vysoký vektor
M2- λ-nízký vektor
M3-průnik M1 a M2
-pravděpodobnost třeba toho, že když dlouho nějaké číslo nepadlo, zvyšuje se pravděpodobnost toho, že padne
Rovnoměrná – náhodný jev se může vyskytnout kdykoli v daném čase (např. pokud ve sportce nebylo dlouho taženo nějaké číslo, tak to podle této verze neznamená, že je větší pravděpodobnost, že bude taženo)
deterministickou subkalkulaci-redukovaný, očekávaný časový horizont, v tomto intervalu provádíme simulaci.
Pi
Hreal H
3. Kombinovaná - Lineární koridor o dvou funkcích - kde generátor generuje náhodná čísla v koridoru, pokud se vybírají čísla z nějaké množiny, tak v tom prvním případě generátor nejdříve zmenší tu množinu o ty oblasti, kde vysoce nepravděpodobné, že se náhodný jev vyskytne...tzn. že nevybírá z celé množiny, ale z množiny, kde je pouze 95% možnost výskytu toho náhodného jevu a v druhým případě určí generátor koridor, v