4EK213 Lineární modely Flashcards
Ekonomický model
Vyjádření rozhodovacího problému formou jeho slovního, případně číselného popisu
Matematický model
Matematická formalizace ekonomického modelu rozhodovacího problému
Matematické programování
Disciplína operačního výzkumu, která se zabývá řešením optimalizačních úloh, ve kterých se jedná o optimalizaci kriteriální funkce na množině variant, které jsou určeny soustavou omezení ve formě lineárních nebo nelineárních rovnic či nerovnic
Alternativní optimální řešení
Způsob zakončení výpočtu, při kterém nemá úloha lineárního programování pouze jediné optimální řešení
Degenerované základní řešení
Takové základní řešení úlohy lineárního programování, ve kterém je alespoň jedna hodnota základní proměnné rovna nule
Ekvivalentní soustava rovnic
Soustava lineárních rovnic získaná převedením soustavy vlastních omezení na soustavu rovnic pomocí přídatných proměnných
Kanonický tvar soustavy lineárních rovnic
Takový tvar soustavy m rovnic, ve kterém obsahuje matice strukturních koeficientů jednotkovou submatici m×m
Intervaly stability cenových koeficientů
Intervaly, jež určují meze, ve kterých se mohou měnit cenové koeficienty, aby stávající řešení zůstalo optimální (změní se pouze redukované a stínové ceny a hodnota účelové funkce)
Intervaly stability pravých stran
Intervaly, jež určují meze, ve kterých se mohou pohybovat hodnoty pravé strany omezujících podmínek, aby stávající optimální řešení zůstalo přípustné
Nepřípustné řešení
Řešení, které nevyhovuje alespoň jedné omezující podmínce úlohy
Omezující podmínky
Soustava vlastních omezení, podmínky nezápornosti, případně další speciální podmínky definované v úloze lineárního programování
Optimální řešení úlohy lineárního programování
Nejlepší ze všech přípustných řešení
Podmínky nezápornosti
Omezení, která zabezpečují, že budou všechny proměnné modelu kladné, případně nulové
Pomocná účelová funkce
Minimalizační účelová funkce doplněná k modelu s cílem vyloučit z něj všechny pomocné proměnné a získat tak výchozí základní řešení úlohy lineárního programování
Pomocné proměnné
Umělé doplněné proměnné k ekvivalentní soustavě rovnic s cílem získat kanonický tvar
Přídatné proměnné
Proměnné, které vyjadřují rozdíl mezi kapacitou zdroje a jeho čerpáním (u omezení typu ≤), případně mezi úrovní plnění a minimální požadavkem (u omezení typu ≥), které se doplňují k modelu pro převedení soustavy nerovnic na soustavu rovnic
Přípustné řešení úlohy lineárního programování
Řešení, které splňuje všechny omezující podmínky modelu, tj. soustavu vlastních omezení i podmínky nezápornosti
Redukované ceny
Koeficienty příslušející strukturním proměnným modelu, které vyjadřují míru výhodnosti jednotlivých procesů
Rozšířená soustava rovnic
Soustava vzniklá z ekvivalentní soustavy rovnic po doplnění pomocných proměnných
Simplexová metoda
Iterační postup pro řešení úloh lineárního programování
Simplexová tabulka
Tabulka, ve které se realizuje výpočet simplexovou metodou
Stínové ceny
Koeficienty, příslušející omezujícím podmínkám ve tvaru nerovnic, vyjadřující změnu hodnoty účelové funkce na jednotku pravé strany
Účelová (kritériální) funkce
Vyjádření cíle optimalizace v matematické podobě
Vlastní omezení
Podmínka ve tvaru rovnice či rovnice, vyjadřující například omezenou kapacitu zdrojů, technologické vztahy, požadavky odběratelů apod.
Základní proměnné
Proměnné, kterým v kanonickém tvaru soustavy lineárních rovnic odpovídá jednotkový vektor – jejich hodnoty jsou rovné hodnotám pravých stran
Základní řešení úlohy lineárního programování
Každé základní řešení ekvivalentní soustavy rovnic, které vyhovuje podmínkám nezápornosti; má maximálně tolik nenulových proměnných, kolik je lineárně nezávislých řádků této soustavy
Základní věta lineárního programování
Má-li úloha lineárního programování optimální řešení, má také optimální řešení základní; podle této věty stačí hledat optimální řešení pouze mezi základními řešeními úlohy lineárního programování (kterých je konečný počet)
Bivalentní proměnné
Proměnné, které fungují jako “přepínače” nějakého stavu – nabývají pouze hodnot 0 nebo 1
Celočíselné programování
Řešení úloh lineárního programování, ve kterých je požadováno, aby všechny nebo některé proměnné nabývaly pouze celočíselných hodnot
Cílová místa (odběratelé)
Místa, do kterých v dopravním problému (případně v jiných distribučních úlohách) směřují zásilky
Degenerované řešení v dopravním problému
Řešení, ve kterém je v tabulce dopravního problému obsazeno méně než m+n-1 polí
Dopravní problém
Úloha, ve které se jedná o minimalizaci nákladů při distribuci zboží od zdrojů (dodavatelů) do cílových míst (k odběratelům)
Vyrovnaný dopravní problém
Dopravní problém, ve kterém se součet kapacit dodavatelů rovná součtu požadavků odběratelů
Nevyrovnaný dopravní problém
Dopravní problém, ve kterém se součet kapacit dodavatelů nerovná součtu požadavků odběratelů
Fiktivní činitel
Zdroj nebo cílové místo doplněné do modelu nevyrovnaného dopravního problému s takovou kapacitou nebo požadavkem, aby byl tento problém převeden na vyrovnaný
Gomoryho metoda
Metoda ze skupiny řezných nadrovin pro řešení úloh celočíselného programování
Indexní metoda maticového minima
Metoda pro výpočet výchozího základního řešení dopravního problému, která prioritně obsahuje pole s minimálním ohodnocením přepravy
Modifikovaná distribuční metoda MODI
Metoda pro výpočet optimálního řešení dopravního problému
Metoda severozápadního rohu
Metoda pro výpočet výchozího základního řešení dopravního problému, která obsahuje pole bez ohledu na výhodnost či nevýhodnost přepravy (vybere vždy pole v tabulce vlevo nahoře)
VAM
Metoda pro výpočet výchozího základního řešení dopravního problému
Metoda větvení a mezí
Kombinatorický postup pro hledání množiny příbuzných řešení, určený pro řešení celočíslných úloh lineárního programování
Obecný distribuční problém
Distribuční úloha, ve které nejsou uvedeny požadavky odběratelů a kapacity dodavatelů ve stejných jednotkách
Základní řešení dopravního problému
Řešení které obsahuje maximálně m+ n-1 nenulových proměnných
Zdroje (dodavatelé)
Místa, ze kterých jsou v dopravním problému (případně v jiných distribučních úlohách) rozváženy zásilky