Teorie-emm ke zkoušce

• postup pro nalezení max. toku v síti

  • nasycená cesta

    • vpřed – nelze zvýšit průtok

    • vzad – průtok lze snížit

  • výchozí tok je nulový

  • najdeme nenasycenou cestu

  • zvýšíme tok

  • konec – nelze-li nalézt nenasycenou cestu

• cíl: najít jiné nezáporné hranové ohodnocení sítě nazývané tok, splňující následující podmínky

  • pro každou hranu musí být tok menší nebo roven kapacitě

  • pro každý uzel kromě vstupu a výstupu sítě musí být: suma toků hran (jejichž je koncovým uzlem) = sumě toků hran (jejichž je počátečním uzlem)

  • aby suma toků hran vycházejících ze vstupu sítě byla maximální možná

• HRANY, JEJICHŽ TOK JE ROVEN KAPACITĚ, SE NAZÝVAJÍ NASYCENÉ

téma 10: DALŠÍ DOPRAVNÍ MODELY

1) Uveďte podstatu a komponenty přiřazovací úlohy.

• stejně jako jednostupňová dopravní úloha patří k nejjednodušším typům distribučních úloh

• zabývá se přiřazováním určitých prvků ke stejnému počtu jiných prvků (např. pracovníků k pracovištím, výrobků ke strojům,…) a to tak, aby výsledný efekt byl optimální = minimální náklady a maximální výkon

• cíl: nalézt optimální přiřazení objektů v poměru 1:1

• je to speciální případ JDÚ, který má stejný počet dodavatelů a spotřebitelů a všechny jejich kapacity a požadavky se rovnají jedné

• je to silně degenerovaná úloha

• komponenty modelu:

  • dodavatelé (zdroj přiřazení), celkově m

  • odběratelé (cíl přiřazení), celkově n

  • matice sazeb – nákladů přiřazení

• v této úloze dochází k n – násobné degeneraci > bylo by obtížné a zdlouhavé řešit to metodou MODI, proto byla vyvinuta speciální metoda pro tento typ úloh a nazývá se MAĎARSKÁ METODA, která je založena na teorii grafů a řešení značně urychlí

2) K čemu slouží maďarská metoda? Stručně popište její princip.

• tato metoda slouží k usnadnění výpočtu úlohy přiřazovací

• řeší úlohu pomocí redukce matice sazeb

• princip

  • primární redukce

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

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

    • dělíme:

      • řádková redukce

      • sloupcová redukce

  • výběr nezávislých nul, konstrukce krycích čar

    • nule je nezávislá, je-li jediná v řádku nebo sloupci

    • krycí čáru vedeme přes řadu, která je kolmá na řadu nezávislé nuly

    • dva typy nuly

      • silně nezávislá nula = je sama v řádku i sloupci

      • slabě nezávislá nula = je sama alespoň v řádku nebo sloupci

        • když je sama ve sloupci > škrtám řádek

  • test optimality

    • počet nezávislých nul = počet krycích čar = m > řešení je optimální

  • sekundární redukce

    • je-li počet krycích čar menší než n

      • vyberu nejmenší číslo (minimum) z nepřeškrtnutých prvků

      • od nepřeškrtnutých prvků toto minimum odečtu

      • minimum přičtu k číslům, která jsou 2x přeškrtnutá

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

  • nová matice sazeb > znovu výběr nezávislých nul