| Operační výzkum | ⟶ Soubor disciplín zaměřených na analýzu rozhodovacích problémů
⟶ Snaha nalézt nejlepší (optimální) řešení daného problému při respektování všech omezení, která mají vliv na chod systému |
| Podstata operačního výzkumu | ⟶ Reální systém ⟶ Definice problému ⟶ Ekonomický model ⟶ Matematický model ⟶ Řešení úlohy ⟶ Interpretace výsledků a Verifikace modelu ⟶ Implementace |
| Matematický a Ekonomický model | ⟶ Zjednodušený obraz reálného systému |
| Účelová funkce (cíl analýzy) | ⟶ Sledované kritérium optimalit
⟶ Funkce nproměnných (lineární či nelineární, většinou jedna) |
| Proměnné (procesy) | ⟶ Reálné aktivity probíhající s jistou intenzitou
⟶ Hodnoty odpovídají intenzitám jednotlivých procesů |
| Omezující podmínky (činitelé) | ⟶ Omezení mající vliv na intenzitu procesů
⟶ Většinou rovnice či nerovnice |
| Parametry (vzájemné vztahy) | ⟶ Jsou mezi procesy, činiteli a cílem analýzy
⟶ Jejich hodnoty nemůže uživatel ovlivňovat |
| Úloha lineárního programování (LP) | ⟶ Jsou-li všechny funkce jsou lineární |
| Úloha nelineárního programování (NLP) | ⟶ Je-li alespoň jedna z funkcí nelineární |
| Matematický model úlohy LP | ⟶ Nalézt extrém účelové funkce na soustavě vlastních omezení za podmínek nezápornosti |
| Grafické řešení úlohy LP | ⟶ zvolíme souřadnicový systémos x1a x2
⟶ znázorníme všechna omezení modelu
⟶ najdeme jejich průnikv prvním kvadrantu
⟶ znázorníme účelovou funkci
⟶ rovnoběžně ji posuneme tak, aby se dotkla průniku množin (shora nebo zdola)
⟶ v bodě (popř. bodech) dotyku účelové funkce a množiny přípustných řešení je optimální řešení |
| Interpretace řešení úlohy LP - rezervy | ⟶ Vypočtené rezervy jsou ekonomickou interpretací tzv. přídatných proměnných |
| Přidatné proměnné | ⟶ Přídatné proměnnéjsou nezáporné
⟶ Přídatná proměnná v omezení typu ≤ ukazuje objem nevyužité kapacityu, ≥ ukazuje velikost překročení požadavku
⟶ Cena přídatné proměnné je vzhledem k její ekonomické interpretaci rovna nule |
| Přípustné řešení úlohy LP | ⟶ Je vektor,jehož složky splňují vlastní omezení úlohy a podmínky nezápornosti |
| Počet přípustných řešení (PŘ) | ⟶ Protože v řešení soustavy rovnic (ESR) je počet proměnných větší neý počet rovinic má úloha buď:
1. nekonečně mnoho přípustných řešení
2. žádné přípustné řešení
3. jedno přípustné řešení (extrémní případ) |
| Základnímu řešení | ⟶ Průsečík každých dvou omezení |
| Vrcholy konvexního polyedru (množiny přípustných řešení) | ⟶ Zobrazují tzv. Základní přípustná řešení |
| Optimální řešení | ⟶ Úlohy LP je takové přípustné řešení,které má nejvyšší (nejnižší) hodnotu účelové funkce. |
| O počtu optimálních řešení rozhoduje | ⟶ Množina přípustných řešení
Počet přípustných řešení (žádné, nekonečně mnoho)
Tvar množiny přípustných řešení (prázdná, omezená, neomezená)
⟶ Účelová funkce |
| Žádné optimální řešení | ⟶ Prázdná množina přípustných řešení
⟶ Neomezená hodnota účelové funkce |
| Má jedinéoptimální řešení | ⟶ MPŘ je omezená ve směru hledaného optima
⟶ Účelová funkce se MPŘ dotkne v jediném bodě
⟶ OŘ je ve vrcholu konvexního polyedru –je ZPŘ |
| Má nekonečně mnoho optimálních řešení | ⟶ MPŘ je omezená ve směru hledaného optima
⟶ Účelová funkce je rovnoběžná s hranou (stěnou) MPŘ
⟶ Alespoň jedno OŘ je ve vrcholu konvexního polyedru –ZPŘ |
| Základní věta lineárního programování (ZVLP) | ⟶ Má-li úloha LP optimální řešení,pak má také základní optimální řešení
⟶ Věta nic neříká o případu, kdy úloha LP nemá optimální řešení! |
| Důsledek základní věty lineárního programování: | ⟶ Má-li úloha LP optimální řešení, pak alespoň jedno z nich je základní přípustné řešení. |
| Význam základní věty lineárního programování: | ⟶ Optimální řešení stačí hledat mezi základními přípustnými řešeními. |
| Redukovaná cena | ⟶ O kolik je třeba zlepšit cenový koeficient, aby byl příslušný proces realizován.
⟶ O kolik se zhorší hodnota účelové funkce, když budeme nuceni realizovat příslušný proces s jednotkovou intenzitou. |
| Stínová cena (duální cena, duální proměnná) | ⟶ O kolik se zlepší z, pokud se kapacita uvolní o jednotku. |
| Stínová cena
Omezení ve tvaru nerovnice typu ≤: | ⟶ Zvětšení pravé strany rozšiřuje množinu přípustných řešení
⟶ Zlepšení řešení
maximalizace –zvýšení hodnoty účelové funkce
minimalizace –snížení hodnoty účelové funkce |
| Stínová cena
Omezení ve tvaru nerovnice typu ≥: | ⟶ Zvětšení pravé strany zmenšuje množinu přípustných řešení
⟶ Zhoršení řešení
maximalizace –snížení hodnoty účelové funkce
minimalizace –zvýšení hodnoty účelové funkce |
| Redukované a stínové ceny | ⟶ Interpretace pro redukované i stínové ceny platí jen při malých změnách (v rámci intervalu stability) |
| Celočíselnostv úlohách LP | ⟶ Množina přípustných řešení obsahuje jen celočíselné body
⟶ LINGO:funkce @gin(x1);
⟶ Při použití podmínek celočíselnostiztratíme informaci o redukovaných a stínových cenách |
