- •Co je to modelování? Proveďte klasifikaci modelů podle alespoň jednoho hlediska. Ke každému typu modelů uveďte příklad.
- •Uveďte 4 možné výsledky řešení modelů lineárního programování a znázorněte je graficky V prostoru řešení
- •Optimální řešení neexistuje
- •Optimální řešení existuje
- •Uveďte a stručně komentujte základní vlastnosti modelů lineárního programování
- •Charakterizujte pojmy: „přípustné řešení“, „optimální řešení“, „alternativní řešení“, „suboptimální řešení“ V kontextu modelů lineárního programování.
- •Co je to bázické a nebázické řešení modelu lineárního programování? Jak se bázické řešení reprezentuje graficky?
- •Popište postup převodu modelu z rovnicového do kanonického tvaru. Proč tento krok při řešení modelu lineárního programování provádíme?
- •Uveďte a stručně popište typy proměnných V modelech lineárního programování. Ke každému typu proměnných uveďte příklad interpretace
- •Uveďte dvě základní podmínky pro aplikovatelnost simplexového algoritmu. Jaký je jejich význam, proč je jejich splnění nutné?
- •Popište postup převodu modelu z nerovnicového do rovnicového tvaru. Proč tento krok při řešení modelu lineárního programování provádíme?
- •X … strukturní proměnné
- •Uveďte a stručně popište typy omezujících podmínek V modelech lineárního programování. Ke každému typu uveďte příklad použití
- •Prezentujte obecnou simplexovou tabulku. Jaké informace simplexová tabulka poskytuje?
- •Popište účel, princip a postup provedení testu optimality V simplexové tabulce
- •Popište účel, princip a postup provedení testu přípustnosti V simplexové tabulce
- •Interpretace výsledku, dualita Uveďte způsob, jak V simplexové tabulce identifikujete bazické a nebazické proměnné. Rovněž uveďte, jak určíte hodnoty všech proměnnách V daném bazickém řešení.
- •Co jsou duální ceny proměnných? Jak je určíme a interpretujeme?
- •Co jsou to matice báze a inverzní matice V modelech lineárního programování? Jak tyto matice určíme a jaký je jejich význam?
- •Co je to dualita modelů lineárního programování? Uveďte alespoň jeden příklad, kdy nám teorie duality výrazně zjednoduší řešení úlohy
- •Popište vztahy mezi prvky duálně sdružených úloh
- •Co říká základní věta o dualitě? Její význam?
- •Jednostupňová dopravní úloha Uveďte podstatu a komponenty jednostupňové dopravní úlohy
- •Co je to degenerace V modelu jednostupňové dopravní úlohy? Jak vzniká, jak se určuje a odstraňuje.
- •Uveďte podstatu a komponenty přiřazovací úlohy.
- •C harakterizujte graf typu síť, dokumentujte rovněž graficky.
- •Uveďte podstatu a vlastnosti metody cpm. Jaké informace nám umožňuje zjistit?
- •Popište způsob provedení časové analýzy V metodě cpm.
- •Pořadové číslo
- •Činnost a
- •Nejdříve přípustná doba realizace
- •Volná časová rezerva
- •Zvláštní časová rezerva
- •Nezávislá rezerva
Co říká základní věta o dualitě? Její význam?
Má-li jedna z dvojice sdružených úloh optimální řešení, má optimální řešení i úloha druhá a optimální hodnoty obou účelových funkcí jsou stejné. Může-li hodnota účelové funkce jednoho se sdružených problému růst nebo klesat neomezeně, pak druhý problém nemá přípustné řešení.
Jednostupňová dopravní úloha Uveďte podstatu a komponenty jednostupňové dopravní úlohy
Dopravní úloha je založena na faktu, že existuje více dodavatelů identického produktu. Dopravní úlohou řešíme jak co možno nejlépe provést přepravu mezi jednotlivými dodavateli a odběrateli.
Komponenty:
Dodavatelé – nabízejí předmět přepravy (maximální kapacity)
Odběratelé – poptávají předmět přepravy (minimální požadavky)
Dopravní trasy – slouží k dopravě přepravovaného a jsou ohodnoceny nákladovými sazbami přepravy.
Účelová funkce – součin přepravovaného množství a ceny za přepravu jedné jednotky, minimalizují se přepravní náklady.
Co je to vyváženost jednostupňové dopravní úlohy a jak se provádí?
Je to vyrovnání mezi kapacitami dodavatelů a požadavky odběratelů. Provádí se proto, aby všechny vztahy a omezující podmínky mohli být považovány za podmínky typu rovnice. Provádíme ji pomocí fiktivního sloupce nebo fiktivního řádku, které nám vlastně dopomáhají k tomu, aby se nám tyto dva vztahy rovnaly.
Popište princip metody severozápadního rohu. K čemu se používá. Jak dobré výsledky dává.
Funguje na tom principu, že zkrátka nalezne nějaké výchozí bazické řešení bez ohledu na ceny jednotlivých tras. Postupuje z levého horního rohu do pravého spodního rohu, přičemž obsahuje políčka maximálně možnými sazbami. Z pohledu kvality patří mezi nejhorší metodu, protože jenom “nějak“ obsazuje políčka. Používá se k jednookruhovým dopravním úlohám.
Popište princip indexové metody. K čemu se používá. Jak dobré výsledky dává.
Indexová metoda je založena na postupu obsazování polí podle nejmenších indexů. Tzn. začíná od nejmenšího tedy nejvýhodnějšího indexu v tabulce. S kvalitou výsledků je o mnoho lepší než metoda severozápadního rohu, protože už obsazuje s nějakým plánem, ale než vogelova metoda lepší není.
Popište princip Vogelovy aproximační metody. K čemu se používá. Jak dobré výsledky dává.
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. Je z těchto tří metod nejspolehlivější.
Co je to degenerace V modelu jednostupňové dopravní úlohy? Jak vzniká, jak se určuje a odstraňuje.
V takové úloze bychom si měli po vytvoření každého řešení ověřit, zda řešení je nebo není degenerované. 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 10: Další dopravní modely