Ekonomicko matematické metody I. – Lineární programování
Systémové modelování kvantifikace modelu
Modelování • Modelování je způsob zkoumání reality, při němž složitost, chování a další vlastnosti jednoho celku vyjadřujeme složitostí, chováním a vlastnostmi jiného celku – modelu. • Model je záměrně zjednodušený obraz skutečnosti vytvořený pomocí zvolených zobrazovacích prostředků. Typy modelů z hlediska záměru Normativní modely • Ukazují optimální, žádoucí stav systému Deskriptivní modely • Popisují systém a jeho chování, neobsahují kritérium Koncepční modely • Popisují koncepci nově navrhovaného systému
definice systému
konstrukce modelu
OBJEKT
SYSTÉM implementace řešení
MODEL interpretace výsledků
verifikace modelu
Vybrané E-M modely • Matematické programování – optimalizační modely • Distribuční modely • Teorie grafů, modely projektového řízení • Modely konfliktních situací • Vícekriteriální rozhodování • Strukturní analýza • Stochastické modely • Simulační modely • Modely systémové dynamiky
Typy modelů z hlediska reprezentace Ikonické (materiální) modely • stroje a předměty; • zařízení pracující na principu analogie. Symbolické modely • grafické; • slovní - verbální; • matematické – modely operačního výzkumu.
Lineární programování - Definice modelu a jeho grafické řešení
Prvky matematických modelů • Proměnné a konstanty - modelují prvky systému o endogenní, stavové - zobrazují charakteristiky vnitřního stavu systému; o exogenní, vstupní nebo výstupní - zobrazují vztahy systému a okolí. • Rovnice a nerovnice o zobrazují vazby systému. • Funkce a relace o popisují chování a další vlastnosti systému. Systém • Tvoří most mezi realitou a modelem • Záměrně zjednodušený obraz reality • Systém je neprázdná, účelově definovaná třída prvků a vazeb mezi nimi, která spolu se svými vstupy a výstupy vykazuje jako celek ve svém vývoji kvantifikovatelné vlastnosti a chování. • Nelze opomenout o účel; o strukturu: prvky, hranice, okolí, vazby; o chování: y = T(x).
Vybrané aplikace • Optimalizace výrobních programů • Směšovací úlohy, řezné plány • Rozvrhy směn • Jiné oblasti operačního výzkumu o teorie her; o dopravní úlohy; o plánování projektů; o apod.… Model lineárního programování Cíl: nalézt vázaný extrém lineární funkce více proměnných, který vyhovuje daným lineárním omezujícím podmínkám Komponenty modelu • proměnné; • omezující podmínky; • účelová (kriteriální) funkce; • podmínky nezápornosti.
-1-
Proměnné • Rozhodovací (strukturní) proměnné • Značí se xi • Zachycují počet realizací daného procesu • Vyjadřují se ve vhodných jednotkách o z hlediska cíle rozhodování; o z hlediska výpočtů. Omezující podmínky • Vymezují přípustné kombinace hodnot proměnných • Základní typy omezujících podmínek o kapacitní „ ≤ “; o požadavkové „ ≥ “ ; o určení „ = “. Účelová funkce • Vyjádřena jako skalární součin jednotkových cen proměnných a jejich hodnot • Základní typy účelových funkcí o minimalizační; o maximalizační. Podmínky nezápornosti • Požadujeme pro všechny proměnné • Zajišťují praktickou aplikovatelnost řešení Matematický zápis
Sestavení modelu • Identifikace proměnných o podle cíle řešení úlohy; o hledejte otázku – proměnné by ji měly zodpovědět. • Jednotky proměnných o volba jednotky - opět podle cíle řešení úlohy; o rozměr jednotky - aby se s proměnnými dobře pracovalo. • Identifikace omezujících podmínek (OP) o z textu zadání; o vše, co rozhodovatele limituje při rozhodování; o rovněž OP mají svoje jednotky.
• •
Účelová funkce o přímo popisuje cíl rozhodování; o opět nezapomínáme na jednotky. Podmínky nezápornosti
Grafické řešení modelu LP • Prostor řešení o nejvýše dvě rozhodovací proměnné; o libovolný počet omezujících podmínek. • Prostor požadavků o libovolný počet rozhodovacích proměnných; o nejvýše dvě omezující podmínky. Prostor řešení • Proměnné – osy souřadnic • Omezující podmínky o kapacitní, požadavkové – poloroviny; o určení – přímky. • Podmínky nezápornosti – 1. kvadrant • Účelová funkce – mapa spojnic kombinací proměnných s konstantní hodnotou ÚF Možné výsledky • Optimální řešení existuje o právě jedno optimální řešení; o nekonečně mnoho optimálních řešení. • Optimální řešení neexistuje o žádné přípustné řešení; o hodnota účelové funkce může neomezeně růst nebo klesat. Vlastnosti a omezení modelu LP • Linearita o Aditivita (sčitatelnost) o Spojitost o Neomezená záměna faktorů o Libovolná dělitelnost • Deterministický charakter • Statický charakter Specifická řešení modelu LP • Přípustné řešení • Optimální řešení • Alternativní řešení • Suboptimální řešení • Bázické řešení
-2-
Bázické řešení modelu LP • Vektorový prostor • Báze vektorového prostoru • Kanonická báze vektorového prostoru • Řešení soustavy lineárních rovnic • Řešení soustavy lineárních rovnic s parametrem • Bázické řešení modelu lineárního programování
Simplexový algoritmus • Splnění podmínek simplexového algoritmu • Výchozí bázické řešení • Test optima (vstupu) • Test přípustnosti báze (výstupu) • Přechod na nové řešení Jordanovou eliminační metodou
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í. • 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.
Podmínky simplexového algoritmu • Nezápornost složek vektoru pravých stran o stačí zkontrolovat; o pokud není splněna, lze příslušné omezující podmínky vynásobit hodnotou (-1). • Matice soustavy v kanonickém tvaru o krok 1: rovnicový tvar modelu; o krok 2: kanonický tvar modelu.
Prostor požadavků • Podmínka použití: model musí být v rovnicovém tvaru • Realizujeme pomocí tzv. doplňkových proměnných takto: o kapacitní podmínky – přičteme hodnotu doplňkové proměnné k levé straně OP o požadavkové podmínky – od levé strany OP hodnotu doplňkové proměnné odečteme o podmínky určení – rovnice, žádná transformace není potřeba • Doplňkové proměnné o přebírají jednotku omezující podmínky; o neovlivňují ÚF, vždy jim přiřazujeme nulovou sazbu; o rovněž musí být nezáporné.
Rovnicový tvar • Nerovnice vyrovnáme na rovnice • Doplňkové proměnné o značíme d, indexujeme číslem omezující podmínky; o přebírají jednotky omezující podmínky; o v účelové funkci ohodnocujeme nulovou sazbou; o požadujeme jejich nezápornost. • Přidáváme do omezujících podmínek o kapacitních s kladným znaménkem (rezerva); o požadavkových se záporným znaménkem (překročení požadavku).
Řešení modelu LP v PP • Eliminujeme různé ocenění proměnných v účelové funkci – vydělíme matici A koeficienty v účelové funkci • Zobrazíme v grafu míru uspokojení požadavků příslušnou proměnnou (v hodnotovém vyjádření) • Zakreslíme vektor požadavků a zjistíme, které kombinace proměnných tento požadavek mohou uspokojit • Nalezneme tu kombinaci proměnných, která daný požadavek uspokojí co nejlevněji (MIN) resp. co nejdráže (MAX) • Vypočteme z původních podmínek hodnoty proměnných v optimálním řešení a hodnotu účelové funkce.
Kanonický tvar • Nerovnice vyrovnáme na rovnice (doplňkové proměnné) • Zajistíme úplnou jednotkovou submatici • Pomocné proměnné o značíme p, indexujeme číslem omezující podmínky; o přebírají jednotky omezující podmínky; o v účelové funkci ohodnocujeme nevýhodnou (prohibitivní) sazbou; o požadujeme jejich nezápornost.
Použité symboly a značení • Proměnné o x … strukturní proměnné; o d … doplňkové proměnné; o p … pomocné proměnné. • Omezující podmínky … Ax ≤ b o A = (aij) … matice soustavy; o b … vektor pravých stran.
•
Účelová funkce … z = c.x o c … cenové koeficienty proměnných (jednotkové ceny)
Pomocné proměnné • Přidáváme do omezujících podmínek o požadavkových; o typu určení; o vždy s kladným znaménkem. • Interpretace • kolik jednotek zbývá do splnění omezení; • řešení s kladnou hodnotou pomocné proměnné je proto automaticky nepřípustné.
-3-
Výchozí bázické řešení • Sestavení výchozí simplexové tabulky • Identifikace bázických a nebázických proměnných • Určení hodnot proměnných ve výchozím bázickém řešení • Určení hodnoty účelové funkce Test optimality • Existuje bázické řešení s lepší hodnotou ÚF? • Záměna proměnných v bázi • Koeficient zj – cj o záporný: hodnota ÚF se zvyšuje; o kladný: hodnota ÚF se snižuje; o nulový: proměnná nemá vliv na hodnotu ÚF. • Řešení je optimální o minimalizace: zj – cj ≤ 0 pro všechna j; o maximalizace: zj – cj ≥ 0 pro všechna j. • Klíčový sloupec: maximální hodnota |zj – cj| z těch, které porušují podmínku optimality
Příklad • Farma se rozhoduje o vyhrazení části své půdy pro pěstování pšenice, ječmene a žita. o tyto plodiny mají obsadit celkem právě 140 hektarů; o potřeba chlévského hnoje je 40; 15 a 20 t/ha, k dispozici je maximálně 3000 t hnoje; o odhadované zisky v tis. Kč/ha jsou pro jednotlivé plodiny 1; 1 a 2 (bráno po řadě), je požadováno dosáhnout alespoň 200 tis. Kč zisku. • Farma chce minimalizovat dopady na životní prostředí, které vyjadřuje v „jednotkách zátěže“ (JZ/ha) a které jsou pro jednotlivé plodiny 7; 2 a 4. Na jaké ploše by měly být vysety jednotlivé plodiny?
Výpočet v simplexové tabulce
Test přípustnosti • I nové řešení musí splňovat podmínky SA • Nezáporné složky vektoru b • Známe klíčový sloupec (z testu optima) • Určíme klíčový řádek podle podílů
, kde k je index klíčového sloupce • Pouze pro aij > 0 • Minimum z těchto podílů určuje klíčový řádek Nové řešení • Jeden krok Jordanovy eliminační metody • Přesun jednotkového vektoru pod proměnnou, která vstupuje do báze • Průsečík klíčového řádku a klíčového sloupce = klíčový prvek • Klíčový řádek vydělíme klíčovým prvkem • Od ostatních řádků odečteme vhodný násobek NOVÉHO klíčového řádku Interpretace výsledku • Rozdělení proměnných na bázické a nebázické • Hodnoty všech proměnných • Hodnota účelové funkce • Relativní nevýhodnost nebázických proměnných – duální (stínové) ceny
Interpretace výsledku • Rozdělení proměnných na bázické a nebázické • Hodnoty všech proměnných o zápis vektorem bázického řešení; o zápis vektorem obecného řešení. • Hodnota účelové funkce • Matice báze B, inverzní matice báze B-1 • Relativní nevýhodnost nebázických proměnných – duální (stínové) ceny -4-
Dualita lineárních modelů • Princip: otočení úhlu pohledu o 90o
Simplexová metoda • Ověření podmínek simplexového algoritmu • Výchozí bázické řešení • Test optimality • Test přípustnosti • Přechod na nové řešení • Interpretace výsledku
Tvorba duálního modelu
Postoptimalizační úvahy • Tvorba nebázického řešení o maximální hodnota nebázické proměnné. • Analýza stability báze vzhledem ke složkám vektoru pravých stran • Analýza citlivosti řešení vzhledem ke změnám cenových koeficientů o nebázických proměnných; o bázických proměnných.
Dualita lineárních modelů • Matice koeficientů A v primárním modelu a matice AT v duálním • Vektor pravých stran b v primárním modelu a vektor cen b v duálním • Vektor cen c v primárním modelu a vektor pravých stran c v duálním • Největší problém: typ omezení a podmínky nezápornosti proměnných Vztahy dvojice duálně sdružených modelů • Primární úloha má optimální řešení xo právě tehdy, když má duální úloha optimální řešení yo . • Navíc platí cTxo = bTyo. • Nechť má primární úloha přípustné řešení x a duální úloha přípustné řešení y, pro která platí cTx = bTy, pak jsou tato řešení optimálními řešeními obou úloh. Věta o dualitě Pro dvojici duálně sdružených úloh platí buď: • obě úlohy mají přípustná řešení, pak mají i optimální řešení nebo • jedna z úloh přípustné řešení nemá, pak druhá nemá optimální řešení (buď také nemá přípustné řešení nebo má neomezenou účeovou funkci)
Suboptimální řešení • Sousední bázické řešení • Zařazení nebázické proměnné do báze • Interpretace o rozhodovací proměnná – přidání aktivity; o doplňková proměnná – změna omezení. • Změny o maximální hodnota – do hodnoty testu přípustnosti; o změna účelové funkce – o součin duální hodnoty a počtu zařazovaných jednotek proměnné. Inverzní matice báze • Základ pro všechny postoptimalizační úvahy • Značíme B-1 • Umožní spočítat výslednou tabulku z výchozí v jednom kroku • Zjistíme z výsledné tabulky na místech, kde ve výchozí tabulce byly jednotkové vektory Interval stability pravých stran • Pro jednu konkrétní složku bi • Cíl: aby výsledné řešení zůstalo přípustné • Vyjádříme parametricky jako bi + λ • Musí platit B-1b ≥ 0 • Hledáme přípustné hodnoty parametru λ
-5-
• Ekvivalentně o dolní mez změny – test přípustnosti pro i-tý sloupec matice B-1 pro kladné hodnoty; o horní mez změny – test přípustnosti pro i-tý sloupec matice B-1 pro záporné hodnoty.
Směnové rozvrhy Minimalizace počtu pracovníků ve směnách • při dodržení požadavků v jednotlivých hodinách a • umožnění odpracovat nepřerušovanou směnu.
Interval stability cen • Pro jednu konkrétní složku ci • Cíl: aby výsledné řešení zůstalo optimální • Vyjádříme parametricky jako cj + ν • Hledáme přípustné hodnoty parametru ν, aby platil test optimality o pro nebázickou proměnnou – zhoršení neomezené, zlepšení nejvýše o hodnotu testu optima; o pro bázickou proměnnou – podle poměrů testu optimality a hodnot v řádku bázické proměnné.
Program Linkosa • Doplněk MS Excel • Řeší modely LP pomocí simplexové metody • Poskytuje následující výstupy o optimální řešení; o matice alfa; o stabilita pravých stran; o stabilita cen.
Praktické aplikace modelů LP • Výrobní program • Směšovací úlohy • Řezné plány • Plán směn Směšovací úlohy Také nutriční, výživové, apod. Cíl: Hledání optimální směsi produktů různých vlastností a cen • Krmné dávky • Dietní přípravky pro lidskou výživu • Surové ropné produkty pro různé druhy prodávaných paliv • Složky barev Řezné plány • Obecně: úlohy o dělení • Hledání racionálního způsobu dělení • Dodržení podmínek o Počet kusů apod. • Kritérium o Minimalizace spotřebovaného materiálu o Minimalizace odpadu, který vzniká při dělení (řezání) ocele, kůže apod. z plátu, desky, tyče, roury apod. základního materiálu
-6-
