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.
řešení), má stejnou hodnotu účelové funkce jako optimální
Suboptimální řešení - sousední bázické ř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
- takové řešení, kdy všechny nebázické proměnné jsou rovny 0 a hodnoty bázický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 bázické. 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í bázickým vektorům=> nebázické 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 nebázické proměnné položí určité hodnoty a získají se
konkrétní hodnoty i pro bázické proměnné
4) 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 bázický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
5) 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í.