Vypracovane-zkouskove-otazky - teorie

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ší cenová 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. Po vypočítání diferencí vybereme pole s maximální diferencí a v té řadě nebo sloupci obsadíme pole s nejvýhodnější – nejnižší cenou.

- 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?

• Počet obsazených polí je menší než m + n - 1

• Dopad: nelze určit hodnoty všech duálních proměnných ui a vj

• Řešení: fiktivní obsazení některého z polí fiktivní hodnotou ε

  • ε … hodnota limitně se blížící nule;

  • nelze na pole, která s již obsazenými vytváří uzavřený obvod.

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

• Hledání duálně přípustného řešení

Primární model Duální model

xij ≥ 0 xi1 + … + xin = ai i = 1, 2, …, m //ui

x1 X1j + … + xmj = bj j = 1, 2, …, n //vj

z = z = c11x11 + c12x12 + … + cmnxmn → MIN

xij ≥ 0

0xij

xij ≥ 0

ui + v ui + vj ≤ cij i = 1, …, m, j = 1, …, n

zz z = a1u1 + … + amum + b1v1 + … + bnvn → MAX

ui uj , vj … libovolné

• Řešení je optimální, pokud jsou splněna všechna omezení duálního modelu

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

• Dantzigovy uzavřené obvody

• Na nově obsazované pole přidáváme, na ostatních polích střídavě ubíráme a přidáváme

• Nikde nesmí být záporné množství, proto přesouváme minimum z polí, kde ubíráme

• Nesmíme rozhodit splnění omezujících podmínek, proto přičítáme (odčítáme) stejné množství

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

• Analýza perspektivity tras

  • posouzení výhodnosti nebázických tras;

  • hodnoty ui + vj – cij. (sloupec úplně vpravo= ui, poslední řádek= vj)

4) Co je to propustnost dopravních tras? Jak se analýza propustnosti provádí?

• Analýza propustnosti tras

  • posouzení využitelnosti nebázických tras;

  • pomocí Dantzigových uzavřených obvodů.

5) Uveďte podstatu a komponenty jednostupňové dopravní úlohy.

Model JDÚ

• Cílem je nalézt co nejvýhodnější plán přepravy

• Obvykle minimalizace nákladů

• Přeprava substrátů od více dodavatelů k více odběratelům

• Předpoklad homogenity substrátu