EMM_I_dlya_ustnoy

• Nebázické řešení= takové řešení, kdy se za nebazické proměnné položí určité hodnoty a získají se konkrétní hodnoty i pro bazické proměnné.

1. Co je to degenerované řešení modelu lineárního programování? Jak se degenerované řešení reprezentuje graficky?

• Degenerované řešení= takové řešení, kde alespoň jedna z bazických proměnných má nulovou hodnotu. Takové řešení obsahuje více než n-m nulových složek

• Pokud je počet nenulových položek menší než počet nezávislých rovnic

1. K čemu slouží „základní věty lineárního programování“? Jaké mají důsledky pro hledání optimálního řešení modelu LP?

• Základní věty LP:

• Optimální řešení úlohy LP leží vždy na hranici množiny přípustných řešení.

• Má-li úloha LP přípustné řešení, má i přípustné bázické řešení.

• Má-li úloha LP optimální řešení, má i optimální bázické řešení.

• Má-li úloha LP více než jedno optimální bázické řešení, je optimálním řešením i jejich lineární konvexní kombinace

1. Uveďte 4 možné výsledky řešení modelů lineárního programování a znázorněte je graficky v prostoru požadavků.

1. Model nemá přípustné řešení (MINIMALIZAČNÍ ÚLOHA)

2. Model má právě jedno optimální řešení (MINIMALIZAČNÍ ÚLOHA)

3. Alternativní optimální řešení (MINIMALIZAČNÍ ÚLOHA)

4. Model má přípustné řešení, ale hodnota účelové funkce může neomezeně růst nebo klesat (MAXIMALIZAČNÍ ÚLOHA)

1. Uveďte, jak v prostoru požadavků určíte přípustné řešení modelu lineárního programování a jak vyberete řešení optimální. Dokumentujte rovněž graficky.

• Pokud jde o MIN. nákladů

• Hledám 2 proměnné x, které mi protnou přímku b

• V grafu je více přípustných řešení, například x4, x1 (podmínka protnutí přímky b je tu splněna), další přípustné řešení jsou znázorněny v grafu ->

• Jako přípustné řešení se nebere například x1,x3 (neprotínají přímku b)

• Pokud chci najít optimální řešení pro MIN., musím najít proměnné x, které jsou nejdále 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 (b)

  • stačí zkontrolovat

  • pokud není splněna, lze příslušné omezující podmínky vynásobit hodnotou (-1).

• Matice soustavy v kanonickém tvaru

  • krok 1: rovnicový tvar modelu

  • krok 2: kanonický tvar modelu

    1. 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é