Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Matematika I – 8a Lineární rovnice a nerovnice, problém lineárního programování Jan Slovák Masarykova univerzita 14. 11. 2011 Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Obsah přednášky 1 Lineární rovnice a procesy 2 Optimalizační lineární modely 3 Poznámky o využití v ekonomii Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Plán přednášky 1 Lineární rovnice a procesy 2 Optimalizační lineární modely 3 Poznámky o využití v ekonomii Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Jednoduché lineární procesy jsou dány lineárními zobrazeními ϕ : V → W na vektorových prostorech. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Jednoduché lineární procesy jsou dány lineárními zobrazeními ϕ : V → W na vektorových prostorech. vektor v ∈ V představuje stav nějakého námi sledovaného jevu (třeba počty občanů tříděných dle nejvyšší dosažené kvalifikace, stav zásob jednotlivých dílů a výrobků atd.) ϕ(v) může představovat výsledek provedené operace (výsledek vzdělávací činnosti školské soustavy nebo výroba a prodej za určité časové období apod.). Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Jednoduché lineární procesy jsou dány lineárními zobrazeními ϕ : V → W na vektorových prostorech. vektor v ∈ V představuje stav nějakého námi sledovaného jevu (třeba počty občanů tříděných dle nejvyšší dosažené kvalifikace, stav zásob jednotlivých dílů a výrobků atd.) ϕ(v) může představovat výsledek provedené operace (výsledek vzdělávací činnosti školské soustavy nebo výroba a prodej za určité časové období apod.). Pokud chceme dosáhnout předem daného výsledku b ∈ W takového jednorázového procesu, řešíme problém ϕ(x) = b pro neznámý vektor x. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii V pevně zvolených souřadnicích pak máme matici A zobrazení ϕ a souřadné vyjádření vektoru b: A · x = b Pro b = 0 je množina řešení vektorovým podprostorem (jádro ϕ). Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii V pevně zvolených souřadnicích pak máme matici A zobrazení ϕ a souřadné vyjádření vektoru b: A · x = b Pro b = 0 je množina řešení vektorovým podprostorem (jádro ϕ). Snadno ověříme základní popis všech řešení: Theorem (Homogenní soustava rovnic) Pokud je dimenze V = n < ∞ a dimenze obrazu zobrazení ϕ je k, pak dimenze podprostoru všech řešení je právě n − k. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Skutečně: sloupce matice zobrazení jsou právě obrazy bázových vektorů, v matici systému je právě k lineárně nezávislých sloupců a tedy i stejný počet lineárně nezávislých řádků; při převodu na řádkový schodovitý tvar zůstane nakonec právě n − k nulových řádků; při řešení systému rovnic tak zůstane právě n − k volných parametrů a dosazením vždy jednoho z nich hodnotou jedna a vynulováním ostatních získáme právě k lineárně nezávislých řešení. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Skutečně: sloupce matice zobrazení jsou právě obrazy bázových vektorů, v matici systému je právě k lineárně nezávislých sloupců a tedy i stejný počet lineárně nezávislých řádků; při převodu na řádkový schodovitý tvar zůstane nakonec právě n − k nulových řádků; při řešení systému rovnic tak zůstane právě n − k volných parametrů a dosazením vždy jednoho z nich hodnotou jedna a vynulováním ostatních získáme právě k lineárně nezávislých řešení. Fundamentální systém řešení Každé takové k–tici lineárně nezávislých řešení říkáme fundamentální systém řešení daného homogenního systému lineárních rovnic. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Uvažme nyní obecný systém rovnic A · x = b. Jestliže rozšíříme matici A o sloupec b, můžeme, ale nemusíme, také zvětšit počet lineárně nezávislých sloupců a tedy i řádků. Pokud se tento počet zvětší, pak systém rovnic nemůže mít řešení (prostě se naše ϕ vůbec do b nestrefí). Jestliže ale naopak máme stejný počet nezávislých řádků, znamená to, že sloupec b musí být lineární kombinací sloupců matice A. Koeficienty takové kombinace jsou právě řešení. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Uvažme nyní obecný systém rovnic A · x = b. Jestliže rozšíříme matici A o sloupec b, můžeme, ale nemusíme, také zvětšit počet lineárně nezávislých sloupců a tedy i řádků. Pokud se tento počet zvětší, pak systém rovnic nemůže mít řešení (prostě se naše ϕ vůbec do b nestrefí). Jestliže ale naopak máme stejný počet nezávislých řádků, znamená to, že sloupec b musí být lineární kombinací sloupců matice A. Koeficienty takové kombinace jsou právě řešení. Mějme tedy dvě pevně zvolená řešení x a y našeho systému a nějaké řešení z systému homogenního se stejnou maticí. Pak zjevně A · (x − y) = b − b = 0 A · (x + z) = 0 + b = b. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Můžeme proto shrnout: Theorem (Struktura všech řešení systému lineárních rovnic) podprostor všech řešení homogenního systému rovnic A · x = 0 má dimenzi n − k, kde n je počet proměnných a k je počet lineárně nezávislých rovnic, všechna řešení jsou generována tzv. fundamentálním systémem n − k řešení, který lze obdržet z Gausovy eliminace postupným dosazováním nul a jedniček za volné parametry, řešení nehomogenního systému existuje právě, když přidáním sloupce b k matici A nezvýšíme počet lineárně nezávislých řádků. V takovém případě je prostor všech řešení dán součty jednoho pevně zvoleného partikulárního řešení systému a všech řešení systému homogenního se stejnou maticí. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Plán přednášky 1 Lineární rovnice a procesy 2 Optimalizační lineární modely 3 Poznámky o využití v ekonomii Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Představme si velice specializovaného natěrače v černobílém světě.Natírá fasády buď malých rodinných domků nebo naopak velikých veřejných budov a pochopitelně používá jen černou a bílou barvu. Může si zcela volně vybírat, v jakém rozsahu bude dělat x jednotek plochy prvého typu nebo y jednotek druhého. Předpokládejme, že jeho maximální pracovní zátěž je ve sledovaném období L jednotek plochy, jeho čistý výnos (tj. po odečtení nákladů) je na jednotku plochy c1 u malých domků a c2 u veřejných staveb. Zároveň má k dispozici maximálně W kg bílé a B kg černé barvy. Konečně na jednotku plochy rodinného domu potřebuje w1 kg bílé barvy a b1 kg černé, zatímco u veřejných staveb jsou to hodnoty w2 a b2. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Když si to celé shrneme do (ne)rovnic, dostáváme omezení x1 + x2 ≤ L (1) w1x1 + w2x2 ≤ W (2) b1x1 + b2x2 ≤ B. (3) Celkový čistý výnos natěrače h(x1, x2) = c1x1 + c2x2 bychom přitom rádi měli co největší. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Každá z uvedených nerovnic zadává v rovině proměnných (x1, x2) polorovinu, ohraničenou přímkou zadanou příslušnou rovnicí, a jistě musíme také předpokládat, že jak x1 tak x2 jsou nezáporná reálná čísla, protože záporné velikosti ploch natěrač neumí. Ve skutečnosti máme tedy omezení na hodnoty (x1, x2), které může být buď nesplnitelné nebo je dáno jako vnitřek mnohoúhleníku s maximálně pěti vrcholy. Obecně hovoříme o problému lineárního programování, jestliže hledáme buď maximum nebo minimum lineární formy h na Rn na množině ohraničené pomocí systému lineárních nerovnic, kterým říkáme lineární omezení. Vektoru na pravé straně pak říkáme vektor omezení, lineární formě h také účelová funkce. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Formulace s nerovnostmi ≤ u omezujících podmínek, nezápornými proměnnými a maximalizaci účelové funkce říkáme standardní maximalizační problém. Naopak, standardní minimalizační problém je hledání minima účelové funkce při omezujících podmínkách s nerovnostmi ≥, přičemž opět uvažujeme nezáporné proměnné. Je snadné nahlédnout, že každý obecný problém lineárního programování lze převést na kterýkoliv ze standardních. Kromě změn znamének můžeme ještě pracovat s rozdělením případných proměnných bez omezení znaménka na rozdíl dvou kladných. Bez újmy na obecnosti se tedy budeme dále věnovat jen standardnímu maximalizačnímu problému. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Jak takový problém řešit? Hledáme maximum lineární formy h na podmnožinách M vektorového prostoru, které jsou zadány lineárními nerovnostmi, tj. v rovině pomocí průniku polorovin, obecně budeme v další kapitole hovořit o poloprostorech. Všimněme si, že každá lineární forma na reálném vektorovém prostoru h : V → R (tj. libovolná lineární skalární funkce) v každém vybraném směru buď stále roste nebo stále klesá. Přesněji řečeno, jestliže vybereme pevný počáteční vektor u ∈ V a „směrový“ vektor v ∈ V , pak složením naší formy h s parametrizací dostaneme t → h(u + t v) = h(u) + t h(v). Tento výraz je skutečně s rostoucím parametrem t vždy buď rostoucí nebo klesající, případně konstantní (podle toho, zda je h(v) kladné nebo záporné, případně nulové). Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Jistě tedy musíme očekávat, že problémy podobné tomu s natěračem budou buď nesplnitelné (když je množina zadaná omezením prázdná) nebo bude výnos neohraničený (když omezení zadají neomezenou část celého prostoru a forma h v některém z neomezených směrů bude nenulová) nebo budou mít maximální řešení v alespoň jednom z „vrcholů“ množiny M (přičemž zpravidla půjde o jediný vrchol, může ale jít o konstatní maximální honotu na části horanice oblasti M). Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Formulace pomocí lineárních rovnic Ne vždy je nalezení optima tak snadné jako v předchozím případě. Problém může zahrnovat velmi mnoho proměnných a velmi mnoho omezení a jen rozhodnout, zda je množina M splnitelných bodů neprázdná je problematické. Začneme srovnáním se systémy lineárních rovnic – těm už totiž rozumíme dobře. Zapišme si rovnice vektorově v obecném tvaru: A · x ≤ b, kde x je nyní n–rozměrný vektor, b je m–rozměrný vektor a A odpovídající matice a nerovností myslíme jednotlivé nerovnosti po řádcích. Maximalizovat chceme součin c · x pro daný řádkový vektor koeficientů lineární formy h. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Jestliže si pro každou z rovnic přidáme jednu pomocnou proměnnou a ještě si přimyslíme proměnnou z jako hodnotu linární formy h, můžeme celý problém přepsat jako systém lineárních rovnic 1 −c 0 0 A Em ·   z x xs   = 0 b kde matice je složena z bloků o 1 + n + m sloupcích a 1 + m řádcích a tomu odpovídají jednotlivé komponenty vektorů. Dodatečně přitom požadujeme pro všechny souřadnice x i xs nezápornost. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Pokud tedy má daný systém rovnic řešení, hledáme v této množině řešení takové hodnoty proměnných z, x a xs, aby všechna x byla nezáporná a z maximální možné. Konkrétně v našem problému černobílého naterače bude systém linárních rovnic vypadat takto:     1 −c1 −c2 0 0 0 0 1 1 1 0 0 0 w1 w2 0 1 0 0 b1 b2 0 0 1     ·         z x1 x2 x3 x4 x5         =     0 L W B     Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Plán přednášky 1 Lineární rovnice a procesy 2 Optimalizační lineární modely 3 Poznámky o využití v ekonomii Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Náš velice schematický problém černobílého natěrače můžeme použít jako ilustraci jednoho z typických ekonomických modelů, tzv. model plánování výroby. Jde přitom o zachycení problému jako celku, tj. se zahrnutím vnitřních i vnějších vztahů. Levé strany rovnic i účelové funkce h(x1, x2) jsou vyjádřením různých výrobních vztahů. Podle povahy problému pak jsou požadovány na pravé straně buď přesné hodnoty (pak řešíme systém rovnic) nebo požadujeme kapacitní omezení a optimalizaci účelu (a pak dostáváme právě problémy lineárního programování). Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii Můžeme tak tedy obecně řešit problém alokace zdrojů při dodavatelských omezeních a přitom buď minimalizovat náklady nebo maximalizovat zisk. Z tohoto pohledu lze také nahlížet dualizaci problémů. Jestliže by náš natěrač chtěl hypoteticky nastavit svoje náklady spojené se svojí prací yL, bílou barvou yW a černou barvou yB, pak bude chtít minimalizovat účelovou funkci L · yL + WyW + ByB při omezujících podmínkách yL + w1yW + b1yB ≥ c1 yL + w2yW + b2yB ≥ c2. To je tzv. duální problém k původnímu a hlavní věta lineárního programování říká, že optimální stav je takový, kdy účelové funkce mají stejnou hodnotu. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii V ekonomických modelech najdeme mnoho modifikací. Jednou z nich jsou úlohy finančního plánování, související s optimalizací portfolia. Určujeme přitom objemy investic do jednotlivých investičních variant s cílem držet se daných omezení na rizika a optimalizovat přitom zisk, resp. při očekávaném objemu minimalizovat rizika. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii V ekonomických modelech najdeme mnoho modifikací. Jednou z nich jsou úlohy finančního plánování, související s optimalizací portfolia. Určujeme přitom objemy investic do jednotlivých investičních variant s cílem držet se daných omezení na rizika a optimalizovat přitom zisk, resp. při očekávaném objemu minimalizovat rizika. Dalším obvyklým modelem jsou marketingové aplikace, např. alokace nákladů na reklamy v různých médiích nebo umísťování reklam do časových termínů. Omezujícími podmínkami bude disponibilní rozpočet, rozložení cílových skupin apod. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii V ekonomických modelech najdeme mnoho modifikací. Jednou z nich jsou úlohy finančního plánování, související s optimalizací portfolia. Určujeme přitom objemy investic do jednotlivých investičních variant s cílem držet se daných omezení na rizika a optimalizovat přitom zisk, resp. při očekávaném objemu minimalizovat rizika. Dalším obvyklým modelem jsou marketingové aplikace, např. alokace nákladů na reklamy v různých médiích nebo umísťování reklam do časových termínů. Omezujícími podmínkami bude disponibilní rozpočet, rozložení cílových skupin apod. Velmi obvyklé jsou modely výživových problémů, tj. návrh návek různých komponent výživy s daným složením a omezujícími požadavky na celkové objemy výživových látek. Lineární rovnice a procesy Optimalizační lineární modely Poznámky o využití v ekonomii V ekonomických modelech najdeme mnoho modifikací. Jednou z nich jsou úlohy finančního plánování, související s optimalizací portfolia. Určujeme přitom objemy investic do jednotlivých investičních variant s cílem držet se daných omezení na rizika a optimalizovat přitom zisk, resp. při očekávaném objemu minimalizovat rizika. Dalším obvyklým modelem jsou marketingové aplikace, např. alokace nákladů na reklamy v různých médiích nebo umísťování reklam do časových termínů. Omezujícími podmínkami bude disponibilní rozpočet, rozložení cílových skupin apod. Velmi obvyklé jsou modely výživových problémů, tj. návrh návek různých komponent výživy s daným složením a omezujícími požadavky na celkové objemy výživových látek. Problémy lineárního programování se objevují při personálních úlohách, kdy jsou pracovníci s různými kvalifikacemi a dalšími předpoklady rozdělováni do směn. Obvyklé jsou také problémy směšování, problémy dělení a problémy distribuce zboží.