EMM_I_dlya_ustnoy

5) Stručně popište princip Vogelovy aproximační metody v modelu jednostupňové dopravní úlohy. K čemu se tato metoda používá, jak dobré výsledky poskytuje?

• Tato metoda se rozhoduje podle největší diference v příslušných řádcích a sloupcích (diference = nejvýhodnější – druhá nejvýhodnější tedy nejmenší sazba). Tzn. vybereme nejvyšší diference (nezáleží zda ve sloupci nebo v řádku) a zde v tomto řádku nebo sloupci vybereme nejvýhodnější index, kde obsadíme maximálně možnou sazbu. Snaží se vlastně zamezit největším ztrátám.

  • NEJSPOLEHLIVĚJŠÍ METODA

6) Co je to degenerace v modelu jednostupňové dopravní úlohy? Jak vzniká, jak se určuje a jak se odstraňuje?

Ověřujeme to vzorcem m+n-1 = počtu námi obsazených políček. Pokud se to nerovná, úloha je degenerovaná a musíme jí odstranit. Odstraníme ji tak, že do tabulky libovolně napíšeme velmi malou kladnou hodnotu, kterou značíme epsilon s podmínkou, že ji musíme vložit tak, aby netvořila uzavřený dantzigův obvod s ostatními prvky v tabulce.

Téma 8 a 9: Jednostupňová dopravní úloha II, dvoustupňová úloha

1) Uveďte princip metody MODI při řešení modelu jednostupňové dopravní úlohy.

• založena na teorii duality

• touto metodou se provádí test optimality

• jde o výpočet duálních hodnot ui a vj , tak že ve vhodné řadě zvolíme ui nebo vj rovno nule a dopočítáme s hodnotou sazby

• Ve všech ostatních řadách dopočítáme ui a vj tak, aby pro všechna obsazená pole platilo, že

ui + vj = cij Cij –cena políčka v pravém horním rohu

• Řešení je optimální, pokud pro všechna neobsazená pole platí, že ui + vj – cij £ 0

- Lze jen pro nedegenerované řešení !!

• když řešení není optimální vybereme pole které má tuto hodnotu nejvyšší a je vhodné ho zařadit pomocí Danzigova uzavřeného obvodu

2) Co je to Danzigův uzavřený obvod? K čemu slouží při řešení modelu jednostupňové dopravní úlohy?

• pomocí něj se přechází na lepší řešení, změna báze se provádí přímo v dopravní tabulce

- při minimalizační úloze vybereme políčko s nejvyšší hodnotou testu optimality - hodnoty v levém horním rohu pole.

- pro toto pole sestavíme Dantzigův uzavřený obvod, je znázorněn lomenou čarou, vychází z námi určeného prázdného pole, které chceme obsadit, lomí se v obsazených polích a končí zpět ve výchozím prázdném poli, pole kde se obvod lomí označíme střídavě znaménky + a -, podle znamének ji přičítáme, nebo odčítáme

- znovu test optimality a znovu Danzigův uzavřený obvod, až do nalezení optimálního řešení

3) Co je to perspektivita dopravních tras? Jak se analýza perspektivity provádí?

- hodnota testu optimality v optimálním řešení, počítá se u nerealizovaných tras

- určuje míru zhoršení účelové funkce při realizaci tohoto spoje (čím je toto číslo menší, tím je spoj výhodnější)