Vypracovane-zkouskove-otazky - teorie

6) 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í existuje

• právě jedno optimální řešení → nastává tehdy, když přímka účelové funkce protíná množinu přípustných řešení právě v jednom bodě

• nekonečně mnoho optimálních řešen í→pokud přímka účelové funkce splývá s hranou konvexního polyedru (množina přípustných řešení)

Optimální řešení neexistuje

• žádné přípustné řešení →není možné splnit všechny omezující podmínky

• hodnota účelové funkce může neomezeně růst nebo klesat

Téma 2: Grafické řešení modelu LP v prostoru požadavků. Bázická a nebázická řešení
1) Uveďte a stručně komentujte základní vlastnosti modelů lineárního programování

• Linearita

• Aditivita (sčitatelnost)-počet jednotlivých dílčích funkcí

• Spojitost

• Neomezená záměna faktorů

• Libovolná dělitelnost

• Deterministický charakter- nepracuje s náhodou a neurčitostí

• Statický charakter- nepracují s časem, opakem jsou dynamické modely

2) 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í.

• Přípustné řešení - splňuje podmínky a omezení, ale není nejlepším možným řešením

• Optimální řešení - nejlepší přípustné řešení

• Alternativní řešení – náhradní řešení, stejně dobré jako optimální (v případě, že má úloha více řešení), má stejnou hodnotu účelové funkce jako optimální

• Suboptimální řešení – sousední bazické řešení, není optimální, ale jeho hodnota se blíží optimu

3) Co je to bázické a nebázické řešení modelu lineárního programování? Jak se bázické řešení reprezentuje graficky v prostoru požadavků?

Bázické (základní) řešení= vektorový prostor (množina všech vektorů dané dimenze, všechny skaláry a odčítání)

• Takové řešení, kdy všechny nebázické proměnné jsou rovny 0 a hodnoty bazických proměnných jsou pak jednoznačně určeny ze soustavy

• Takové řešení, ve kterém nejvýše m proměnných nabývá kladné hodnoty. Tyto proměnné označujeme bazické. V matici soustavy jim přísluší jednotkové vektory a nabývají hodnot odpovídající složky vektoru pravých stran

• vektor, jehož nenulové složky odpovídají bazickým vektorům=> nebazické jsou tedy rovny 0

• 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.

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