Teorie-emm ke žkoušce EMM

- 

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

  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 

  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 -> lze škrtnout sloupec či řádek 
  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 

  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 

  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 

  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ě, že z 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: