EMM_I_dlya_ustnoy

- Postup se opakuje tak dlouho, dokud se nevrátíme do výchozího místa

- Prověřit všechna místa jako výchozí – pro zlepšení hodnoty účelové funkce

Vogelova aproximační metoda

• zachován výpočet diferencí mezi dvěma nejvýhodnějšími trasami v každém řádku i sloupci úlohy

- Výběr řady s maximální diferencí – ošetření rizika neobsazení nejvýhodnější trasy

- Výběr nejvýhodnější trasy z této řady a její zařazení do okruhu, abychom eliminovali přílišné zhoršení účelové funkce

- než přepočítáme diference, musíme zákázat všechny trasy, které již není možno použít, která by nám předčasně uzavírala okruh

Mayerova metoda

• začínáme v centrálním místě a jedeme do místa, které je nejvzdálenější, pak již pokračujeme metodou nejbližšího souseda (tj. do míst, která jsou nejblíž) až dokud např. nevyčerpáme kapacitu, vrátíme se a opět začínáme v centrálním místě, jedeme opět nejdál a pak metodou nejbižšího souseda, ale pouze do míst kde jsme nebyli v prvním okruhu

- nesmí se do výchozího ani tam, kde už jsme byli) ani se nesmí předčasně uzavřít okruh

5) Kde a k čemu se používá metoda nejbližšího souseda? Stručně popište její princip.

• používá se v okružních dopravních problémech k nalezení co nejlepší trasy, pomocí které navštívíme všechna požadovaná místa a nakonec se vrátíme zpět

Princip

- Stanoví se výchozí místo pro tvorbu okruhu

- Přejde se k místu, které je nejbližší místu aktuálnímu (nesmí se do výchozího ani tam, kde už jsme byli) ani se nesmí předčasně uzavřít okruh

- Postup se opakuje tak dlouho, dokud se nevrátíme do výchozího místa

- Prověřit všechna místa jako výchozí – pro zlepšení hodnoty účelové funkce

6) Kde a k čemu se používá Mayerova metoda? Stručně popište její princip.

• používá se ve víceokruhových okružních dopravních problémech, přeprava musí být rozdělena do více okruhů např. kvůli nedostatečné kapacitě, je tedy třeba naplánovat několik okruhů tak aby každý začínal a končil v centrálním místě

Princip

- začínáme v centrálním místě a jedeme do místa, které je nejvzdálenější, pak již pokračujeme metodou nejbližšího souseda až dokud např. nevyčerpáme kapacitu, vrátíme se a opět začínáme v centrálním místě, jedeme opět nejdál a pak metodou nejbižšího souseda, ale pouze do míst kde jsme nebyli v prvním okruhu

- nesmí se do výchozího ani tam, kde už jsme byli) ani se nesmí předčasně uzavřít okruh

Téma 11: Modely teorie grafů

1. Co rozumíme termínem "graf" v teorii grafů? Jaký je rozdíl mezi orientovaným a neorientovaným grafem?

Grafem rozumíme uspořádanou dvojici, která se skládá z množiny uzlů (vrcholů) a množiny hran, přičemž hrany jsou dvojice uzlů

a) Orientovaný graf

- máli všechny hrany orientované

- Hrana je určena uspořádanou dvojicí vrcholů