Vypracovane-zkouskove-otazky - teorie

Úloha řešená Maďarskou metodou má tolik optimálních řešení, kolika způsoby lze vybrat nezávislé nuly.

Postup výpočtu přiřazovací úlohy Maďarskou metodou:

1. PRIMÁRNÍ REDUKCE

   • Jejím cílem je dostat alespoň jeden nulový prvek v každém řádku i sloupci matice sazeb;

1. Řádková

   • Cílem řádkové redukce je alespoň jedna 0 v každém řádku.

   • Od každé řady odečítáme hodnotu jejího minimálního prvku.

2. Sloupcová

   • Cílem sloupcové redukce je alespoň jedna 0 v každém sloupci.

   • Od každého sloupce odečítáme hodnotu jeho minimálního prvku.

1. VÝBĚR NEZÁVISLÝCH NUL + KONSTRUKCE KRYCÍCH ČAR

• Vybíráme v každém řádku a sloupci právě jednu 0 (ostatní nepřipadají v úvahu).

• Silně nezávislá nula je jediná (sama) v řádku a sloupci,

• Slabě nezávislá nula je jediná (sama) v řádku nebo sloupci.

• Krycí čáru vedeme kolmo k řadě/sloupci kde není vybrána nezávislá 0. Vedeme ji nezávislou nulou.

  • Počet krycích čar se musí rovnat počtu nezávislých nul.

1. TEST OPTIMALITY

• Řešení je optimální, pokud počet nezávislých nul = m(m = počet krycích čar).

  • Všechny nezávislé 0 musí být ve všech řádcích a sloupcích právě jednou.

1. SEKUNDÁRNÍ REDUKCE

• Provádí se, je-li počet nezávislých nul menší než m.

• Vybereme minimum z nepokrytých (nepřeškrtnutých)prvků

  • Toto minimum odečteme od nepřeškrtnutých polí

    • 1x přeškrtnutá pole necháme beze změny

    • 2x přeškrtnutá pole – to minimum k nim přičteme

1. NOVÝ VÝBĚR NEZÁVISLÝCH NUL

• Provádíme, dokud nám nevyjde test optimality.

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

Jedná se o problém, kdy potřebujeme nalézt nejvhodnější trasu, v případě, žez 1 místa vycházíme, musíme obejít všechna místa a poté se znovu vracíme do výchozího místa.

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

V okružním dopravním problému se jedná např. o: problém listonoše; problém obchodního cestujícího; kurýrní služby; trasy zájezdů cestovních kanceláří, apod.

4) Uveďte a stručně charakterizujte základní typy okružních dopravních problémů.

1. JEDNOOKRUHOVÝ ODP

• klasický problém obchodního cestujícího.

1. VÍCEOKRUHOVÝ ODP

• vícenásobný problém obchodního cestujícího – pevný počet okruhů;

• trasovací problém – kapacitní omezení rozvozu.

1. PROBLÉM ČÍNSKÉHO LISTONOŠE

• cílem je projít nikoliv všechny uzly, ale hrany.

1. KOMBINOVANÉ PROBLÉMY

• s různým dodatečným kapacitním, požadavkovým nebo časovým omezením.

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

Metoda nejbližšího souseda je metoda hrubé síly. Používá se pro menší úlohy okružních dopravních problémů.