Lineární modely MB141, 4. část David Krum 17.4. 2024 Fibonacciho posloupnost 1,1,2,3,5,8,13,21,34,55,... Rekurentní (implicitní) zadání: *1 = 1, x2 = 1, Xn+2 = *n+ *n+l Explicitní řešení: xn = Tradiční postup: řešením charakteristického polynomu a dosazením do „předpokládaného tvaru". My si řešení odvodíme užitím maticového počtu a teorie vlastních čísel. Fibonacciho posloupnost — vlastní čísla 0 i 1 i Xn \ Xn+l) Xn+1 \ *n + Xn+i J ÍXn+1 \Xn+2 Za počáteční vektor můžeme volit w = (xo,xi) = (0,1) (je to o něco pohodlnější), protože Aw = (1,1) = (xi,X2). Pro matici A = (° \) spočítáme \A — XE\: -A 1 1 1 - A = -A(l -A)-1 = A2-A-1 = = A- A - 1 - V5 (Diskriminant kvadratické rovnice je 1 + 4 = 5.) Kořeny Ai = 1+2 , A2 = 1~2 vyjadřují tzv. zlatý řez. Fibonacciho posloupnost - Vlastní vektor pro Ai = vlastní vektory i+Vš A - XiE = 1 í-Vš í+Vš 2 + i-Vš 2 0 u = 1 i + Vš Vlastní vektor pro A2 = 1 ^ A-X2E = 1 + Fibonacciho posloupnost — dokončení výpočtu Víme, že Au = Ail/, Av = A2t/: a tedy i Anu = Xnľu, Anv = \%v. Vektor w vyjádříme v bázi (l/, \/) jako 1/1/ = ~^{u — v) a dostáváme Anw = -^"(u - v) = -^=(A?ií - \n2v). xn se vyskytuje (např.) jako 1. složka vektoru Anw, odkud již Rekurentní posloupnosti (lineární) Fibonacciho posloupnost je nejznámějším příkladem rekurentní posloupnosti. Obecněji se jedná o posloupnosti zadané počátečními podmínkami a rekurentním vztahem pro vytváření nových členů. V explicitní formuli se vždy objeví kořeny charakteristického polynomu (vlastní čísla) v příslušné mocnině. Vlastní vektory není nutné počítat, pokud využijeme metodu neurčitých koeficientů: koeficienty u mocnin kořenů najdeme tak, aby vyhověly všem počátečním podmínkám, což vede na soustavu lineárních rovnic. Koeficienty charakteristického polynomu přímo odpovídají koeficientům rekurentního vztahu, jak si i na dalším příkladu ukážeme. Příklad na rekurentní posloupnost I Najděte explicitní vyjádření rekurentní posloupnosti x0 = 1, xi = 2. x2 = 4 xn+3 = xn - 2xn+i + 2xn+2- Řešení: Matice příslušného lineárního operátoru je 0 1 o' 0 0 1 1-2 2 charakteristický polynom počítáme -A 1 0 0 -A 1 1 -2 2-A = -A -A 1 0 1 -2 2 - A 1 2-A = -A3 + 2A2 - 2A + 1 = -(A - 1)(A2 - A + 1) = -(A-l) A- 1 + iVš' X- 1 - iy/3 Příklad na rekurentní posloupnost Pro kořeny Ai = 1, A2 = 1+2 , A3 = 1~1 předpokládáme řešení ve tvaru Xn = a\1 + bXZ + c\nz. Dosazením n = 0,1,2 do počátečních podmínek dostáváme systém lineárních rovnic a + b+c = 1 1 + /V3 i_/V3 a+---6+---c = 2 , -l + iVŠu , -1-/V3 a+---b+---c = 4 Odečtením třetí od druhé rovnice a jejich sečtením: b+ c = -2 2a + iVŠ(b - c) = 6 Příklad na rekurentní posloupnost Ze soustavy a + b+c = 1 b+c = -2 2a + / - c) = 6 snadno odvodíme a = 1 — (—2) = 3.b—c = 0.b = c = —1 Dostáváme explicitní formuli: 1 + /V3V (l-iVŽ n / ^\ n l 1 + ;\/3 \ Xn = 3 - „Zkouška": x3 = x0 - 2xi + 2x2 = 1 - 2 • 2 + 2 • 4 = 5, X3 = 3-|^V-Í^V = 3-(-1)-(-D = 5. Komentáře k rekurentním posloupnostem ► V předchozím příkladu lze charakteristický polynom sestavit přímo z rovnice xn+3 — 2xn+2 + 2xn+i — xn = 0 jako A3 — 2A2 + 2A — 1, tj. posunutí indexů vůči n odpovídají mocninám A. ► Fibonacciho posloupnost se vyskytuje ve spoustě modelů růstu. Zlatý řez je současně limitním poměrem (r? —> oc) sousedních členů. ► Protože se spokojíme s vyjádřením xn, nepotřebujeme celý vektor a můžeme úlohu řešit metodou neurčitých koeficientů. ► Obdobné úvahy si objeviv matematické analýze při řešení obyčejných diferenciálních rovnic (derivace je lineárním operátorem na funkcích). ► Požadavky: Umět sestavit charakteristický polynom, spočítat jeho kořeny, metodou neurčitých koeficientů z počátečních podmínek dopočítat koeficienty do explicitního vyjádření. Rozumět podstatě maticové konstrukce. Leslieho model Leslieho populační model popisuje vývoj populace v čase lineárním operátorem (čtvercovou maticí). ► Populace je rozdělena do věkových kategorií stejných časových délek. ► Jedna iterace modelu odpovídá přesunu jedinců z mladší do následující starší kategorie a započítání nového potomstva. ► Model počítá se ztrátami (úhyn, porážka, prodej, atp.). Míru/pravděpodobnost přežití mezi kategoriemi vyjadřujeme číslem z intervalu [0,1] (0 nikdo, 1 všichni). ► Na rekurentní posloupnosti můžeme pohlížet jako na speciální případ: vytvoření nového členu = potomstvo, „nulový úhyn", koeficient přežití = 1. ► Matici obvykle sestavujeme od nejmladší kategorie po nejstarší (tj. obráceně než u rekurentních posloupností). ► Sloupce odpovídají vstupním kategoriím, řádky výstupním. Příklad se slepicemi Populace: vektor v = (a, £», c, d). a . . . kuřata, b ... mladé slepice, c ... střední slepice, d ... staré slepice, Pravděpodobnosti přežití: Potomstvo: a b 60% = 3/5 b ->• c 80% = 4/5 c c/ 75% = 3/4 a 0 6 2 c 5 c/ 2 Leslieho matice: L /O 2 3/5 0 5 2\ 0 4/5 V 0 0 rronův (stacionární) vektor, populační dynamika v . .. počáteční stav populace, Lv ... stav po 1 období, L2v ... stav po 2 obdobích, ... Teorie předvídá, že Leslieho matice má (při smysluplných parametrech populace) tzv. dominantní vlastní číslo A, které je kladné a dokonce v absolutní hodnotě větší než všechna ostatní. Pro model je podstatné pouze toto A a jeho vlastní vektor, kterému říkáme Perronův nebo stacionární Za obvyklých okolností poměr věkových kategorií v populaci konverguje k Perronovu vektoru. Dominantní vlastní číslo A určuje, zda populace roste ... A > 1, je stabilní ... A = 1, nebo vymírá ... A < 1. Chov slepic I Spočítáme charakteristický polynom matice L (použil se iterovaný Laplaceův rozvoj podle posledního sloupce): -A 2 5 3/5 -A 0 0 4/5 -A 0 0 3/4 — -2 • 18 12 2 0 0 -A 3/5 -A 0 -A 2 5 2 0 4/5 -A -A 3/5 -A 0 0 0 3/4 0 4/5 -A 25 -A 5 3/5 -A 0 4/5 -A -A 2 3/5 -A 25 25 Chov slepic II Dominantní vlastní číslo: A « 1.69356. Perronův vektor: (13.4928,4.78027,2.25809,1). Závěr: Protože A > 1, chov se rozrůstá. Další úloha: Kolik máme prodávat kuřat, aby byl chov stabilní? Řešeni: Pravděpodobnost přežiti kuřat 4/5 zmenšíme o číslo p udávající prodávaná kuřata. Upravená Leslieho matice musí mít dominantní vlastní číslo 1. Z této podmínky určíme p, aniž bychom počítali charakteristický polynom: -1 2 5 2 3/5-p -1 0 0 0 4/5 -1 0 0 0 3/4 -: 0 Chov slepic Na rozdíl od minulého výpočtu povedeme rozvoj podle prvního sloupce abychom si člen s p „nerozbili": 0= L - E -1 0 4/5 -1 o : l-(i-p 0 0 -1 -( ;h 2 4/5 0 -1 0 4 5 2 3/4 -1 ~ 5 3/4 -1 2 0 = l-'i-" „ 4 13 2 H---- 5 2 3 5 P = 36 5 83 P = Odpověď: Prodáváme p = 3 ___ 5 ~ 36 ~ 180 ^ z počtu kuřat. Obrácená úloha O hejnu slepic je známo, zeje stabilní, potomstvo vychovávají pouze střední slepice a poměr kategorií je 8:4:2:1. Určete kolik (průměrná) střední slepice vyvede kuřat. Řešení: V prvním řádku matice L bude jen jedna nenulová buňka ve sloupci středních slepic s parametrem p, o který se zajímáme. Ostatní neznámé parametry pro pravděpodobnost přežití zatím označme x,y,z. Tedy /O 0 p 0\ x 0 0 0 0 y 0 0 ' \0 0 z 0/ Obrácená úloha Je-li ovšem populace stabilní, je A = 1 dominantním vlastním číslem pro vlastní vektor v — (8, 4, 2,1), tj. vektor v je řešením homogenní soustavy s maticí L-E = 0 p X -1 0 0 0 y -i 0 \o 0 z -1/ Z prvního řádku máme rovnici —8 + 2p = 0, tedy p = 4. Odpověď: Střední slepice průměrně vyvede 4 kuřata. Poznámka: Kdyby nás zajímaly parametry x,y,z, snadno je rovněž dopočítáme z (L — E)v = 0 jako x = y = z = 1/2. Komentáře k Leslieho modelu ► Model lze rozšířit o další možnosti vývoje — „dokupovaní" dospělých jedinců (migrace u volně žijících organismů), setrvání v nevyšší věkové kategorii, atd. ► Model popisuje vývoj diskrétně, tj. po pevně zvolených časových skocích (sezóny, generace). Vývoj v plynulé časové ose popisují spojité modely (matematická analýza). ► Požadavky: Znát formát Lesliho matice a umět ji sestavit pro slovně zadanou úlohu. Umět spočítat dominantní vlastní číslo a jeho vlastní vektor a interpretovat výsledek. Poradit si s obráceně formulovaným typem zadání — jak vypadají pravidla pro přírůstek potomstva a pravděpodobnosti přežití, když známe dynamiku populace, atp. Markovské procesy (řetězce) V markovských procesech v roli „členů posloupnosti" nebo „generací" vystupují stavy určitého systému. Systém může ve stejném stavu setrvávat nebo přejít do jiného. Vše se odehrává nahodile (pravděpodobnostně). Cílem úlohy bývá obvykle zjišťování rozložení pravděpodobnosti, jak často se systém nachází v tom kterém stavu (za dostatečně dlouhou dobu sledování). Pravděpodobnosti přechodů mezi stavy zaznamenáváme v přechodové matici, kde opět sloupce odpovídají vstupním a řádky výstupním stavům. Před konstrukcí matice může být praktické znázornění přechodů ohodnoceným grafem či nedeterministickým automatem. Příklad markovského procesu I Pepíček je nemocný a dokáže se zabavit jen jednoduchou hrou, kde podle hodnoty na kostce pohybuje figurkou mezi třemi políčky — modrým, zeleným a červeným. Pohyb se řídí těmito pravidly: ► Z modrého pole se figurka přesouvá na zelené pole, padne-li 1 nebo 2, na červené pole, padne-li 3 nebo 4. Pro 5 a 6 zůstává na místě. ► Ze zeleného pole se figurka přesouvá na modré při liché hodnotě na kostce, při sudé hodnotě zůstává na místě. ► Z červeného pole se figurka přesouvá na zelené při hodnotách 1-4, jinak zůstává na místě. Určete pravděpodobnosti, se kterými se bude figurka po dostatečně dlouhém hraní nacházet na modrém, zeleném, resp. červeném poli. Příklad markovského procesu II Vlastnosti markovských procesů ► Na rozdíl od předchozích modelů jsou možné jakékoli přechody mezi stavy. ► Model je pravděpodobnostní, tedy váhy přechodů musí být čísla mezi 0 a 1. ► Figurka „nikdy neumře", tj. z každého stavu se určitě někam dostane. Součet odchozích pravděpodobností z každého stavu je 1, a tedy i součty ve sloupcích markovské matice jsou 1. ► Nic „nepřirůstá ani nevymírá", stacionární vektor je určen dominantním vlastním číslem A = 1. V markovských procesech se tedy vůbec nezabýváme charakteristickým polynomem a rovnou řešíme homogenní soustavu (M — E)v = 0. ► Stacionární vektor v chceme mít pravděpodobnostní, tj. normalizujeme ho na násobek, v němž je součet složek 1. To odpovídá vydělení libovolného stacionárního vektoru součtem jeho složek. Řešení Pepíčkovy hry M - E = 2/3 1/2 /3 -1/2 /3 0 '1/3 0 0 -1/2 , o 1/2 = 8, x = 6, i -| + / <- + 4/3 + Zvolme z = 3. Pak y = 8, x = 6, tj. v = (6, 8, 3). Stacionární vektor v normalizujeme vydělením 6 + 8 + 3 = 17 na vektor w = (6/17, 8/17, 3/17). Odpověď: Figurka se bude s pravděpodobností 6/17 nacházet na modrém, s pravd. 8/17 na zeleném a s s pravd. 3/17 na červeném poli. Stabilita markovských procesů Počáteční stav systému odpovídá vektoru standardní báze — figurka určitě stojí na jednom poli a určitě nestojí na ostatních. Mocniny matice M aplikované na počáteční vektor v určují rozdělení pravděpodobnosti mezi stavy po příslušném počtu kol: v . .. start, Mv .. . rozdělení po 1 kole, M2v ... rozdělení po 2 kolech, atd. Zajímáme se zejména o tzv. ergodické markovské procesy. V nich je stacionární vektor jediný a je limitou iterací v, Mv, M2v,... bez ohledu na volbu počátečního vektoru v. Stabilitu lze zaručit požadavkem, aby se mezi jakýmikoli stavy bylo možné přesunout několika tahy s nenulovou pravděpodobností. Příklady ergodických a neergodických procesů (1) V Pepíčkově hře nebylo možné se přímo dostat např. ze zeleného pole na červené. Nicméně dvěma tahy se tam dostaneme přes modré pole s pravděpodobností | • | = g > 0. Podobně se z červeného pole dostaneme na modré přes zelené. Ostatní dvojice stavů mají už přímé přechody nenulové, proces je tedy ergodický. (2) Dvoustavový markovský proces daný jednotkovou maticí je příkladem nestabilního. Figurka zůstává na místě, v — Ev — E2v = ..., tj. výsledek je určen počátečním vektorem. Všechny vektory jsou vlastní pro A = 1, a tedy stacionární. (3) Proces daný maticí M = ^o 1/2) s'ce nesP'"uJe „možnost úniku" z 2. stavu, ale v, Mv, M2v,... konverguje k vektoru (1, 0). Pozitivní a primitivní matice Matici nazýváme pozitivní, má-li všechny buňky kladné. Matici nazýváme primitivní, má-li pro nějaké n £ N pozitivní r?-tou mocninu. (Pozitivní matice je tedy rovnou primitivní pro volbu n = 1.) Matice Mn reprezentují pravděpodobnosti přechodů n tahy. Primitivita přechodové matice tedy přesně odpovídá dříve vyslovenému požadavku pro ergodicitu. Je-li Mn pozitivní, jsou pozitivní i vyšší mocniny. Při testování primitívnosti tedy můžeme „spěchat" a testovat rovnou mocniny M, M2, M4, M8,____Počítání provádíme v booleovské logice (nula 0, nenula +). Příklad: + + o\2 /+ + +\ (+ + +\2 /+ + + + + + = + + + , + + + = + + + + 00/ V+ + 0/ V++0/ V+ + + Komentáře k markovským procesům ► Matice s nezápornými vstupy a součty sloupců 1 se nazývá stochastická. ► I markovské procesy lze studovat ve spojité variantě. ► 0 markovských procesech se hovoří jako o „bezpaměťových". Jedinou známou informací v každém okamžiku je stav (kde se figurka nachází), ale nepamatujeme si, jak jsme se do něj dostali. ► Požadavky: Rozumět podstatě markovských procesů, umět přepsat slovní zadání do přechodové matice, spočítat pravděpodobnostní stacionární vektor, interpretovat výsledek. Poradit si s obráceným zadáním —jak doplním přechodovou matice, když znám stacionární vektor. Umět ověřit primitivnost matice. Úloha o jídle Hostinský se chystá nabízet k polednímu menu dvě jídla: guláš a ovocné knedlíky. Příprava jedné porce guláše zabere 0.1 hodiny, jedné porce ovocných knedlíků 0.3 hodin. Kuchaři mají na přípravu jídla 10 („člověko") hodin. Na přípravu houskového knedlíku do guláše i pro těsto na ovocné knedlíky je třeba shodně 0.1 kg mouky pro jednu porci. Ve spíži je 6 kg mouky. Čistý zisk z 1 porce guláše je 20 Kč, z 1 porce ovocných knedlíků 30 Kč. Předpokládáme, že všechno navařené jídlo se prodá. Určete optimální počet porcí guláše a ovocných knedlíků. Přepis do rovnic a nerovnic Omezení: Účelová funkce: 0.1x + 0.3y < 10 O.lx + O.ly < 6 x > 0 y >o c = 20x + 30y Odpověď: Hospodský dosáhne maximálního zisku 1400 Kč pro 40 porcí guláše a 20 porcí ovocných knedlíků. Obecná formulace úlohy lineárního programování Řešená úloha je příkladem úlohy lineárního programování (lineární optimalizace). Typickou úlohu tvoří trojice informací: ► nerovnice omezení ve tvaru a\x\ + a2X2 + • • • + anxn < b, ► „triviální" omezení ve tvaru x; > 0 (nezapomínat na ně!), ► účelová funkce c = wixi + 1/1/2x2 + • • • + wnxn. Cílem optimalizace je maximalizovat hodnotu účelové funkce při dodržení omezení. Geometricky rovnice odpovídají nadrovinám v r?-rozměrném prostoru, nerovnice poloprostorům (viz obecná rovnice v afinní geometrii). anipulace s nerovnicemi I Rovnici aiXi + 32x2 H-----1- 3nxn = b lze nahradit dvojicí nerovnic aixi + a2x2 H-----h anxn < b, aixi + a2x2 H-----h a„x„ > b. Obráceně, z nerovnice aixi + a2x2 H-----h anxn < b vytvoříme rovnici aixi + a2x2 H-----h a„x„ + an+ixn+i = b přidáním doplňkové proměnné xn+\ spolu s omezením x„+i > 0. □ s1 anipulace s nerovnicemi II Nerovnice lze smysluplně sčítat, jen pokud souhlasí symbol nerovnosti (< nebo >). Násobení záporným skalárem otáčí symbol nerovnosti. Pokud koeficienty z omezení přepíšeme do matice A a koeficienty z účelové funkce do vektoru w, můžeme (s využitím výše popsaných vlastností nerovnic) úlohu LP přepsat do tvaru: Ax < b, x > 0, c — i/i/x. případně Ax — b. x > 0. c — i/i/x. (Případy s omezeními typu x; < 0, atp., se nebudeme zabývat.) Řešení úlohy LP simplexovou metodou Geometricky si lze úlohu představit stále jako přikládání nadroviny účelové funkce k mnohostěnu určenému omezeními. Bodům mnohostěnu říkáme přípustná řešení (protože splňují všechna omezení). Přípustným řešením s maximálním hodnotou účelové funkce říkáme optimální řešení Optimálním řešením bývá často jediný bod, ale může jít i o jakoukoli stěnu mnohostěnu. (Stěna je definována velmi obecně bez ohledu na rozměr a zahrnuje tak např. hrany.) Geometrické řešení je vhodné nanejvýš pro dimenzi 2, už v dimenzi 3 by bylo velmi komplikované. Principem simplexové metody je cestování po sousedních vrcholech mnohostěnu tak, aby se co nejvíc zlepšovala hodnota účelové funkce. Pokud se nelze přesunout na sousední vrchol s vyšší hodnotou účelové funkce, algoritmus končí. Inicializace simplexové metody Úlohu LP zformulujeme do tvaru: Ax = b. x > 0. c — wx. Následně sestavíme simplexovou tabulku: — koeficienty w účelové funkce c nuly hodnota c původní koeficienty omezení z matice A koeficienty doplňk. prom. pravé strany b (Triviální omezení x/ > 0 do tabulky nezaznamenávame.) Krok simplexové metody Simplexovou tabulku postupně upravujeme pomocí Gaussovy eliminační metody takto: ► Vybereme první sloupec se záporným koeficientem v záhlaví (odděleném „nultém" řádku). ► Zaměříme se na řádky s kladnou hodnotou a,y ve vybraném sloupci a výběrem z nich ten s maximálním poměrem aij/b;. ► Normalizujem pivota a,y na 1 vydělením řádku a,y. ► Eliminujeme ostatní řádky násobky /-tého (včetně záhlaví). Ve vektoru pravých stran b se v průběhu výpočtu nesmí objevit záporné číslo. To by indikovalo „vyběhnutí z mnohostěnu" způsobené nesprávně zvoleným pivotem. Hodnota c v pravém horním rohu by měla růst (nebo aspoň neklesat). Může se stát, že se v průběhu výpočtu musíme vrátit do sloupce víc vlevo, než jsme už byli. Konec výpočtu Výpočet končí v momentě, kdy ze záhlaví zmizí záporná čísla. Výsledná simplexová tabulka se nazývá optimální. Z tabulky ihned vyčteme optimální hodnotu účelové funkce c. Hodnoty proměnných z vektoru x se objeví ve vektoru pravých stran a proměnným je přiřadíme podle pivotů v maticové části tabulky (ukážeme na příkladu). Pokud pivot v některém „základním" sloupci chybí (sloupec byl přeskočen nebo pivot přepsán při eliminaci), má příslušná proměnná hodnotu 0. (Dané zboží vůbec nevyrábíme, roli proměnné převzala některá z „jalových" pomocných proměnných.) Nalezené optimální řešení můžeme prověřit kontrolou splnění omezení. Příklad na simplexovou metodu Lesník obnovuje les na pasece a chce tam vysadit 1000 stromů ze směsi smrku, modřínu, buku a dubu. Platné vyhlášky a doporučení pro stabilitu lesa mu ukládají dodržet tyto zásady: ► Listnatých stromů musí být aspoň 40%. ► Modřínu a dubu (meliorační a zpevňovací dřeviny) musí být aspoň 20%. ► Smrku bude maximálně 40%. ► Každý z navrhovaných druhů bude zastoupen aspoň 5%. Ceny sazenic v korunách jsou: smrk modřín buk dub 10 15 15 20 Přiklad s lesem — formalizace zadání Ze zadání máme: s + m + b + d = 1000, b+d > 400, m + d > 200, s < 400, s, m, b, d > 50, s, m,b,d > 0, c = -lOs - 15m - 156 - 20c/. To neodpovídá formátu pro užití simplexové metody. Provedeme úpravy omezení i účelové funkce — dáme „dotaci" 30 Kč za každý vysazený strom: s + m + b+ d < 1000, s + m < 600, s + b < 800, s < 400, m + b + oř < 950, s + b+d < 950, s + m + c/< 950, s + m+/b< 950, s,m,b,d>0, c = 20s + 15m + 156 + 10c/. Přiklad s lesem — inicializace 20 -15 -15 -10 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1000 1 1 0 0 0 1 0 0 0 0 0 0 600 1 0 1 0 0 0 1 0 0 0 0 0 800 1 0 0 0 0 0 0 1 0 0 0 0 400 0 1 1 1 0 0 0 0 1 0 0 0 950 1 0 1 1 0 0 0 0 0 1 0 0 950 1 1 0 1 0 0 0 0 0 0 1 0 950 1 1 1 0 0 0 0 0 0 0 0 1 950 Přiklad s lesem — po 1. kroku SM 0 - 15 -15 -10 0 0 0 20 0 0 0 0 8000 0 1 1 1 1 0 0 -1 0 0 0 0 600 0 1 0 0 0 1 0 -1 0 0 0 0 200 0 0 1 0 0 0 1 -1 0 0 0 0 400 1 0 0 0 0 0 0 1 0 0 0 0 400 0 1 1 1 0 0 0 0 1 0 0 0 950 0 0 1 1 0 0 0 -1 0 1 0 0 550 0 1 0 1 0 0 0 -1 0 0 1 0 550 0 1 1 0 0 0 0 -1 0 0 0 1 550 Přiklad s lesem — po 2. kroku SM 0 0 - 15 -10 0 15 0 5 0 0 0 0 11000 0 0 1 1 1 -1 0 0 0 0 0 0 400 0 1 0 0 0 1 0 -1 0 0 0 0 200 0 0 1 0 0 0 1 -1 0 0 0 0 400 1 0 0 0 0 0 0 1 0 0 0 0 400 0 0 1 1 0 -1 0 1 1 0 0 0 750 0 0 1 1 0 0 0 -1 0 1 0 0 550 0 0 0 1 0 -1 0 0 0 0 1 0 350 0 0 1 0 0 -1 0 0 0 0 0 1 350 Přiklad s lesem — po 3. kroku SM 0 0 0 - 10 0 0 0 5 0 0 0 15 16250 0 0 0 1 1 0 0 0 0 0 0 -1 50 0 1 0 0 0 1 0 -1 0 0 0 0 200 0 0 0 0 0 1 1 -1 0 0 0 -1 50 1 0 0 0 0 0 0 1 0 0 0 0 400 0 0 0 1 0 0 0 1 1 0 0 -1 400 0 0 0 1 0 1 0 -1 0 1 0 -1 200 0 0 0 1 0 -1 0 0 0 0 1 0 350 0 0 1 0 0 -1 0 0 0 0 0 1 350 Přiklad s lesem — optimální tabulka 0 0 0 0 10 0 0 5 0 0 0 5 16750 0 0 0 1 1 0 0 0 0 0 0 -1 50 0 1 0 0 0 1 0 -1 0 0 0 0 200 0 0 0 0 0 1 1 -1 0 0 0 -1 50 1 0 0 0 0 0 0 1 0 0 0 0 400 0 0 0 0 -1 0 0 1 1 0 0 0 350 0 0 0 0 -1 1 0 -1 0 1 0 0 150 0 0 0 0 -1 -1 0 0 0 0 1 1 300 0 0 1 0 0 -1 0 0 0 0 0 1 350 Přiklad s lesem — odpověď a diskuze Lesník má vysadit 400 smrků, 200 modřínů, 350 buků a 50 dubů. S dotací dosáhne zisku 16 750 Kč, což odpovídá nákladům 30 000 - 16 750 = 13 250 Kč za sazenice. „Zkouška": Stromů je dohromady opravdu 1000, každého druhu aspoň 50, platí i ostatní omezení (smrk, listnáče, MZD). Také platí 400 • 10 + 200 • 15 + 350 • 15 + 50 • 20 = 13250 a nalezené optimum „vypadá rozumně". Chybějící druh v tříčlenných nerovnovnicích by se dal využít jako doplňková proměnná, čímž by se tabulka zjednodušila. Také jsme na začátku mohli zasadit 50 stromků každého druhu a následně řešit až skladbu zbývajících 800. (To by si ovšem transformovalo ostatní podmínky.) Řešení úlohy o jídle simplexovou metodou 0.1x + 0.3y < 10 x > 0 O.lx + O.ly < 6 y >0 c = 20x + 30y První dvě podmínky si vynásobíme 10: x + 3y < 100 x + y < 60 -20 -30 0 0 0 1 3 1 1 1 0 0 1 100 60 0 - 10 0 20 1200 0 2 1 -1 40 1 1 0 1 60 0 0 5 20 1400 0 1 1 0 1/2 -1/2 -1/2 1/2 20 40 Úloha o jídle cesta mnohostěnem Komentáře k lineárnímu programování ► Obecnější zadání řeší matematické programování. ► Zdrojem těžkostí v optimalizaci jsou hlavně omezení (ne tolik účelová funkce). I simplexová metoda je NP-úplný problém. ► Simplexová metoda začíná v počátku s nulovým ziskem. „Zisk" vytváří jalové doplňkové proměnné (jakožto aktuální pivoti). V průběhu výpočtu postupně přebírají roli aktivních proměnných „výrobky" (též se hovoří o bázi SM). Role proměnné se může několikrát změnit. ► V LP je důležitým pojmem dualita. Zjednodušeně řečeno, v duální úloze dochází k výměně rolí vektoru proměnných a vektoru pravých stran. ► Požadavky: Umět zapsat slovně zadanou úlohu soustavou rovnic a nerovnic a účelovou funkcí, transformovat úlohu do standardního tvaru, sestavit počáteční simplexovou tabulku, optimalizovat tabulku Gaussovými eliminacemi, vyčíst z optimální tabulky optimální řešení a hodnotu účelové funkce. Rozumět grafickému řešení dvojrozměrné úlohy LP.