Vypracovane-otazky-emm ke ZK

Propustnost a perspektivita

• Perspektivita spoje – hodnota testu optimality v optimálním řešení u nerealizovaného spoje. Určuje míru zhoršení účelové funkce při realizaci tohoto spoje. Čím je toto číslo menší, tím je spoj výhodnější

• Propustnost spoje – určuje maximální možné množství produktu, které může být na spoji přepraveno bez primární přípustnosti řešení. U optimálních spojů se propustnost rovná přímo přepravovanému množství produktu na tomto spoji.

CPM a PERT

• Základní metody síťové analýzy na grafech AOA

• Matematické metody pro nalezení kritické cesty

Rozdíl mezi CPM a PERT

• CPM – metoda postupu dopředu

  • doba činností je známa = má deterministický charakter

• PERT – doba trvání činnosti není přesně známa, je dána s určitou pravděpodobností

  • Doba trvání je náhodná veličina s určitým rozdělením pravděpodobnosti

  • Často vznikají časové rezervy – ale jen s určitou pravděpodobností

  • Zpětná metoda

Rozdíl čistá a smíšená strategie

• Čistá strategie = hráč dosáhne svého cíle pouze uplatněním jediné své strategie

• Smíšená strategie = hráč musí najít způsob střídání svých strategií, je popsána vektorem pravděpodobností

• Setkáme se s tím v teorii her – hry dvou inteligentních hráčů

• Použití při opakování hry – při mnoha partiích

Vlastnosti síťového grafu

• Základní formalizační prostředek

• Konečný, spojitý, orientovaný, acyklický, má 1 počáteční a 1 koncový bod

• Každý uzel v síti má své číslo, uzly mohou být ohodnoceny

• Hranově definované grafy x uzlově definované grafy

• Činnosti = hrany ( ohodnocené ), vazby mezi činnostmi = uzly ( neohodnocené )

Vlastnosti LP

• Soubor metod umožňující výběr optimální varianty při daném kritériu optimality a daných omezujících podmínkách

• Matematický model má 3 části: účelová fce, omezující podmínky, podmínky nezápornosti

Matematický model okružního problému

• Velmi podobné přiřazovací úloze

• Okružní trasu můžeme popsat tak, že každému místu, které projíždíme, přiřadíme místo, které je na okružní trase následuje

• K modelu přidány tzv. Tuckerovy podmínky

Algoritmus pro nejkratší cestu

• Nalezení nejkratší cesty, která obsahuje všechny vrcholy

• Je dáno n míst a je potřeba všechny projet a vrátit se do výchozího

• Postup pro nalezení matematického optima neexistuje

• Počet možností roste exponenciálně s rostoucím n

Metoda VAM + k čemu slouží + jeho algoritmus

• Využívá rozdílů mezi 2 nejvýhodnějšími vazbami v řadách dopravní tabulky

• Zajišťuje v celém průběhu rovnoměrné obsazování výhodných spojů

• Použití: jednostupňová dopravní úloha a okružní dopravní systém

Danzigův uzavřený obvod

• Je to lomená čára, která vychází z neobsazené buňky, lomí se v obsazených buňkách a končí

• v původní buňce

• Buňky, ve kterých se obvod lomí, označujeme střídavě znaménky + a -, zda příslušnou hodnotu k trase přidáváme, nebo z trasy odebíráme

• Používá se při řešení dopravních úloh – tím, že změníme hodnoty po obvodu přibližujeme se k optimálnímu řešení úlohy