Teorie-emm ke žkoušce EMM
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
4) Uveďte a stručně charakterizujte základní typy okružních dopravních problémů.
Jednookruhový ODP - klasický problém obchodního cestujícího
Víceokruhový ODP - vícenásobný problém obchodního cestujícího – pevný počet okruhů
-
trasovací problém – kapacitní omezení rozvozu
Problém čínského listonoše - cílem je projít nikoliv všechny uzly, ale hrany
Kombinované problémy - s různým dodatečným kapacitním, požadavkovým nebo časovým
omezením
5) Kde a k čemu se používá metoda nejbližšího souseda? Stručně popište její
princip.
- metoda hrubé síly – pro menší úlohy ODP
stanovit výchozí místo pro tvorbu okruhu
přejít k místu, které je nejbližší aktuálnímu místu (nesmí se do výchozího ani tam, kde už jsme
byli)
postup opakovat tak dlouho, dokud se nevrátíme do výchozího místa
prověřit všechna místa jako výchozí
6) Popište modifikaci Vogelovy aproximační metody pro řešení okružních
dopravních problémů. - pomocí VAM určíme nejvýhodnější pořadí míst v daném okruhu
výpočet diferencí mezi dvěma nejvýhodnějšími trasami v každém řádku i sloupci úlohy
výběr řady/sloupce s maximální diferencí
výběr nejvýhodnější trasy (nejnižší vzdálenosti) z této řady a její zařazení do okruhu
aktualizace náčrtku
zákaz všech tras, které již není možno použít (=> vyškrtnout řádek i sloupec dané trasy +
cestu zpět)
návrat k bodu 1
7) Kde a k čemu se používá Mayerova metoda? Stručně popište její princip. - používá se u víceokruhového trasovacího problému – úloha rozšířena o kapacitní podmínky
- nevyřeší problém úplně – pouze rozdělí místa do jednotlivých okruhů s ohledem na minimalizaci
nákladů a kapacitní podmínky