Teorie-emm ke žkoušce EMM
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
od
0 => v tomto grafu to je X2,X3
optimálním řešením může být ale také jen
jedna z proměnných
Téma 3: Simplexový algoritmus 1) Uveďte dvě základní podmínky pro aplikovatelnost simplexového algoritmu. Jaký
je jejich význam, proč je jejich splnění nutné?
Nezápornost složek vektoru pravých stran
-
stačí zkontrolovat; pokud není splněna, lze příslušné omezující podmínky vynásobit (-1)
Matice soustavy v kanonickém tvaru
-
krok 1: rovnicový tvar modelu
-
krok 2: kanonický tvar modelu- zavádí se pomocné proměnné do všech omezujících
podmínek typu >= nebo typu určení „=“
2) 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? Při řešení úlohy LP vždy nejprve získáme výchozí základní přípustné řešení. K tomu je potřeba mít
omezující podmínky úlohy ve tvaru soustavy lineárních rovnic v kanonickém tvaru. Jelikož omezující
podmínky v úloze LP bývají zpravidla ve tvaru nerovnic, je prvním krokem převod této soustavy
lineárních nerovnic (SLN) na soustavu lineárních rovnic (SLR)
- matice soustavy musí obsahovat jednotkovou submatici, kterou tvoří koeficienty základních
proměnných (kanonický tvar)
nerovnice vyrovnáme na rovnice - k tomu potřebujeme doplňkové proměnné (značí se d)
-
nahrazují ≥,≤,a =
-
indexujeme číslem omezující podmínky, přebírají její jednotky
-
v účelové funkci ohodnocujeme 0 sazbou
-
požadujeme jejich nezápornost
přidáváme do omezujících podmínek
-
kapacitních s kladným znaménkem (rezerva);
-
požadavkových se záporným znaménkem (překročení požadavku)
3) 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? Provádíme, protože jednou z podmínek pro aplikaci simplexového algoritmu je, že matice soustavy
musí být v kanonickém tvaru (tvoří koeficienty základních proměnných)-jednotkovou submatici,
abychom mohli využít Jordanovu eliminační metodu.