Teorie-emm ke zkoušce

• tato metoda se používá pro řešení víceokruhového dopravního problému > okružní přeprava rozdělena do více okruhů z důvodu kapacitního omezení

• je to případ okružního spojení, kdy nelze z kapacitních důvodů projet všechna místa jedním okruhem, a proto z centrálního místa, odkud/kam probíhá rozvoz/svoz, musí vyjet více vozidel nebo jedno vozidlo vícekrát

• typický příklad: použití více dopravních prostředků pro rozvoz homogenního substrátu

• cíle řešení víceokruhového trasovacího problému

  • nalezení co nejvýhodnějšího počtu okruhů

  • nalezení co nejvýhodnějšího pořadí míst v jednotlivých okruzích

  • vše s ohledem na minimalizaci celkových nákladů na přepravu

• nevyřeší problém úplně, pouze rozdělí místa do jednotlivých okruhů

• algoritmus

  • vyber uzel nejvzdálenější od centra z dosud nezařazených a založ okruh

  • k tomuto uzlu vyber nejbližší nezařazené místo a přidej ho do okruhu

  • přidávej další místa, která jsou nejblíže jakémukoliv místu právě tvořeného okruhu, dokud stačí kapacita vozidla

  • zpět k bodu 1

• pořadí míst v okruzích lze stanovit např. metodou VAM

téma 4: INTERPRETACE VÝSLEDKU, DUALITA

1) Uveďte způsob, jak v simplexové tabulce identifikujete bázické a nebázické proměnné. Rovněž uveďte, jak určíte hodnoty všech proměnných v daném bázickém řešení.

BAZICKÉ PROMĚNNÉ = jsou rovny nějakým reálným číslům, obsahují jednu jedničku a dvě nuly, a v testu optima vychází nula

NEBAZICKÉ PROMĚNNÉ = jsou rovny hodnotě nula, hodnoty jsou různé, v simplexové tabulce nevycházejí jedničky a nuly

URČENÍ HODNOT VŠECH PROMĚNNÝCH V BAZICKÉM ŘEŠENÍ

• ve sloupci B vyčtu hodnotu

• zápis vektorem bazického řešení

• zápis vektorem obecného řešení

2) Co je to matice báze a inverzní matice báze v modelech lineárního programování? Jak tyto matice určíme a jaký je jejich význam?

MATICE BÁZE B = hledáme ve výchozí tabulce čísla na místech jednotkového vektoru z poslední tabulky

INVERZNÍ MATICE B-1 = její význam spočívá v tom, že lze s její pomocí transformovat úlohu z výchozí do výslední tabulky v jediném kroku

• tuto matici transformace nalezneme ve výsledné simplexové tabulce na místech, kde v tabulce výchozí byly jednotkové vektory tvořící bázi úlohy

• hledáme ve výsledné tabulce čísla na místech jednotkových vektorů z první tabulky

3) Co jsou to duální ceny proměnných? Jak je určíme a interpretujeme?

= stínové ceny > relativní nevýhodnost nebazických proměnných

• určují, jak se změní hodnota účelové funkce, když do řešení zařadíme danou proměnnou na jednotkové úrovni

4) Popište obsah vektoru bázického řešení a vektoru obecného řešení modelu lineárního programování. Uveďte příklady obou vektorů.

bazické řešení

obecné řešení

5) Co je to dualita modelů lineárního programování? Uveďte alespoň jeden příklad, kdy nám teorie duality výrazně zjednodušuje řešení úlohy.