Teorie-emm ke zkoušce

3) Uveďte podstatu a komponenty okružního dopravního problému.

• cíl modelu: nalézt takovou hamiltonovskou kružnici v grafu, která bude z hlediska celkového ocenění nejvýhodnější

• komponenty modelu:

  • navštěvovaná místa

  • trasy mezi navštěvovanými místy

  • ocenění tras, obvykle vzdáleností mezi místy

• možnosti řešení ODP

  • neexistuje obecný algoritmus pro nalezení optimálního řešení jakéhokoliv ODP

  • pro malé úlohy: metoda hrubé síly

  • pro větší úlohy: aproximační metody

    • metody vytvářející řešení

      • se sekvenčním postupem

      • s paralelním postupem

    • metody zlepšující řešení

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.

• jedná se o nejjednodušší aproximační metodu pro ODP

• 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)

• 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í

6) Popište modifikaci Vogelovy aproximační metody pro řešení okružních dopravních problémů.

• tato metoda je známá z řešení jednostupňové dopravní úlohy, ale dá se s ní řešit i okružní dopravní problémy > pro tento účel se musí patřičně modifikovat

• rozdíly oproti řešení při JDÚ

  • není třeba uvažovat přepravované množství > zapíší se pouze sazby a v průběhu algoritmu se obsazované buňky pouze označí (např. kroužkem), což znamená, že tyto buňky jsou zařazovány do konstruované trasy obchodního cestujícího

  • vyškrtávání po obsazení buňky > škrtá se jak řádek, tak i sloupec (protože cestující jede z i do každého místa jen jednou) + navíc se škrtá jedna další buňka, která s buňkou právě obsazenou uzavírá kruh (město A > město B; město B > město A)

• 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í

• výběr nejvýhodnější trasy 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

• návrat k bodu 1

• nestandardní situace:

  • diference ve dvou nebo více řadách budou shodné

    • porovnáme obsazovaná pole a vybereme to s minimální sazbou

  • trasy mezi všemi místy nemusí existovat

    • lze vyřešit prohibitivní sazbou

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