Teorie-emm ke zkoušce

5) Uveďte a stručně charakterizujte dva základní způsoby grafického řešení modelů lineárního programování. Za jakých podmínek je možné je použít?

PROSTOR ŘEŠENÍ

• 2 rozhodovací proměnné

• libovolný počet omezujících podmínek

• proměnné – osy souřadnic

• omezující podmínky – kapacitní, požadavkové, určené (přímka)

• podmínky nezápornosti – 1. kvadrant

• účelová funkce – mapa spojnic kombinovaných proměnných s konstantní hodnotou účelové funkce

PROSTOR POŽADAVKŮ

• více proměnných

• 2 omezující podmínky

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

právě jedno optimální řešení nekonečně OPT

žádné přípustné řešení přípustné řešení, ale hodnota ÚF není omezena

téma 2: GRAFICKÉ ŘEŠENÍ MODELU LP V PROSTORU POŽADAVKŮ. BAZICKÁ A NEBAZICKÁ ŘEŠENÍ

1) Uveďte a stručně komentujte základní vlastnosti modelů lineárního programování

LINEARITA

• aditivita (sčitatelnost)

• spojitost

• neom. záměna faktorů

• libovolná dělitelnost

DETERMINISTICKÝ CHARAKTER – nepracuje s náhodou, není neurčitý

STATICKÝ CHARAKTER – neumožní fak. času, pracuje s náhodou

DYNAMICKÝ CHARAKTER – umí pracovat s časem

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Í – není optimální, ale vyhovuje omezujícím podmínkám

OPTIMÁLNÍ ŘEŠENÍ – nejlepší přípustné

ALTERNATIVNÍ ŘEŠENÍ – model má nekonečně mnoho řešení OPT, má stejnou hodnotu jak ÚF

SUBOPTIMÁLNÍ ŘEŠENÍ – poměrně dobré řešení, téměř optimální

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?

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

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?

6) 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ů.

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

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

I. nezápornost složek pravých stran

II. matice soustavy v kanonickém tvaru

• rovnicový tvar

• kanonický tvar + pomocné proměnné přidáním do omezujících podmínek

  • pokud je pomocná proměnná + tak určuje, že jsme nesplnili požadavek