Buscar
Estás en modo de exploración. debe iniciar sesión para usar MEMORY

   Inicia sesión para empezar

level: Lineární programování

Questions and Answers List

level questions: Lineární programování

QuestionAnswer
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