Název projektu Rozvoj vzdělávání na Slezské univerzitě v Opavě Registrační číslo projektu CZ.02.2.69/0.0./0.0/16_015/0002400 Ekonomicko-matematické metody Distanční studijní text Jaroslav Ramík, Radomír Perzina Karviná 2017 Obor: Ekonomie, matematika. Klíčová slova: matematické programování, konvexní programování, lineární programováni, DEA, teorie portfolia, síťová analýza, optimalizace na grafech, CPM, PERT, GERT. Anotace: Tento text je určen studentům navazujícího magisterského stupně studia na Slezské univerzitě, Obchodně podnikatelské fakultě v Karviné. Jakožto studijní opora je určen především studentům kombinované formy studia, mohou jej však stejně dobře využít i studenti prezenční formy. Autor předpokládá, že čtenář – student má z předchozího studia znalosti ze základních kurzů matematiky a statistiky (kvantitativních metod) a též absolvoval základy z operačního výzkumu (operační analýzy). S těmito prerekvizitami je studium tohoto textu přirozeně jednodušší, neboť některá témata se částečně překrývají, avšak autor se snažil i o to, aby text byl samonosný, tedy aby mu bylo možno porozumět bez předchozího studia uvedených předmětů. K řešení příkladů uvnitř textu je systematicky využíván standardní program MS Excel. Mimo uvedenou teorii se proto čtenář naučí používat Excel-Řešitel k řešení konkrétních úloh. To mu umožní lépe pochopit podstatu matematického modelování a také ekonomickou interpretaci dosažených výsledků. Obsahově text pokrývá témata: matematické programování, konvexní programování, lineární programování, DEA, teorie portfolia, síťová analýza, optimalizace na grafech, CPM, PERT, GERT. Autor: Prof. RNDr. Jaroslav Ramík, CSc. Ing. Radomír Perzina, Ph.D. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 4 Obsah ÚVODEM............................................................................................................................7 RYCHLÝ NÁHLED STUDIJNÍ OPORY...........................................................................8 1 EKONOMICKO-MATEMATICKÉ MODELOVÁNÍ .............................................10 1.1 Trocha historie o matematickém modelování v ekonomii..................................10 1.2 Maximalizace zisku při omezených výrobních zdrojích a omezeném odbytu....11 1.2.1 Výrobní program..........................................................................................12 1.2.2 Jednotlivé zisky a celkový zisk....................................................................12 1.2.3 Omezené zdroje ...........................................................................................12 1.2.4 Technologické (strukturní) koeficienty........................................................12 1.2.5 Omezení odbytu...........................................................................................12 1.2.6 Přípustné výrobní programy (PVP) .............................................................13 1.2.7 Optimální výrobní program .........................................................................13 1.2.8 Optimalizace výrobního programu ..............................................................13 1.3 Model v podmínkách rizika a neurčitosti............................................................17 2 MATEMATICKÝ APARÁT EMM..........................................................................19 2.1 Funkce.................................................................................................................19 2.2 Matice a vektory..................................................................................................20 3 OPTIMALIZAČNÍ PROBLÉMY, EXTRÉMY FUNKCE.......................................28 3.1 Optimalizační úlohy............................................................................................28 3.2 Matematické programování.................................................................................30 3.3 Ekvivalentní tvary úloh matematického programování ......................................32 3.4 Lokální a globální extrémy .................................................................................33 3.5 Existence řešení...................................................................................................35 4 MATEMATICKÉ PROGRAMOVÁNÍ – KONVEXNÍ ÚLOHY ............................45 4.1 Konvexní množiny a konvexní a konkávní funkce.............................................45 4.2 Teorie sedlových bodů ........................................................................................49 4.3 Kuhn-Tuckerovy podmínky a dualita v LP.........................................................52 5 LINEÁRNÍ PROGRAMOVÁNÍ...............................................................................57 5.1 Úlohy lineárního programování ..........................................................................57 5.2 Optimální alokace zdrojů ....................................................................................58 5.3 Základní pojmy LP..............................................................................................59 5.4 Simplexová metoda.............................................................................................62 5.5 Dvoufázová simplexová metoda.........................................................................63 6 ŘEŠENÍ OPTIMALIZAČNÍCH ÚLOH V EXCELU...............................................66 6.1 Řešitel..................................................................................................................66 Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 5 7 DUALITA, DOPRAVNÍ A PŘIŘAZOVACÍ PROBLÉM .......................................78 7.1 Dualita jako vztah mezi dvěma úlohami lineárního programování ....................78 7.2 Vztahy mezi (P) a (D) úlohou LP........................................................................83 7.3 Ekonomická interpretace duality.........................................................................85 7.4 Ekonomický a matematický model dopravního problému (DP).........................86 7.5 Přiřazovací problém – speciální DP....................................................................92 8 VÍCEKRITERIÁLNÍ A CÍLOVÉ PROGRAMOVÁNÍ............................................97 8.1 Vícekriteriálnost v ekonomickém rozhodování ..................................................97 8.2 Nelineární VKP – základní úloha........................................................................98 8.3 Kriteriální prostor úlohy VKP a nedominovaná varianta ...................................99 8.4 Nedominované varianty ......................................................................................99 8.5 Vícekriteriální lineární programování VKLP ...................................................100 8.6 Metoda váženého průměru účelových funkcí ...................................................102 8.7 Minimaxová optimalizace.................................................................................105 8.8 Cílové programování.........................................................................................108 9 MATEMATICKÉ METODY OPTIMALIZACE PORTFOLIA ............................114 9.1 Akciové analýzy................................................................................................114 9.1.1 Fundamentální analýza ..............................................................................114 9.1.2 Psychologická analýza...............................................................................115 9.1.3 Technická analýza......................................................................................115 9.1.4 Finanční analýza ........................................................................................115 9.2 Teorie portfolia, výnos a riziko.........................................................................116 9.3 Klasický stochastický model PF – historický přístup .......................................116 9.4 Klasický stochastický model PF – expertní přístup ..........................................125 10 SHARPEHO, MARKOWITZŮV A FAKTOROVÝ MODEL PORTFOLIA........129 10.1 Optimalizace portfolia jako 2-kriteriální problém nelineárního programování 129 10.2 Sharpeův model .............................................................................................130 10.3 Markowitzův model.......................................................................................131 10.4 Faktorové modely..........................................................................................132 10.5 Postup při výpočtu optimálního PF – jednoindexový „historický“ model....133 11 OPTIMALIZAČNÍ METODY NA GRAFECH......................................................140 11.1 Základy teorie grafů.......................................................................................140 11.2 Minimální kostra............................................................................................145 11.3 Nejkratší cesta v síti.......................................................................................147 11.4 Maximální tok v síti.......................................................................................151 12 ČASOVÁ ANALÝZA PROJEKTŮ (CPM, PERT, GERT) ...................................157 Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 6 12.1 Projekt............................................................................................................157 12.2 Konstrukce síťového grafu projektu..............................................................158 12.3 Metoda CPM..................................................................................................162 12.4 Metoda PERT ................................................................................................169 12.5 Metoda GERT................................................................................................173 LITERATURA ................................................................................................................176 SHRNUTÍ STUDIJNÍ OPORY.......................................................................................177 PŘEHLED DOSTUPNÝCH IKON.................................................................................178 Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 7 ÚVODEM Tento text je určen studentům navazujícího magisterského stupně studia na Slezské univerzitě, Obchodně podnikatelské fakultě v Karviné. Jakožto studijní opora je určen především studentům kombinované formy studia, mohou jej však stejně dobře využít i studenti prezenční formy. Autor předpokládá, že čtenář – student má z předchozího studia znalosti ze základních kurzů matematiky a statistiky (kvantitativních metod) a též absolvoval základy z operačního výzkumu (operační analýzy). S těmito prerekvizitami je studium tohoto textu přirozeně jednodušší, neboť některá témata se částečně překrývají, avšak autoři se snažili i o to, aby text byl samonosný, tedy aby mu bylo možno porozumět bez předchozího studia uvedených předmětů. K řešení příkladů uvnitř textu je systematicky využíván standardní program MS Excel. Mimo uvedenou teorii se proto čtenář naučí používat ExcelŘešitel k řešení konkrétních úloh. To mu umožní lépe pochopit podstatu matematického modelování a také ekonomickou interpretaci dosažených výsledků. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 8 RYCHLÝ NÁHLED STUDIJNÍ OPORY Tento text nazvaný Ekonomicko-matematické metody (EMM) se zabývá matematickým modelováním v ekonomii. Začíná trochou historie tohoto oboru a na příkladu maximalizace zisku při omezených výrobních zdrojích a omezeném odbytu ukazuje možnosti matematického modelování s využitím počítačů. Nejprve je souhrnně představen matematický aparát EMM, jmenovitě funkce jedné a více reálných proměnných, dále operace s maticemi i vektory, a to i s využitím Excelu, podrobněji se věnujeme optimalizačním problémům a extrémům funkcí. V další části publikace se systematicky věnujeme tzv. matematickému programování. Nejprve je to teorie nelineárního programování zaměřená na konvexní a konkávní funkce, dále jsou to stručné základy lineárního programování (LP) aplikované na praktické úlohy optimální alokace zdrojů, dopravní a přiřazovací problém. Jednokriteriální matematické programování se dále rozšiřuje na vícekriteriální a cílové programování (VKP). Zde se věnujeme obecné nelineární úloze VKP, poté vyšetřujeme úlohy lineárního VKP, které řešíme metodami minimaxového a cílového přístupu. Speciální pozornost je věnována též modelům analýzy obalu dat (DEA), jakožto speciální aplikaci LP s cílem stanovení ekonomické efektivnosti skupiny homogenních produkčních jednotek. Posledním tématem této části jsou matematické metody optimalizace portfolia. Nejprve je představen klasický stochastický model portfolia (PF) jako úloha dvojkriteriálního nelineárního matematického programování, poté se zabýváme Sharpeho, Markowitzovým a indexovými modely PF. Poslední část publikace je věnována EMM s využitím grafů. Nejprve jsou uvedeny stručné základy teorie grafů, poté se řeší známé optimalizační úlohy na grafech: úloha nalezení minimální kostry ohodnoceného grafu, nejkratší cesta v grafu a úloha nalezení maximálního toku v grafu. V poslední kapitole se pak věnujeme časové analýze projektů modelovaných síťovými grafy. Jsou popsány a na řešených příkladech ilustrovány metody CPM, PERT a GERT. V celém textu se k řešení příkladů systematicky využívá známý program MS Excel a zejména jeho doplněk Řešitel. Text je určen především studentům vyšších ročníků magisterského a navazujícího magisterského studia všech studijních programů a jejich studijních oborů na VŠ ekonomického zaměření. Předpokladem úspěšného studia je absolvování základních bakalářských předmětů matematiky a statistiky, výhodou je absolvování základního předmětu operačního výzkumu nebo jemu odpovídajícího předmětu s jiným názvem. Charakteristickou vlastností tohoto textu je aktivní používání Excelu. V současné době je Excel považován za základní pracovní nástroj každého vysokoškolsky vzdělaného ekonoma. Funkčnost Excelu se neomezuje jen na základní aritmetické operace, ale je rozšířena o další speciální funkce matematicko-statistického charakteru a analytické nástroje, které umožňují hlubší analýzy datových souborů. Za nejsofistikovanější analytický nástroj Excelu je možné považovat Řešitel (Solver); ten umožňuje řešit i optimalizační úlohy, jejichž řešení poskytuje návod komplikovaných rozhodnutí ve složitých systémech. Jedním s hlavních cílů tohoto textu je naučit čtenáře – studenta využívat Excel na kvalitativně vyšší úrovni včetně využití Řešitele. V textu nalezne čtenář řešené úlohy s podrobným návodem jejich řešení pomocí Excelu a na dalších úlohách si pak může sám zkontrolovat zvládnutí jak teoretického základu, tak také praktického použití Excelu k řešení problému. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 9 Ekonomicko-matematické modelování 10 1 EKONOMICKO-MATEMATICKÉ MODELOVÁNÍ RYCHLÝ NÁHLED KAPITOLY V této kapitole se dozvíte základní informace o historii matematického modelování v ekonomii. Na příkladu úlohy maximalizace zisku při omezených výrobních zdrojích a/nebo omezeném odbytu bude sestaven matematický model, který bude dále rozšířen v podmínkách rizika a neurčitosti. CÍLE KAPITOLY Po prostudování této kapitoly budete umět:  Stručnou historii matematického modelování v ekonomii.  Definovat základní prvky výrobního programu.  Graficky vyřešit jednoduchý výrobní program. KLÍČOVÁ SLOVA KAPITOLY Výrobní program, celkový zisk, zdroje, přípustný výrobní program, optimální výrobní program. 1.1 Trocha historie o matematickém modelování v ekonomii Matematika se do ekonomie začala prosazovat ve 30. letech minulého století. Zřejmě pod vlivem úspěšného použití matematiky ve fyzice se více a více začínala uplatňovat i v jiných oblastech vědy, avšak ke skutečnému boomu došlo až s nástupem počítačů. Bylo to v padesátých letech a tehdy se matematika začala více uplatňovat jak při hledání optimálních rozhodnutí na nižší a střední řídicí úrovni, tak na úrovni rozhodnutí makroekonomických systémů. Problematika použití matematiky v hospodářství je však mnohem starší. Uvádí se, viz např. [5], že staroegyptský tzv. Rhind-Ahmesův papyrus ze 17. stol. př. n. l. obsahuje některé hospodářské úlohy, které lze při troše tolerance považovat za matematické aplikace v ekonomii. V novověké historii se lze setkat s matematickým modelováním již v klasických pracích o politické ekonomii, např. v díle Political arithmetics od anglického filosofa W. Pettyho Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 11 (1623 – 1687). Ten kladl při studiu národního hospodářství důraz na měření veličin a modelování základních vztahů mezi nimi. Až mnohem později švýcarský ekonom L. Walras (1834 – 1910) jako první používal matematický aparát jako nedílnou součást svých ekonomických úvah o marginální teorii užitku a v teorii ekonomické rovnováhy. Žák L. Walrase - V. Pareto (1848 – 1923) dovedl používání matematiky v ekonomii k dnešním standardům zejména ve svém příspěvku Économie mathématique v díle Encyklopédie des sciences mathematiques pures et appliqueés. S jeho jménem se dnes setkáváme zejména u pojmu paretovské optimality ve vícekriteriálním rozhodování (viz kap. 6) a u tzv. paretova prin- cipu. Norský vědec R. Frisch (1895 – 1973) založil již v roce 1930 Ekonometrickou společnost a od r. 1933 začal vycházet časopis Econometrica, kde se zformovalo vědní odvětví ekonometrie, která za svoji hlavní náplň považuje matematicko – statistickou verifikaci ekonomických vztahů, v širším pojetí zavádění matematických metod do ekonomie, viz [5]. V roce 1939 vyšla publikace W. Leontieffa, která se stala základem tzv. Strukturní analýzy. Přibližně ve stejnou dobu L. Kantorovič vydal práci, která obsahovala základy lineárního programování. V roce 1944 vyšla klasická kniha J. Von Neumanna a O. Morgensterna Teorie her a ekonomického chování, jež položila základy stejnojmennému oboru. Zásluhou simplexového algoritmu G. Danziga se naplno rozvinuly možnosti lineárního programování, na které navázala teorie nelineárního programování, vícekriteriálního a cílového programování, také celočíselného programování a konečně dynamického programování, jehož principy zformuloval v roce 1957 R. Bellman. V tu dobu se konstituuje mezioborová disciplína nazvaná operační výzkum (později nazývaný též operační analýza). Vznikají teorie hromadné obsluhy, teorie optimalizace zásob, síťová analýza a další. Začíná vycházet celá řada vědeckých časopisů, které se věnují jednotlivým oblastem operačního výzkumu. Matematické prostředky a jazyk matematiky zdomácňují i na stránkách učebnic ekonomie (Samuelson – Nordhaus). V ekonomii se podobně jako ve fyzice už komunikace prostřednictvím vzorců nepovažuje za aplikaci matematiky. Uplatňování matematiky v ekonomii působí také zpětně na rozvoj nových matematických odvětví. Příkladem je vznik teorie fuzzy množin, která respektuje skutečnost, že v oblasti společenských věd některé pojmy nelze přesně vymezit, a přesto se s nimi běžně pracuje. Je obtížné stanovit, kde končí čistá matematika a začíná aplikovaná matematika, což platí též o aplikacích matematiky v ekonomii. Soužití matematiky a ekonomie je prospěšné pro oba vědní obory. Ekonomie je přiváděna k exaktním a kvantitativním vyjádřením ekonomických závislostí (zákonitostí), na druhou stranu matematika je obohacována o zcela nové oblasti zkoumání mimo tradiční oblasti fyziky a techniky. 1.2 Maximalizace zisku při omezených výrobních zdrojícha omezeném odbytu V této subkapitole se zamyslíte nad typickou úlohou nalezení optimálního (tj. nejlepšího) výrobního programu podniku. Budete přitom mít na paměti základní axiom podni- kání. Axiom: Maximalizace zisku je hlavní cíl podnikání. Ekonomicko-matematické modelování 12 1.2.1 VÝROBNÍ PROGRAM Výrobní program je představován dvěma skupinami prvků:  Výrobkový seznam: n výrobků, pro jednoduchost je pojmenujeme přirozenými čísly: 1, 2, …, n.  Objem výroby jednotlivých výrobků: množství, kusy (x1, x2, …, xn) předem neznámý rozsah výroby, tvoří n-tice čísel, tj. vektor x = (x1, x2, …, xn). 1.2.2 JEDNOTLIVÉ ZISKY A CELKOVÝ ZISK Uvažujeme tyto veličiny: ci - zisk z výroby jednotky výrobku i = 1,2, …, n , cixi - zisk z výroby xi výrobku i, c1x1 + c2x2 + … + cnxn - celkový zisk celého výrobního programu x = (x1, x2, …, xn). 1.2.3 OMEZENÉ ZDROJE Máme seznam omezených zdrojů: m zdrojů „pojmenovaných“ (pro jednoduchost) přirozenými čísly: 1, 2, …, m. Dále máme disponibilní množství těchto zdrojů v množstvích: b1, b2, …, bm. Eventuálně můžeme uvažovat volný nákup zdrojů z celkové omezené částky. 1.2.4 TECHNOLOGICKÉ (STRUKTURNÍ) KOEFICIENTY Pro danou technologii výroby uvažujeme: aij - technologický koeficient představující množství zdroje " i " potřebného k výrobě jednotky výrobku " j ", aij xj - množství zdroje " i " potřebného k výrobě xj jednotek výrobku " j ", ai1 x1 + ai2 x2 + … + ain xn - množství zdroje "i" potřebného k výrobě výrobního programu X = (x1, x2, …, xn). 1.2.5 OMEZENÍ ODBYTU Dále uvažujeme: hi - horní omezení odbytu výrobku "i", 0 ≤ xj ≤ hj - objem výroby výrobku " j " nesmí překročit odbytové možnosti. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 13 1.2.6 PŘÍPUSTNÉ VÝROBNÍ PROGRAMY (PVP) Je přirozené, že PVP x = (x1, x2, …, xn) splňuje následující podmínky disponibilních zdrojů: ai1 x1 + ai2 x2 + … + ain xn ≤ bi , a dále podmínky odbytových možností: 0 ≤ xj ≤ hj j = 1, 2, …, n. 1.2.7 OPTIMÁLNÍ VÝROBNÍ PROGRAM Optimální výrobní program je takový přípustný výrobní program x = (x1, x2, …, xn), který maximalizuje celkový zisk: c1x1 + c2x2 + … + cnxn Pro nalezení OVP musíte tedy shromáždit:  výrobkový seznam  jednotkové zisky  disponibilní množství zdrojů  technologické koeficienty  omezení odbytu 1.2.8 OPTIMALIZACE VÝROBNÍHO PROGRAMU Hledáme maximální celkový zisk, tj. c1x1 + c2x2 + … + cnxn → MAX; (1-1) za omezení ai1 x1 + ai2 x2 + … + ain xn ≤ bi , i = 1,2,…, m, (1-2) 0 ≤ xj ≤ hj j = 1,2, …, n. (1-3) Řešením této úlohy získáme optimální výrobní plán x = (x1, x2, …, xn), který maximalizuje celkový zisk z výroby za existujících technologických a odbytových omezení. Takto zformulovanou obecnou úlohu si ozřejmíte na konkrétní úloze. ŘEŠENÁ ÚLOHA 1-1 Výrobce tzv. „racio“ pokrmů plánuje výrobu dvou typů směsí. Na jejich výrobu má na jedno plánovací období k dispozici rýži s kapacitou 270 tun, pšenici v množství 100 tun a ovesné vločky o kapacitě 60 tun. Při výrobě dvou typů směsí je třeba dodržovat složení daných směsí podle následující tabulky. Ekonomicko-matematické modelování 14 Na základě všech nákladů souvisejících s výrobou a dle předpokládané prodejní ceny obou směsí byl vykalkulován zisk 2000 Kč za 1 tunu směsi typu I a 3000 Kč/t směsi typu II. Jak má firma naplánovat výrobu, aby byl celkový zisk maximální? Řešení: Nejprve převedeme ekonomický model na matematický: 2 procesy: 1.výroba směsi typu I v množství x1 ≥ 0; 2.výroba směsi typu II v množství x2 ≥ 0; 3 činitelé (zdroje): rýže, pšenice, ovesné vločky. Efektivnost procesů: 1 tuna směsi typu I přináší zisk 2000 Kč, 1 tuna směsi typu II přináší zisk 3000 Kč, z = 2000x1 + 3000x2 je zisk z produkce x1 tun směsi typu I, a zároveň x2 tun směsi typu II. Omezující podmínky: 0,9 x1 + 0,3 x2 ≤ 270 rýže, 0,5 x2 ≤ 100 pšenice, 0,1 x1 + 0,2 x2 ≤ 60 vločky. Strukturní (technologické) koeficienty jsou koeficienty na levých stranách nerovností. Kapacitní koeficienty jsou koeficienty pravých stran nerovností. Podmínky nezápornosti: x1 ≥ 0, x2 ≥ 0 Matematický model LP: 2 procesy, 3 zdroje (činitele): z = 2000x1 + 3000x2 → MAX; za podmínek Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 15 0,9 x1 + 0,3 x2 ≤ 270 0,5 x2 ≤ 100 0,1 x1 + 0,2 x2 ≤ 60 x1 ≥ 0, x2 ≥ 0 NĚKTERÁ PŘÍPUSTNÁ A NEPŘÍPUSTNÁ ŘEŠENÍ ÚLOHY LP: Jaké je optimální řešení úlohy, tj. takové x1 a x2, které dávají maximální zisk? Grafické znázornění podmínky: 0,9 x1 + 0,3 x2 ≤ 270, (x1 ≥ 0, x2 ≥ 0) Grafické znázornění podmínky: 0,5 x2 ≤ 100, (x1 ≥ 0, x2 ≥ 0) Ekonomicko-matematické modelování 16 Grafické znázornění podmínky: 0,1 x1 + 0,2 x2 ≤ 60, (x1 ≥ 0, x2 ≥ 0) Grafické znázornění množiny všech přípustných řešení: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 17 Grafické řešení úlohy LP: x1 = 240 x2 = 180 z = 1 020 000 1.3 Model v podmínkách rizika a neurčitosti V příkladu z předchozí kapitoly jsme uvažovali se ziskem 2000,- Kč z jedné tuny směsi typu I, resp. ziskem 3000,- Kč z jedné tuny směsi typu II. Ve skutečnosti je velikost zisku závislá na mnoha dalších okolnostech, které v modelu neuvažujeme a nemáme nad nimi kontrolu, např. pohyby ceny surovin na světových trzích apod. Tyto okolnosti způsobují, že skutečný zisk se může od uvažovaného lišit. Proto je vhodné jednotkové zisky považovat za náhodné veličiny s diskrétním nebo spojitým rozdělením pravděpodobnosti. V takovém případě pak i celkový zisk z produkce bude rovněž náhodná veličina. Připomeňme si, že náhodná veličina je množina hodnot spolu s příslušnými pravděpodobnostmi jejich možné realizace. Tak např. 1 tuna směsi typu I přináší očekávaný (průměrný) zisk: 1500 Kč s pravděpodobností 0,2 Ekonomicko-matematické modelování 18 2000 Kč s pravděpodobností 0,6 2500 Kč s pravděpodobností 0,2 Očekávaný (průměrný) zisk (střední hodnota): E(jednotkový zisk1) = 1500.0,2 + 2000.0,6 + 2500.0,2 = 2000 Kč 1 tuna směsi typu II přináší očekávaný (průměrný) zisk: 2000 Kč s pravděpodobností 0,2 3000 Kč s pravděpodobností 0,6 4000 Kč s pravděpodobností 0,2 Očekávaný (průměrný) zisk (střední hodnota): E(jednotkový zisk2) = 2000.0,2 + 3000.0,6 + 4000.0,2 = 3000 Kč Strukturní, resp. kapacitní koeficienty mohou být rovněž rizikové (tj. náhodné veličiny). Optimalizační úlohy s náhodnými koeficienty se řeší pomocí metod stochastického matematického programování. OTÁZKY  Charakterizujte výrobní program podniku pomocí jeho hlavních prvků a uveďte, jak lze tyto prvky modelovat pomocí matematických prostředků.  Napište výsledný matematický model. SHRNUTÍ KAPITOLY V této úvodní kapitole jste se dozvěděli základní informace o matematickém modelování v ekonomii. Na příkladu nalezení optimálního výrobního plánu podniku jste si demonstrovali postup tvorby matematického modelu, jak je to obvyklé v oboru nazývaném matematickém programování. Na příkladu výroby dvou typů směsi byl symbolicky i graficky vyřešen problém stanovení optimálního výrobního plánu. Další možnosti rozšíření modelu spočívá v zahrnutí podmínek rizika a neurčitosti do modelu, což řeší obor stochastické matematické programování nebo fuzzy matematické programování. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 19 2 MATEMATICKÝ APARÁT EMM RYCHLÝ NÁHLED KAPITOLY Tato kapitola je poměrně krátká a má pomocný charakter. Je věnována základním matematickým pojmům, které se vyskytují v oblasti optimalizačních metod, totiž funkcím jedné a více reálných proměnných. Dále se naučíte prakticky zacházet s maticemi a vektory s využitím vložených funkcí Excelu a konečně řešit soustavy lineárních rovnic pomocí Excelu. Pozor, rozlišujte pojem funkce reálné proměnné jako matematický pojem (zobrazení z nějaké množiny do množiny reálných čísel) a funkce v MS Excelu, což je SW realizace matematického pojmu funkce pro některé konkrétní případy. CÍLE KAPITOLY Po prostudování této kapitoly budete umět:  Zapsat funkci jedné i více reálných proměnných.  Základní operace s maticemi a vektory.  Vyřešit jednoduchou maticovou rovnici v Excelu. KLÍČOVÁ SLOVA KAPITOLY Funkce, vektor, matice, součin matic, inverzní matice. 2.1 Funkce Funkce jedné reálné proměnné: Rozumné používání jazyka matematiky v ekonomické oblasti obvykle vyžaduje kompromis mezi požadavkem přesnosti a potřebami srozumitelnosti. Jestliže veličina y závisí na veličině x, říkáme, že „ y je funkcí x “ a tento fakt zapisujeme: y = f(x) , kde y - je závisle proměnná, x - je nezávisle proměnná. Příklad 1: HV = f(ZP) Matematický aparát EMM 20 „Hrubá výroba“ je funkcí „základních prostředků“. Zde chceme zdůraznit, že studujeme objem hrubé výroby (tj. množství měřené v peněžních jednotkách) jako funkci objemu základních prostředků (měřených rovněž v peněžních jednotkách). Funkce více proměnných: „y je funkcí x1, x2, ..., xn “............ zápis: y = f(x1, x2, ..., xn ) kde y - je závisle proměnná, xi -jsou nezávisle proměnné. Příklad 2: TC = f(K, L, r, w) „Celkové náklady“ jsou funkcí „množství kapitálu K a práce L, mzdové sazby w a úroku (nájemného) r“, konkrétně platí např. vztah: TC = r.K + w.L, přičemž r je úrok (nájemné) a w je mzdová sazba. 2.2 Matice a vektory Vhodným prostředkem pro vyjadřování ekonomických závislostí je maticová symbolika (někdy se používá termín vektorová symbolika). Matice A je obdélníkové schéma reálných čísel z R uspořádaných v m řádcích a n sloupcích. V tomto případě říkáme, že matice A je typu mn. Prvek matice A umístěný v i-tém řádku a j-tém sloupci označujeme aij. Matici zapisujeme takto: (2-1) Matice A se nazývá čtvercová, jestliže je m = n. Řádky a sloupce matice A se nazývají vektory. Ve speciálním případě se matice A může skládat pouze z jednotlivého řádkového vektoru, nebo z jednotlivého sloupcového vektoru, v tom případě stačí jediný index prvku matice. Například A = (a1, ..., an) je řádkový vektor. Jsou-li rovněž všechna aii = 0 pro i = 1, 2, ..., n, pak A se nazývá nulová matice a je označována 0. Jednotková nebo-li identická matice E je matice, pro kterou platí aij = 1 pro i = j, aij = 0 pro i a j. Transponovaná matice k matici A se označuje symbolem AT a vznikne přemístěním prvku v i,j pozici matice A na prvek v pozici j,i, to znamená, že vzájemně vyměníme řádky a sloupce matice A zrcadlově kolem hlavní diagonály a tak získáme AT . Dvě matice jsou shodné, jestliže se jejich odpovídající prvky rovnají. Definujeme dále symetrickou matici jako matici, pro kterou platí A = AT , tj. aij = aji pro všechna i a j. Nechť A= {aij }, B = {bij} jsou matice typu mn. Matice A je nezáporná (píšeme A  0), jestliže aij  0 pro všechna i = 1, 2, ..., m, j = 1, 2, ..., n. Matice A je kladná (píšeme A > 0), jestliže aij > 0 pro všechna Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 21 i a j. Definujeme rovněž A  B, jestliže platí aij  bij pro všechna i = 1, 2, ..., m, j = 1, 2, ..., n. Matice C = {cij} je součtem matic A a B, tj. C = A + B, jestliže platí cij = aij + bij pro všechna i = 1, 2, ..., m, j = 1, 2, ..., n. Pro součet matic stejného typu platí známé komutativní, asociativní a distributivní zákony, stejně jako pro sečítání reálných čísel. Skalární násobek matice A = {aij} je matice jejíž všechny prvky jsou rovny součinu každého prvku z A s konstantou a Î R, tj. aA={aaij}. Nechť A = {aij} je matice typu mn, B = {bjk} je matice typu nr. Matice C= {cik}, typu mr, je součinem matic A a B, tj. C = A.B, jestliže platí: jk n j ijik bac    1 (2-2) pro všechna i = 1, 2, ..., m, k = 1, 2, ..., r. Prvek výsledné matice C, vzniklé součinem matic A a B v i-tém řádku a k-tém sloupci je „skalárním„ součinem dvou vektorů: i-tého řádku matice A a k-tého sloupce matice B, viz obrázek 2.2. níže. Pro součin matic odpovídajícího typu (počet sloupců matice A je stejný, jako počet řádků matice B) platí známé asociativní a distributivní zákony stejně jako pro násobení reálných čísel. Obrázek 2.1: Schéma násobení matic Historicky vznikly matice ze seznamu koeficientů jako zjednodušující metoda řešení systému lineárních rovnic: (2-3) Matematický aparát EMM 22 Práce s takovým systémem je jednodušší, jestliže koeficienty, aij jsou odděleny od neznámých xj. Potom systém (2-3) lze zapsat takto: (2-4) Označíme-li vektor x = (x1, x2, ..., xn)T jako sloupcový vektor a stejně tak b = (b1, b2, ..., bm)T , můžeme systém lineárních rovnic (2-4), označovaný jako nehomogenní systém m lineárních rovnic o n neznámých, zapsat jednoduše takto: A x = b. (2-5) Inverzní matice A-1 ke čtvercové matici A typu nn má vlastnost: AA-1 = A-1 A = E. Pomocí inverzní matice můžeme získat řešení systému (2-5) ve tvaru: x = A-1b. (2-6) Pro b = 0, pak nenulové řešení homogenní soustavy Ax = 0 existuje, právě když neexistuje A-1 , jinak x =A-1 0 = 0 je jediným řešením. Matice A-1 neexistuje, právě když determinant A je roven nule. To platí pro čtvercovou matici. Samozřejmě neexistuje matice A-1 k obdélníkové matici, která není čtvercová! ŘEŠENÁ ÚLOHA 2-1 ŘEŠENÁ ÚLOHA 2-2 ŘEŠENÁ ÚLOHA 2-3 Ekvivalentní soustavy: Ax = b Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 23 ŘEŠENÁ ÚLOHA 2-4 Pomocí maticových funkcí v Excelu řešte soustavu rovnic: Řešení: Ekvivalentní soustava v maticovém tvaru vypadá takto: Ve worksheetu v Excelu si připravíte data: Matematický aparát EMM 24 Označíte pole, kde má být uložena inverzní matice A-1 k matici soustavy A, tj. pole A7:C9. Dále vložíte funkci pro výpočet inverzní matice v menu: fx (Vložit funkci)  Matematické  INVERZE: otevře se zadávací okno V okně Argumenty funkce vložíme pole, kde je uložena matice A, tj. A2:C4, potvrdíme OK za současného stisku kláves Shift+Ctrl ! V poli A7:C9 pro inverzní matici se objeví výsledek: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 25 Nakonec vyřešíme soustavu rovnic s pomocí maticového řešení: x = A-1 b. Nejprve označíme buňky pro vektor řešení x, tj. pole E2:E4. Pak vložíte funkci pro výpočet součinu matic: fx (Vložit funkci) Matematické  SOUČIN.MATIC: otevře se zadávací okno Argumenty funkce: V okně Argumenty funkce vložíme pole, kde jsou uloženy matice A-1 a b pro součin, tj. A7:C9 a G2:G4, pak potvrdíme OK za současného stisku kláves Shift+Ctrl ! V poli E2:E4 pro neznámý vektor x se objeví výsledek: Matematický aparát EMM 26 Řešením soustavy je tedy vektor x = (x1, x2, x3) = (-8, -9, 9). Zkoušku správnosti výsledku proveďte maticovým násobením původní matice A a vektoru x. Je výsledný součin matic, tedy vektor, roven vektoru pravých stran soustavy b? OTÁZKY  Co je to funkce?  Co je to čtvercová matice?  Jak se vypočítá inverzní matice?  Za jakých podmínek lze vynásobit dvě matice? SHRNUTÍ KAPITOLY Tato kapitola byla poměrně krátká a měla pomocný charakter. Byla věnována základním matematickým pojmům, které se vyskytují v oblasti optimalizačních metod, totiž funkcím jedné a více reálných proměnných. Dále jste se naučili prakticky zacházet s maticemi Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 27 a vektory pomocí vložených funkcí Excelu, což vám umožnilo řešit soustavy lineárních rovnic pomocí Excelu. Optimalizační problémy, extrémy funkce 28 3 OPTIMALIZAČNÍ PROBLÉMY, EXTRÉMY FUNKCE RYCHLÝ NÁHLED KAPITOLY Náplní této kapitoly bude seznámení s problematikou optimalizačních problémů - tzv. matematickým programováním. Hlavními problémy, kterými se budete zabývat, je formulace úloh a nalezení ekvivalentních tvarů těchto úloh, dále definice přípustného řešení a optimálního řešení úlohy matematického programování. Tento problém má dvě roviny: rovinu lokálních extrémů, která je snadněji řešitelná a rovinu globálních extrémů, která je obtížněji řešitelná. Dále se dozvíte o některých nutných a/nebo postačujících podmínkách zajišťujících existenci takových řešení. Budete přitom vycházet ze znalostí, které jste získali v základním kurzu matematiky o průbězích funkcí, využijete zejména základních pojmů diferenciálního počtu: limita a derivace, případně parciální derivace funkce více proměnných. Konečně, se naučíte řešit jednoduché úlohy matematického programování pomocí Excelu – Řešitele. CÍLE KAPITOLY Po prostudování této kapitoly budete umět:  Zapsat obecnou úlohu matematického programování.  Nalézt všechny lokální a globální extrémy funkce v Excelu.  Vypočítat Hessián funkce. KLÍČOVÁ SLOVA KAPITOLY Matematické programování, lineární programování, extrém funkce, Hessián, parciální derivace. 3.1 Optimalizační úlohy Úkolem matematického modelování v ekonomii bývá často nalezení optimálních rozhodnutí, přičemž matematickým protějškem pojmu optimality je pojem extrému funkce. Tím rozumíme buď maximum funkce, nebo její minimum. Jde například o nalezení optimálního výrobního plánu poskytujícího maximální zisk, jak bylo již zmíněno v předchozí kapitole. Jinou úlohou, s níž se budete v následujícím textu zabývat je nalezení plánu převozu určité komodity od dodavatelů k odběratelům, který by minimalizoval funkci přepravních nákladů. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 29 Je-li funkce f definována na množině X, značíme maximální hodnotu, které f na X nabývá symbolem Obvykle nás nezajímá pouze maximální hodnota funkce (např. hodnota zisku) ale spíše ten prvek množiny X, v němž je maximální hodnota dosažena (např. jednotlivé položky výrobního plánu). Takový prvek nazveme optimálním řešením optimalizační úlohy a označíme symbolem Obdobné významy mají symboly V tomto případě se jedná o minimální hodnotu funkce f(x) a „prvek“ množiny X, v němž se minimum realizuje, tj. optimální řešení. Pracujeme-li s funkcemi, je třeba rozlišovat funkci jako pravidlo, které přiřazuje jedné veličině hodnotu jiné veličiny, od funkční hodnoty, tedy čísla přiřazené konkrétní hodnotě nezávisle proměnné. Proto ze zápisu f(x) není zřejmé, máme-li na mysli pravidlo nebo hodnotu pro dané x. Proto je někdy lepší se dohodnout na značení funkce pouze symbolem f a symbolem f(x) rozumět funkční hodnotu pro x. S takovým zápisem jsou však také potíže: je-li např. f(x) = sin x, pak bychom podle právě uvedené dohody měli psát f = sin, což je ovšem v odborné literatuře nezvyklé. Navíc je někdy nutné označit, co je proměnná funkce, a to naše dohoda neumožňuje. Pro ulehčení orientace v textu budeme při používání matematické symboliky dodržovat tyto zásady:  množiny budeme označovat velkými písmeny, např. X, M, Y, Z, apod.,  matice, resp. vektory budeme označovat tučnými velkými, resp. malými písmeny, tedy např. A, B, resp. x, y, apod.,  pro funkce, jejich první i druhé derivace apod. budeme používat symboliku známou ze základních kurzů matematiky, tedy např. f(x), f´(x), f´´(x), dx df , 2 2 dx fd , apod. ŘEŠENÁ ÚLOHA 3-1 Maximalizujte funkci f(x) danou níže uvedeným předpisem. Řešení: Optimalizační problémy, extrémy funkce 30 Uvažujme nyní obdobnou úlohu, kde opět X = [0, 3]: f(x) = 2 - (x - 0,9)2 pro x  [0, 0,9] = 2 pro x  (0,9, 3] Potom, viz obrázek níže, je min f(x) = 1,19 , argmin f(x) = 0 , max f(x) = 2 , argmax f(x) = [0,9 , 3]. 3.2 Matematické programování Speciální případ optimalizačních úloh se vžil pod názvem matematické programování. Dnešní význam slova „programování“ se váže jednoznačně k programování počítačů, matematické programování se však konstituovalo ještě těsně před nástupem počítačů v padesátých letech minulého století a slovo „programování“ v něm má spíše význam „plánování“, případně „projektování“. Speciálním případem matematického programování je vám již známé lineární programování. Pokud některá z vystupujících funkcí není lineární, hovoříme o nelineárním programování. Častou úlohou řídicí praxe je nalezení optimální varianty z množiny variant vymezené soustavou podmínek. Takovou úlohou jste se zabývali v předešlé kapitole: byla to úloha Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 31 optimálního výrobního plánování, která patří do lineárního programování. Účinnost řízeného ekonomického systému je v ní měřena hodnotou ukazatele, který je chápán jako hlavní charakteristika stavu systému. V předchozí kapitole byl tímto ukazatelem zisk. Optimální variantou je potom taková varianta, která extremalizuje (tj. maximalizuje nebo minimalizuje) hodnotu tohoto ukazatele. Při použití vhodného kódování je možné popsat každou variantu pomocí uspořádané n-tice čísel, tj. vektorem x = (x1, x2, ..., xn). Podmínky, které musí varianta splňovat, aby byla přípustná, je možné symbolicky zapsat pomocí funkcí g1, g2, ..., gm. Úlohu matematického programování lze proto symbolicky vyjádřit takto: f(x1, x2, ..., xn) → MAX (MIN); (3-1) za podmínek g1(x1, x2, ..., xn)  b1, g2(x1, x2, ..., xn)  b2, ............................................... gm(x1, x2, ..., xn)  bm , (3-2) x1  0 , x2  0 , ..., xn  0. (3-3) O podmínkách (3-3) je hovoří jako o podmínkách nezápornosti. Prvních m omezujících podmínek (3-2) jsou tzv. vlastní omezení. Funkce f v (3-1) se nazývá účelová (cílová) funkce. Množina všech x = (x1, x2, ..., xn) splňujících omezení (3-2) a (3-3) se nazývá množinou přípustných řešení. Ještě připomeňme, že přípustné řešení x*, v němž funkce f nabývá svého maxima (minima) nazýváme optimálním řešením úlohy (3-1) – (3-3). Úloha matematického programování, kde všechny funkce f, a gi v úloze (3-1) – (3-3) jsou lineární, tj. jsou ve tvaru (1-1), (1-2), se nazývá úlohou lineárního programování (LP). V teorii lineárního programování se vystačí s poměrně jednoduchým aparátem lineární algebry a rovněž výpočty úloh LP se obejdou bez složitých výpočetních postupů. Teorie LP proto tvoří základní součást teorie matematického programování. V dnešní době tvoří tyto výpočetní postupy součásti běžně používaných SW systémů, např. v populárním MS Excel je LP součástí položky Řešitel (Solver). Podrobněji se budete zabývat LP v kapitole 5, tam se rovněž naučíte řešit úlohy LP pomocí Řešitele v Excelu. Předpoklady vedoucí k modelu LP jsou ovšem často značně zjednodušující, což v mnoha případech neumožňuje vystihnout podstatu modelovaného jevu. Tak např. jednotkový zisk cj v účelové funkce (1-1) jsme považovali za nezávislý na rozsahu výroby xj. V případě, kdy však uvažujeme i s rozsahem výroby xj = 0, tedy že se výrobek vůbec nevyrábí, je tento předpoklad značně nerealistický. Obvykle je tomu tak, že s růstem produkce jednotkový zisk rovněž roste, například lineárně, tedy cj = djxj + bj, kde dj > 0. Účelová funkce vyjadřující celkový zisk je potom nelineární, konkrétně má kvadratickou formu f(x) = ∑ (djxj + bj)xj, (3-4) Optimalizační problémy, extrémy funkce 32 pak i příslušná maximalizační úloha s účelovou funkcí (3-4) a lineárními omezeními (1- 2), (1-3), je úlohou nelineárního (konkrétně kvadratického) programování. Následující optimalizační úloha je příkladem úlohy nelineárního matematického programování ve tvaru (3-1) až (3-3): (x1)2 + (x2)3 → MAX; za podmínek x1 + 3x2  10, x1 + x2  6, x1  0 , x2  0. Řešením této úlohy pomocí Excelu-Řešitele se budeme zabývat na konci kapitoly. Nelineární tvar účelové funkce se projevuje druhou mocninou proměnné x1 a třetí mocninou proměnné x2, omezující podmínky jsou lineární. 3.3 Ekvivalentní tvary úloh matematického programování Z hlediska nalezení řešení optimalizační úlohy nezáleží na tom, zda se jedná o úlohu maximalizační nebo minimalizační. To vyplývá z jednoduchého vztahu min f(x) = - max -f(x) , který znamená, že minimální hodnota nějaké funkce f na jisté množině X je rovna mínus maximální hodnotě z funkce mínus f na téže množině X. Jinak řečeno a vyjádřeno: x* = arg min f(x) = arg max (- f(x)). Tento fakt je zřejmý také z následujícího obrázku. Lze se tedy omezit pouze na úlohy s maximalizací účelové funkce. Další ekvivalentní úpravy se vztahují k vlastním omezením optimalizační úlohy. Nejprve si uvědomte, že každá nerovnice se znaménkem nerovnosti „” může být převedením levé strany na pravou (se současnou změnou znaménka) a obráceně z levé na pravou, změněna na nerovnici se znaménkem nerovnosti „”. Tedy například nerovnice g(x1, x2, ..., xn)  b, Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 33 je totéž, co nerovnice - g(x1, x2, ..., xn)  - b. Pokud se tedy při sestavování modelu vyskytnou omezující podmínky typu „”, lze je snadno převést na omezující podmínky typu „”, tedy na úlohu (3-1) – (3-3). Dále si všimneme omezující podmínky typu rovnice. Takové omezení lze zaměnit na dvojici omezujících podmínek typu nerovnice, např. rovnici g(x1, x2, ..., xn) = b, lze zaměnit za 2 nerovnice s různými typy nerovnosti g(x1, x2, ..., xn)  b a g(x1, x2, ..., xn)  b, anebo také za 2 nerovnice se stejnými typy nerovnosti, např. -g(x1, x2, ..., xn)  -b a g(x1, x2, ..., xn)  b. Nerovnici můžeme také zaměnit za rovnici a podmínku nezápornosti pomocí tzv. přídatné proměnné. Tedy namísto g(x1, x2, ..., xn)  b, můžeme uvažovat dvě omezení g(x1, x2, ..., xn) + xn+1= b, xn+1  0. Uvedené ekvivalentní úpravy umožňují zabývat se při řešení úloh matematického programování pouze jediným typem formulace úlohy, na který lze každou úlohu vždy převést. Tento typ se v odborné literatuře nazývá standardní tvar úlohy matematického programování. Tímto tvarem je obvykle maximalizační úloha s omezeními typu „” a omezeními nezápornosti, tj. úloha (3-1) - (3-3). 3.4 Lokální a globální extrémy Úlohy matematického programování (MP) lze rozdělit na dva typy. Postup řešení v zásadě vždy spočívá v tom, že z jakéhokoliv výchozího přípustného nebo i nepřípustného řešení úlohy (3-1) – (3-3) postupnými kroky získáváme nová přípustná řešení úlohy (3-1) – (3-3), přitom zlepšujeme hodnotu účelové funkce. U prvního typu úlohy MP získáváme z jakéhokoliv výchozího přípustného nebo i nepřípustného řešení úlohy postupnými kroky nová přípustná řešení, přičemž zlepšujeme hodnotu účelové funkce, až nakonec obdržíme optimální řešení úlohy (3-1) – (3-3). U druhého typu úlohy MP rovněž získáváme nová přípustná řešení, zlepšujeme hodnotu účelové funkce, avšak optimální řešení úlohy (3-1) – (3-3) nemusíme vždy obdržet. Závisí to na tom, jaké výchozí přípustné řešení jsme zvolili. Tyto vlastnosti úlohy MP úzce souvisí s existencí tzv. lokálních extrémů, které buď jsou nebo nejsou současně extrémy globálními. Přesněji to vyjádří následující definice, kterou ilustruje níže uvedený obrázek 3.1. Optimalizační problémy, extrémy funkce 34 DEFINICE 3-1 Řekneme, že x0  X je prvkem (nebo též bodem) lokálního maxima funkce f na množině X, jestliže existuje okolí U bodu x0 takové, že pro všechna x  X z tohoto okolí platí f(x) ≤ f(x0 ). Funkční hodnotu f(x0 ) nazýváme lokální maximum funkce f na X. Řekneme, že x*  X je prvkem globálního maxima funkce f na množině X, jestliže pro všechna x  X platí f(x) ≤ f(x* ). Funkční hodnotu f(x* ) nazýváme globální maximum funkce f na X. Úlohy MP prvního typu splňují tu vlastnost, že každý bod lokálního maxima je zároveň bodem globálního maxima. Úlohami tohoto typu jsou např. úlohy konvexního programování a také úlohy lineárního programování. Těmi se budete zabývat v následujících ka- pitolách. Úlohy MP druhého typu se vyznačují tím, že některá lokální maxima nejsou současně globální, viz např. x0 v následujícím obrázku je bodem lokálního maxima (neboť existuje příslušné okolí U z definice 3-1). Bodem globálního maxima na množině X je však bod x*. Namísto hledání „bodu lokálního/globálního maxima f(x)“ často zkráceně (a poněkud nepřesně) říkáme, že hledáme „lokální maximum f(x)“. Máme přitom však na mysli, že hledáme prvek, v němž se realizuje maximální hodnota účelové funkce, tj. argmax f(x). Analogicky lze definovat pojem lokální minimum a globální minimum funkce f(x) na X. Obrázek 3.1: Lokální a globální extrémy funkce f(x) Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 35 3.5 Existence řešení Nejprve se budeme zabývat otázkou, za jakých podmínek existuje optimální řešení úlohy MP, tedy úlohy (3-1) – (3-3). Odpověď dává následující matematický teorém (věta). VĚTA Je-li účelová funkce f v úloze (3-1) – (3-3) spojitá na neprázdné množině X dané soustavou nerovnic (3-2) a (3-3) a množina přípustných řešení X je přitom uzavřená a omezená množina, potom existuje alespoň jedno optimální řešení úlohy MP (3-1) – (3-3). Význam výše uvedené věty se dá přetlumočit také takto: Spojitá funkce f nabývá na uzavřené omezené množině X svého maxima (i minima). Přitom funkce je spojitá na množině X, je-li spojitá v každém bodě této množiny, tedy jestliže se limita funkce v každém bodě této množiny rovná funkční hodnotě v tomto bodě: Spojitost funkce si lze představit jako souvislost grafu funkce, kdy graf funkce není nikde „roztržen”, viz obrázek níže. Obrázek 3.2: Spojitá funkce Příklad nespojité funkce s „roztrženým“ grafem je na následujícím obrázku Obrázek 3.3: Nespojitá funkce Množina X je uzavřená, jestliže obsahuje i svoji hranici, např. v rovině to může být kruh včetně jeho obvodové kružnice. Naproti tomu kruh bez své hranice – obvodové kružnice – není uzavřená množina a tvoří tzv. otevřenou množinu. Optimalizační problémy, extrémy funkce 36 Množina je omezená, jestliže se vejde do nějakého kruhu (přesněji: vícerozměrné koule o konečném poloměru). Příkladem omezené množiny v rovině je čtverec, příkladem neomezené množiny v rovině je polopřímka nebo celý první kvadrant. Ze základního kurzu matematiky si jistě pamatujete vyšetřování průběhu funkce jedné reálné proměnné. Učili jste se, že maximum (minimum) se obvykle nabývá v těch bodech, kde je derivace rovna nule. Jinak řečeno, tečna ke grafu funkce je v tomto bodě rovnoběžná s osou x. Tento poznatek nyní rozšíříme také pro funkce n proměnných. VĚTA 3-2 Nechť f je funkce n proměnných x1, x2, ..., xn definovaná na množině X a x0 = (x10, x20, ..., xn0) je bodem lokálního maxima (nebo lokálního minima) funkce f na X. Jestliže pro nějakou proměnnou xj existuje parciální derivace potom je tato parciální derivace nulová, tj. V bodě lokálního extrému x0 je tedy každá parciální derivace nulová, tedy také gradient, což je vektor všech parciálních derivací, který značíme takto: je nulový vektor. Dále jste se při vyšetřování průběhu funkce f jedné proměnné dozvěděli, že tam, kde je (první) derivace nulová a zároveň je tam druhá derivace záporná, nabývá funkce f svého lokálního maxima. Pokud je druhá derivace kladná, nabývá tam funkce svého lokálního minima, pokud je však nulová, jedná se o tzv. inflexní bod a funkce tam nemusí nabývat žádný lokální extrém. Také tento poznatek rozšíříme na funkce více proměnných. Budeme k tomu potřebovat pojem Hessiánu, tj. matice druhých parciálních derivací. DEFINICE 3-2 Nechť f je funkce n proměnných x1, x2, ..., xn definovaná na množině X a nechť x0 = (x10, x20, ..., xn0)  X. Matice druhých parciálních derivací H v bodě x0 se nazývá Hessovou maticí (Hessiánem) funkce f v bodě x0 a označuje se takto Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 37 DEFINICE 3-3 Hlavními subdeterminanty čtvercové matice H typu (nxn) nazýváme determinanty všech takových matic, které vzniknou z H tím, že z H vypustíme libovolné sloupce i1, i2, ..., ik a zároveň vypustíme řádky i1, i2, ..., ik . Poznámka: Hlavních subdeterminantů matice H je tedy tolik, kolik je způsobů vypuštění sloupců (a řádků), tj. 2n – 1. Hlavním subdeterminantem je také determinant samotného Hessiánu H, kdy se nevypustí žádný řádek ani sloupec. Na druhou stranu vypuštění všech řádků i sloupců v matici H neuvažujeme, proto je počet všech hlavních subdeterminantů matice H snížen o 1. Nyní se dostáváme ke slíbenému tvrzení o existenci lokálního extrému úlohy MP. Nejprve formulujeme známé tvrzení pro funkce jedné reálné proměnné. Poté zformulujeme rozšíření této věty pro funkce více proměnných. VĚTA 3-2 Jestliže funkce f(x) definovaná na množině X  R má spojitou prvou a druhou derivaci v okolí x0 X, derivace f´(x0 ) = 0 a zároveň druhá derivace f´´(x0 ) > 0, potom x0  X je bodem lokálního minima funkce f(x). Pokud je zároveň druhá derivace f´´(x0 ) < 0, potom x0  X je bodem lokálního maxima funkce f(x). VĚTA 3-3 Jestliže funkce n proměnných x1, x2, ..., xn definovaná na množině X má spojité první a druhé parciální derivace v okolí x0 = (x1 0 , x2 0 , ..., xn 0 )X, gradient f(x0) = 0 a zároveň všechny hlavní subdeterminanty Hessiánu H = {f(x0)} jsou kladné (tj. > 0), potom x0 =(x1 0 , x2 0 , ..., xn 0 ) X je bodem lokálního minima funkce f(x1, x2, ..., xn ). Pokud jsou zároveň a všechny hlavní subdeterminanty Hessiánu H = {2 f(x0)} záporné (tj. < 0), potom x0 X je bodem lokálního maxima funkce f(x1, x2, ..., xn ). Optimalizační problémy, extrémy funkce 38 ŘEŠENÁ ÚLOHA Nalezněte Hessián funkce f tří proměnných v bodě x0 = (1, 1, 1), přitom: Dále vypočítejte všechny hlavní subdeterminanty! Řešení: Nejprve vypočítáme gradient f(x1, x2, x3), tj. vektor všech 3 parciálních derivací:               3 33 2 2 2 32 3 1 321 88 8 4 ,, xxx xx x xxxf Dále vypočítáme matici druhých parciálních derivací, tj. parciálních derivací funkcí v gradientu a nakonec dosadíme bod x0 = (1, 1, 1): Hlavních subdeterminantů je celkem 23 – 1 = 7. Determinant matice 1. řádu, tj. matice typu (1x1) (tj. s 1 prvkem) je roven přímo tomuto prvku. Známým Sarrusovým pravidlem pro výpočet determinantů 2. a 3. řádu vypočítáte hodnoty dalších hlavních subdeterminatů: 12, 8, 32, 96, 0, 384, 0. ŘEŠENÁ ÚLOHA 3-2 Nalezněte všechny lokální i globální extrémy funkce f(x) = 2 - (x - 1)2 pro x  [0 , 3]. Použijte přitom Excel – Řešitel. Řešení: Nejprve zobrazíme graf funkce f(x). V uvažovaném intervalu [0 , 3] vytvoříme dělicí body ve sloupci se záhlavím x, v poli A3:A33 s diferencí d = 0,1. V těchto dělicích bodech zjistíme hodnoty uvažované funkce, tak, že v levém krajním bodě x0 = 0 vypočítáme Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 39 funkční hodnotu podle vzorce =2-(A3–1)^2 zapsaného v buňce B3 a poté vzorec nakopírujeme roztažením do celého pole B3:B33 se záhlavím f(x). Dva vytvořené sloupce zobrazíme ve spojnicovém tvaru bodového grafu, viz Obr. 3.5. Z grafu je zřejmé, že globální maximum nabývá funkce v bodě x* = 1, globální minimum nabývá funkce v bodě x** = 3, v bodě x0 = 0 nabývá funkce lokální minimum, které však není globálním minimem. Příprava k použití Excelu-Řešitele se nachází v poli D2:E3, viz Obr. 3.5. Účelová funkce má adresu E3 a je v ní vzorec na výpočet funkční hodnoty: =2 - (D3 – 1)^2. Proměnná x je označena zelenou barvou, má adresu D3. V hlavní nabídce zvolíme Data  Řešitel... otevře se okno Parametry Řešitele, viz Obr. 3.4. Obrázek 3.4: Parametry řešitele Tlačítko Hledat: zvolíme Max, neboť nejprve budeme funkci maximalizovat. Do omezujících podmínek vložíme nerovnosti 0  x  3, což v Excelu vyjádříme vzorci: D3 <=3 a D3 >=0. Po kliknutí tlačítka Řešit obdržíme řešení v buňkách D3 (hodnota proměnné x) a E3 (funkční hodnota). Globální maximum se tedy nabývá funkce v bodě x* = 1, hodnota funkce v tomto bodě je f(x*) = 2. Optimalizační problémy, extrémy funkce 40 Obrázek 3.5: Graf funkce f(x) = 2 - (x - 1)2 pro x  [0 , 3] Řešitel používá k nalezení řešení zabudovanou iterační metodu (tzv. zobecněnou Newtonovu metodu): začne výpočet ze zadaného počátečního řešení x(0) = 0 v buňce D3. Metoda nabídne další řešení x(1) z množiny X=[0,3], kde je hodnota účelové funkce vyšší, potom další řešení x(2), kde je hodnota účelové funkce ještě vyšší, atd., až se po určitém počtu kroků dostane do x* = 1, kde již nelze hodnotu účelové funkce dále zvýšit: to je hledaný bod extrému. Celý výpočet proběhne ve zlomku sekundy. Řešitel však (bohužel) vypočítá pouze lokální extrém (v tomto případě maximum) a nic nezaručuje, že se jedná o extrém globální. Toto dodatečné stanovení, zda jde zároveň o globální extrém, či nikoliv, musí učinit člověk – řešitel, který to pozná např. z grafu funkce, jako v našem případě. Pokud má vyšetřovaná funkce více lokálních extrémů, pak Řešitel nalezne jedno z nich, obvykle to, které je nejblíže výchozímu řešení x(0). Tuto vlastnost Řešitele si demonstrujeme při hledání minima naší funkce f(x). Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 41 V Parametrech Řešitele pro tlačítko Rovno: zvolíme Min, neboť nyní budeme funkci minimalizovat, ostatní parametry ponecháte beze změny. Pokud bude výchozí řešení x(0) = 1 (což je bod globálního maxima), Řešitel tento bod vypočítá nesprávně(!) jako bod lokálního minima. V případě že výpočet zahájíte z jiného výchozího řešení např. x(0) = 0,5, pak řešitel vypočítá bod lokálního minima x** = 0. Pokud však výpočet zahájíte z výchozího řešení např. x(0) = 2, pak řešitel vypočítá bod lokálního minima x** = 3, hodnota funkce v tomto bodě je f(x**) = -2. Je vidět, že v tom případě závisí nalezené minimum (lokální nebo globální) na výchozím počátečním řešení, z něhož iterační výpočet startuje. Nakonec vyřešíme úlohu matematického programování se dvěma proměnnými. ŘEŠENÁ ÚLOHA 3-3 Nalezněte optimální řešení (tj. bod globálního maxima) úlohy nelineárního MP: (x1 )2 + (x2)3  MAX; za podmínek x1 + 3x2  10, x1 + x2  6, x1  0 , x2  0. Využijte Excel – Řešitel. Řešení: Příprava k použití Excelu-Řešitele ve worksheetu na Obr. 3.7. Účelová funkce má adresu C3 a je v ní vzorec na výpočet funkční hodnoty: =A3^2+B3^3. Proměnné x1 a x2 jsou označeny zelenou barvou, mají adresu A3 a B3. Levé strany omezujících podmínek jsou umístěny v buňkách C5, resp. C6 pomocí vzorců A3+3*B3, resp. A3+B3. Příslušné pravé strany těchto omezujících podmínek jsou v buňkách D5, resp. D6. V hlavní nabídce zvolíme Data  Řešitel... otevře se okno Parametry Řešitele, které vyplníme podle Obr. 3.6. Optimalizační problémy, extrémy funkce 42 Obrázek 3.6: Parametry řešitele Obrázek 3.7: Příprava pro použití Řešitele Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 43 Obrázek 3.8: Množina přípustných řešení v úloze 3-3 Všimněte si, že při zadávání omezujících podmínek v Parametrech řešitele, viz Obr. 3.6, byla použita možnost zadání více buněk (blok 2 buněk) najednou na levé i pravé straně omezení. Po kliknutí tlačítka Řešit obdržíme řešení v buňkách A3 (hodnota proměnné x1) a B3 (hodnota proměnné x2). Globální maximum se tedy nabývá funkce v bodě x* = (x1, x2) = (0, 41 /3), hodnota funkce v tomto bodě je f(x*) = 37,04. Pozor, pokud vstupní hodnoty proměnných x1 a x2 budou rovny 0, pak Řešitel nenalezne maximum, ale minimum. Proto je zapotřebí před začátkem řešení nastavit vhodné nenulové hodnoty pro x1 a x2, např. stačí nastavit x1 = x2 = 1. OTÁZKY  Ukažte, že nalezené řešení v řešené úloze 3-3 je bodem globálního maxima (že úloha nemá jiné lokální maximum).  Pomocí Excelu – Řešitele samostatně vyřešte následující úlohu MP: Nalezněte všechny (lokální i globální) extrémy funkce f(x) v intervalu [-1, 1], resp. v intervalu [2, 3]: Optimalizační problémy, extrémy funkce 44 SHRNUTÍ KAPITOLY Náplní této kapitoly bylo seznámení s problematikou optimalizačních problémů – matematickým programováním. Hlavními problémy, kterými jste se zabývali, byla formulace úloh a nalezení ekvivalentních tvarů těchto úloh, dále definice přípustného řešení a optimálního řešení úlohy matematického programování. Tento problém má dvě roviny: rovinu lokálních extrémů, která je snadněji řešitelná a rovinu globálních extrémů, která je obtížněji řešitelná. Dále jste se dozvěděli formou matematických vět o některých nutných a/nebo postačujících podmínkách zajišťujících existenci takových řešení. Přitom jste vycházeli ze znalostí, které jste získali v základním kurzu matematiky o průbězích funkcí, využili jste zejména základních pojmů diferenciálního počtu: limity, derivace funkce jedné proměnné a parciální derivace funkce více proměnných. Konečně, jste se naučili řešit jednoduché úlohy matematického programování pomocí Excelu – Řešitele. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 45 4 MATEMATICKÉ PROGRAMOVÁNÍ – KONVEXNÍ ÚLOHY RYCHLÝ NÁHLED KAPITOLY V minulé kapitole jsme rozdělili úlohy matematického programování (MP) do dvou skupin: v první skupině jsou takové úlohy, kde lokální extrém je vždy zároveň globálním, ve druhé skupině jsou úlohy, kde lokální extrém nemusí být současně globálním. Dále se budete zabývat 1. skupinou úloh MP. Ukážeme, že jsou to takové úlohy, kde jak účelová funkce f, tak funkce gi v omezujících podmínkách splňují podmínky konvexnosti, resp. konkávnosti. V této kapitole se proto budete zabývat tzv. konvexním programováním, což je součást MP. Speciálním případem konvexního programování je potom lineární programování, kterému budou věnovány další kapitoly. Důležitou částí matematického programování je teorie tzv. sedlových bodů. Tato teorie se týká zajímavé a důležité souvislosti mezi úlohou MP a sedlovým bodem jisté přidružené funkce, která se nazývá Lagrangián. Význam této teorie spočívá v tom, že jednak umožňuje konstrukci řady praktických výpočetních postupů k řešení úloh MP, jednak je východiskem k teorii duality v MP. Nakonec formulujeme tzv. Kuhn-Tuckerovy podmínky umožňující nalézt sedlový bod pomocí řešení soustavy nerovností, což je zobecněna podmínka „nulovosti derivace“. CÍLE KAPITOLY Po prostudování této kapitoly budete umět:  Rozlišit konvexní a konkávní funkci.  Vypočítat Lagrangián k úloze matematického programování s omezujícími podmín- kami.  Nalézt optimální řešení úlohy matematického programování s omezujícími podmínkami v Excelu. KLÍČOVÁ SLOVA KAPITOLY Konvexní funkce, konkávní funkce, Lagrangián, sedlový bod, Kuhn-Tuckerovy pod- mínky. 4.1 Konvexní množiny a konvexní a konkávní funkce V minulé kapitole jsme rozdělili úlohy matematického programování (MP) (3-1) – (3- 3) do dvou skupin: v první skupině jsou takové úlohy, kde lokální extrém je vždy zároveň Matematické programování – konvexní úlohy 46 globálním, ve druhé skupině jsou úlohy, kde lokální extrém nemusí být současně globálním. Dále se budete zabývat 1. skupinou úloh MP. Ukážeme, že jsou to takové úlohy, kde jak účelová funkce f v (3-1), tak funkce gi v omezujících podmínkách (3-2) splňují podmínky konvexnosti, resp. konkávnosti. V této kapitole proto budete zabývat tzv. konvexním programováním, což je část MP. Speciálním případem konvexního programování je potom lineární programování, kterému budou věnovány další kapitoly. DEFINICE 4-1 Množina X  Rn je konvexní množina, jestliže pro každé dva body x(1) , x(2) z X a pro každá dvě čísla 1 0, 2  0 taková, že 1 + 2 = 1 platí, že 1x(1) + 2x(2) patří do X. Tato definice vyjadřuje skutečnost, že množina je konvexní, když s každými dvěma body do ní patří také celá úsečka tyto body spojující. DEFINICE 4-2 Funkce f definovaná na konvexní množině X  Rn je konvexní funkcí na množině X, jestliže pro každé dva body x(1) , x(2) z X a pro každá dvě čísla 1 0, 2  0 taková, že 1 + 2 = 1 platí: f(1x(1) + 2x(2) ) ≤ 1 f(x(1) ) + 2 f(x(2) ). (4-1) Ekvivalentně k (4-1): pro každé číslo 0 ≤ l ≤ 1 , platí f(x(1) + (1-)x(2) ) ≤ l f(x(1) ) + (1-) f(x(2) ). (4-2) Funkce f je ryze konvexní na konvexní množině X  Rn , jestliže pro každé dva body x(1) , x(2) z X a každá dvě čísla 1 > 0 , 2 > 0 taková že 1 + 2 = 1 platí: f(1x(1) + 2x(2) ) < 1 f(x(1) ) + 2 f(x(2) ). (4-3) Funkce f je na konvexní množině X  Rn konkávní (resp. ryze konkávní), jestliže je funkce (- f ) konvexní (resp. ryze konvexní) na X. Konkávní (resp. ryze konkávní) funkce lze také analogicky definovat pomocí nerovností podobných jako (4-1) až (4-3), s tím rozdílem, že namísto nerovností „≤“ v (4-1) a (4-2) platí nerovnost obrácená, tedy „”. Snadno lze ukázat, že když je funkce gi konvexní a bi jsou reálná čísla, potom množina všech x = (x1, x2, ... , xn)Rn splňujících nerovnici gi(x1, x2, ..., xn)  bi (4-4) je konvexní množina, pro i = 1, 2, ..., m. V tom případě je ovšem množina X daná podmínkami (3-2) a (3-3) také konvexní množina, neboť je průnikem m konvexních množin. V následujících obrázcích jsou znázorněny nejprve grafy funkcí v R, které jsou konvexní (nikoliv ryze konvexní) a ryze konvexní: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 47 Obrázek 4.1: Graf konvexní (nikoliv ryze) funkce a Graf ryze konvexní funkce Dále jsou znázorněny grafy funkcí v R, které nejsou konvexní, i když to na první pohled tak vypadá: Obrázek 4.2: Grafy funkcí, které nejsou konvexní Na dalších obrázcích jsou znázorněny grafy funkcí v R, které jsou konkávní (nikoliv ryze) a ryze konkávní. Obrázek 4.3: Graf konkávní (nikoliv ryze) funkce a Graf ryze konkávní funkce Na poslední dvojici obrázků jsou znázorněny grafy funkcí v R2 , které jsou konkávní (nikoliv ryze) a ryze konkávní. Matematické programování – konvexní úlohy 48 Úlohu matematického programování (1-10) – (1-12), kde funkce f je konvexní (pro MIN) nebo konkávní (pro MAX) a všechny funkce gi jsou konvexní nazýváme úlohou konvexního programování. Dále uvedeme dříve zmíněné výsledky o lokálních a globálních extrémech úlohy konvexního programování. VĚTA 4-1 Jestliže jsou všechny funkce gi konvexní a bi jsou reálná čísla pro i = 1, 2, ..., m, potom množina všech x = (x1, x2, ..., xn)Rn splňujících podmínky gi(x1, x2, ... , xn)  bi, i = 1, 2, ..., m, xj  0, j = 1, 2, ..., n, (4-5) je konvexní množina. Následující tvrzení odpovídá na otázku, jak poznáme, že je nějaká funkce konvexní. V základním kurzu matematiky jste se dozvěděli, že funkce jedné proměnné je konvexní na nějakém intervalu, je-li druhá derivace kladná v každém bodě tohoto intervalu. Tento poznatek rozšíříme na funkce více proměnných. Použijeme k tomu již známé pojmy z předchozí kapitoly. VĚTA 4-3 Jestliže funkce f definovaná na konvexní množině X Rn má pro každé xX všechny hlavní subdeterminanty Hessiánu H = {f(x)} nezáporné, tj.  0, (resp. nekladné, tj. potom f je na X konvexní (resp. konkávní). Pokud jsou pro každé x X všechny hlavní subdeterminanty Hessiánu H = {2 f(x)} kladné, tj. > 0, (resp. záporné, tj. < 0), potom f je na X ryze konvexní (resp. ryze konkávní). Také následující věta může být užitečná při stanovení toho, zda funkce je konvexní. Vyplývá z ní, že kladný násobek konvexní funkce je opět konvexní a součet dvou (nebo více) konvexních funkcí je rovněž konvexní. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 49 VĚTA 4-4 Nechť f1(x), f2(x) jsou konvexní funkce na konvexní množině X, y1, y2 nechť jsou nezáporné konstanty. Potom funkce g(x) = y1 f1(x) + y2 f2(x) je konvexní funkce na X. ŘEŠENÁ ÚLOHA 4-1 Zjistěte, na jaké množině je funkce f(x,y) = 2x2 + xy2 + 3y3 konvexní. Řešení: Nejprve vypočítáme Hessián funkce f, tj. Dále vypočítáme hlavní subdeterminanty H (jsou 3!): 4, 2x+18y, 4(2x+18y) – 4y2 . Množinu X, kde jsou všechny hlavní subdeterminanty nezáporné, a tedy funkce f je konvexní, lze zřejmě vymezit takto: X = {(x,y)| x + 9y  0, 2x + 18y – y2  0}. 4.2 Teorie sedlových bodů Důležitou částí matematického programování je teorie tzv. sedlových bodů. Tato teorie se týká zajímavé a důležité souvislosti mezi úlohou MP a sedlovým bodem jisté přidružené funkce, která se nazývá Lagrangián. Význam této teorie spočívá v tom, že jednak umožňuje konstrukci řady praktických výpočetních postupů k řešení úloh MP, jednak je východiskem k teorii duality v MP. Nově zavedené proměnné, které vystupují v duálních úlohách, poskytují cenné informace o vlastnostech optimálních řešení úlohy MP. V dalším výkladu budeme vycházet ze základního tvaru úlohy (3-1) – (3-3) matematického programování, který zde pro pohodlí čtenáře zopakujeme: f(x1, x2, ..., xn) → MAX; (4-6) za podmínek g1(x1, x2, ..., xn)  b1 g2(x1, x2, ..., xn)  b2 (4-7) Matematické programování – konvexní úlohy 50 ............................................... gm(x1, x2, ..., xn)  bm x1  0 , x2  0 , ..., xn  0 (4-8) Lagrangián k úloze MP je funkcí původních n proměnných x1, x2, ..., xn a nových m proměnných y1, y2, ..., ym. Tyto nové proměnné nazýváme duální proměnné, někdy se nazývají také Lagrangeovy multiplikátory. F(x,y) = f(x1, x2, ... , xn) + yi(bi - gi(x1, x2, ... , xn)) (4-9) Vidíte, že v lagrangiánu F jsou duální proměnné yj vzájemně jednoznačně přiřazeny k omezujícím podmínkám (4-7). Sedlový bod (nezáporný) funkce F je taková dvojice x0Rn , y0Rm , pro kterou platí nerovnosti F(x, y0)  F(x0, y0)  F(x0,y) (4-10) pro všechna x  0, y  0. VĚTA 4-5 Nechť x0Rn , y0Rm je nezáporný sedlový bod Lagrangiánu úlohy (4-6), (4-8). Potom x0 je optimální řešení úlohy (4-6), (4-8). Na větě 4-5 je pozoruhodný fakt, že pro její platnost nejsou nutné žádné předpoklady o vlastnostech funkcí f a gi. Její důkaz je tak jednoduchý a instruktivní, že jej zde uvedeme: Nechť x0  0, y0  0, je nezáporný sedlový bod Lagrangiánu úlohy (4-6), (4-8). Z pravé nerovnosti ve (4-10) plyne, že x0 je přípustné, když volíme postupně yi =1 a yj = 0 pro j  i. Kdyby pro přípustné x0 byl výraz yi 0 (bi – gi(x0)) > 0, potom by pravá nerovnost ve (4- 10) nemohla být splněna pro y = 0. Proto musí platit yi 0 (bi – gi(x0)) = 0. Potom ale z levé nerovnosti ve (4-10) plyne: f(x) + yi 0 (bi – gi(x))  f(x0), a pro každé přípustné x musí platit yi 0 (bi – gi(x))  0. Odtud dostáváme, že f(x)  f(x0) pro každé přípustné x. Proto je x0 optimální řešení úlohy (4-6), (4-8). Pro ilustraci sedlového bodu uvedeme následující obrázek. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 51 Obrázek 4.5: Sedlový bod funkce F(x,y) = -x2y2 Obrácené tvrzení k větě 4-5 platí jen za poměrně silných předpokladů tzv. Regularity. VĚTA 4-6 Nechť f, gi jsou konvexní funkce na množině přípustných řešení X dané podmínkami (4- 7) a (4-8), dále nechť existuje bod x0, takový, že platí: gi(x0) < 0 pro všechna i pro která je gi nelineární (tzv. podmínka regularity). Potom existují x0 Rn , y0Rm - nezáporný sedlový bod Lagrangiánu úlohy (4-6), (4-8). VĚTA 4-7 (KUHN – TUCKERŮV TEORÉM) Nechť f, gi jsou konvexní diferencovatelné funkce na množině přípustných řešení X dané podmínkami (4-7) a (4-8). Potom (x0, y0) je nezáporným sedlovým bodem Lagrangiánu F, právě když splňuje tyto podmínky: (*) x F(x0, y0)  0, y F(x0, y0)  0, x0  0, (**) xT xF(x0, y0) = 0, yTyF(x0, y0) = 0, y0  0. Podmínky (*), (**) se nazývají Kuhn – Tuckerovy podmínky. K.-T. podmínky umožňují nalézt sedlový bod řešením soustavy nerovností (*), což je zobecněna podmínka „nulovosti gradientu“. Matematické programování – konvexní úlohy 52 4.3 Kuhn-Tuckerovy podmínky a dualita v LP Uvědomte si, že lineární funkce jsou současně konvexní i konkávní na celém prostoru Rn , podmínka regularity v úloze LP je triviálně splněna, neboť funkce ve všech omezujících podmínkách jsou lineární. Podle věty 4-6 potom existuje nezáporný sedlový bod Lagrangiánu úlohy (4-6), (4-8). Vektorový zápis úlohy (4-6) – (4-8) je následující: (P) cT x  MAX; při omezeních A x  b , x  0. Úlohu (P) označujeme jako primární úloha LP. Ze stejných vstupních údajů k ní definujeme tzv. duální úlohu LP. (D) bTy  MIN; při omezeních ATy  c , y  0. Lagrangián k primární úloze (P) je podle definice: F(x,y) = cTx + yT (b - Ax) K.T. podmínky z věty 4-7 (*): xF(x,y) = c - ATy  0  ATy  c, yF(x,y) = b - A x  0  A x  b. Dualitou v LP se budete podrobněji zabývat v následujících kapitolách. ŘEŠENÁ ÚLOHA 4-2 Napište Kuhn-Tuckerovy podmínky k řešení úlohy 6 x1 + 3 x2  MAX; při omezeních 4 x1 + 2 x2 ≤ 20 , 2 x1 + 4 x2 ≤ 22 , x1  0 , x2  0 . Nalezněte nezáporný sedlový bod Lagrangiánu této úlohy a z něj její optimální řešení. Řešení: Lagrangián k primární úloze (P) je podle definice F(x1,x2, y1,y2) = cT x + yT (b - Ax) = 6x1+3x2 +y1(20 - 4x1 - 2x2) +y2(22 - 2x1 - 4x2) . Parciální derivace Lagrangiánu se snadno vypočítají Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 53 F/x1 = 6 - 4y1 - 2y2 F/x2 = 3 - 2y1 - 4y2 F/y1 = 20 - 4x1 - 2x2 F/y2 = 22 - 2x1 - 4x2 Podle K.-T. Podmínky (*) pro gradienty (tj. vektory parciálních derivací) Lagrangiánu platí xF = (F/x1 , F/x2) ≤ 0 , tj. 6 - 4y1 – 2y2 ≤ 0 , 3 - 2y1 – 4y2 ≤ 0 , neboli 4y1 – 2y2  6 , 2y1 – 4y2  3 . To jsou tzv. duální omezení. Dále podle druhé podmínky (*) platí yF = (F/y1 , F/y2)  0 , tj. 20 - 4x1 - 2x2  0 , 22 - 2x1 - 4x2  0 , neboli 4x1 + 2x2 ≤ 20 , 2x1 + 4x2 ≤ 22 . To jsou tzv. primární omezení, vlastně původní omezující podmínky. Nyní vyjádříme K.-T. podmínky (**): xT xF = x1F/x1 + x2F/x2 = 0 , tj. x1 (6 - 4y1 – 2y2) + x2 (3 - 2y1 – 4y2) = 0 . Druhá K.-T. podmínka (**): yT yF = y1F/y1 + y2F/y2 = 0 , tj. y1 (20 - 4x1 - 2x2 ) + y2 (22 - 2x1 - 4x2) = 0 . Shrňme: Nalezení optimálního řešení včetně Lagrangeových multiplikátorů vyžaduje podle K.-T. podmínek řešit tuto soustavu rovnic a nerovnic 4y1 – 2y2  6 , 2y1 – 4y2  3 , 4x1 + 2x2 ≤ 20 , 2x1 + 4x2 ≤ 22 , x1 (6 - 4y1 – 2y2) + x2 (3 - 2y1 – 4y2) = 0 , y1 (20 - 4x1 - 2x2 ) + y2 (22 - 2x1 - 4x2) = 0 , x1  0 , x2  0 , y1  0 , y2  0 . Snadno se dosazením přesvědčíte, že tato soustava má řešení: x1 * = 4 , x2 * = 2 , y1 * = 1,5 , y2 * = 0 , Matematické programování – konvexní úlohy 54 což podle Věty 4-7 představuje nezáporný sedlový bod Lagrangiánu naší úlohy. Přitom je podle Věty 4-5 x1 * = 4 , x2 * = 2 , optimálním řešením naší úlohy. ŘEŠENÁ ÚLOHA 4-3 Nalezněte optimální řešení (tj. bod globálního maxima) úlohy nelineárního MP: (x1)2 + (x2)2 + 3(x3)2 + 4(x4)2 → MAX; za podmínek (x1 - 1)2 + (x2 - 2)2 + (x3 - 3)2 + (x4 - 4)2  169, x1  0 , x2  0, x3  0 , x4  0. Využijte Excel – Řešitel. Řešení: Příprava k použití Excelu-Řešitele ve worksheetu na Obr. 4.6. Účelová funkce má adresu E3 a je v ní vzorec na výpočet funkční hodnoty: =A3^2+B3^2+3*C3^2+4*D3^2. Proměnné x1 až x4 jsou označeny zelenou barvou, mají adresu A3:D3 a počáteční hodnotu 1 (jinak řešitel nalezne minimum namísto maxima). Levá strana omezující podmínky je umístěna v buňce E5, pomocí vzorce =(A3-1)^2+(B3-2)^2+(C3-3)^2+(D3-4)^2. Příslušná pravá strana této omezující podmínky je v buňce F5. V hlavní nabídce zvolíme Data  Řešitel... otevře se okno Parametry Řešitele, které vyplníme podle Obr. 4.7. Optimální řešení je uvedeno v následujícím Obr. 4.8. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 55 Obrázek 4.6: Worksheet pro Řešitele Obrázek 4.7: Parametry Řešitele Matematické programování – konvexní úlohy 56 Obrázek 4.8: Optimální řešení úlohy 4-3 OTÁZKY  Je úloha MP v Řešené úloze 4-3 úlohou konvexního programování? Zdůvodněte, proč ano, nebo proč ne.  Zvolíte-li výchozí (počáteční) řešení nulové, tj. xi = 0 pro i =1, 2, 3, 4, potom Řešitel poskytne nesprávné optimální řešení (nulové). Proč? SHRNUTÍ KAPITOLY Úlohy MP jsme rozdělili do dvou skupin: v první skupině jsou takové úlohy, kde lokální extrém je vždy zároveň globálním, ve druhé skupině jsou úlohy, kde lokální extrém nemusí být současně globálním. V této kapitole jste se zabývali 1. skupinou úloh MP. Ukázalo se, že jsou to takové úlohy, kde jak účelová funkce f, tak funkce gi v omezujících podmínkách splňují podmínky konvexnosti, resp. konkávnosti. Jedná se o úlohy tzv. konvexního programování – součást MP. Speciálním případem konvexního programování je potom lineární programování, kterému bude věnována příští kapitola. Důležitou částí matematického programování je teorie tzv. sedlových bodů. Význam této teorie spočívá v tom, že umožňuje konstrukci řady praktických výpočetních postupů k řešení úloh MP. Nakonec jsme zavedli tzv. Kuhn-Tuckerovy podmínky umožňující nalézt sedlový bod pomocí řešení soustavy nerovností, což je zobecněna podmínka „nulovosti derivace“. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 57 5 LINEÁRNÍ PROGRAMOVÁNÍ RYCHLÝ NÁHLED KAPITOLY V této kapitole se budete zabývat úlohami lineárního programování (LP), které tvoří speciální třídu úloh MP. Při studiu úloh LP nás budou zajímat především tyto otázky: Jaké vlastnosti úloh LP lze využít k výpočtům řešení, tj. optimálního řešení úlohy LP? Za jakých podmínek má úloha LP přípustné řešení, resp. optimální řešení? Jakou strukturu má množina všech přípustných řešení, resp. všech optimálních řešení úlohy LP? K řešení konkrétních úloh budete používat Excel – Řešitel, který má v sobě mimo jiné zabudován známý Simplexový algoritmus. CÍLE KAPITOLY Po prostudování této kapitoly budete umět:  Za jakých podmínek má úloha LP přípustné řešení, resp. optimální řešení.  Převést úlohu lineárního programování na základní tvar.  Základní kroky simplexové metody. KLÍČOVÁ SLOVA KAPITOLY Lineární programování, základní řešení, umělá proměnná, polytop, polyedr, simplexová metoda, optimální řešení. 5.1 Úlohy lineárního programování Lineární programování (LP) je snad nejčastěji a nejúspěšněji používanou matematickou metodou vůbec. Máme samozřejmě na mysli sofistikované matematické metody, k nímž je zapotřebí využívat počítače, nikoliv triviální matematické metody typu „trojčlenka“ apod. Při studiu úloh LP nás budou zajímat především tyto otázky:  Jaké vlastnosti úloh LP lze využít k výpočtům řešení, tj. optimálního řešení úlohy LP?  Za jakých podmínek má úloha LP přípustné řešení, resp. optimální řešení?  Jakou strukturu má množina všech přípustných řešení, resp. všech optimálních řešení úlohy LP? Lineární programování 58 Přestože komerčně dodávané SW balíky jsou dnes schopny řešit úlohy LP se statisíci až milióny proměnných a omezujících podmínek, výpočet relevantních řešení bez znalosti teorie LP lze jen stěží dovést k úspěšnému konci. Stejné konstatování platí i pro řešení úloh LP v Řešiteli MS Excelu, který budete používat. Důvody potíží při výpočtech bývají tyto:  Chyby při formulaci modelu. Počítač např. hlásí, že úloha nemá přípustné, resp. optimální řešení, i když modelovaný ekonomický systém reálně existuje a funguje, tudíž příslušné řešení by mělo existovat.  Chyby při zavádění dat do počítače. Člověk je tvor omylný a snadno se splete. Častou chybou (zejména studentů) je např. to, že číslo je do počítače v Excelu vloženo jako text. Tato chybička není na první pohled patrná a způsobuje, že počítač nic nevypočítá (ani nepodá zprávu o typu chyby). 5.2 Optimální alokace zdrojů V kapitole 1 jsme zformulovali úlohu nalezení optimálního výrobního programu podniku, která spočívala v alokaci zdrojů b1, ..., bm tak, aby se maximalizovala účelová funkce (zisk) c1x1+ c2x2+ ... + cnxn → MAX; (5-1) za podmínek a11x1+ a12x2+ ... + a1nxn ≤ b1 a21x1+ a22x2+ ... + a2nxn ≤ b2 ....................... am1x1+ am2x2+ ... + amnxn ≤ bm (5-2) x1  0 , x2  0 , ... , xn  0. (5-3) Úloha (5-1) – (5-3) je úlohou lineárního programování (LP), neboť funkce vystupující v (5-1) a (5-2) jsou lineární. Pro studium základních vlastností úloh LP, které je potřeba znát při řešení těchto úloh, je výhodné předpokládat, že omezující podmínky jsou ve tvaru rovnic. Jak bylo ukázáno v kapitole 3.3, lze toho dosáhnout snadno tak, že přidáme ke každé nerovnici v (5-2) na levé straně nezápornou doplňkovou proměnnou, čímž získáme úlohu LP v standardní formě (standardním tvaru) c1x1+ c2x2+ ... + cnxn → MAX; (5-4) za podmínek a11x1+ a12x2+ ... + a1nxn = b1 a21x1+ a22x2+ ... + a2nxn = b2 ....................... am1x1+ am2x2+ ... + amnxn = bm (5-5) x1  0 , x2  0 , ... , xn  0. (5-6) ŘEŠENÁ ÚLOHA 5-1 Převeďte následující optimalizační úlohu (úloha 4-1) na standardní tvar: 6 x1 + 3 x2  MAX; Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 59 při omezeních 4 x1 + 2 x2 ≤ 20 , 2 x1 + 4 x2 ≤ 22 , x1  0 , x2  0 . Řešení: 6 x1 + 3 x2  MAX; při omezeních 4 x1 + 2 x2 + x3 = 20 , 2 x1 + 4 x2 + x4 = 22 , x1  0 , x2  0 , x3  0 , x4  0. Nakonec uveďme ještě vektorový tvar úlohy LP ve standardní formě cT x  MAX; (5-7) při omezeních A x = b , (5-8) x  0 . (5-9) 5.3 Základní pojmy LP V následující analýze vlastností úloh LP budeme označovat množinu všech přípustných řešení úlohy LP (5-7) až (5-9) symbolem X, tj. X = {x = (x1, x2, ... , xn) Rn | A x = b, x  0 } (5-10) a množinu všech optimálních řešení této úlohy, tj. množinu všech x = (x1, x2, ... , xn) X  Rn , kde účelová funkce nabývá svého (globálního) maxima, symbolem X*. Uvědomte si, že každá úloha LP je zároveň úlohou konvexního programování, a proto podle Věty 4-1 platí, že každý bod lokálního maxima je zároveň bodem globálního maxima. Jednoznačnost optimálního řešení však podle Věty 4-1 není zaručena, neboť lineární účelová funkce (5-7) není ani ryze konvexní ani ryze konkávní. Každý vektor x = (x1 , x2,..., xn) splňující (5-8) a (5-9) je přípustným řešením úlohy LP (5-7) – (5-9). Sloupce matice A z (5-8) budeme značit symboly a(1) , a(2) , ... , a(n) , takže matici A typu (mn) můžeme psát takto A = (a(1) , a(2) , ... , a(n) ) . (5-11) Podle pravidel maticového (vektorového) násobení můžeme psát soustavu rovností (5- 8) Lineární programování 60 x1 a(1) + x2 a(2) + ... + xn a(n) = b . (5-12) DEFINICE 5-1 Nechť všechny řádky v matici A typu (mn) z (5-11) jsou lineárně nezávislé. Řešení soustavy (5-8), (5-9) mající nejvýše m kladných složek, které jsou koeficienty u lineárně nezávislých vektorů v kombinaci (5-12), se nazývá základní řešení (také bázické řešení) soustavy (5-8), (5-9). Základní řešení, které má právě m kladných složek, se nazývá nedegenerované. Je-li kladných složek v (5-12) méně než m, nazývá se toto řešení degenerované. Připomeňme, že soustava vektorů je lineárně nezávislá, jestliže žádný z vektorů není lineární kombinací ostatních vektorů. Dále platí, že mezi m-člennými vektory (v našem případě sloupci matice A) může být nejvýše m lineárně nezávislých vektorů. Jinak řečeno, pokud má soustava více než m vektorů, pak je lineárně závislá. Pro nalezení optimálního řešení úlohy LP má zásadní význam tato věta. VĚTA 5-1 (ZÁKLADNÍ VĚTA LINEÁRNÍHO PROGRAMOVÁNÍ) Má-li úloha LP (5-7) – (5-9) optimální řešení, je mezi optimálními řešeními i základní řešení soustavy omezujících podmínek (5-8), (5-9). Soustava omezujících podmínek (5-8), (5-9) má zřejmě nejvýše C(n,m) = n!/(n-m)!m! základních řešení. Tolika způsoby lze totiž mezi n proměnnými x1, x2, ..., xn vybrat m kandidátů na kladné složky v základním řešení. V běžných případech je ovšem základních řešení podstatně méně, než udává výše uvedené kombinační číslo C(n,m), neboť ne každý výběr kandidátů na kladné složky, představuje skutečně základní řešení. Věta 5-1 nám umožňuje se v praxi omezit při hledání optimálního řešení úlohy LP pouze na základní řešení, kterých je konečné množství, zatímco všech přípustných řešení je obecně nekonečně mnoho. Ve speciálních případech může být množina přípustných řešení také prázdná, nebo v případě m = n může obsahovat jediný bod. Geometricky je množina přípustných řešení průnikem poloprostorů vymezených nadrovinami omezujících podmínek, je to tedy konvexní geometrický útvar nazývaný polytop, konkrétně v případě, že jde o omezenou množinu se polytop nazývá polyedr. Speciálním případem polyedru v rovině R2 je konvexní mnohoúhelník. Následující věta charakterizuje množinu všech přípustných řešení v úloze LP. VĚTA 5-2 Jestliže je množina přípustných řešení X úlohy LP (5-7) – (5-9) omezená, potom X je množina všech konvexních kombinací utvořených ze všech základních řešení. Je tedy konvexním polyedrem. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 61 ŘEŠENÁ ÚLOHA 5-2 Uvažujte úlohu LP z příkladu 5-1: 6 x1 + 3 x2  MAX; při omezeních 4 x1 + 2 x2 + x3 = 20 , 2 x1 + 4 x2 + x4= 22 , x1  0 , x2  0 , x3  0 , x4  0. Nalezněte všechna základní řešení této úlohy. Řešení: Matice A je typu (24), úlohu LP můžeme psát maticově takto při omezeních Ze sloupců matice A je možné sestavit C(4,2) = 6 dvojic sloupců a odtud 6 potenciálních základních řešení, z nich jsou 4 základní Odpovídající hodnoty účelové funkce jsou Lineární programování 62 cT x(1) = 30 , cT x(2) = 30, cT x(3) = 33/2 , cT x(4) = 0 . 5.4 Simplexová metoda Simplexová metoda je iterační výpočetní postup pro nalezení optimálního řešení úlohy lineárního programování (pokud takové řešení existuje). Výchozím bodem tohoto algoritmu je nalezení výchozího základního řešení úlohy lineárního programování. Pokud je již takové řešení k dispozici, potom simplexová metoda v jednotlivých krocích vypočte vždy nové základní řešení s lepší nebo alespoň stejnou – v případě maximalizace vyšší – hodnotou účelové funkce. Po konečném počtu kroků musí tedy tento výpočetní postup vést k nalezení základního řešení s nejlepší hodnotou účelové funkce nebo ke zjištění, že takové řešení neexistuje. Při jeho nalezení se musí podle základní věty LP – Věty 5-1 jednat o řešení optimální. Postup výpočtu pomocí simplexové metody se někdy dělí na dvě fáze I. nalezení výchozího základního řešení, II. iterační postup vedoucí k optimalizaci účelové funkce. V některých speciálních případech je nalezení výchozího základního řešení natolik snadné, že I. fáze výpočtu vlastně odpadá. V takovém případě se celý postup označuje jako jednofázová simplexová metoda. V obecném případě nemusí být však nalezení výchozího základního řešení úlohy LP jednoduché. Potom mluvíme o dvoufázové simplexové me- todě. Základní ideu simplexové metody znázorňuje následující obrázek, v němž je množina přípustných řešení D znázorněna zeleným konvexním mnohoúhelníkem v rovině R2 . Jde o následující úlohu LP: Jednotlivé vrcholy xi mnohoúhelníku D představují základní řešení úlohy LP. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 63 Obrázek 5.1: Simplexová metoda Jak již bylo výše řečeno, simplexová metoda nemusí vždy nalézt optimální řešení! Pokud neexistuje přípustné řešení, znamená to, že zadané omezující podmínky jsou ve vzájemném rozporu, což bývá v důsledku špatné specifikace modelu. V tom případě simplexová metoda ukončí I. fázi indikací neexistence přípustného řešení a samozřejmě také neexistence optimálního řešení. V případě, že základní přípustné řešení existuje, končí I. fáze simplexové metody jeho nalezením a dále pokračuje II. fáze. Ta má za úkol přejít postupně přes základní řešení k takovému, které se vyznačuje nejlepší hodnotou účelové funkce, tj. k optimálnímu (základnímu) řešení. Takové optimální řešení však nemusí existovat, např. v případě, když je množina všech přípustných řešení neomezená a hodnota účelové funkce se může zvyšovat nade všechny meze. V praktických úlohách je tato situace obvykle důsledkem špatné specifikace modelu, obecně však může nastat. Naštěstí II. fáze simplexové metody tuto situaci indikuje a algoritmus se zastaví. Při přechodu na nové bázické řešení ve II. fázi simplexové metody se nemusí vždy zvyšovat hodnota účelové funkce, může zůstat stejná. Nastane to v situaci, když algoritmus narazí na degenerované základní řešení. Taková situace by mohla vést k zacyklení výpočtu, kdyby se při nezvyšování účelové funkce po několika krocích dospělo do stejného základního řešení. Naštěstí k tomu v praxi v důsledku zaokrouhlovacích chyb v počítači nedo- chází. V tomto textu určeném pro studenty navazujících magisterských oborů ekonomického zaměření nepovažujeme za nezbytné vysvětlovat podrobný postup algoritmu simplexové metody. Zájemce odkazujeme na bohatou literaturu, resp. internet, viz např. http://www1.osu.cz/studium/mopv2/simplex/. Důležité je porozumění hlavní myšlence simplexové metody, kterou jsme právě popsali, a také její aplikace na ekonomické problémy včetně interpretace dosažených výsledků. K tomu by mělo sloužit zvládnutí řešení úloh LP pomocí Řešitele v Excelu, viz kapitola 6. 5.5 Dvoufázová simplexová metoda V tomto odstavci podrobněji popíšeme a na příkladu demonstrujeme postup dvoufázové simplexové metody. Lineární programování 64 1. fáze: Řeší se úloha eTw  MIN; kde eT= (1, 1, …, 1), w = (w1, w1, …, wm) – tzv. umělé proměnné při omezeních A x + w = b , x  0 , w  0 . Jestliže pro optimální řešení platí eTw = 0, potom se získá přípustné základní řešení (výchozí pro II. fázi), jinak. tj. když pro optimální řešení platí eTw > 0, přípustné řešení neexistuje a metoda končí. 2. fáze: V případě, že I. fáze končí nalezením výchozího přípustného základního řešení, řeší se původní úloha cTx  MAX; při omezeních A x = b , x  0 . Získá se optimální bázické řešení, nebo indikace, že účelová funkce je na množině všech přípustných řešení shora neomezená, a tudíž optimální řešení neexistuje. ŘEŠENÁ ÚLOHA 5-3 Následující úlohu LP řešte pomocí dvoufázové simplexové metody 3 x1 + 2 x2 + x3  MAX; při omezeních 2 x1 +3 x2 + 6 x3  6 , 4 x1 + 2 x3  10 , xi  0 , i = 1,2,3. Řešení: 1. fáze: w1 + w2  MIN; při omezeních 2 x1 +3 x2 + 6 x3 + w1 = 6 , 4 x1 + 2 x3 + w2 = 10 , xi, wj  0 , i = 1,2,3, j = 1,2. Optimální základní řešení = výchozí přípustné základní řešení pro 2. fázi (x1, x2, x3, w1,w2) = (2,4; 0; 0,2; 0; 0). 2. fáze: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 65 3 x1 + 2 x2 + x3  MAX; při omezeních 2 x1 +3 x2 + 6 x3 = 6 , 4 x1 + 2 x3 = 10 , xi  0 , i = 1,2,3. Optimální základní řešení (x1, x2, x3) = (2,5; 0,3; 0). Výsledky prověřte pomocí Řešitele v Excelu. OTÁZKY  Co je to základní řešení?  Kdy má úloha LP optimální řešení?  Jaký je základní princip simplexové metody? SHRNUTÍ KAPITOLY V této kapitole jste se zabývali úlohami lineárního programování (LP), které tvoří speciální třídu úloh MP. Při studiu úloh LP nás zajímaly především tyto otázky: Jaké vlastnosti úloh LP lze využít k výpočtům řešení, tj. optimálního řešení úlohy LP? Za jakých podmínek má úloha LP přípustné řešení, resp. optimální řešení? Jakou strukturu má množina všech přípustných řešení, resp. všech optimálních řešení úlohy LP? Řešení optimalizačních úloh v Excelu 66 6 ŘEŠENÍ OPTIMALIZAČNÍCH ÚLOH V EXCELU RYCHLÝ NÁHLED KAPITOLY Tato kapitola demonstruje řešení vybraných úloh LP v doplňku Řešitel programu Microsoft Excel. Po jejím prostudování byste měli být schopni samostatně vyřešit podobné problémy LP. CÍLE KAPITOLY Po prostudování této kapitoly budete umět:  Vyřešit nutriční problém v Excelu.  Zadat různé podmínky v Řešiteli.  Zobrazit citlivostní zprávu. KLÍČOVÁ SLOVA KAPITOLY Řešitel, nutriční problém, účelová funkce, omezující podmínka, skalární součin. 6.1 Řešitel Optimalizační moduly v tabulkových kalkulátorech naleznete ve všech běžně používaných verzích a jsou v podstatě totožné. Dále je proto nebudeme navzájem odlišovat a zaměříme se na práci s nejpoužívanějším z nich s Řešitelem (Solver) tabulkového kalkulátoru MS Excel. Ten je určený pro řešení standardních úloh matematického programování. Je tedy možné řešit jak lineární, tak i nelineární optimalizační úlohy. My se však zaměříme především na úlohy lineárního programování, které MS Excel rozšiřuje o některé další možnosti. Nejvýraznější z nich je možnost řešení úloh s podmínkami celočíselnosti - tzn. některé nebo všechny proměnné modelu mohou být definovány jako celočíselné proměnné. Možnosti řešení úloh větších rozměrů jsou v MS Excelu výrazně omezené, proměnných i omezujících podmínek může být nejvýše několik set, pro naše účely je to však dostačující. V praxi se však řeší úlohy LP o rozsahu několika milionů proměnných i omezujících podmínek, k tomu už zřejmě Excel nestačí a zde je naštěstí k dispozici specializovaný SW. MS Excel je u nás rozšířen především v české verzi. Setkat se lze však i s verzí anglickou. Proto budeme v následujícím popisu uvažovat českou verzi a pro eventuální uživatele Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 67 anglické verze budeme však uvádět (většinou v závorkách) současně anglické ekvivalenty používaných termínů (zvýrazněných kurzívou). Pro ilustraci řešení úlohy LP v Excelu použijeme následující příklad úlohy LP, tzv. nutriční problém. ŘEŠENÁ ÚLOHA 6-1 Denní dávka výživy pro skupinu dospělých osob by měla mít energetickou hodnotu v rozmezí od 15000 do 20000 kJ, měla by obsahovat minimálně 80 g bílkovin, 15 mg železa a 10000 jednotek vitamínu A. Pro zabezpečení uvedených požadavků je k dispozici 8 základních druhů potravin. Jejich složení z hlediska uvažovaných komponent (vždy na 100 g dané potraviny) a jejich cena v Kč za 100 g je uvedená v tabulce 6.1. V denní dávce výživy může být přitom od každé potraviny maximálně 400 g a minimálně 100 g. Cílem v dané úloze je nalezení takové skladby výživy, která bude respektovat všechny výše uvedené požadavky a současně bude co nejlevnější. V matematickém modelu úlohy lineárního programování bude zřejmě 8 proměnných, které budou vyjadřovat množství jednotlivých potravin ve stovkách gramů v navržené denní dávce výživy. Každá z proměnných bude zdola i shora omezena (maximální množství každé potraviny je 400 g, minimální množství je 100 g). Každé výživové komponentě bude odpovídat jedna omezující podmínka (kromě energie, kde budou tyto podmínky dvě), která zabezpečí splnění definovaných požadavků. Řešení: Budeme vycházet z údajů v následující tabulce: Tabulka 6.1: Vstupní údaje pro úlohu LP (nutriční problém) Potravina Energie [kJ] Bílk. [g] Železo [mg] Vit. A [jedn.] Cena [Kč] Maso vepř. 1200 18,4 3,1 20 12,00 Máslo 3000 0,6 0,2 2500 11,20 Chléb 1160 7,2 0,8 0 1,50 Brambory 300 1,6 0,6 40 0,70 Jablka 240 0,0 0,5 60 1,80 Sýr eidam 1260 31,2 0,6 1100 10,60 Kuře 650 20,2 1,5 0 6,50 Jogurt bílý 450 7,0 0,2 260 3,20 Matematický model vypadá tedy následovně: 12x1 +11,2x2 +1,5x3 +0,7x4 +1,8x5 +10,6x6 +6,5x7 +3,2x8  MIN; za podmínek 1200x1 +3000x2 +1160x3 +300x4 +240x5 +1260x6 +650x7 +450x8 ≥ 15000 , 1200x1 +3000x2 +1160x3 +300x4 +240x5 +1260x6 +650x7 +450x8 ≤ 20000 , 18,4x1 + 0,6x2 + 7,2x3 + 1,6x4 + 31,2x6 +20,2x7 +7,0x8 ≥ 80 , 3,1x1 + 0,2x2 + 0,8x3 + 0,6x4 + 0,5x5 + 0,6x6 + 1,5x7 + 0,2x8 ≥ 15 , 20x1 + 2500x2 + 40x4 + 60x5 +1100x6 + 260x8 ≥ 10000 , Řešení optimalizačních úloh v Excelu 68 1 ≤ xi ≤ 4 , i = 1, 2, ..., 8 . Při řešení konkrétní optimalizační úlohy v Excelu musí uživatel nejprve připravit v tabulce vstupní data. Jejich uspořádání může být v podstatě libovolné, musí být však dodržena jistá pravidla, která vyžaduje optimalizační modul. Obr. 6.1 ukazuje, jak mohou být ve tabulce Excelu rozvržena vstupní data výše uvedeného příkladu. Většina koeficientů ve spreadsheetu na Obr. 6.1 jsou přímo zadané numerické hodnoty – například v naší úloze se jedná o koeficienty, popisující složení jednotlivých potravin (blok A9:H13), jejich cena (A3:H3), minimální a maximální požadavky na jednotlivé komponenty (M9:M13), dolní a horní meze pro použití jednotlivých potravin (jsou součástí zadání parametrů řešitele. V matematickém modelu naší úlohy bylo definováno 8 proměnných. Ve spreadsheetu jsme pro tyto proměnné rezervovali blok A7:H7 a každé z těchto proměnných jsme přiřadili počáteční hodnotu 1 (viz Obr. 6.1). Obrázek 6.1: Upravená vstupní data pro úlohu LP – MS Excel Aby bylo možné ve spreadsheetu zapsat jednotlivé omezující podmínky, je třeba nejprve vyjádřit jejich levou stranu. Ta bude potom porovnána s konstantami na pravé straně. Pro ilustraci uvažujme první omezující podmínku našeho příkladu (energetická bilance – dolní mez): 1200x1 +3000x2 +1160x3 +300x4 +240x5 +1260x6 +650x7 +450x8 ≥ 15 000. Podobně vyjádříme druhou omezující podmínku našeho příkladu (energetická bilance – horní mez). Abychom zachovali stejný směr nerovnosti, vynásobíme nerovnici -1: -1200x1 -3000x2 -1160x3 -300x4 -240x5 -1260x6 -650x7 -450x8 ≥ -20 000. Levá strana těchto omezení je vlastně skalárním součinem vektoru strukturních koeficientů, které vyjadřují energetickou vydatnost na 100 g jednotlivých potravin, s vektorem proměnných modelu. Ve spreadsheetu na Obr. 6.1 se jedná o skalární součin řádkového vektoru, který je umístěn v bloku A9:H13 s vektorem v bloku A7:H7. V Excelu je na výpočet skalárního součinu k dispozici funkce, kterou lze v této souvislosti využít. V české verzi Excelu se jedná o funkci SOUČIN.SKALÁRNÍ(a;b), v anglické verzi je to Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 69 SUMPRODUCT(a,b), kde a, b jsou bloky obsahující vektory, pro které se má vypočítat skalární součin. Pro první výše uvedené omezení bude tedy levá strana vyjádřena jako =SOUČIN.SKALÁRNÍ(A9:H9;A7:H7). Tento vzorec je ve spreadsheetu na Obr. 6.1 umístěn v buňce K9. Podobně v buňkách K10 až K13 jsou skalární součiny vyjadřující levé strany zbývajících omezení (bilance energie – horní mez, bílkovin, železa a vitamínu A). Jaké výrazy jsou zapsány v buňkách K10, K11, K12 a K13, ukazuje přehledně následující tabulka: omez. podmínka buňka Vzorec Energie-horní mez K10 =SOUČIN.SKALÁRNÍ(A10:H10;A7:H7) bílkoviny K11 =SOUČIN.SKALÁRNÍ(A11:H11;A7:H7) železo K12 =SOUČIN.SKALÁRNÍ(A12:H12;A7:H7) Vitamín A K13 =SOUČIN.SKALÁRNÍ(A13:H13;A7:H7) Tabulka 6.2: Zápis omezujících podmínek ve spreadsheetu Analogicky lze namísto 5 funkcí SOUČIN.SKALÁRNÍ použít jedenkrát funkci SOUČIN.MATIC. K tomu musí mít všechny nerovnosti stejný směr. Posledním krokem při přípravě vstupních dat ve spreadsheetu je definice optimalizačního kritéria – účelové funkce. Toto kritérium musí být zapsáno rovněž ve tvaru vzorce a umístěno do některé z buněk. V našem příkladu je účelová funkce vyjádřena jako skalární součin vektoru cenových koeficientů (blok A3:H3) s vektorem proměnných (blok A7:H7). Tento součin zapíšeme pomocí funkce =SOUČIN.SKALÁRNÍ(A3:H3;A7:H7). Na Obr. 6.1 je tento vzorec umístěn v buňce J7. Po ukončení přípravy vstupních dat lze aktivovat vlastní optimalizační modul. V Excelu je k tomuto účelu k dispozici položka menu Data-Řešitel (Data-Solver). Pokud se položka Řešitel v menu Data nevyskytuje, potom je doplněk Řešitel třeba aktivovat. Od verze Excelu 2007 se Řešitel doinstaluje tak, že po kliknutí Tlačítka Office zvolíte Možnosti aplikace Excel, poté zvolíte Doplňky, vyberete Řešitel a potvrdíte OK. Řešitele pak naleznete v hlavním menu v položce Data a Analýzy. Po spuštění řešitele, je třeba v dialogovém okně Parametry řešitele, které je uživateli zobrazeno, specifikovat požadované informace. Ukázka dialogového okna pro náš příklad je na Obr. 6.2. 1. Kritérium optimality, tj. účelová funkce (set objective). Jedná se o jedinou buňku obsahující vzorec, jejíž hodnota se bude optimalizovat. V naší úloze je optimalizační kritérium obsaženo v buňce J7. 2. Charakter kritéria optimality, tj. hledat: max, min, hodnota (to: max, min, value of). Zde se určí to, zda se jedná o maximalizaci nebo minimalizaci účelové funkce nebo o řešení úlohy, ve které je cílem nalezení požadované úrovně kritéria. K dispozici jsou mož- nosti:  maximalizace kritéria (max),  minimalizace kritéria (min), což odpovídá naší úloze, Řešení optimalizačních úloh v Excelu 70  dosažení cílové hodnoty (value of) - při této volbě je třeba dále zadat cílovou hodnotu (value). 3. Oblast proměnných modelu, tj. proměnné modelu (by changing variable cells). Na Obr. 6.2 se jedná o oblast A7:H7. 4. Omezující podmínky (subject to the constraints) Při definici nového či opravě již dříve zadaného omezení musí uživatel určit tři položky:  adresu buňky obsahující vzorec (cell reference), jehož výsledek musí být menší, větší nebo roven omezující hodnotě; tento vzorec obsahuje v typickém případě proměnné modelu (odvolávky na buňky obsahující proměnné) nebo se může jednat přímo o buňku s proměnnou – na Obr. 6.3 se jedná o buňky v blocích K9:K13 a M9:M13, anebo se jedná o buňky v bloku A7:H7, což je vlastně blok proměnných (kvůli definici dolních a horních mezí proměnných),  typ omezení, což je jedna z možností ≤, =, ≥, celé (int), tj. podmínka celočíselnosti nebo binární (bin), tj. podmínka, že proměnné budou nabývat pouze hodnot 0 nebo 1,  omezující hodnotu (constraint), která může být reprezentována buď buňkou obsahující numerickou hodnotu nebo může být přímo vložena z klávesnice jako konstanta – na Obr. 6.3 jsou tyto hodnoty vloženy na pravou stranu omezujících podmínek (hodnoty 4, 0, 1). Obrázek 6.2: Parametry řešitele Dialogové okno, které se zobrazí při postupném přidávání nebo dodatečné úpravě omezujících podmínek, uvádíme na Obr. 6.3. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 71 Obrázek 6.3: Zadávání omezujících podmínek Omezující podmínky lze definovat buď samostatně nebo v bloku. Pokud jsou definovány v bloku, potom všechny buňky bloku musí splňovat stejnou zadanou relaci ≤, ≥ nebo =. V případě, že se jedná o stejnou hodnotu pravých stran, např. 0, (nebo 4, případně 1), pak stačí vložit jedinou hodnotu. Kompletní podoba omezujících podmínek pro náš ilustrační příklad je zřejmá z Obr. 6.2. Kdyby bylo třeba doplnit soustavu omezujících podmínek o podmínky celočíselnosti pro všechny proměnné (v našem ilustračním příkladu to potřebné není), stačí tuto soustavu rozšířit o omezení ve tvaru A7:H7 celé (omezující podmínka se v tomto případě pochopitelně neuvádí). 5. Nastavit podmínky nezápornosti (make unconstrained variables non-negative) je dvoupolohový přepínač, jehož zapnutí má za následek, že jsou při výpočtu automaticky uvažovány podmínky nezápornosti. Tyto podmínky se potom nezadávají mezi běžnými omezujícími podmínkami. Při řešení běžných úloh lineárního programování doporučujeme zapnout tuto volbu. 6. Vyberte metodu řešení (select a solving method) nabízí 3 metody (gradientní metoda, simplexová metoda a evoluční algoritmus). Při řešení úloh lineárního programování je rozumné zvolit simplexovou metodu (standardně je vybrána gradientní). Pokud je ponecháno standardní nastavení (tj. gradientní metoda), potom to vede u lineárních úloh k výraznému prodloužení doby zpracování a k jiné podobě výstupu výsledků, než bude uvedeno dále. Pro lineární případ používá totiž systém k výpočtu standardní simplexovou metodu, resp. metodu větvení a mezí pro řešení úloh LP s podmínkami celočíselnosti. Pro řešení nelineárních modelů je použit blíže nespecifikovaný iterační postup – jistá podoba gradientní metody. V případě řešení nelineárních úloh s mnoha lokálními extrémy může být užitečné zvolit evoluční algoritmus, který je sice pomalejší, ale má lepší předpoklady pro nalezené globálního extrému. Při zpracování konkrétní optimalizační úlohy může být důležité nastavení určitých parametrů. Toto nastavení se provádí pomocí položky Možnosti (options), která je součástí okna parametry řešitele (Obr. 6.2). Po aktivaci této položky je zobrazeno dialogové okno možnosti řešitele (viz Obr. 6.4). Z uživatelského hlediska postačí zmínit se pouze o vybraných položkách, uvedených v tomto okně: Řešení optimalizačních úloh v Excelu 72 Obrázek 6.4: Dialogové okno možnosti řešitele 1. Přesnost omezující podmínky (constraint precision) je konstanta, která udává přesnost, se kterou musí souhlasit levá a pravá strana omezující podmínky tak, aby byla považována tato podmínka za splněnou. Tato konstanta má význam především u nelineárních optimalizačních úloh, kterými se zde podrobněji nezabýváme. Je to hodnota blízká nule (standardní nastavení je 0,000001). Její zvýšení může vést ke zrychlení výpočtu, ale ke snížení přesnosti výsledků. 2. Optimalita celých čísel (integer optimality) je procentní odchylka pro celočíselné řešení. Zvýšení tolerance vede zpravidla ke snížení doby výpočtu celočíselného řešení. Toto snížení je však na úkor přesnosti. Pro úlohy, ve kterých nejsou definovány podmínky celočíselnosti, nemá tato konstanta žádný význam. 3. Maximální čas (max time) zpracování. Je to hodnota ve vteřinách (standardně je nastaveno 100), po jejímž uplynutí je výpočet přerušen. Uživatel má potom možnost ve výpočtu dále pokračovat nebo jej definitivně ukončit. Maximální čas zpracování může být nastaven až na 32767 vteřin (tj. cca 9 hod.). 4. Iterace (iterations) je počet iterací, po jejímž uplynutí je výpočet přerušen a uživateli je nabídnuto řešení z poslední iterace. Uživatel se poté může opět rozhodnout o pokračování výpočtu nebo o jeho ukončení. Limitní počet iterací může být nastaven až na hodnotu 32767. U obou uvedených limitů je však třeba podotknout, že u většiny běžných úloh stačí standardně nastavené hodnoty a není je tedy nezbytné nijak měnit. Po definici všech potřebných údajů v dialogovém okně parametry řešitele, případně v okně možnosti řešitele je možné spustit zpracování pomocí tlačítka řešit (solve). Vlastní výpočet může trvat, v závislosti na rozsahu řešené úlohy, na tom, zda jsou či nejsou v modelu zahrnuty podmínky celočíselnosti a na rychlosti počítače použitého pro zpracování, i několik minut. U běžných školních úloh, ve kterých bývá pouze několik málo proměnných Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 73 a omezujících podmínek, je však výsledek zpracování k dispozici takřka okamžitě. Po ukončení výpočtu je zobrazeno dialogové okno (Obr. 6.5), ve kterém je informace, zda bylo či nebylo nalezeno řešení splňující všechny omezující podmínky (optimální řešení). Uživatel má potom možnost zvolit, zda si přeje uchovat vypočtené řešení nebo vrátit původní hodnoty. Typická volba bude nejčastěji uchovat řešení. V takovém případě jsou optimální hodnoty proměnných umístěny do bloku proměnných a v návaznosti na to je vypočtena optimální hodnota účelové funkce. Kromě této základní podoby výstupu si může (ale nemusí) uživatel dále zvolit výstup podrobnějších informací. Stačí, když v dialogovém okně výsledky řešení označí některé (nebo všechny) Zpráva (reports): Každá z vybraných zpráv je potom umístěna do automaticky vygenerovaného samostatného listu. K dispozici jsou tři druhy “zpráv”: Obrázek 6.5: Dialogové okno výsledky řešení 1. Výsledková zpráva (answer report), se objeví na novém listu s názvem Výsledková zpráva. Obsahuje jednak informace o původních a konečných hodnotách optimalizačního kritéria a proměnných modelu a jednak informace o vztahu levé a pravé strany omezujících podmínek. Pro všechny prvky modelu (kritérium optimality, proměnné, omezení) je zde rovněž odkaz na odpovídající buňky spreadsheetu. Obrázek 6.6: Optimální řešení Řešení optimalizačních úloh v Excelu 74 Obrázek 6.7: Výsledková zpráva Citlivostní zpráva (sensitivity report) se objeví na novém listu s názvem Citlivostní zpráva. Obsahuje intervaly stability pro cenové koeficienty (v české verzi MS Excelu je termín cenový koeficient chybně přeložen jako úkolový koeficient) a pro hodnoty pravé strany omezujících podmínek. V první tabulce této zprávy (viz Obr. 6.8) je pro každou proměnnou uveden její název, hodnota, redukovaný cenový koeficient (snížené náklady), cenový (cílový) koeficient a interval stability pro tento koeficient, který je definovaný povoleným nárůstem a poklesem. Tento interval stability určuje, v jakém rozmezí se může měnit cenový koeficient, aniž by se změnilo optimální řešení úlohy. Druhá tabulka citlivostní zprávy obsahuje pro každou omezující podmínku její název, hodnotu levé a pravé strany (konečná hodnota a pravá strana podmínky), stínovou cenu a interval stability pro hodnotu pravé strany ve formě povoleného nárůstu a poklesu. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 75 Obrázek 6.8: Citlivostní zpráva 3. Limitní zpráva (limit report) se objeví na novém listu s názvem Limitní zpráva. Uvádí, jak se mění hodnota optimalizačního kritéria při změně hodnot proměnných v zadaných mezích. Řešení optimalizačních úloh v Excelu 76 Obrázek 6.9: Limitní zpráva V tabulce na Obr. 6.9 jsou k dispozici podrobné výsledky optimalizace našeho příkladu. Pro úplnost budeme tyto výsledky interpretovat:  v denní dávce bude 165 vepřového masa, 328 másla, 314chleba, po 400 g brambor a jablek a po 100 g eidamu, jogurtu a kuřecího masa,  pokud by se cena potravin snížila/zvýšila alespoň o hodnotu redukovaných cen (redukovaný gradient), potom by bylo efektivní mít tyto potraviny v návrhu ve množství vyšším než minimálním případně nižším než maximálním (např. pokud by cena u eidamu klesla z 10,60 Kč minimálně o 3,24 Kč, potom by byl tento sýr v návrhu ve vyšším množství než 100 g),  energie je v návrhu výživy na horní hranici, tj. 20000 kJ, bílkoviny jsou překročeny o 39,8 g, železo a vitamín A jsou přesně na minimálně požadovaném množství,  cena navržené dávky výživy je přibližně 91,60 Kč; požadavek na zvýšení obsahu železa o 1 mg povede ke zvýšení celkové ceny o 4,24 Kč (stínová cena pro železo); podobně pro vitamín A – požadavek na zvýšení o 1000 jednotek povede ke zvýšení ceny denní dávky o 6,32 Kč. Vlastnosti optimalizačního modulu v Excelu nejsou nijak mimořádné. Výpočetní zkušenosti však ukazují, že při jisté dávce trpělivosti lze pomocí tohoto modulu zpracovat poměrně spolehlivě i úlohy LP s mezními rozměry (200 proměnných, 200 omezení) za předpokladu, že model neobsahuje podmínky celočíselnosti. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 77 OTÁZKY  Co reprezentují pravé strany omezujících podmínek u nutričního problému?  Jak změníme v Řešiteli maximalizační účelovou funkci na minimalizační? SHRNUTÍ KAPITOLY K řešení konkrétních úloh jste se naučili používat Excel – Řešitel, který má v sobě mimo jiné zabudován známý Simplexový algoritmus. Na příkladu konkrétní úlohy – směšovacího problému (tzv. nutričního problému) jste se podrobně seznámili se všemi možnostmi a funkcemi Řešitele. V příští kapitole se budete věnovat ještě speciálním skupinám úloh LP: dopravním a přiřazovacím problémům. Dualita, Dopravní a přiřazovací problém 78 7 DUALITA, DOPRAVNÍ A PŘIŘAZOVACÍ PROBLÉM RYCHLÝ NÁHLED KAPITOLY Dualita má v lineárním programování značný význam. Vzpomeňte si na úlohu optimálního výrobního plánování v kapitole 1. Matematický model této úlohy vycházel ze 3 typů vstupních údajů: koeficientů jednotkových zisků cj jednotlivých výrobních procesů (výrobků), disponibilních množství jednotlivých zdrojů bi a matice technologických koeficientů aij, které představují měrné spotřeby daných zdrojů v jednotlivých výrobních procesech. Z těchto vstupních údajů lze sestavit dva sice odlišné, avšak vzájemně příbuzné modely LP, které označujeme jako duálně sdružené úlohy LP. První z nich nazýváme primární úloha LP, druhou duální úloha LP. Významná je zejména ekonomická interpretace řešení duální úlohy ve vztahu k řešení úlohy primární. Často je, v závislosti na cílech analýzy, znalost a interpretace duální úlohy důležitější než znalost a interpretace primárního modelu. Duality se také využívá v tzv. postoptimalizační analýze, která se zabývá dopady změn vstupních údajů na optimální řešení. Dále se v této kapitole budete zabývat speciálními a zároveň velmi praktickými úlohami lineárního programování, konkrétně dopravním a přiřazovacím problémem, jejich matematickými modely a způsobem jejich řešení v Excelu – Řešiteli. CÍLE KAPITOLY Po prostudování této kapitoly budete umět:  Vytvořit duální úlohu z libovolné úlohy lineárního programování.  Definovat základní vztahy mezi primární a duální úlohou.  Vysvětlit ekonomickou interpretaci duální úlohy.  Vyřešit dopravní a přiřazovací problém v Excelu. KLÍČOVÁ SLOVA KAPITOLY Dualita, přípustné řešení, optimální řešení, intervaly stability, dopravní problém, přiřazovací problém. 7.1 Dualita jako vztah mezi dvěma úlohami lineárního programo- vání Lineární funkce jsou současně konvexní i konkávní na celém prostoru Rn . Proto je podmínka regularity formulovaná ve znění věty 4-6 triviálně splněna, neboť funkce ve všech Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 79 omezujících podmínkách jsou lineární. Podle věty 4-6 potom tedy existuje nezáporný sedlový bod Lagrangiánu úlohy (4-6), (4-8). Vektorový zápis úlohy (4-6) – (4-8) je následující: (P) cT x  MAX; (7-1) při omezeních A x  b , x  0. (7-2) Úlohu (P) označujeme jako primární úloha LP. Lagrangián k primární úloze (P) je podle definice: F(x,y) = cT x + yT (b - Ax) Kuhn-Tuckerovy (KT) podmínky z věty 4-7 jsou pro tento Lagrangián následující yF(x,y) = b - A x  0, x  0.  A x  b, x  0. xF(x,y) = c - AT y  0, y  0.  ATy  c, y  0. První KT podmínka představuje omezující podmínky primární úlohy (P). Druhá KT podmínka definuje omezující podmínky jiné úlohy LP, kterou nazýváme duální úloha LP, konkrétně jde o úlohu LP s vektorem proměnných yRm : (D) bTy  MIN; (7-3) při omezeních ATy  c , y  0. (7-4) Dualitou v úlohách lineárního programování rozumíme vzájemný, přesně definovaný vztah mezi dvojicí úloh lineárního programování. Důležitý je fakt, že dualita úloh (7-1), (7-2) a (7-3), (7-4) je vzájemně symetrickým vztahem obou úloh. Proto v této souvislosti používáme pro dvojici uvedených úloh LP termín dvojice duálně sdružených úloh LP. Formulace duální úlohy k primární úloze závisí na tvaru primární úlohy, tj. na tom, zda je primární úloha v obecném tvaru z Tab. 7.1, nebo nikoliv. Podle toho budeme rozlišovat dva případy – souměrnou a nesouměrnou dualitu. Souměrná dualita – maticový zápis: Primární úloha Duální úloha maximalizovat z = cT x minimalizovat f = bT y Ax ≤ b AT y ≥ c x ≥ 0 y ≥ 0 Tabulka 7.1: Definice souměrné duality – maticový zápis Dualita, Dopravní a přiřazovací problém 80 Primární úloha Duální úloha maximalizovat minimalizovat Tabulka 7.2: Definice souměrné duality – obyčejný zápis Z výše uvedených tabulek je zřejmé, že duální úloha má jiný vektor proměnných než úloha primární. Označili jsme jej y a jedná se o m-složkový vektor, tj. vektor, který má tolik složek, kolik měla primární úloha vlastních omezení. Transformace primární úlohy na úlohu duální probíhá v těchto krocích:  Maximalizace účelové funkce se mění na minimalizaci, popř. naopak,  ke každému vlastnímu omezení (P) přiřadíme jednu duální proměnnou yi, i = 1, 2, …, m a dále podmínku yi  0,  ke každé proměnné xj, j = 1, 2, …, n, (P) přiřadíme vlastní omezení duální úlohy,  matice strukturních koeficientů (D) je rovna transponované matici těchto koeficientů (P),  koeficienty pravé strany (D) jsou shodné s koeficienty účelové funkce (P) a naopak,  smysl nerovností vlastních omezení se v (D) mění na opačný!  u souměrné duality byla v úloze s maximalizací účelové funkce všechna vlastní omezení ve tvaru nerovnic se smyslem nerovnosti „≤“,  pro všechny proměnné platily podmínky nezápornosti. Formulaci duálně sdružené úlohy k úloze LP „Krmné směsi“ z kap. 1 vidíte v Tab. 7.3. Primární úloha Duální úloha maximalizovat minimalizovat Tabulka 7.3: Duálně souměrné úlohy Dle výše uvedených kroků vidíte, že: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 81  primární úloha je maximalizační, proto duální úloha je úlohou minimalizační,  primární úloha má 2 proměnné x1, x2,  protože primární úloha měla tři vlastní omezení, má duální úloha tři nezáporné proměnné y1, y2, y3,  každé podmínce nezápornosti primární úlohy odpovídá jedno vlastní omezení duální úlohy vytvořené z transponované matice strukturních koeficientů,  znak nerovnosti ve vlastních omezeních se změnil z  na ,  cenové koeficienty z primární úlohy přešly na pravé strany vlastních omezení duální úlohy a naopak, pravé strany omezení primární úlohy se staly koeficienty účelové funkce duální úlohy. Při definování souměrné duality jsme uvažovali model LP pouze ve tvaru (7-1), (7-2), viz též Tab. 7.1, kdy v úloze s maximalizací účelové funkce byla všechna vlastní omezení ve tvaru nerovnic se znakem nerovnosti  a pro všechny proměnné platily podmínky nezápornosti. V reálných úlohách LP se však vyskytují jiná vlastní omezení než uvedené nerovnice a všechny proměnné rovněž nemusí být v praxi nezáporné. Pokud se v omezujících podmínkách vyskytne nerovnice s opačným znakem nerovnosti, lze ji snadno vynásobením –1 převést do požadovaného tvaru. Podívejme se nyní blíže na situaci, kdy se v primární úloze bude vyskytovat vlastní omezení ve tvaru rovnosti. Sestavení duální úlohy budeme demonstrovat na příkladu krmné směsi, kde ve 3. vlastním omezení uvažujeme namísto nerovnosti  rovnost =. ŘEŠENÁ ÚLOHA 7-1 K úloze LP 2000x1 + 3000x2  MAX; za podmínek 0,9x1 + 0,3x2 ≤ 270 0,5x2 ≤ 100 0,1x1 + 0,2x2 = 60 x1 ≥ 0 x2 ≥ 0 sestavte úlohu duální. Řešení: Protože jde v příkladu o maximalizaci účelové funkce, je třeba, aby všechny omezující podmínky byly nerovnice se znakem nerovnosti ≤. První dvě omezení tento požadavek splňují. U třetího omezení lze podmínku ve tvaru rovnosti rozložit na dvě nerovnice: 0,1x1 + 0,2x2 ≤ 60 a 0,1x1 + 0,2x2 ≥ 60 Dualita, Dopravní a přiřazovací problém 82 Abychom úlohu převedli do vhodného tvaru podle Tab. 7.1, resp. 7.2, zbývá ještě druhou z těchto nerovnic vynásobit číslem –1. Obdržíme novou úlohu: 2000x1 + 3000x2  MAX; za podmínek Původní soustava tří vlastních omezení se tak rozšířila na soustavu čtyř omezení. Duální úloha bude proto obsahovat 4 proměnné, označíme je y1, y2, y3‘, y3‘‘. Duální úloha je tedy následující:   min60100270 '' 3 ' 321  yyyyf za podmínek Při sestavování duální úlohy jsme úmyslně provedli drobnou úpravu tím, že jsme vytkli stejné koeficienty v účelové funkci i v omezujících podmínkách, a to tak, že v závorce zůstal vždy rozdíl duálních proměnných '' 3 ' 3 yy  . Označíte-li nyní '' 3 ' 33 yyy  , můžete duální úlohu zjednodušit: dosadíte za výrazy v závorkách novou proměnnou 3y , a protože rozdíl dvou nezáporných čísel může být jak nezáporný, tak záporný, vypustíme z modelu omezení nezápornosti 0' 3 y a 0'' 3 y . Na novou proměnnou 3y tedy neklademe omezení nezápornosti. Výslednou primární a také duální úlohu nyní vidíte v Tab. 7.4. Primární úloha Duální úloha maximalizovat minimalizovat Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 83 Tabulka 7.4: Duálně nesouměrné úlohy 7.2 Vztahy mezi (P) a (D) úlohou LP Hlavní význam duality spočívá ve vzájemných vztazích, které platí mezi primární a duální úlohou. Formulujeme je ve formě 6 matematických vět: VĚTA 7-1 Duální úloha k duální úloze LP je úloha primární. VĚTA 7-2 Mají-li obě úlohy (P) a (D) přípustné řešení, pak mají také řešení optimální. VĚTA 7-3 Je-li x libovolné přípustné řešení úlohy (P) a y libovolné přípustné řešení úlohy (D), pak platí cT x ≤ bT y. VĚTA 7-4 Platí-li cT x = bT y, pro přípustná řešení x a y, pak x je optimální řešení úlohy (P) a y je optimální řešení úlohy (D). Dualita, Dopravní a přiřazovací problém 84 VĚTA 7-5 Má-li jedna z úloh (P) a (D) přípustné řešení, ale nemá řešení optimální, pak druhá úloha nemá žádné přípustné řešení. VĚTA 7-6 Má-li jedna z úloh (P) a (D) optimální řešení, má jej také druhá úloha, přičemž platí, že hodnoty účelových funkcí jsou stejné. ŘEŠENÁ ÚLOHA 7-2 Na příkladu primární a duální úlohy demonstrujte věty 7-3 a 7-6. Řešení: (P) 3 x1 + 2 x2 + x3 → MAX; při omezeních 2 x1 + 3 x2 + 6 x3  6 4 x1 + 2 x3  10 xi  0 (D) 6 y1 + 10 y2 → MIN; při omezeních 2 y1 + 4 y2  3 3 y1  2 6 y1 + 2 y2  1 yj  0 Přípustná řešení (např.): xT = (1 ; 0 ; 0) , yT = (1 ; 1). Potom 3.1+2.0+0 = 3 < 16 = 6.1+10.1 . Optimální řešení: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 85 x*T = (2,5 ; 0,33 ; 0) , y*T = (0,67 ; 0,42), cT x* = bT y* = 8,17. Obě úlohy mají přípustné, a tedy i optimální řešení, přičemž hodnoty účelových funkcí úlohy (P) i úlohy (D) jsou stejné. 7.3 Ekonomická interpretace duality Ekonomická interpretace řešení duálního modelu velmi těsně souvisí s interpretací primárního modelu. Všechny úvahy budeme demonstrovat na konkrétním příkladu výrobního plánování z kapitoly 1. Primární a duální model tohoto problému je uveden v Tab. 7.3. Nejdříve si připomeňte jednotlivé prvky primárního modelu: x1 množství vyrobené směsi I, x2 množství vyrobené směsi II, z celkový zisk, z = 1 020 000,- Kč, b1 disponibilní kapacita rýže, b1 = 270, b2 disponibilní kapacita pšenice, b2 = 100, b3 disponibilní kapacita vloček, b3 = 60, x* optimální výrobní program (vektor), x* = (240;180). Označme y* optimální řešení duální úlohy. Snadno zjistíte (např. za použití Excelu), že        14000,0, 3 2000* y Podle hlavní věty o dualitě platí: z = cT x* = bT y* , tedy 102000014000600100 3 2000 270 z . Jinak řečeno, celkový zisk z výroby lze vyjádřit jako součin kapacit jednotlivých zdrojů a hodnot duálních proměnných. Duální proměnné můžeme tedy interpretovat jako ocenění jednotky příslušného zdroje. Jedná se však o marginální ocenění kapacit, to znamená nejvyšší cenu jednotky využitého zdroje, za kterou se ještě „vyplatí“ nakoupit tento zdroj, neboť přírůstek účelové funkce (např. zisk) je vyšší. Jinak řečeno, jestliže je skutečná cena jednotky takového zdroje menší než marginální ocenění, vyplatí se rozšířit výrobu nákupem tohoto zdroje. Hodnota marginálního (duálního) ocenění se nazývá stínová cena (anglicky: shadow price) nebo také náklady obětované příležitosti (anglicky: opportunity Dualita, Dopravní a přiřazovací problém 86 costs). Proto také nevyčerpaný zdroj má nulovou hodnotu duální proměnné, tj. nulovou stínovou cenu. Jeho zvýšení o jednotku totiž nezpůsobí zvýšení zisku. Například jednotka 1. zdroje (rýže) se podílí na celkovém zisku hodnotou 666,67 Kč. Hodnota y2 = 0 znamená, že se 2. zdroj (pšenice) na zisku přímo nepodílí. Tento zdroj není plně využit, jeho zvýšení o jednotku nezpůsobí zvýšení hodnoty účelové funkce. Znalost hodnot duálních proměnných nám pomůže nalézt odpověď na otázku: Jak se změní hodnota účelové funkce (zisk), jestliže se kapacita rýže zvýší o jednotku? Odpověď bude prostá: změní se o hodnotu příslušné duální proměnné, v našem případě o y1 = 2000/3. Protože y2 = 0, změna kapacit u 2. zdroje nemá na výsledný zisk vliv. Jistě vás však ihned napadne, že kdyby kapacita pšenice výrazně poklesla, stala by se pak nedostatkovou, a to by jistě celkový zisk ovlivnilo. Znamená to, že hodnoty duálních proměnných je nutné uvažovat jen v rámci určitých intervalů stability pro kapacity jednotlivých zdrojů, obecně pak pro hodnoty pravých stran vlastních omezení. Podle hlavní věty o dualitě platí: z* = cT x* = bT y*, z* = 270·666,67 + 100·0 + 60·14000 = 1020000. Je-li skutečná cena jednotky zdroje menší než stínová cena, vyplatí se rozšířit výrobu nákupem tohoto zdroje. Stínová cena představuje náklady obětované příležitosti: nevyčerpaný zdroj má nulovou hodnotu duální proměnné, tj. nulovou stínovou cenu. Jeho zvýšení o jednotku proto nezpůsobí zvýšení zisku! Jestliže se tedy kapacita rýže zvýší o jednotku, pak zisk vzroste o hodnotu příslušné duální proměnné y1 = 2000/3 (ověřte v Excelu – Řešiteli!). Jestliže je y2 = 0 pak změna kapacit u 2. zdroje nemá na výsledný zisk žádný vliv. Kdyby kapacita pšenice (2. zdroj) výrazně poklesla (o kolik?), stala by se pak nedostatkovou, a to by jistě celkový zisk ovlivnilo hodnoty duálních proměnných. Proto je nutné uvažovat jen v rámci intervalů stability jednotlivých zdrojů! 7.4 Ekonomický a matematický model dopravního problému (DP) Dopravní problém (DP) představuje klasickou úlohu LP, která modeluje praktický problém optimalizace přepravy určité komodity. V DP se vyskytují dva typy prvků: m zdrojů (skladů, dodavatelů) označených D1, D2, …, Dm a n cílových míst (odběratelů) označených O1, O2, …, On. Jednotlivé zdroje mají postupně kapacity a1, a2, …, am, tj. množství, která jsou v uvažovaném období schopny dodat, na druhé straně odběratelé mají požadavky b1, b2, …, bn, tj. množství, která v daném období potřebují. Náklady na přepravu jedné jednotky zboží ze zdroje Di k odběrateli Oj jsou označeny cij. Cílem řešení dopravního problému je stanovit objem přepravy xij mezi Di a Oj tak, aby byly uspokojeny požadavky dodavatelů i odběratelů a aby celkové přepravní náklady byly minimální. Takto zformulovaný dopravní model můžeme přehledně vyjádřit v podobě tabulky: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 87 Tabulka 7.5: Formalizovaný ekonomický model dopravního problému Vzhledem k celkovým kapacitám dodavatelů a požadavkům odběratelů rozlišujeme dva typy dopravního problému:  Vyrovnaný dopravní problém, o kterém hovoříme v případě, když souhrn všech kapacit dodavatelů se rovná souhrnu všech požadavků odběratelů, tj. jinak řečeno, všechny požadavky budou uspokojeny a všechny kapacity budou vyčer- pány.  Nevyrovnaný dopravní problém, o kterém hovoříme tehdy, když výše uvažovaná rovnost neplatí, tj. Při převisu nabídky zůstane část kapacity dodavatelů nevyužitá, při převisu poptávky nedojde k uspokojení všech požadavků. Jak ihned uvidíte, lze každý nevyrovnaný dopravní problém upravit na vyrovnaný dopravní problém, budeme se proto zabývat pouze vyrovnaným dopravním problémem. Tato úprava se provede následujícím způsobem.  Při převisu nabídky: Přebývá-li dodavatelům přepravovaná komodita, přidáme do modelu fiktivního odběratele Of, jehož požadavek bf se bude rovnat danému přebytku, tj. Dualita, Dopravní a přiřazovací problém 88  Při převisu poptávky: Převyšuje-li poptávka nabídku, doplníme model o fiktivního dodavatele Df, jehož kapacita af se bude rovnat chybějícímu množství, tj. Protože přeprava mezi reálnými a fiktivními místy je také pouze fiktivní, položíme odpovídající cenové koeficienty rovny nule. Dále vyjádříme ekonomický model dopravního problému matematickými prostředky. Protože se v modelu vyskytuje m dodavatelů a n odběratelů, budeme uvažovat celkem m×n možných variant přepravy, proto zavedeme m×n proměnných xij. V modelu se vyskytují dva typy omezujících podmínek. Prvních m omezení bude vyjadřovat fakt, že z každého zdroje může být přepraveno množství, které představuje kapacitu tohoto zdroje. Na levých stranách těchto omezení proto jsou řádkové součty proměnných z Tab. 7.5, které se rovnají příslušným kapacitám na pravých stranách. Zbylých n podmínek modeluje situaci z pohledu odběratele, ke kterému je přepraveno zboží o objemu odpovídajícímu jeho požadavku. Levé strany těchto podmínek jsou součtem požadavků odběratelů. Matematický model (vyrovnaného) DP je následující: za omezení SAMOSTATNÝ ÚKOL 7-1 Vytvořte Lagrangián k vyrovnanému DP a sestavte k němu příslušnou duální úlohu. Poznámka: Duální úloha k DP se využívá k řešení DP: na jejím základě byly vytvořeny efektivní algoritmy a metody k řešení DP například tzv. Maďarská metoda k řešení DP. My se jimi zde zabývat nebudeme, naučíme se řešit úlohu DP pomocí Excelu. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 89 ŘEŠENÁ ÚLOHA 7-3 S pomocí Excelu vyřešte dopravní problém se 3 dodavateli a 3 odběrateli, jehož zadání naleznete v následující Tab. 7.6. Tabulka 7.6: Zadání úlohy 7-3 Řešení: Postup použití Excelu pro řešení dopravního problému je analogický jako dřívější postup při řešení jiných úloh LP uvedený v kapitole 6. Také zde začnete nejdříve tím, že si vhodně vymezíte místo ve spreadsheetu, kde budete ukládat vstupní údaje, formule a proměnné veličiny, s nimiž později budete pracovat v Řešiteli. Jako vhodné se jeví například uspořádání na Obr. 7.1. Daný nevyrovnaný dopravní problém není nutné pomocí fiktivního odběratele vyrovnat. V oblasti B8:D10 jsou umístěny proměnné, tyto buňky není nutné na začátku vyplňovat, případně pro kontrolu správnosti použitých formulí je vyplňte samými nulami nebo jedničkami. V buňkách oblasti B11:D11 jsou umístěny součty hodnot ze sloupců nad nimi. Podobně se v buňkách oblasti E8:E10 nacházejí řádkové součty. V buňkách B13:D13 jsou uvedeny požadavky odběratelů, v buňkách G8:G10 pak kapacity dodavatelů. V buňkách B3:D5 se nacházejí jednotkové přepravní náklady. Účelová funkce je umístěna do buňky F3 a vypočítá se jako součin modelových proměnných a jednotkových přepravních nákladů. Pro výpočet tohoto součinu je vhodné použít funkci SOUČIN.SKALÁRNÍ. Dále zvolte v hlavním menu položku Data – Řešitel a vyplňte položky v příslušném dialogovém okně. Dualita, Dopravní a přiřazovací problém 90 Obrázek 7.1: Vstupní data pro DP ve spreadsheetu Excelu Na Obr. 7.2 jsou parametry řešitele pro naši úlohu. Cílem řešení DP je minimalizace celkových nákladů, proto nastavíme buňku F3 na Min. Měněnými buňkami jsou proměnné, které uložíme do oblasti B8:D10. Omezující podmínky musí obsahovat jednak podmínky nezápornosti pro všechny proměnné, dále pak podmínky vyjadřující porovnání kapacit (požadavků) dodavatelů (odběratelů) s jejich využitím. Protože jde o nevyrovnaný problém s převisem nabídky, nemohou odběratelé odebrat veškeré nabízené množství, což vyjadřuje znak nerovnosti ve třetí podmínce. Nakonec stiskneme tlačítko Řešit. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 91 Obrázek 7.2: Parametry řešitele DP Výsledné řešení je zachyceno na Obr. 7.3. Zde vidíme, že např. přeprava od dodavatele D1 k odběrateli O1 se nebude realizovat (v buňce B8 je 0), od dodavatele D1 k odběrateli O2 se přepraví 40 jednotek komodity (v buňce C8 je 40). Celkové přepravní náklady jsme umístili do buňky F3 a jejich minimální hodnota činí 4960. Obrázek 7.3: Výsledné řešení Dualita, Dopravní a přiřazovací problém 92 7.5 Přiřazovací problém – speciální DP Speciálním případem DP je přiřazovací problém (PP). V něm se jedná o přiřazení n objektů na n aktivit tak, aby se maximalizoval celkový užitek z přiřazení: za podmínek cij je dílčí užitek z přiřazení objektu i na aktivitu j, xij = 1, pokud objekt i se přiřadí na aktivitu j, xij = 0, pokud objekt i se nepřiřadí na aktivitu j, tedy jinak. Jak je vidět, v každé z omezujících podmínek vystupuje právě jedno xij = 1, ostatní jsou rovny 0. Tím je vyjádřena skutečnost, že na každou aktivitu se přiřadí právě jeden objekt. Čtvercová matice typu nn vytvořena z prvků xij má proto v každém řádku a v každém sloupci právě jednu jedničku. ŘEŠENÁ ÚLOHA 7-4 Na uvolněné 3 pozice ve firmě se přihlásili 3 uchazeči: U1, U2, U3. První pozice vyžaduje především komunikační dovednosti, druhá pozice vyžaduje především numerické dovednosti a třetí pozice vyžaduje zejména speciální znalosti daného oboru. Uchazeči se podrobili 3 testům: komunikačnímu testu T1, numerickému testu T2 a znalostnímu testu T3. V každém z testů bylo možné dosáhnout maximálně 100 bodů. Výsledky uchazečův jednotlivých testech jsou uvedeny v následující Tab. 7.7. Počet dosažených bodů v daném testu se považuje za stupeň kompetence uchazeče pro danou pozici. Jak mají být uchazeči na dané pozice přiděleni, aby celková kompetence byla co možná nejvyšší? Sestavte matematický model a vyřešte úlohu pomocí Excelu. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 93 Tabulka 7.7: Zadání úlohy PP Řešení: Matematický model našeho přiřazovacího problému sestavíme takto: Položíme xij = 1 pokud uchazeč Ui se přiřadí na pozici j, xij = 0 jinak, přitom i,j = 1, 2, 3. Přitom pokud se uchazeč Ui přiřadí na pozici j, pak dílčí kompetence z tohoto přiřazení je dána jeho výsledkem v testu Tj a je tedy rovna tij . xij , přitom tij představuje výsledek uchazeče Ui v testu Tj. Celková kompetence je pak dána součtem všech dílčích kompetencí. Matematický model lze vyjádřit takto: 50x11 + 70x12 + 90x13 + 55x21 + 10x22 + 35x23 + 60x31 + 20x32 + 50x33  MAX; za podmínek x11 + x12 + x13 = 1, x21 + x22 + x23 = 1, x31 + x32 + x33 = 1, x11 + x21 + x31 = 1, x12 + x22 + x32 = 1, x13 + x23 + x33 = 1, xij {0,1}. V Excelu vyřešíme úlohu pomocí Řešitele: Vstupní data jsou na Obr. 7.4. uspořádána stejně jako v DP na Obr. 7.1. Pro kontrolu jsme do pole proměnných B2:D4 vložili samé jedničky. Hodnota účelové funkce je pak součtem dílčích kompetencí, tj. „cen“, tedy 440. Takové stanovení výchozích hodnot však není přípustným řešením! Parametry Řešitele na Obr. 7.5. jsou zvoleny analogicky jako v DP na Obr. 7.2. Namísto tlačítka Min jsme však zde zvolili tlačítko Max. Výsledné řešení je na Obr. 7.6. Odtud je zřejmé, že optimální přiřazení je U1 na 2. pozici, U2 na 1. pozici a U3 na 3. pozici. Maximální hodnota celkové kompetence je 175. Dualita, Dopravní a přiřazovací problém 94 Obrázek 7.4: Vstupní data přiřazovacího problému Obrázek 7.5: Parametry Řešitele přiřazovacího problému Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 95 Obrázek 7.6: Optimální řešení přiřazovacího problému OTÁZKY  Jaký má smysl zabývat se řešením duální úlohy?  Čemu je rovna optimální hodnota účelové funkce duální úlohy  Jak vyrovnáme nevyrovnaný dopravní problém v případě převisu poptávky?  Jaké hodnotě jsou rovny pravé strany podmínek přiřazovacího problému? SHRNUTÍ KAPITOLY Ze vstupních údajů úlohy LP lze sestavit dva odlišné, avšak vzájemně příbuzné modely LP, které označujeme jako duálně sdružené úlohy LP. První z nich nazýváme primární úloha LP, druhou duální úloha LP. Významná je zejména ekonomická interpretace řešení duální úlohy ve vztahu k řešení úlohy primární. Často je, v závislosti na cílech analýzy, znalost a interpretace duální úlohy důležitější než znalost a interpretace úlohy primární. Dualita se také využívá v tzv. postoptimalizační analýze, tam se zabývá dopady změn vstupních údajů na optimální řešení. Dále jste se v této kapitole zabývali speciálními a zároveň velmi praktickými úlohami lineárního programování, konkrétně dopravním a přiřazovacím problémem, jejich matematickými modely a způsobem jejich řešení v Excelu – Řešiteli. Dualita, Dopravní a přiřazovací problém 96 Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 97 8 VÍCEKRITERIÁLNÍ A CÍLOVÉ PROGRAMOVÁNÍ RYCHLÝ NÁHLED KAPITOLY V předchozích kapitolách jste se věnovali úlohám matematického programování, kde se maximalizovala (minimalizovala) jediná účelová funkce. Úlohy vícekriteriálního programování (VKP) jsou úlohy, ve kterých se na množině přípustných řešení optimalizuje několik skalárních účelových (kriteriálních) funkcí (krátce: kritérií). Množina přípustných řešení je přitom definována podobně jako v úlohách matematického programování, tj. soustavou omezujících podmínek ve formě rovnic a nerovnic. Za předpokladu linearity omezujících podmínek i účelových funkcí se jedná o úlohy vícekriteriálního lineárního programování (VKLP). Nejprve se seznámíte s pojmem nedominované řešení (též Paretovského řešení) úlohy VKP, jakožto základním „optimálním“ řešením, kterých však bývá v dané úloze obvykle mnoho, a proto tento pojem neposkytuje návod pro praktické rozhodnutí. Poté se seznámíte s několika principy a postupy tzv. skalarizace, které převádějí úlohu s více kritérii na úlohu s jediným (skalarizovaným) kritériem. Nejznámějšími postupy jsou skalarizace pomocí váženého průměru a tzv. cílové programování. Tyto metody prakticky omezují množinu všech Paretovských řešení obvykle na řešení jediné, které pak slouží jako podklad pro konkrétní rozhodování. Na příkladech se naučíte řešit úlohy VKLP s pomocí Excelu – Řešitele. CÍLE KAPITOLY Po prostudování této kapitoly budete umět:  Zapsat úlohu vícekriteriálního programování.  Nalézt nedominované varianty.  Vyřešit úlohu vícekriteriálního lineárního programování v Excelu pomocí metody skalarizace a minimaxu. KLÍČOVÁ SLOVA KAPITOLY Vícekriteriální programování, cílové programování, nedominovaná varianta, Paretovské řešení, skalarizace. 8.1 Vícekriteriálnost v ekonomickém rozhodování Podstatnou charakteristikou v sociálně-ekonomické sféře je její víceaspektovost – vícekriteriálnost. Jednotlivé varianty, o nichž se rozhoduje a z nichž se vybírá nejlepší, nelze Vícekriteriální a cílové programování 98 dobře charakterizovat pouze jediným kvantifikovatelným ukazatelem – kritériem, podle jehož hodnoty se nejlepší varianta stanoví. V souvislosti s ekonomickým rozhodováním není dost dobře možné řešení úlohy výběru nejlepší možnosti – varianty striktně vázat na přesnou definici umožňující jednoznačné uspořádání variant. Pojmy jako nejlepší projekt, nejlepší podnikatel, nejkrásnější dívka nebo nejlepší restaurace závisejí na kontextu a mají silnou subjektivní a intuitivní náplň. Problém výběru nejlepší varianty pak většinou představuje vypracování metodiky hodnocení variant a její následnou aplikaci. Přitom je nutné kombinovat metody logicko-matematické, ekonomické a empirické. V přechozích kapitolách jste se věnovali úlohám matematického programování, kde se maximalizovala (minimalizovala) jediná účelová funkce. Úlohy vícekriteriálního programování (VKP) jsou úlohy, ve kterých se na množině přípustných řešení optimalizuje několik skalárních účelových (kriteriálních) funkcí (krátce: kritérií). Množina přípustných řešení je přitom definována podobně jako v úlohách matematického programování. Za předpokladu linearity omezujících podmínek i účelových funkcí se hovoří o úlohách vícekriteriálního lineárního programování (VKLP). 8.2 Nelineární VKP – základní úloha Jak jsme zmínili v úvodu, představuje úloha VKP současnou optimalizaci (my se zde ve shodě s předchozí úvahou o ekvivalentnosti maximalizace a minimalizace účelové funkce omezíme na maximalizaci) několika, řekněme k > 1, účelových funkcí – kritérií: f1(x1, x2, ..., xn) → „MAX“; (8-1) f2(x1, x2, ..., xn) → „MAX“; ..................................... fk(x1, x2, ..., xn) → „MAX“; za podmínek g1(x1, x2, ..., xn)  b1 , (8-2) g2(x1, x2, ..., xn)  b2 , ............................................... gm(x1, x2, ... ,xn)  bm , kde fi a gj jsou obecně nelineární funkce n proměnných. Symbol MAX zde uvádíme záměrně v uvozovkách jako „MAX“, neboť obvykle nelze současně dosáhnout maxima všech uvažovaných funkcí a jde tedy o „přijatelný“ kompromis. O tom, jaký kompromis to má být, bude pojednáno v dalších odstavcích. Namísto zápisu (8-1) budeme používat také stručnější zápis: „maximalizujte“ fi(x1, x2, ..., xn) , i = 1,2,...,k. (8-3) za podmínek (8-2). Omezující podmínky (8-2) mohou v úloze VKP chybět, nebo to mohou být také omezení nezápornosti. Každý n-rozměrný vektor x = (x1, x2, ..., xn) splňující omezující podmínky (8-2), zde nazýváme varianta, nebo alternativa. Ve shodě s přechozí terminologií jej nazýváme též Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 99 přípustným řešením. Množinu všech přípustných řešení označujeme symbolem X, přitom platí X  Rn . Cílem při řešení úloh vícekriteriálního programování (VKP) je zpravidla nalezení nějakého kompromisního řešení, to je řešení, které bude kompromisem mezi definovanými účelovými funkcemi. Pro výpočet kompromisního řešení úlohy VKP je možné použít několik základních principů. Většina z nich zpravidla vede k řešení jedné či několika standardních úloh matematického programování. Toto řešení lze nalézt běžnými postupy pro řešení optimalizačních úloh, jak jsme se s nimi již dříve seznámili. Je zřejmé, že kompromisní řešení získané podle takových principů musí splňovat podmínku nedominovanosti, tj. musí to být takové řešení, ke kterému neexistuje jiné přípustné řešení, které by bylo lepší (nebo by nebylo horší) podle všech účelových funkcí. Je to jistě podmínka pochopitelná, protože kdyby splněna nebyla, potom by bylo vhodnější vzít jako kompromisní řešení právě to řešení, které je lepší (není horší) podle všech účelových funkcí. Dříve, než definujeme přesně pojem nedominované řešení, zavedeme některé další nezbytné pojmy. 8.3 Kriteriální prostor úlohy VKP a nedominovaná varianta Uvažujte nějaké přípustné řešení úlohy VKP, např. x = (x1, x2, ..., xn)  X  Rn , položte postupně y1 = f1(x1, x2, ..., xn) , y2 = f2(x1, x2, ..., xn) , ............................... yk = fk(x1, x2, ..., xn) , potom y = (y1, y2, ..., yk)  Rk . Nyní zavedeme zobrazení F : X  Rk , takové, že platí F(x) = ( f1(x), f2(x), ..., fk(x) )  Y  Rk , Potom množinu Y = F(X) nazýváme kriteriální prostor. Kriteriální prostor je tedy množina, která je obrazem množiny všech přípustných řešení pomocí zobrazení sestaveného ze všech kriteriálních funkcí. 8.4 Nedominované varianty DEFINICE 8-1 Nechť x(1) , x(2) jsou dvě přípustná řešení vyhovující omezením (8-2). Řekneme, že x(1) dominuje x(2) , jestliže F(x(1) ) ≥ F(x(2) ), přičemž F(x(1) ) ≠ F(x(2) ), Vícekriteriální a cílové programování 100 tj. pro každé j = 1, …, m platí fj(x(1) ) ≥ fj(x(2) ) a alespoň pro jedno j je fj(x(1) ) ≠ fj(x(2) ). Nechť x(0) je přípustné řešení úlohy VKP. Jestliže neexistuje přípustné x(1) takové, že F(x(1) ) ≥ F(x(0) ) , přičemž F(x(1) ) ≠ F(x(0) ), nebo-li x(1) dominuje x(0) , potom se x(0) nazývá nedominovaná (Paretovská) varianta nebo nedominované (Paretovské) řešení. Dále vyjasníme vztah mezi nedominovaným řešením úlohy VKP a optimálním řešením skalarizované úlohy VKP. VĚTA 8-1 Nechť jsou f1, f2, ..., fk ryze konkávní kriteriální funkce (kritéria), dále nechť jsou g1, g2, ..., gm konvexní funkce. Potom platí, že x* je nedominované (Paretovské) řešení úlohy VKP (7-1), (7-2), právě když existují váhy kritérií v1, v2, ..., vk, vi ≥ 0, Σ vi = 1, takové, že x* je optimální řešení skalarizované úlohy: ∑vj fj(x1, x2, ... ,xn) → MAX; (8-4) za omezení (8-2). 8.5 Vícekriteriální lineární programování VKLP Speciální a důležitý případ úlohy VKP nastává, když fj , gi jsou lineární funkce, tj. fj(x1, x2, ... , xn) = c1jx1 + c2jx2 + ... + cnj xn , j = 1, 2, ..., k, gi(x1, x2,..., xn) = a1ix1 + a2ix2 + ... + ani xn , i= 1, 2, ..., m. Vektorový tvar úlohy VKLP: C x → „MAX“; (8-5) za omezení A x  b, (8-6) x ≥ 0. Množina přípustných řešení X je tedy definována takto X = {x | A x  b, x ≥ 0}. (8-7) Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 101 Skalarizovaný tvar úlohy VKLP je založen na vektoru vah v = ( v1, v2, ..., vk ), přitom vi ≥ 0, pro i = 1, 2, ..., k, a ∑ vi = 1. Vícekriteriální úloha LP (8-5), (8-6) se skalarizací transformuje na jednokriteriální úlohu: vT C x → MAX; (8-8) za omezení (8-6), přitom je Následující věta je obdobou věty 8-1 pro úlohu VKLP. VĚTA 8-2 Nechť x* je nedominované (Paretovské) řešení úlohy VKLP (8-5), (8-6). Potom existuje vektor vah v = (v1, v2, ..., vk), takových, že x* je optimální řešení skalarizované úlohy VKLP (8-8), (8-6). Nechť v = (v1, v2, ..., vk) je vektor kladných vah, x* je optimální řešení skalarizované úlohy VKLP (8-8), (8-6). Potom x* je nedominované (Paretovské) řešení úlohy VKLP (8- 5), (8-6). První část věty 8-2 říká, že ke každému nedominovanému řešení úlohy VKLP existuje vektor vah, přičemž toto řešení je optimálním řešením skalarizované úlohy VKLP s tímto vektorem vah. Druhá část věty 8-2 říká, že každé optimální řešení skalarizované úlohy s kladným vektorem vah je nedominovaným řešením úlohy VKLP. ŘEŠENÁ ÚLOHA 8-1 Nalezněte všechna nedominovaná (Paretovská) řešení následující úlohy VKLP: f1(x1, x2) = 2x1 + x2  MAX; f2(x1, x2) = x1 + 5x2  MAX; f3(x1, x2) = x1 - 3x2  MAX; za omezení x1 + x2  3, 0  x1  2, 0  x2  2. Řešení: Upravíme všechny 3 účelové funkce do tvaru rovnice přímky v rovině x1 - x2 : Vícekriteriální a cílové programování 102 x2 = - 2x1 + f1, x2 = - 0,2x1 + 0,2.f2, x2 = 1 /3 x1 - 1 /3 f3. Grafické znázornění množiny všech přípustných řešení včetně účelových funkcí je na následujícím obrázku: Obrázek 8.1: Grafické znázornění Paretovských řešení úlohy VKLP Na obrázku jsou „červenými body“ znázorněna 3 nedominovaná řešení: x1 * = (2 , 1), x2 * = (1 , 2), x3 * = (2 , 0). (7-9) Tato Paretovská řešení jsou vrcholy „zeleného“ konvexního pětiúhelníku, který představuje množinu všech přípustných řešení X. Paretovskými řešeními jsou však také všechny body na dvou úsečkách spojujících uvedené „červené“ body (8-9). Pozor, Paretovskými řešeními nejsou všechny vrcholy „zeleného“ pětiúhelníku; vrcholy (0, 0) a (0, 2) nejsou Paretovskými řešeními. (Prověřte podle definice!) Paretovských řešení je obvykle velké množství, např. v předchozím příkladu jich je nekonečně mnoho (tj. všechny body ležící na dvou uvedených úsečkách). Proto budeme hledat způsob, který omezí počet Paretovských řešení jen na ta, jež vyhovují vhodným dalším požadavkům. Získáme tak kompromisní řešení úlohy VKP, která jsou Paretovská, avšak jejich počet je „rozumný“, nejlépe pouze jediné řešení. Postupů, kterými se takové kompromisní řešení získá, existuje několik, zde si uvedeme tři z nich. První se nazývá metoda váženého průměru účelových funkcí (nebo metoda agregace účelových funkcí), druhý je minimaxová optimalizace, třetí nazýváme cílové programování. 8.6 Metoda váženého průměru účelových funkcí Metoda váženého průměru účelových funkcí (nebo metoda agregace účelových funkcí) je založena na větě 8-2. Ta říká, že jako vážený průměr z kriteriálních funkcí vytvořená nová účelová funkce poskytne v nové skalarizované optimalizační úloze VKLP Paretovské řešení původní úlohy VKLP. Přitom váhy kritérií v1, v2, ..., vk jsou kladné, Σ vi = 1, představují relativní významnost kritérií vzhledem k celkové významnosti představované všemi Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 103 kritérii. Optimálním řešením skalarizované úlohy je vektor, který je považován za kompromisní řešení úlohy VKLP a zároveň je to podle věty 8-2 Paretovské řešení úlohy VKLP. Pro ilustraci se vrátíme k již dříve řešené úloze 8-1. ŘEŠENÁ ÚLOHA 8-2 Uvažujme opět úlohu VKLP: f1(x1, x2) = 2x1 + x2  MAX; f2(x1, x2) = x1 + 5x2  MAX; f3(x1, x2) = x1 - 3x2  MAX; za omezení x1 + x2  3, (8-10) 0  x1  2, 0  x2  2. (8-11) Dále uvažujeme, že kritérium f1 má relativní významnost 50%, tj. váhu v1= 0,5 , kritérium f2 má relativní významnost 30%, tj. váhu v2= 0,3 a kritérium f3 má relativní významnost 20%, tj. váhu v3= 0,2. Nalezněte kompromisní řešení této úlohy VKLP. Řešení: Nejprve vytvoříme skalarizovanou účelovou funkce se zadanými váhami: f(x1, x2) = 0,5(2x1 + x2 ) +0,3(x1 + 5x2 ) +0,2(x1 - 3x2 ) = 1,5x1 + 1,4x2 , (8-12) kterou maximalizujeme za omezujících podmínek (8-10), (8-11). Musíme tedy vyřešit úlohu LP maximalizovat (8-12) za omezení (8-10), (8-11). Úlohu teď budeme řešit pomocí řešitele v Excelu. Nejprve vytvoříme tabulku vstupních údajů, viz Obr. 8.2. Zde jsme namísto excelovské funkce SOUČIN.SKALÁRNÍ použili funkci SOUČIN.MATIC, která dává stejný výsledek. Následně vyplníme parametry řešitele, viz Obr. 8.3. včetně zadání omezujících podmínek (8-11) a zaškrtnutí volby Nastavit podmínky nezápornosti. Optimální řešení je na Obr. 8.4. Odtud vyplývá, že kompromisním řešením je vektor x* = (2;1), který je zároveň Paretovským řešením naší úlohy VKLP. Vícekriteriální a cílové programování 104 Obrázek 8.2: Vstupní data skalarizované úlohy Obrázek 8.3: Parametry Řešitele skalarizované úlohy Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 105 Obrázek 8.4: Optimální řešení skalarizované úlohy 8.7 Minimaxová optimalizace Cílem minimaxové optimalizace je nalezení takového kompromisního řešení, které bude maximalizovat minimální – tedy nejhorší hodnotu všech kriteriálních funkcí. Budeme tedy řešit optimalizační úlohu: min{ f1(x), f2(x), …, fk(x)} → MAX; (8-13) za omezení g1(x)  b1, ………..... (8-14) gm(x)  bm , x = (x1, x2, ..., xn) X. Označíme-li tuto minimální hodnotu účelové funkce jako w, potom lze kompromisní řešení najít jako řešení následující ekvivalentní úlohy LP: w → MAX; (8-15) za omezení f1(x) ≥ w, ………… (8-16) fk(x) ≥ w, x = (x1, x2, ..., xn) X. Pro ilustraci minimaxové optimalizace se opět vrátíme k řešené úloze 8-1. Vícekriteriální a cílové programování 106 ŘEŠENÁ ÚLOHA 8-3 Uvažujme opět úlohu VKLP: f1(x1, x2) = 2x1 + x2  MAX; f2(x1, x2) = x1 + 5x2  MAX; f3(x1, x2) = x1 - 3x2  MAX; za omezení x1 + x2  3, (8-10) 0  x1  2, 0  x2  2. (8-11) Nalezněte minimaxové řešení této úlohy VKLP. Řešení: Nejprve vytvoříme minimaxovou úlohu (8-15), (8-16): w → MAX; za omezení 2x1 + x2 - w  0, x1 + 5x2 - w  0, x1 - 3x2 - w  0, x1 + x2  3, 0  x1  2, 0  x2  2. Zde jsme všechny proměnné, tedy x1, x2, w, převedli na levou stranu omezujících podmínek. Úlohu budeme opět řešit pomocí Řešitele v Excelu. Nejprve vytvoříme tabulku vstupních údajů, viz Obr. 8.5. Zde jsme namísto excelovské funkce SOUČIN.SKALÁRNÍ použili funkci SOUČIN.MATIC, která dává stejný výsledek. Následně vyplníme parametry řešitele, viz Obr. 8.6. včetně zadání omezujících podmínek (8-11) a zaškrtnutí volby Nastavit podmínky nezápornosti. Optimální řešení minimaxové úlohy je na Obr. 8.7. Odtud vyplývá, že kompromisním řešením je vektor x* = (2, 0), který je zároveň Paretovským řešením naší úlohy VKLP. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 107 Obrázek 8.5: Vstupní data minimaxové úlohy Obrázek 8.6: Parametry Řešitele minimaxové úlohy Vícekriteriální a cílové programování 108 Obrázek 8.7: Optimální řešení minimaxové úlohy 8.8 Cílové programování Účelové funkce (kritéria) se v metodě cílového lineárního programování (CLP) nazývají cílové funkce fi. Přitom jsou předem známy cílové hodnoty qi, kterých mají cílové funkce fi dosáhnout, nebo ke kterým se mají co nejvíce přiblížit. Optimální řešení proto minimalizuje součet odchylek cílových funkcí fi od cílových hodnot qi, tj. (8-17) za omezení x = (x1, x2, ..., xn)  X. (8-18) Jinak řečeno, optimální řešení minimalizuje součet odchylek cílových funkcí fi od cílových hodnot di a hi, kde di je nezáporná hodnota, která kritériu fi chybí k dosažení cíle qi, zatímco hi je nezáporná hodnota, která kritériu fi přebývá k dosažení cíle qi, tj. (8-19) za omezení x = (x1, x2, ..., xn)  X. (8-20) Cílové hodnoty qi jsou v praxi často zvoleny jako ideální hodnoty účelových funkcí, tj. nejlepší možné hodnoty, kterých lze na množině přípustných řešení X individuálně dosáhnout. Metoda CLP potom poskytuje takové kompromisní řešení, které minimalizuje součet odchylek (v absolutní hodnotě) od takto zvolených ideálních hodnot. Tento postup ilustrujeme opět na naší známé úloze 8-1. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 109 ŘEŠENÁ ÚLOHA 7-3 Uvažujte opět úlohu VKLP: f1(x1, x2) = 2x1 + x2  MAX; f2(x1, x2) = x1 + 5x2  MAX; f3(x1, x2) = x1 - 3x2  MAX; za omezení x1 + x2  3, (8-10) 0  x1  2, 0  x2  2. (8-11) Nalezněte nejprve ideální řešení individuálních kritérií. Poté vyřešte úlohu cílového programování, kde jsou jako cíle zvoleny ideální hodnoty kritérií. Řešení: Nejprve je třeba zjistit ideální hodnoty jednotlivých kritérií, tzn. vyřešit 3 monokriteriální úlohy LP s individuálními kritérii. Tím získáme ideální hodnoty qi, i =1, 2, 3. Poté sestavíme úlohu CLP (8-19), (8-20), kterou vyřešíme a získáme tak kompromisní řešení, které minimalizuje součet odchylek od zvolených ideálních hodnot. Úlohu budeme opět řešit pomocí Řešitele v Excelu. Začneme vytvořením tabulky vstupních údajů k postupnému řešení 3 úloh LP s jednotlivými kriteriálními funkcemi, viz Obr. 8.8. Tuto tabulku využijeme k řešení 3 úloh LP postupně s účelovými funkcemi f1 , f2 , f3 . V parametrech Řešitele vždy změníme buňku Účelová funkce, viz Obr. 8.9. Obrázek 8.8: Vstupní data úlohy Vícekriteriální a cílové programování 110 Obrázek 8.9: Parametry řešitele Obrázek 8.10: Optimální řešení úlohy s f1 Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 111 Obrázek 8.11: Optimální řešení úlohy s f2 Obrázek 8.12: Optimální řešení úlohy s f3 Obrázek 8.13: Vstupní data úlohy CLP Vícekriteriální a cílové programování 112 Obrázek 8.14: Optimální řešení úlohy CLP Řešením 3 úloh získáte ideální hodnoty účelových funkcí, viz Obr. 8.10. až Obr. 8.12., tyto ideální hodnoty jsou 4, 11, 2. Nakonec vytvoříte tabulku pro řešení úlohy cílového programování CLP s proměnnými xj, di, a hi (jsou označeny v tabulce vstupních dat na Obr. 8.13. zelenou barvou). Odtud vyplývá, že kompromisním řešením je vektor x* = (1, 2), který je zároveň Paretovským řešením naší úlohy VKLP. OTÁZKY  Co je to nedominovaná varianta?  Uveďte základní princip metody váženého průměru účelových funkcí.  Uveďte konkrétní příklad reálného problému, kde by bylo vhodné použít cílové pro- gramování. SHRNUTÍ KAPITOLY Úlohy vícekriteriálního programování (VKP), kterými jste se v této kapitole zabývali, jsou úlohy, ve kterých se na množině přípustných řešení optimalizuje několik účelových (kriteriálních) funkcí – kritérií. Množina přípustných řešení je přitom definována podobně jako v úlohách matematického programování soustavou omezujících podmínek – rovnic a/nebo nerovnic. Za předpokladu linearity omezujících podmínek i účelových funkcí se hovoří o úlohách vícekriteriálního lineárního programování (VKLP). Nejprve jste se seznámili s pojmem nedominované řešení (Paretovské řešení) úlohy VKP, jakožto základním „optimálním“ řešením. Těch však bývá v dané úloze obvykle velké množství (nekonečně mnoho), a proto tento pojem neposkytuje návod pro konkrétní rozhodnutí. Poté jste se seznámili s několika principy a postupy tzv. skalarizace, které převádějí úlohu s více kritérii na úlohu s jediným (skalarizovaným) kritériem. Nejznámějšími postupy jsou skalarizace pomocí váženého průměru a tzv. cílové programování. Tyto metody prakticky omezují Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 113 množinu všech Paretovských řešení obvykle na řešení jediné, které pak slouží jako podklad pro konkrétní rozhodování. Na příkladech jste se naučili řešit úlohy VKLP s pomocí Excelu – Řešitele. Matematické metody optimalizace portfolia 114 9 MATEMATICKÉ METODY OPTIMALIZACE PORTFO- LIA RYCHLÝ NÁHLED KAPITOLY V této kapitole si zopakujete některé poznatky z oboru financí, konkrétně z tzv. matematiky cenných papírů, teorie portfolia a finančního modelování. V návaznosti na kapitolu o vícekriteriálním programování zformulujeme úlohu optimalizace PF jako dvojkriteriální úlohu VKMP. Úloha optimalizace PF spočívá v nalezení takových relativních podílů aktiv v PF, aby se maximalizoval očekávaný výnos PF a minimalizovalo se jeho riziko. CÍLE KAPITOLY Po prostudování této kapitoly budete umět:  Vytvořit dvojkriteriální model optimalizace portfolia.  Vypočítat kovarianční matici.  Nalézt efektivní hranici portfolia. KLÍČOVÁ SLOVA KAPITOLY Akciová analýza, portfolio, riziko, směrodatná odchylka, výnos, kovarianční matice, efektivní hranice. 9.1 Akciové analýzy 9.1.1 FUNDAMENTÁLNÍ ANALÝZA K analýze akcií lze přistupovat různě. Fundamentální analýza předpokládá, že každá akcie má v daném okamžiku určitou "vnitřní hodnotu". Předmětem zkoumání fundamentální analýzy je hledání podhodnocených cenných papírů k nákupu a nadhodnocených k prodeji (tzv. picking). Hledá významné faktory, které mohou podstatně ovlivňovat vnitřní hodnotu akcie. Fundamentální analýzu lze provádět na několika úrovních. Globální analýza zkoumá krátkodobé i dlouhodobé vlivy ekonomických makroagregátů na ceny akcií (inflace, hospodářského růstu, úrokových sazeb atd.). Odvětvová analýza měří citlivost odvětví na hospodářský cyklus, rozsah a způsob vládní regulace, sílu odborů, míru inovací v daném Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 115 odvětví atd. Pomocí finanční analýzy jednotlivých titulů se pak stanoví odhad vnitřní hodnoty příslušné akcie. U společností ve fázi dospělosti (kdy lze lépe prognózovat některé veličiny) se pro účel stanovení vnitřní hodnoty akcie používají tzv. dividendové diskontní modely. Ty vychází z předpokladu, že vnitřní hodnota akcie je současnou hodnotou veškerých budoucích pří- jmů z akcie. Je to jistá analogie k oceňování dluhopisů. V případě akcií však neexistuje doba splatnosti, výplaty dividend jsou nejisté a jistina je nahrazena očekávanou prodejní cenou. Při stanovení požadované výnosové míry je třeba zahrnout i jakousi "prémii" za riziko a k tomu lze využít indexového modelu (viz další kapitola). Ke stanovení míry růstu dividend lze zase využít informace o míře zadrženého zisku na dosahovaném čistém zisku společ- nosti. Na vyspělých trzích patří mezi často používané metody oceňování akcií tzv. ziskové modely. Jsou obvykle založeny na poměru P/E (tržní kurs/čistý zisk na akcii). P/E poměr je pozitivně ovlivněn růstovými příležitostmi trhu a negativně požadovanou výnosovou mírou, která je pozitivně ovlivněna především mírou inflace. Poptávka po akciích s růstem P/E poměru většinou klesá. 9.1.2 PSYCHOLOGICKÁ ANALÝZA Psychologická analýza předpokládá, že kursy jsou v krátkém období silně ovlivněny psychologickými faktory (např. případ start-up firem). Předmětem zkoumání není kurs samotný, ale chování investorů. Teoretickým východiskem je mimo jiné známá Le Bonova práce "Psychologie davu". A. Kostolany razí filosofii "plout proti proudu" (uvádí max. 10% sofistikovaných investorů), a tak obelstít burzovní koloběh střídání cenových vzestupů a sestupů. 9.1.3 TECHNICKÁ ANALÝZA Technická analýza předpokládá, že kursy akcií se pohybují v trendech (bull – bear, akumulační a distribuční fáze apod.). Předmětem analýzy jsou časové řady tržních cen, objemů obchodů a různých indexů. Technický analytik se pokouší rozpoznat v pohybu kursu určitý tvar (formaci) a podle něj časuje nákup a prodej libovolného cenného papíru (timing). K tomu používají matematické modely, grafické metody (linie podpory a odporu, vlajky, prapory atd.) a další technické nástroje (např. klouzavé průměry, oscilátory ap.). V této kapitole budeme navazovat především na technickou analýzu akcií. 9.1.4 FINANČNÍ ANALÝZA Z finančních výkazů akciové společnosti se počítají nejrůznější poměrové ukazatele, které jsou následně používány v rámci akciových analýz. Ukazatele rentability informují investora o výkonnosti společnosti. Nejpoužívanějšími jsou ukazatele ROA (čistý zisk/celková aktiva) a ROE (čistý zisk/vlastní jmění). O úrovni finančního rizika firmy mnohé vypovídají ukazatele zadluženosti. Jsou to např. debt ratio (cizí zdroje/celková aktiva) nebo leverage ratio (cizí zdroje/vlastní jmění). Matematické metody optimalizace portfolia 116 9.2 Teorie portfolia, výnos a riziko Investoři na finančních trzích neinvestují celý svůj majetek jen do jediného finančního instrumentu, byť by byli přesvědčeni, že je to v danou chvíli nejvýhodnější. Zejména v případě akcií vytvářejí s dostupných investičních aktiv určité soubory splňující jejich představy, které nazýváme (investiční) portfolio. V ekonomice je portfolio (PF) odborný termín mající význam: souhrn akcií a ostatních aktiv držených investorem. Někdy také v užším významu: skladba cenných papírů. Obecně se investor snaží vytvořit takové portfolio, aby minimalizoval možná rizika a maximalizoval zisk, což jsou protichůdné snahy. Výnos akcie je tvořen zpravidla dvěma složkami. Kapitálový výnos je rozdíl mezi nákupní a prodejní cenou akcie. Druhou složkou je výnos z dividend. Rizikem investice (akcie, PF) budeme rozumět kolísání její hodnoty v čase. Riziko obvykle měříme směrodatnou odchylkou ("průměrné" vychýlení od průměru). Jednotlivá PF je pro názornost výhodné graficky znázorňovat v tzv. (σ,R)-rovině, v níž každému PF odpovídá bod s vodorovnou souřadnicí ve výši rizika a svislou souřadnicí ve výši výnosu PF. Teorii portfolia lze charakterizovat jako hledání takové kombinace aktiv, při níž je dosažen požadovaný přiměřený výnos ve vztahu k přiměřenému riziku. Pozoruhodnou vlastností portfolií je možnost vytvářet portfolia s menším rizikem, než jsou rizika všech jednotlivých titulů zastoupených v portfoliu. Důvodem této vlastnosti PF jsou záporné kovarianční vazby mezi zastoupenými tituly (mnohdy stačí i slabé pozitivní kovariance/korelace). Eficientní portfolio je pak takové portfolio, které při daném výnosu minimalizuje riziko (resp. při daném riziku maximalizuje výnos). Výběr konkrétního portfolia záleží na vztahu investora k riziku. Jednotliví investoři se mohou lišit svými investičními preferencemi především stupněm své averze vůči riziku. Investor s mírnou (resp. silnou) averzí vůči riziku přistoupí na jednotkový nárůst rizika ve svém PF za malou (resp. velkou) prémii ve formě navýšení výnosu. Indiferenční křivka je množina portfolií v (σ,R)-rovině která, jsou z hlediska investorových preferencí stejně přijatelná (indiferentní), jinak řečeno, každý bod indiferenční křivky má pro investora stejný užitek. Indiferenční křivky jsou v (σ,R)rovině navzájem paralelní. Čím je investor více averzní vůči riziku, tím jsou zřejmě jeho indiferenční křivky strmější. Pro udržení jednoduchosti nebudeme zpočátku uvažovat možnost vypůjčovánía zapůjčování peněz pro účely okamžitého nákupu jiných aktiv - tzv. krátký prodej a existenci bezrizikového aktiva, tj. aktiva s nulovým rizikem. 9.3 Klasický stochastický model PF – historický přístup V tomto odstavci zformulujeme klasický stochastický model PF jakožto problém dvojkriteriálního matematického programování. Cílem modelu je nalezení takové skladby PF na zadané trvání N časových jednotek z daných M aktiv, aby se maximalizoval výnos PF měřený jeho střední hodnotou a minimalizovalo se riziko měřené směrodatnou odchylkou. K dispozici jsou přitom časové řady cen jednotlivých aktiv na T časových jednotek, přitom T je mnohem větší než N. V tomto období se předpokládají konstantní vnější podmínky, a proto je možné předpokládat, že výnos každého aktiva je náhodná veličina, jejíž realizace se projevuje v každé časové jednotce. Stejně tak výnos celého PF je náhodná veličina vzniklá jako vážený průměr individuálních výnosů, přičemž váhy jsou tvořeny relativními podíly uvažovaných aktiv. K formulaci modelu budeme používat následující symboly, označení a předpoklady: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 117 M - počet aktiv (AK) v portfoliu PF (např. akcií), N - počet časových jednotek trvání PF, T - počet časových jednotek - délka časové řady N < T, cit - tržní cena i-tého AK v čase t = 1, 2, ..., T, Zi - relativní podíl i-tého AK v PF, přitom ∑ Zi = 1, Xi - výnos i-tého AK za dobu trvání PF, tj. N, je náhodná veličina, Ri = E(Xi) - očekávaný výnos i-tého AK za dobu N je střední hodnota výnosu, XPF = ∑ Zi Xi - výnos PF za dobu N (při rel. podílech aktiv Zi) je náhodná veličina, RPF = E(XPF) = ∑ Ri Zi - očekávaný výnos PF za dobu N je střed. hodnota výnosu, xit- realizace náhod. veličiny Xi v čase t, t = N+1, N+2,...,T (výnos i-tého AK v %), (9-1) - Výnos i-tého AK v čase t, (9-2) - odhad náhodné veličiny Ri, tj. odhad očekávaného výnosu i-tého AK iiPF ZRR  ˆˆ (9-3) Dále označíme σij = Cov(Xi,Xj) - kovariance výnosu i-tého a j-tého AK,  ii xVar σi 2 = σii = Cov(Xi,Xi) = Var(Xi) - rozptyl výnosu i-tého AK, - riziko výnosu i-tého AK,    M ji jiijPF ZZ 1,  - riziko PF,        T Nt jjtiitij RxRx NT s 1 ˆˆ1 (9-4) - odhad kovariance σij, Matematické metody optimalizace portfolia 118      T Nt iiti Rx NT s 1 2 ˆ1 (9-5) - odhad rizika výnosu i-tého AK za dobu trvání PF, tj. N,   M ji jiijPF ZZss 1, (9-6) - odhad rizika výnosu PF za dobu trvání PF, tj. N. Úloha optimalizace PF spočívá v nalezení takových podílů Zi , i = 1, 2, ..., M, (relativní podíl i-tého AK v PF), při kterých ∑ Zi = 1, Zi ≥ 0, i = 1,2,...,M, takových, aby se maximalizoval očekávaný výnos PF (9-3) a minimalizovalo se riziko PF (9-6), tj. maxˆ   ii ZRR min 1,   M ji jiij ZZss (9-7) za podmínek ∑ Zi = 1, Zi ≥ 0, i = 1, 2, ..., M. (9-8) Úloha optimalizace PF je tedy úlohou dvojkriteriálního nelineárního matematického programování (účelová funkce s je totiž nelineární, ostatní funkce jsou lineární!). Obraz množiny všech nedominovaných (Paretovských) řešení úlohy (9-7), (9-8) ve dvojrozměrném kriteriálním prostoru o souřadných osách σ a R má v teorii PF speciální název – nazývá se efektivní hranice portfolia. Množina všech přípustných PF vytváří v rovině σ – R útvar s charakteristickým tzv. deštníkovým tvarem (anglicky „umbrella shape“), viz Obr. 9.1. Příklad efektivní hranice PF je na Obr. 9.1. znázorněna červenou barvou. Každý bod křivky efektivní hranice představuje dvojici s, R, která odpovídá eficientnímu portfoliu, což je nedominované (Paretovské) řešení úlohy (9-7), (9-8). Eficientní portfolio představuje určité relativní podíly Zi , i = 1, 2, ..., M, nedominovanost tohoto řešení znamená, že neexistují jiné relativní podíly Z´i , i = 1, 2, ..., M, takové, že pro odpovídající s',R' platí buď s' ≤ s, R' > R, nebo s' < s, R' ≥ R. Jinak řečeno, chceme-li získat eficientní portfolio s nižším rizikem, musíme akceptovat nižší výnos a naopak, chceme-li eficientní portfolio s vyšším výnosem, musíme akceptovat i vyšší riziko. Takto se projevuje princip paretovského řešení. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 119 Obrázek 9.1: Efektivní hranice Nyní jde o to, která dvojice riziko – výnos nejlépe odpovídá danému investorovi. Investor vyjádří svůj postoj k riziku např. pomocí indiferenčních přímek R = ks + q, (9-9) kde k - představuje přírůstek výnosu PF, který je pro investora indiferentní se zvýšením ri- zika o jednotku, q - výnos, který je pro investora indiferentní s nulovým rizikem (pro tzv. bezrizikové aktivum). Pro výše uvedeného investora získáme proto eficientní PF řešením následující skalarizované dvojkriteriální úlohy maxˆ 1,1    M ji jiij M i ii ZZskZR (9-10) za podmínek ∑ Zi = 1, Zi ≥ 0, i = 1, 2, ..., M. (9-11) Dalším rozšířením množiny přípustných portfolií určených podmínkami (9-11) je připustit možnost záporných hodnot Zi . Je-li totiž Zi < 0, pak tuto situaci interpretujeme tak, že si investor půjčuje určité množství i-té akcie za úrokovou míru odpovídající výnosu Ri této akcie. Tato výpůjčka, jejíž výše bývá zpravidla omezena, se označuje jako krátký prodej (angl. short selling). V jeho rámci investor inkasuje finanční prostředky z prodeje cenných papírů patřících jinému investorovi s tím, že se zaváže tyto cenné papíry opět vrátit do stanoveného data. Matematické metody optimalizace portfolia 120 Stejně tak může být např. podmínkami burzy shora omezen podíl jednoho druhu aktiv v PF. Namísto podmínek (9-11) potom obdržíme komplikovanější podmínky ∑ Zi = 1, hi ≥ Zi ≥ di, i = 1, 2, ..., M, (9-12) kde hi , di jsou stanovené horní dolní hranice podílů aktiv v PF. ŘEŠENÁ ÚLOHA 9-1 Vypočítejte eficientní PF sestavované na 5 časových jednotek (obchodovatelných dnů), tvořené 4 aktivy (akcie A, B, C, D na PBCP), přičemž k dispozici jsou časové řady cen těchto akcií za období 32 dnů, viz Tab. 9-1. Indiferenční investorova přímka má rovnici R = 0,5s + q. Tuto rovnici lze interpretovat následovně: investor je ochoten „vyměnit“ (nebo „považuje za ekvivalentní“) přírůstek 2 jednotek rizika (tj. s) za přírůstek jedné jednotky výnosu (tj. R). Investor je tedy „poměrně silně averzní vůči riziku“. Tabulka 9.1: Časové řady cen akcií A, B, C, D Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 121 Řešení: Počet AK: M = 4 Počet údajů čas. řad: T = 32 Matematické metody optimalizace portfolia 122 Počet čas. intervalů trvání PF: N = 5 Na Obr. 9.2. jsou znázorněny časové řady cen akcií A, B, C, D. Nejprve vypočítáme 5-ti denní výnosy AK pro t = 6, 7, ..., 32, i = A, B, C, D, a zároveň jejich průměry – očekávané výnosy podle (9-2), tj.: kde Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 123 Obrázek 9.2: Časové řady cen akcií Výpočet odhadu kovarianční matice S = {sij} podle (9-4), tj. pro t = 6, 7, ..., 32, i, j = A, B, C, D: V Excelu vytvoříme přípravná data pro řešení pomocí Řešitele např. podle Obr. 9.3. Matematické metody optimalizace portfolia 124 Obrázek 9.3: Data a parametry Řešitele Eficientní PF pro investora, pro kterého je indiferentní přírůstek výnosu 0,5 se zvýšením rizika o 1, je složeno z 0,56% titulu A, 47,07% titulu B a 2,13% titulu C. Titul D v eficientním portfoliu chybí. Přitom je výnos tohoto PF 7,07% a jeho riziko je 11,67%, viz Obr. 9.4. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 125 Obrázek 9.4: Eficientní portfolio 9.4 Klasický stochastický model PF – expertní přístup Klasický stochastický model PF – historický přístup nerespektuje očekávání investorů o budoucích výnosech aktiv. Střední hodnoty (očekávané hodnoty) výnosů aktiv (akcií) a tedy i PF složeného z těchto aktiv, které se uvažují v historickém přístupu, nemusí být totiž v souladu s názory expertů, které vycházejí především z fundamentální analýzy akcií. Proto se historický přístup rozšiřuje o názory expertů, které doplňují nebo nahrazují očekávané výnosy akcií, případně kovariance mezi aktivy. Do modelu vstupují nové veličiny: ne - počet expertů, ci - tržní cena (TC) i-tého AK v okamžiku vzniku PF, eik - TC i-tého AK v okamžiku realizace PF, stanovena k-tým expertem, dik - dividendy a další požitky z i-tého AK během trvání PF stanovené k- tým expertem, i iikik ik c cde y   - výnos i-tého AK v okamžiku realizace PF stanovena k-tým expertem,   en k ik e e i y n R 1 1 - experty očekávaný výnos i-tého AK v okamžiku realizace PF,   M i i e i e PF ZRR 1 Matematické metody optimalizace portfolia 126 - odhad experty očekávaného výnosu PF. Dále se používá expertní odhad rizika PF:     en k e jjk e iik e e ij RyRy n s 1 1 - expertní odhad kovariance, speciálně    en k e iik e e i Ry n s 1 21 - expertní odhad rizika výnosu i-tého AK za dobu trvání PF, tj. N, ji e ij e PF ZZss  - expertní odhad rizika výnosu PF. Úloha optimalizace PF je opět úlohou dvojkriteriálního nelineárního matematického programování (9-7), (9-8), resp. (9-7), (9-12) Poznámka: Je zřejmé, že expertní přístup a historický přístup je možné podle situace vhodně kombinovat. ŘEŠENÁ ÚLOHA 9-2 Uvažujme stejnou úlohu, jako byla řešená úloha 9-1 s tím rozdílem, že se 2 (stejně důvěryhodní) experti nezávisle na sobě vyjádřili k hodnotám 5-ti denních výnosů akcií A, B, C, D. Jsou uvedeny v následující tabulce, včetně (váženého) průměru jejich odhadů: Kovarianční matici uvažujeme stejnou jako v úloze 9-1, tedy vypočítanou na základě historického přístupu. Dále uvažujeme rizikově neutrálního investora (k = 1), tedy indiferenční investorova přímka má rovnici R = s + q. Řešení: V Excelu vytvoříme přípravná data pro řešení pomocí Řešitele např. jako na Obr. 9.5. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 127 Obrázek 9.5: Data pro Řešitele včetně řešení Eficientní PF pro investora, který je indiferentní vůči riziku, je složeno z akcií B (71,48%), C (14,18%) a D (14,33%), jak je zřejmé z Obr. 9.5. OTÁZKY  Uveďte příklad bezrizikového aktiva.  Co je to efektivní hranice portfolia?  Lze obecně říci, že s růstem výnosu portfolia klesá riziko portfolia? SHRNUTÍ KAPITOLY V této kapitole jste si zopakovali některé poznatky z oboru financí, konkrétně z tzv. „matematiky cenných papírů“, teorie portfolia a finančního modelování. V návaznosti na kapitolu o vícekriteriálním programování jste formulovali úlohu optimalizace PF jako dvojkriteriální úlohu VKMP. Úloha optimalizace PF spočívá v nalezení takových relativních podílů aktiv v PF, aby se maximalizoval očekávaný výnos PF a minimalizovalo se jeho riziko. Obraz množiny všech nedominovaných (Paretovských) řešení této úlohy ve dvojrozměrném kriteriálním prostoru o souřadných osách σ a R se nazývá efektivní hranice PF. Každý bod křivky efektivní hranice představuje dvojici σ, R, která odpovídá eficientnímu portfoliu, což je nedominované řešení této úlohy. Chceme-li získat eficientní portfolio s nižším rizikem, musíme akceptovat nižší výnos a naopak, chceme-li eficientní portfolio s vyšším výnosem, musíme akceptovat i vyšší riziko. To, která dvojice riziko – výnos nejlépe Matematické metody optimalizace portfolia 128 odpovídá danému investorovi, lze vyjádřit jeho postojem k riziku např. pomocí indiferenčních křivek (např. přímek). S využitím tzv. stochastického historického přístupu jste se na příkladech naučili řešit úlohu nalezení eficientního PF pomocí Řešitele v Excelu. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 129 10 SHARPEHO, MARKOWITZŮV A FAKTOROVÝ MODEL PORTFOLIA RYCHLÝ NÁHLED KAPITOLY V předchozí kapitole jsme uvedli model k nalezení eficientního portfolia pro investora se zadanou indiferenční přímkou. Takové eficientní PF je nedominované řešení této 2-kriteriální úlohy ve smyslu VKP z kapitoly 7. V této kapitole se budeme zabývat dalšími historicky staršími přístupy k výpočtu eficientního PF. První z nich - Sharpeův model - spočívá na myšlence převést kritérium rizika na omezující podmínku se zadanou horní přípustnou hranicí a vzhledem k této omezující podmínce pak maximalizovat očekávaný výnos PF. Druhý přístup - Markowitzův model - je symetrický s prvním v tom smyslu, že převádí kritérium očekávaného výnosu na omezující podmínku se zadanou dolní přípustnou hranicí a vzhledem k této omezující podmínce se pak minimalizuje riziko PF. CÍLE KAPITOLY Po prostudování této kapitoly budete umět:  Základní modely pro nalezení optimálního portfolia.  Vyřešit úlohu optimalizace portfolia v Excelu.  Vysvětlit důvody použití faktorových modelů. KLÍČOVÁ SLOVA KAPITOLY Optimalizace portfolia, Sharpeův model, Markowitzův model, faktorový model, systematické riziko. 10.1Optimalizace portfolia jako 2-kriteriální problém nelineárního programování Úloha optimalizace PF spočívá v nalezení takových podílů Zi , i = 1, 2, ..., M, (relativní podíl i-tého AK v PF), pro které platí ∑Zi = 1, Zi ≥ 0, i = 1,2,...,M, a to takových, aby se maximalizoval očekávaný výnos PF (9-3) a zároveň minimalizovalo se riziko PF (9-6), tj. RPF = ∑Ri Zi → max; (10-1) min;  jiijPF ZZ (10-2) Sharpeho, Markowitzův a FaktorovÝ model portfolia 130 za podmínek ∑ Zi = 1, Zi ≥ 0, i = 1, 2, ..., M, (10-3) di ≤ Zi ≤ hi, i = 1, 2, ..., M. (10-4) Namísto směrodatné odchylky je možné alternativně použít též variační koeficient:   ii jiij PF ZR ZZ V  (10-5) kde Xi – výnos i-tého aktiva (akcie) = náhodná veličina, E(Xi) – střední (očekávaná) hodnota výnosu i-tého aktiva, Ri= E(Xi), RPF = ∑Ri Zi – střední (očekávaná) hodnota výnosu PF, Zi – podíl i-tého aktiva v PF, i = 1, 2, ..., M. Přitom platí: ∑Zi = 1, di ≤ Zi ≤ hi, i = 1, 2, ..., M – počet aktiv. Riziko PF se vyjadřuje směrodatnou odchylkou, případně variačním koeficientem (10- 5): min;  jiijPF ZZ σij = Cov(Xi, Xj) - kovariance mezi aktivy i a j. Přirozená je otázka, jak odhadnout Ri a σij? V předchozí kapitole jsme uvedli vztahy (9- 2) a (9-5) k odhadu těchto veličin z časových řad tržních cen uvažovaných akcií. Je zapotřebí připomenout, že vše se vztahuje na předem zvolený časový interval trvání PF! V předchozí kapitole jsme také uvedli model (9-7), (9-8) k nalezení eficientního portfolia pro investora se zadanou indiferenční přímkou, která charakterizuje investorův postoj k riziku. Takové eficientní PF je nedominované řešení této 2-kriteriální úlohy ve smyslu VKP z kapitoly 7. V současné kapitole se budeme zabývat dalšími historicky staršími přístupy k výpočtu eficientního PF. První z nich (Sharpeův model) spočívá na myšlence převést kritérium rizika na omezující podmínku se zadanou horní hranicí a vzhledem k této omezující podmínce pak maximalizovat očekávaný výnos PF. Druhý přístup (Markowitzův model) je symetrický v tom smyslu, že převádí kritérium očekávaného výnosu na omezující podmínku se zadanou dolní hranicí a vzhledem k této omezující podmínce se pak minimalizuje riziko PF. 10.2Sharpeův model Jak jsme se výše zmínili, Sharpeův model spočívá na myšlence převést kritérium rizika na omezující podmínku se zadanou horní hranicí b, tato omezující podmínka se přidá ke Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 131 stávajícím a vzhledem k takto uvažovaným omezujícím podmínkám se pak maximalizuje očekávaný výnos PF složeného z M aktiv. Vznikne tak model matematického programování s jedinou lineární účelovou funkcí a omezujícími podmínkami obsahujícími jednu nelineární podmínku, tj.: RPF = ∑Ri Zi → max; (10-6) za podmínek b ZR ZZ ii jiij    (10-7) ∑Zi = 1, Zi ≥ 0, i = 1, 2, ..., M, (10-8) di ≤ Zi ≤ hi, i = 1, 2, ..., M. (10-9) Hodnota b v omezující podmínce (10-7) má význam velikosti rizika připadajícího na jednotku výnosu. Omezující podmínky (10-9) umožňují krátký prodej a také přítomnost bezrizikové investice je dovolena. Nechť například i = 1 je bezriziková investice (s nějakým výnosem R1 > 0), potom σi1 = 0, pro všechna i = 2,3,...,M, neboť je nekorelovaná se všemi rizikovými aktivy. Původně byl Sharpeův model uvažován bez možnosti krátkého prodeje a také bez přítomnosti bezrizikové investice. V našem pojetí se proto jedná o zobecněný Sharpeův model. 10.3Markowitzův model Jak jsme se výše zmínili, Markowitzův model je založen na myšlence převést kritérium očekávaného výnosu na omezující podmínku se zadanou dolní hranicí c, tuto omezující podmínku přidat ke stávajícím a vzhledem k takto uvažovaným omezujícím podmínkám pak minimalizovat riziko PF složené z M aktiv. Vznikne tak model matematického programování s jedinou (nelineární) účelovou funkcí a omezujícími podmínkami obsahujícími lineární podmínky: min;  jiijPF ZZ (10-10) za podmínek ∑Ri Zi ≥ c, (10-11) ∑Zi = 1, (10-12) di ≤ Zi ≤ hi, i = 1, 2, ..., M, (10-13) kde c, di, hi – zadané konstanty (úrovně). Hodnota c v omezující podmínce (10-11) má význam velikosti očekávaného výnosu. Omezující podmínky (10-13) umožňují krátký prodej, a také přítomnost bezrizikové investice je dovolena. Nechť například i = 1 je bezriziková investice (s výnosem R1 > 0), potom σi1 = 0, pro všechna i = 2,3,...,M, neboť je nekorelovaná se všemi rizikovými aktivy. Původně byl Markowitzův model uvažován bez možnosti krátkého prodeje a také bez přítomnosti bezrizikové investice. S možností krátkého prodeje se model také nazývá Blackův model PF, s možností bezrizikové investice se pak nazývá Tobinův model PF. V našem pojetí se tedy jedná o zobecněný Markowitzův model PF. Sharpeho, Markowitzův a FaktorovÝ model portfolia 132 10.4Faktorové modely Na myšlence efektivní diversifikace akciového portfolia jsou založeny faktorové (také indexové nebo indexní) modely, kterými se budeme zabývat v této části. Jde vlastně o proces přidání dalších cenných papírů do portfolia za účelem snížení celkového rizika portfolia postřednictvním snížení jedinečného rizika. Nesystematické (jedinečné) riziko vyplývá z jedinečnosti cenných papírů v portfoliu. Systematické (tržní) riziko je na druhou stranu nediverzifikovatelné. Mírou tohoto rizika je tzv. koeficient beta, o kterém bude dále řeč. Celý kapitálový trh je ovšem ne zcela upřesněný pojem. Z toho důvodu je "celý trh" často zastoupen indexem, který odráží chování a pohyby trhu. Na americkém kapitálovém trhu je to např. index Standard&Poor's, nebo známější index Dow Jones. Na pražské burze se používá index PX. V předchozí kapitole jsme riziko PF počítali z kovarianční matice zastoupených M aktiv. V případě velkého počtu aktiv to ale znamená počítat M2 kovariančních koeficientů. Např. pro M = 200 to znamená počítat 200.200/2 = 20 000 kovariančních koeficientů což může být technicky náročné. Jednoindexový (jednofaktorový) model PF tento problém obchází tak, že jednotlivá aktiva vztáhne k jedinému PF nazývanému faktor (nebo index) reprezentujícímu celý kapitálový trh (tzv. tržní PF). Tržní PF zahrnuje všechna aktiva daného kapitálového trhu s příslušnými vahami odpovídajícími jejich skutečnému poměrnému zastoupení na tomto trhu. Proto se v praxi jako tržní PF obvykle bere vhodný tržní (akciový) index. Výnos itého aktiva vyjádříme pomocí jednoduchého lineárního regresního modelu Xi = αi + βi F + ei, (10-14) kde Xi je výnos i-tého aktiva, αi , βi jsou odhadované parametry modelu, F je tržní (akciový) index. Poslední člen ei představuje náhodnou (reziduální) složku modelu, splňující následující předpoklady: (I) E(ei) = 0 pro každé i = 1, 2, ..., M, (II) Cov (ei, F) = 0 pro každé iM, (III) Cov (ei, ej) = 0 pro " i  j, i,jM. Z (I) a (II) :    FVar XFCov i i ,  (10-15) αi = E(Xi) - βi E(F), (10-16) Přitom koeficient αi se považuje za nesystematickou složku modelu (10-14), která zohledňuje specifika aktiva i, druhý člen βi E(F) lze považovat za systematickou složku modelu, která zohledňuje vliv globálního chování trhu. Dosazením do (10-15), (10-16) a s využitím (I) – (III) obdržíme RPF = ∑(αi + αi E(F)) Zi, (10-17)  2 PF = Var(F) ∑∑ βi βj Zi Zj + ∑ Var(ei)Zi 2 . (10-18) Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 133 Sharpeho jednoindexový model PF obdržíme dosazením do modelu (10-6) – (10-9) RPF = ∑ (αi + βi E(F)) Zi → MAX; za podmínek  2 PF = Var(F) ∑∑ βi βj Zi Zj + ∑ Var(ei)Zi 2 ≤ b, ∑ Zi = 1, di ≤ Zi ≤ hi, i = 1, 2, ..., M. Markowitzův jednoindexový model PF obdržíme dosazením do (10-10) – (10-13)  2 PF = Var(F) ∑∑ βi βj Zi Zj + ∑ Var(ei)Zi 2 → MIN; za podmínek ∑(αi + βi E(F)) Zi ≥ c, ∑ Zi = 1, di ≤ Zi ≤ hi, i = 1, 2, ..., M. Uplatněním operátoru “Var” na vztah (10-14): Xi = αi + βi F + ei , obdržíme: Var(Xi) = βi 2 Var(F) + Var(ei) , (10-19) kdy poslední vztah udává rozptyl výnosu Var(Xi), tzv. celkového rizika i-tého aktiva, jako součet systematického rizika i-tého aktiva βi 2 Var(F), kde βi je tzv. beta-koeficient i-tého aktiva a Var(F) je systematické riziko trhu, a nesystematického (individuálního – jedinečného) rizika i-tého aktiva Var(ei). 10.5Postup při výpočtu optimálního PF – jednoindexový „historický“ model Použití Excel-Řešitele pro akcie na PBCP Krok 1. Výběr vhodných aktiv v počtu M (např. akcií obchodovaných na PBCP) a vhodného indexu F (např. F = PX50). Krok 2. Volba N - časového intervalu trvání PF a délku T časových řad (cen cit vybraných aktiv), přitom N < T, ze statistických důvodů je vhodné, aby N + 30 < T . Krok 3. Výpočet relativních kapitálových výnosů Xi vybraných aktiv a relativních změn indexu F. Krok 4. Výpočet statistických charakteristik Xi a F : Ri=E(Xi), Var(Xi) , Var(F), Cov(Xi, F), βi ze vztahu (10-15) a Var(ei) z (10-19). Krok 5. Ověření platnosti předpokladů modelu (I) až (III) Krok 6. Zadání hodnot b, ( resp. c ), d, h a výpočet optimálního složení portfolia Zi opt pomocí Sharpeho ( resp. Markowitzova ) modelu s použitím Excel – Řešitel. Sharpeho, Markowitzův a FaktorovÝ model portfolia 134 ŘEŠENÁ ÚLOHA 10-1 Uvažujte PF složené ze 3 akcií a bezrizikového aktiva. V tabulce jsou uvedeny denní ceny akcií na PBCP včetně hodnot indexu PX za období od 3.9.07 do 7.12.07 (69 obchodovatelných dnů): Do PF je zařazeno bezrizikové aktivum ING Konto s 30-ti denním výnosem 0,0022. Vypočtěte 30-ti denní optimální PF podle: A) Sharpeho indexového modelu – maximalizujte výnos PF při zadaném riziku b = 0,05 (tj. 5%), přitom krátký prodej není povolen, tj. di = 0; B) Markowitzova indexového modelu – minimalizujte riziko PF při zadaném výnosu c = 0,10 (tj. 10%), přitom krátký prodej není povolen. Řešení: M = 4, N = 30, F = PX. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 135 Nejprve vypočítáme 30-ti denní výnosy podobně jako v Řešené úloze 9-1 (Krok1 až Krok3): Sharpeho, Markowitzův a FaktorovÝ model portfolia 136 Dále vypočítáme potřebné charakteristiky Ri=E(Xi), Var(Xi) , Var(F), Cov(Xi, F), βi ze vztahu (10-15) a Var(ei) z (10-19), tj. Krok4: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 137 A) Sharpeho model (řešení pomocí Excel – Řešitel): Optimální PF má složení: CETV – 1,07%, CEZ – 70,6%, KOBA- 0%, ING konto – 28,33%, přitom maximální výnos PF je 9,19%, riziko PF je 5%. B) Markowitzův model (řešení pomocí Excel – Řešitel): Sharpeho, Markowitzův a FaktorovÝ model portfolia 138 Optimální PF má složení: CETV – 1,23%, CEZ – 76,93%, KOBA- 0%, ING konto – 21,84%, přitom výnos PF je (zadaných) 10%, minimální riziko PF je 5,45%. SAMOSTATNÝ ÚKOL TÉMA: OPTIMÁLNÍ PORTFOLIO. 1. Vyberte 5 titulů akcií na PBCP, ze kterých budete sestavovat optimální portfolio. 2. Denní ceny těchto akcií včetně hodnot indexu PX nalezněte na internetu, např. na adrese: www.akcie.cz 3. Zvolte dobu trvání portfolia (od nákupu po prodej) 30 (obchodovatelných) dnů. 4. Nalezněte optimální portfolio pro zvolenou dobu trvání portfolia, tj. optimální podíly investované částky pro jednotlivé akcie a do portfolia zahrňte též možnost uložení v bance na konstantní úrok (vyberte banku, kam částku uložit a zjistěte aktuální úrok, který poskytuje; ten pak použijete jako hodnotu výnosu bezrizikového aktiva). 5. Optimální portfolio sestavte s použitím klasického stochastického přístupu na zá- kladě A) Markowitzova jednofaktorového (indexového) modelu pro hodnotu výnosu 5% (eventuálně jinou vhodnou hodnotu), Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 139 B) Sharpeho jednofaktorového modelu pro hodnotu variačního koeficientu 10% (eventuálně jinou vhodnou hodnotu). Jako index slouží PX. 6. Dosažené výsledky komentujte! OTÁZKY  Co je podstatou Sharpeho modelu optimalizace portfolia?  Co je podstatou Markowitzova modelu optimalizace portfolia?  Jaká je hlavní výhoda faktorových modelů optimalizace portfolia? SHRNUTÍ KAPITOLY V předchozí kapitole jsme uvedli model k nalezení eficientního portfolia pro investora se zadanou indiferenční přímkou. Eficientní PF představuje nedominované řešení této 2kriteriální úlohy ve smyslu VKMP z kapitoly 7. V této kapitole jsme se zabývali dalšími historicky staršími přístupy k výpočtu eficientního PF. První z nich (Sharpeův model) spočívá na myšlence převést kritérium rizika na omezující podmínku se zadanou horní přípustnou hranicí a vzhledem k této omezující podmínce pak maximalizovat očekávaný výnos PF. Druhý přístup (Markowitzův model) je symetrický v tom smyslu, že převádí kritérium očekávaného výnosu na omezující podmínku se zadanou dolní přípustnou hranicí a vzhledem k této omezující podmínce se pak minimalizuje riziko PF. V předchozí kapitole jste riziko PF počítali z kovarianční matice zastoupených M aktiv. V případě velkého počtu aktiv to ale znamená počítat M x M kovariančních koeficientů, což může být technický problém. Jednoindexový (jednofaktorový) model PF tento problém obchází tak, že jednotlivá aktiva vztáhne k jedinému PF nazývanému faktor (nebo index) reprezentujícímu celý kapitálový trh (tzv. tržní PF). Tržní PF zahrnuje všechna aktiva daného kapitálového trhu s příslušnými vahami odpovídajícími jejich skutečnému poměrnému zastoupení na tomto trhu. Proto se v praxi jako tržní PF obvykle bere vhodný tržní (akciový) index. Výnos každého aktiva se vyjádří pomocí jednoduchého regresního modelu. Postup při výpočtu optimálního PF (jednoindexový model „historická“ metoda) za použití Excel-Řešitele pro akcie na PBCP byl demonstrován na příkladu. Optimalizační metody na grafech 140 11 OPTIMALIZAČNÍ METODY NA GRAFECH RYCHLÝ NÁHLED KAPITOLY Tématem této kapitoly je úvod do vědní disciplíny nazývané „Teorie grafů“, která má mnoho společných částí s operačním výzkumem. I když by se mohlo zdát, že takové téma je příliš vzdálené běžnému životu, opak je pravdou. Optimalizační metody na grafech, speciálně v sítích, tzv. metody síťové analýzy, se běžně využívají například v navigačních systémech moderních automobilů, nebo při plánování činností složitých projektů. Nejprve se seznámíte se základní pojmy teorie grafů, poté se naučíte nalézt minimální kostru grafu, nejkratší cestu v síti, stanovit maximální tok v jednoduché síti. K řešení budete používat Excel. Problematika této a následující kapitoly je podrobněji rozpracována např. v publikaci [8] a také v [10], ze které tento text čerpá. CÍLE KAPITOLY Po prostudování této kapitoly budete umět:  Základy teorie grafů.  Nalézt nejkratší cestu v grafu a pochopit princip algoritmů používaných v GPS na- vigacích.  Vytvořit minimální kostru.  Zjistit maximální tok sítě. KLÍČOVÁ SLOVA KAPITOLY Graf, hrana, uzel, smyčka, multigraf, incidenční matice, částečný graf, podgraf, strom, kostra, cyklus, cesta, tok v síti. 11.1Základy teorie grafů Graf je objekt (obvykle si jej představujeme v rovině), který se skládá z uzlů (někdy se také říká vrcholů) a hran. Množinu uzlů budeme značit symbolem U, množinu hran H. Grafem G je pak dvojice množin: G = (U, H). Hrana vždy spojuje dva uzly a je buď neorientovaná, nebo orientovaná. Hrana také může spojovat uzel se sebou samým. Neorientovaná hrana je symetrické spojení dvou uzlů, zatímco u orientované hrany rozlišujeme její směr, který nám udává počáteční a koncový uzel. Neorientovaná hrana má oba možné směry. Neorientovaný graf má všechny hrany neorientované. Za orientovaný graf budeme považovat takový graf, který má alespoň jednu hranu orientovanou. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 141 Nejdříve se budeme zabývat neorientovaným grafem. Všimněte si, že jakákoliv hrana buď spojuje dva různé vrcholy, nebo tvoří „smyčku“ kolem jednoho vrcholu. Obě možnosti jsou zahrnuty v následujícím příkladu, kde jsou zavedeny nové pojmy. Příklad 1: Následující graf je takový, že U = {u1, u2, u3, u4, u5, u6} a H = {A, B, C, D}. Na následujícím obrázku jsou uzly označeny kroužky, hrany pak úsečkami, oblouky, eventuálně smyčkou. Všimněte si, že v předchozím příkladu hrany A a C spojují stejné dva uzly u1 a u2. Takovým hranám se říká paralelní (násobné) hrany. Hrana B začíná i končí ve stejném bodě. Obecně se hrany, které začínají i končí ve stejném bodě, nazývají smyčky. Pro zjednodušení je vhodné zavést definici grafu, který bude „očištěn“ od paralelních hran a smyček. Takovému zjednodušenému grafu se říká prostý graf. Obsahuje-li graf paralelní hrany nebo smyčky, nazývá se multigraf. Příklad 2: Následující prostý graf, který obsahuje 5 uzlů a 4 hrany, je daný tak, že U = {u1, u2, u3, u4, u5, u6} a H = {[u1, u2], [u1, u3], [u1, u5], [u5, u2]}. Kromě uvedeného zápisu a grafického znázornění lze každý prostý graf G zadat pomocí incidenční matice IG. Je to čtvercová matice s počtem řádků a sloupců rovných počtu uzlů grafu. Je-li [ui,uj] hranou grafu G = (U,H), potom prvek incidenční matice aij = 1, v opačném případě je aij = 0. Graf z předchozího příkladu má následující incidenční matici: Optimalizační metody na grafech 142                  00011 00000 00001 10001 10110 GI Všimněte si, že ve čtvrtém řádku a čtvrtém sloupci jsou samé nuly. Tento fakt znamená, že čtvrtý uzel není spojen hranou s žádným jiným uzlem, jak je vidět na obrázku grafu. Incidenční matice umožňuje snadné zakódování každého grafu do počítače. Orientovaná hrana je uspořádaná dvojice uzlů (ui,uj), kde ui je počáteční uzel a uj je koncový uzel, přitom je ui, uj  U. Používáme zde kulatých závorek, na rozdíl od neorientované hrany, kde jsme používali závorek hranatých. Označíme H jako množinu všech orientovaných hran grafu. Pak graf G = (U, H) nazveme orientovaným grafem. Znamená to, že hrany grafu mají zadaný nějaký směr. V obrázku se tento fakt vyznačí šipkami. Příklad 3: Následující orientovaný graf, který obsahuje 5 uzlů a 4 hrany, je zadaný tak, že U = {u1, u2, u3, u4, u5} a H = {(u1, u2), (u1, u3), (u1, u5), (u5, u2)}. Zadání tohoto příkladu je téměř stejné jako u příkladu předchozího. Všimněte si, v čem se obě zadání liší a v čem se pak liší výsledné grafy. Kam ale zařadit graf, který má některé hrany orientované a některé neorientované? Vždyť i silniční síť se skládá z cest obousměrných a cest jednosměrných. Neorientovaná hrana se dá „rozložit“ na dvě opačně orientované hrany, tedy takový graf můžeme považovat za graf orientovaný. Ubráním jedné hrany z grafu G vytvoříme graf G1, který je částečným grafem grafu G. Obecněji, částečný graf vznikne z původního grafu vynecháním některých hran. Samozřejmě můžeme vytvořit nový graf též vynecháním uzlů nebo jak uzlů, tak hran. Podgraf vznikne z původního grafu po vynechání některých uzlů a jim odpovídajících hran, částečným podgrafem rozumíme podgraf po vynechání některých jeho hran. Pro použití grafů (a zdaleka se nejedná jenom o operační analýzu) je výhodné mít ohodnoceny buď hrany grafu (jako příklad může sloužit kilometrická vzdálenost měst v silniční síti), nebo vrcholy grafu (například časové limity). Dostáváme tak hranově ohodnocený graf, nebo uzlově ohodnocený graf. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 143 Příklad 4: Následující graf G1, přestavující silniční síť, je hranově ohodnoceným grafem, graf G2 (počítačová síť) je uzlově ohodnoceným grafem. U prvního z nich označují ohodnocení vzdálenosti uzlů (měst) v km, u druhého jde o hodnoty propustnosti uzlů (serverů) v megabitech za sekundu. Graf G1: Graf G2: Typickým příkladem grafu je silniční síť – viz graf G1 v předešlém příkladu. Možná vás napadne, že jedním z úkolů by mohlo být nalezení nejkratší cesty mezi dvěma uzly zadaného grafu (např. mezi uzly u1 a u4). U grafu G1 se 4 uzly je to ovšem snadné, u grafu s desítkami (stovkami, tisíci atd.) hranami již to snadné být nemusí. K tomu bude zapotřebí zavést ještě další pojmy. Cesta v grafu je taková posloupnost orientovaných hran, v níž vždy následující hrana začíná v uzlu, v němž končí hrana předcházející. Pozor, u cesty musíte dbát na orientaci hran. V případě, že nás orientace hran nezajímá, nebo se jedná o neorientovaný graf, a chceme mít prostě propojení mezi dvěma body, pak hovoříme o řetězu. Řetěz v grafu je cesta bez ohledu na orientaci hran. To znamená, že každá cesta je zároveň řetěz. Uvědomte si však, že existují řetězy, které nejsou cestami. Příklad 5: V grafu G najděte cestu a řetěz mezi uzly u1 a u5. Optimalizační metody na grafech 144 Cestou A z uzlu u1 do uzlu u5 je pouze posloupnost hran: A = {(u1, u2), (u2, u5)}. Cestou B od uzlu u5 do uzlu u1 je jen posloupnost hran B ={(u5, u4), (u4, u1)}. Řetězy jsou 3 a tvoří je posloupnosti hran: C = {[u1, u2], [u2, u5]}, D = {[u1, u3], [u3, u5]} a E = {[u1, u4], [u4, u5]}, z nich pouze D není cesta. Cesta, která začíná i končí v tomtéž uzlu, se nazývá cyklus. V případě smyčky se jedná o degenerovaný cyklus. Cyklus je tedy speciální cesta, skládá se proto z orientovaných hran. U neorientovaného grafu nahradíme každou neorientovanou hranu dvojicí orientovaných hran s opačnou orientací. Cyklus v neorientovaném grafu (složeném z neorientovaných hran) je pak určen odpovídajícími orientovanými hranami. Příklad 6: V grafu G z předchozího příkladu najděte cyklus. V grafu G je jediný cyklus, tvoří ho posloupnost hran F = {(u1,u2), (u2,u5), (u5,u4), (u4,u1)}. Další pojmy, které musíme zavést, se týkají typů grafů. Souvislým grafem nazýváme takový graf, v němž mezi každou dvojicí uzlů existuje alespoň jeden řetěz, který je spojuje. Příklad 7: Následující graf není souvislým grafem. Dá se vytvořit podgraf a částečný graf, které by byly souvislým grafem? Graf G: Jako příklad podgrafu grafu G, který je souvislým grafem, může sloužit graf, který vznikne z grafu G vynecháním uzlů u6 a u7 a jim příslušné hrany. Částečný graf, který by byl souvislým grafem, utvořit nelze. Acyklickým grafem nazýváme graf, který neobsahuje žádný cyklus. Strom je neorientovaný souvislý acyklický graf. Strom je tedy speciálním případem acyklického grafu. Les se skládá z jednoho nebo několika stromů. Platí tedy, že souvislý les je strom. U lesu platí to, že jeho každé dva uzly lze spojit nejvýše jedním řetězem. Některé uzly mohou být takto nepropojitelné. U stromu lze tuto podmínku jemně pozměnit: každé dva uzly lze spojit právě jedním řetězem. Kdyby totiž propojení dvou uzlů nebylo možné, odporovalo by to Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 145 podmínce souvislosti stromu. Kdyby naopak bylo propojení možné dvěma různými cestami, pak by tyto cesty společně tvořily cyklus, což je rozpor s požadavkem na strom. Příklad 8: Zjistěte, kolik hran má strom se třemi uzly. Kolik hran má strom se čtyřmi uzly? Pokuste se takové stromy nakreslit. Pokud jste uvažovali správně, má váš první graf dvě neorientované hrany a druhý má neorientované hrany tři. Obecně platí tento fakt: každý strom s n uzly má (n-1) hran. Oba grafy, které jste načrtli, jsou stromem, lesem i acyklickým grafem. Máte-li o tom pochybnosti, znovu se podívejte na příslušné definice. Zkontrolujte, že to platí u následujícího grafu, který je lesem složeným ze 3 stromů. Každý strom má 7 uzlů, a tedy 6 hran: Úplný graf je takový neorientovaný graf, ve kterém pro každou dvojici uzlů existuje právě jedna neorientovaná hrana, která je spojuje. Jednoduše řečeno, je to graf spojení „každého uzlu s každým“. Rovinný (plochý) graf je takový graf, který lze znázornit v rovině tak, že se nekříží žádná dvojice hran. Příklad 9: Načrtněte úplný graf se třemi vrcholy, úplný graf se čtyřmi vrcholy a úplný graf s pěti vrcholy. Jsou tyto grafy rovinné? Kolik mají hran? Pokuste se odvodit obecný vztah pro počet hran úplného grafu o n vrcholech. Pakliže jste správně uvažovali, pak váš první graf má tři neorientované hrany a je to rovinný graf („trojúhelník“), druhý graf má hran 6 a i tento graf je rovinný („čtyřúhelník včetně úhlopříček, jednu z nich však lze vést „venkem“), naproti tomu třetí graf má hran 10 a není rovinným grafem („pětiúhelník včetně úhlopříček“). Indukcí odvodíte, že počet hran úplného grafu o n uzlech je roven počtu všech dvouprvkových kombinací všech uzlů, což se rovná číslu   2 1 2        nnn . 11.2Minimální kostra Kostra je částečný graf souvislého grafu, který je stromem. Je to tedy acyklický souvislý graf, který vznikl ze souvislého grafu vypuštěním některých hran. Minimální kostra hranově ohodnoceného grafu je kostra s minimálním součtem ohodnocení hran. Optimalizační metody na grafech 146 Algoritmus pro nalezení minimální kostry ohodnoceného grafu popíšeme pro obecnou situaci. Budeme přitom vycházet z úplného hranově ohodnoceného grafu s n vrcholy, kde kij je ohodnocení hrany mezi vrcholy ui a uj. Z předchozího odstavce víme, že kostra takového grafu má (n-1) hran. Algoritmus pro nalezení minimální kostry (Kruskalův algoritmus) Krok 1. Vybereme dvě hrany s minimálním ohodnocením kij a zařadíme je do výsledné kostry (pokud jde o graf orientovaný, vybereme pouze jedinou hranu). Krok 2. Ze zbývajících hran a vybereme další hranu s minimální hodnotou tak, aby s doposud vybranými hranami netvořila cyklus. Krok 3. Podle bodu 2. postupujeme až do vybrání (n – 1) hran, tj. do vytvoření kostry. Výsledná kostra má minimální součet ohodnocení. Příklad 10: Uvažujme následující síť pěti poboček banky, které mají být propojeny počítačovou sítí tak, aby propojení bylo co nejlevnější a aby byly všechny pobočky připojeny do sítě. Hodnoty hran vyjadřují ceny za propojení. Nalezněte nejlevnější propojení. Řešení: Víme, že kostru grafu budou tvořit všechny vrcholy a čtyři hrany. Nejlépe se nám bude kostra hledat, když hrany grafu seřadíme podle rostoucí hodnoty jejich ohodnocení: 1. k34 : 4 5. k13 : 10 09. k15 : 19 2. k23 : 5 6. k45 : 11 10. k25 : 20 3. k14 : 6 7. k12 : 14 4. k24 : 7 8. k35 : 17 Podle uvedeného algoritmu postupně vybereme tyto hrany: k34 : 4, k23 : 5, k14 : 6. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 147 Hranu s dalším nejnižším ohodnocením k24 : 7 nezvolíme, protože tvoří cyklus s předchozími vybranými hranami. Další a poslední vybranou hranou bude k45 : 11. Kostru grafu si zakreslete do obrázku v zadání. 11.3Nejkratší cesta v síti Síť je souvislý, orientovaný, prostý graf, v němž jsou hrany ohodnoceny nezápornými čísly a v němž existuje dvojice uzlů, z nichž jeden je vstupem do sítě (nevstupuje do něj žádná hrana) a druhý je výstupem ze sítě (nevystupuje z něj žádná hrana). Jako příklad může sloužit vodovodní síť, potrubní síť, telefonní síť, železniční nebo silniční síť. Příklad 11: Zdůvodněte, proč nejsou následující tři grafy sítěmi. a) b) c) Optimalizační metody na grafech 148 Řešení V příkladu a) grafu chybí výstupní uzel, neboť ani jeden uzel nesplňuje tu vlastnost, že z něj nevystupuje ani jedna hrana. V příkladu b) graf není souvislý, a tedy nemůže být sítí. V grafu c) chybí vstup do sítě. První algoritmus, kterým se budeme zabývat a který má využití v praxi, je algoritmus hledání nejkratší cesty v síti. Mějme tedy určitou síť, pro názornost uvažujme, že ohodnocení každé hrany představuje délku této hrany. Pojem „nejkratší cesta“ je jistě dostatečně ilustrativní, proto jenom pro upřesnění: délkou cesty rozumíme součet ohodnocení všech hran, které tuto cestu tvoří, a nejkratší cestou rozumíme tu, která má ze všech možných cest mezi vstupem a výstupem nejmenší délku. Přirozená je i poněkud obecnější formulace úlohy: nalezení nejkratší cesty mezi dvěma zvolenými uzly, které nemusí nutně být vstupem a výstupem sítě. Uvedené pojmy mají zřejmý smysl také pro neorientované sítě – namísto cesty uvažujeme řetězec. Příklad 12: Pro následující 3 sítě logickou úvahou nalezněte nejkratší cestu, vyznačte ji do grafu a zjistěte, jaká je její délka. a) Nejkratší cestou je cesta {h12, h23, h34} s délkou 11. b) Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 149 Nejkratší cestou je cesta {h12, h24} s délkou 12. ALGORITMUS PRO NALEZENÍ NEJKRATŠÍ CESTY (DANZIGŮV ALGORITMUS) Algoritmů pro hledání nejkratší cesty v síti existuje několik, my se budeme zabývat jen jedním z nich, je to tzv. Danzigův algoritmus. Přitom budeme předpokládat, že síť má uzly označeny přirozenými čísly od 1 do n. Náš algoritmus nalezne navíc nejkratší cesty z uzlu 1 do všech ostatních uzlů. Algoritmus nejprve popíšeme v krocích: Krok 1. Uzlu 1 přiřadíme hodnotu v1 = 0. Krok 2. Pro m  0 přiřadíme uzlu m hodnotu vm podle vztahu vm = min{vi + kij}, (11-1) Přitom se minimum hledá přes všechna i, pro něž je vi již určeno, a přes všechna j, pro něž vj není dosud určeno. Krok 3. Hodnota vm přiřazená uzlu m představuje délku nejkratší cesty z uzlu 1 do m a pro hrany (i,j), které ji tvoří, platí vztah vj = vi + kij. Krok 2 představuje posloupnost výpočtů hodnot vm pro všechna m  0. Nyní si na konkrétním příkladu ukážeme, jak se nalezení nejkratší cesty podle Danzigova algoritmu provádí v tabulce. Příklad 13: Uvažujte následující silniční síť. Vaším úkolem je nalézt nejkratší cestu mezi uzly 1 (vstupní uzel) a 9 (výstupní uzel). Optimalizační metody na grafech 150 Řešení: Vlastní výpočet je vhodné sestavovat do tabulky, která bude mít tolik sloupců, kolik má graf uzlů, v našem případě 9. V prvním řádku těchto sloupců budeme uvádět postupně vypočtené hodnoty proměnných vm, přičemž začneme hodnotou v1 = 0. Ve druhém řádku uvedeme postupně čísla uzlů, v dalších řádcích vždy dvojice čísel, z nichž první bude číslem uzlu, do něhož vstupuje hrana vystupující z uzlu uvedeného v záhlaví sloupce a druhé (v závorce) bude označovat ohodnocení této hrany. Těchto dvojic bude v každém sloupci uvedeno tolik, kolik hran z daného uzlu vystupuje k ostatním uzlům. Provedeme si tedy společně výpočet nejkratší cesty, výsledky zapisujte do připravené tabulky. Krok 1. Položte v1 = 0. Krok 2. Z uzlu 1 vedou hrany do 5, 6, 7, proto v prvním sloupci vyplníte dvojice 5(10), 6(19), 7(18). Z uzlu 2 vedou hrany do 3, 4, 6, 7, 8 a 9, tedy ve druhém sloupci postupně vyplníte 3(9), 4(18), 6(16), 7(17), 8(11) a 9(24). Obdobně vyplníte zbývající sloupce. Ze sloupců 5, 6 a 7 této tabulky vyškrtnete všechny dvojice začínající 1, neboť uzel 1 je vstupní a žádnou cestu, která by do uzlu 1 vstupovala neuvažujeme. Prozatím je stanoveno pouze v1, proto podle vztahu (*) stanovíte v5 = min{v1 + k1j} = 10 a v 1. sloupci označíte podtržením dvojici 5(10). Hodnotu 10 zapíšete do záhlaví 5. sloupce. Z tabulky vyškrtnete všechny dvojice začínající 5. Nyní již máte stanoveny hodnoty v1 a v5, použitím vztahu (11-1) vypočítáte v6 = min{ v1 + k1j, v5 + k5j} = 17. Hodnotu 17 zapíšete do záhlaví 6. sloupce. Z tabulky vyškrtnete všechny dvojice začínající 6. Dále již jsou stanoveny v1, v5 a v6, opětným použitím vztahu (*) vypočítáte v7 = min{ v1 + k1j, v5 + k5j, v6 + k6j } = 18, atd. Tímto způsobem postupujete tak dlouho, dokud nejsou vypočteny všechny hodnoty vm, tj. dokud není vyplněn 1. řádek tabulky a všechny dvojice jsou buď podtrženy, nebo přeškrtnuty, viz Tab. 11.1. Tabulka 11.1: Výpočet nejkratší cesty v grafu Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 151 Nejkratší cestu z uzlu 1 do uzlu 9 tvoří hrany spojující postupně uzly: 1, 5, 6, 2, 3 a 9. Délka této cesty je 54. Z tabulky lze rovněž vyčíst nejkratší cesty z uzlu 1 ke všem zbývajícím uzlům, včetně jejich délek. 11.4Maximální tok v síti Co může v síti téci? Ve vodovodní síti samozřejmě voda, v plynové potrubní síti zemní plyn, v telefonní nebo počítačové síti to budou elektrony tvořící informace atd. Tokem v síti se obecně rozumí funkce, která každé hraně hij dané sítě přiřadí nezáporné číslo xij, které se nazývá hodnota toku v hraně (i,j). Jako obvykle označíme symbolem kij ohodnocení hrany hij, které představuje kapacitu hrany neboli propustnost hrany. Uvědomte si, že hrana je propustná oběma směry. Podívejte se na následující obrázek 11.2, kde je znázorněna počítačová síť S = (U,H), kapacity hran představují jejich propustnosti v Mb/sekundu a jsou dány použitým technickým zařízením (např. kabely). Zajímá nás problém propustnosti této sítě, tedy kolik informací v Mb/sekundu posílaných z uzlu 1 do uzlu 4 daná síť schopná přenést. Kapacita hran je v obou směrech stejná, proto v našem problému můžeme zaměnit uzly 1 a 4, tj. vstupní za výstupní a obráceně. Obrázek 11.2: Počítačová síť Je zřejmé, že celkový tok T, který vystupuje z uzlu 1, bude do uzlu 4 vstupovat. Symbolicky budeme tento fakt zapisovat takto: x12 + x13 + x14 = x14 + x24 + x34 (11-2) V jednotlivých uzlech (mimo uzel vstupní a výstupní) nepřipouštíme ztráty toku, proto součet hodnot toho, co do uzlu vtéká se musí rovnat součtu hodnot toho, co z uzlu vytéká. Symbolicky vyjádřeno (nejdříve pro uzel 2, potom 3): x12 + x32 + x42 = x21 + x23 + x24 , x13 + x23 + x43 = x31 + x32 + x34 . (11-3) Optimalizační metody na grafech 152 Nakonec musí být splněna podmínka, že tok v žádné hraně nesmí překročit její kapacitu, přitom je kapacita v obou směrech stejná, tj. pro každou hranu platí kij = kji. Symbolicky vyjádřeno: 0 ≤ x12 ≤ 6, 0 ≤ x21 ≤ 6, 0 ≤ x13 ≤ 5, 0 ≤ x31 ≤ 5, 0 ≤ x14 ≤ 3, 0 ≤ x23 ≤ 1, 0 ≤ x32 ≤ 1, 0 ≤ x41 ≤ 3, 0 ≤ x24 ≤ 4, 0 ≤ x42 ≤ 4, 0 ≤ x34 ≤ 6, 0 ≤ x43 ≤ 6. (11-4) Nalezení maximálního toku T představuje maximalizaci T = x14 + x24 + x34 (11-5) za omezujících podmínek (11-3), (11-4) a (11-5). Toto je zřejmě úloha lineárního programování, kterou jsme se zabývali podrobně v předchozích kapitolách. Všimněte si, že poměrně jednoduchá úloha nalezení maximálního toku v síti z Obr. 11.2 má v příslušné formulaci úlohy LP celkem 10 proměnných xij, 3 omezující podmínky ve tvaru rovností a 10 omezujících podmínek ve tvaru nerovností (kromě obvyklých podmínek nezápornosti). ÚKOL K ZAMYŠLENÍ 11-1 Odůvodněte, proč je možné v předchozí úloze LP nahradit účelovou funkci (11-5) touto funkcí: T = x12 + x13 + x14 Vyřešte předchozí úlohu LP (1) – (4) pomocí Excel – Řešitel. Pro nalezení maximálního toku v síti si ukážeme jednoduchý a velice názorný algoritmus, který však je použitelný jen pro speciální sítě, tzv. jednoduché sítě. Síť se nazývá jednoduchá, jestliže je rovinná, tj. lze ji zakreslit v rovině tak, že se žádné dvě hrany nekříží a jestliže lze přidat do sítě další hranu spojující vstupní a výstupní uzel tak, že se nekříží s žádnou hranou. Obrázek 11.3: Síť, která není jednoduchá Na Obr. 11.3 vidíte příklad sítě, která je rovinná, avšak není jednoduchá, neboť je zřejmé, že vstupní uzel „1“ nelze spojit s výstupním uzlem „n“ hranou, která by se nekřížila s jinou hranou sítě. Pojem jednoduché sítě závisí nejen na tom, že je graf rovinný (plochý) grafu, ale také na konkrétním umístění vstupu a výstupu. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 153 ALGORITMUS „NEJSEVERNĚJŠÍ CESTY“ K NALEZENÍ MAXIMÁLNÍHO TOKU V JEDNODUCHÉ SÍTI Krok 1. Určete „nejsevernější“ (díváte-li se na graf jako na mapu) cestu v síti vedoucí od uzlu „1“ (vstup) do uzlu „n“ (výstup) – označte tuto cestu symbolem C1. Krok 2. Na této cestě C1 nalezněte hranu (případně více hran) s nejmenší kapacitou – označte ji hrs. Příslušná kapacita je krs. Potom k(C1) = krs. Krok 3. Odstraňte tuto hranu (případně více hran) s minimální kapacitou a u zbývajících hran cesty C1 snižte kapacitu o hodnotu k(C1). Získáte tak nový ohodnocený částečný graf. Krok 4. Kroky 1 až 3 opakujte tak dlouho, dokud mezi uzly „1“ a „n“ existuje cesta. Jakmile v Kroku 3 odstraníme hranu tak, že mezi těmito uzly již neexistuje žádná cesta, algoritmus ukončíte. Krok 5. Hodnota maximálního toku v síti je Tmax = k(C1) + k(C2) +… Nyní použijeme uvedený algoritmus na síť z Obr. 11.2, avšak narazíme hned na potíž: Zdá se, že naše síť není rovinná, neboť se hrany (1,4) a (2,3) vzájemně kříží. Naštěstí lze síť překreslit tak, jak je uvedeno na Obr. 11.4, přitom ke křížení hran nedojde a výsledná síť bude jednoduchou sítí s původní sítí zcela ekvivalentní. Obrázek 11.4: Ekvivalentní síť se sítí na Obr. 11.2 Postup podle algoritmu demonstruje posloupnost následujících podgrafů sítě z Obr. 11.4: Optimalizační metody na grafech 154 Maximální tok v síti je Tmax = k(C1) + k(C2) + k(C3) + k(C4) = 13. V jednotlivých hranách tento maximální tok realizují toky: x12 = 4, x21 = 0, x13 = 5, x31 = 0, x14 = 3, x41 = 0, x24 = 4, x42 = 0, x34 = 5, x43 = 0. Podle vztahu (11-5) je T = x14 + x24 + x34 = 3 + 4 + 6 = 13 = Tmax. Pokud jste vyřešili správně úlohu LP z výše zadaných úkolů s využitím Excelu, dospěli jste ke stejnému vý- sledku. Protože, jak jsme řekli, lze výše uvedený algoritmus použít jen v případě jednoduché sítě (těch je v praxi většina), zůstávají nám k řešení obecných sítí (těch, které nejsou jednoduché) pouze metody lineárního programování. Ty jsou však pro řešení naší úlohy trochu těžkopádné, a proto pánové L.R. Ford a D.L. Fulkerson navrhli v 60. letech minulého století jednodušší metodu. Zavedli k tomu pojem řez sítě. Definuje se následujícím způsobem: nechť U1 a U2 jsou dvě disjunktní podmnožiny množiny uzlů U grafu G takové, že U1  U2 = U, přitom U1 obsahuje vstup sítě a U2 obsahuje výstup sítě. Pak řezem rozumíme množinu hran grafu G, které mají počáteční uzel v U1 a koncový uzel v U2. Kapacitou řezu rozumíme součet ohodnocení hran kij, které tvoří řez. Přitom platí, že maximální hodnota toku v síti je rovna minimální kapacitě řezu sítě. Tento výsledek se v odborné literatuře nazývá teorém o maximálním toku a minimálním řezu, anglicky Max-Flow-Min-Cut theorem. Vraťte se k našemu příkladu z Obr. 11.2. Síť tu má 4 uzly, tedy U = {1, 2, 3, 4}. Položte například U1 = {1, 3}, U2 = {2, 4}. Příslušný řez obsahuje hrany (1, 2), (1, 4), (3, 2), (3, 4), kapacita řezu je 6+3+1+6 = 16. Jak ihned uvidíte, kapacita tohoto řezu není minimální. Zvolte nyní řez U1 = {1, 2, 3}, U2 = {4}. Tento řez obsahuje hrany (1, 4), (2, 4) a (3, 4), kapacita řezu je 3 + 4 + 6 = 13. Jak víte z dřívějška, Tmax = 13, tedy hodnota maximálního toku se rovná kapacitě uvedeného řezu, což je podle uvedeného Max-Flow-Min-Cut teorému minimální kapacita řezu v dané síti. Ford-Fulkersonův algoritmus zde nebudeme podrobně popisovat, řekneme jen, že vede k nalezení řezu s minimální kapacitou a tedy k hodnotě maximálního toku v síti. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 155 ŘEŠENÁ ÚLOHA 11-1 Pro následující síť určete maximální tok mezi vstupním a výstupním uzlem. Řešení: Jedná se o jednoduchou síť, proto použijte algoritmus Nejsevernější cesty. Nejprve vypusťte hranu (2, 4) a kapacitu k12 snižte o 8, tedy z 9 na 1, pak položte k(C1) = 8. Dále vypusťte hranu (2, 3) a zároveň (1, 2) – mají stejnou kapacitu 1, kapacitu k34 snížíte o 1 na 7 a položte k(C2) = 1. Konečně vypusťte obě zbývající hrany (1, 3) a (3, 4) se stejnou kapacitu 7 a položte k(C3) = 7. Algoritmus končí, neboť vstup 1 a výstup 4 nejsou již spojeny cestou. Maximální tok je Tmax= 8+1+7 = 16. OTÁZKY  Vyjmenujte alespoň 3 úlohy, které lze řešit pomocí grafů  Jakých hodnot mohou nabývat prvky incidenční matice?  Kolik hran má kostra? SHRNUTÍ KAPITOLY V této kapitole jste se zabývali základními pojmy a jednoduchými aplikacemi teorie grafů: optimalizačními úlohami tří typů. S aplikacemi teorie grafů je možno se setkat v běžném životě i při práci v ekonomické i technické oblasti. Všechny uvedené optimalizační úlohy lze formulovat, a tedy i řešit, jako úlohy lineárního programování. Ne vždy je to však výhodné (a možné) pro velký rozsah těchto úloh. Jednou z nejznámějších úloh teorie grafů je úloha nalezení minimální kostry v grafu. Řešení této úlohy umožňuje vytvořit propojení všech bodů v původním grafu s minimálním celkovým ohodnocením hran. Kruskalův algoritmus poskytuje velmi jednoduchou metodu řešení tohoto problému. Dalšími základními optimalizačními úlohami jsou úlohy v sítích – speciálních grafech se vstupem a výstupem. Nejdříve byla pomocí Danzigova algoritmu nalezena nejkratší cesty v síti. S touto úlohou se lze setkat v řadě různých aplikací, jako příklady lze uvést elektronický jízdní řád nebo minimalizaci cestovních nákladů. Poslední algoritmus, kterému se věnovala tato kapitola, byl algoritmus hledání maximálního toku v síti. Pro speciální tzv. jednoduchou síť byl uveden jednoduchý algoritmus Nejsevernější cesty. Pro obecnou síť je vhodný Ford- Optimalizační metody na grafech 156 Fulkersonův algoritmus založený na rovnosti maximálního toku a minimálního řezu v síti. Algoritmy pro hledání maximálního toku se využívají například v logistických problémech ke stanovení maximálního možného přísunu (toku) materiálu vzhledem ke kapacitě jednotlivých cest, nebo při plánování složitých počítačových sítí. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 157 12 ČASOVÁ ANALÝZA PROJEKTŮ (CPM, PERT, GERT) RYCHLÝ NÁHLED KAPITOLY Tématem této kapitoly je jedna z nejdůležitějších ekonomických aplikací teorie grafů – řízení projektů. Úlohy řízení projektů s využitím teorie grafů se objevily koncem 50. let. Konkrétně v roce 1957 uveřejnili pánové M. R. Walker, zaměstnanec chemického koncernu DuPont, a J. E. Kelley ze společnost RAND novou metodu, kterou nazvali Project Planning and Scheduling System (systém plánování a rozvrhování projektů). Později tato metoda dostala název Critical Path Method – CPM (metoda kritické cesty). Další metodou, se kterou se seznámíte je metoda PERT (podle anglického „Program Evaluation and Review Technique“). Obě metody vznikly v 50. letech 20. století jako reakce na požadavky z praxe. Zatímco CPM předpokládá deterministicky určené délky trvání jednotlivých činností, PERT pracuje s pravděpodobnostním odhadem trvání činností. Problematika této kapitoly je podrobněji rozpracována v [2], nebo též v publikaci [10], ze které tento text bohatě čerpá. CÍLE KAPITOLY Po prostudování této kapitoly budete umět:  Vytvořit síťový graf projektu.  Provést časovou analýzu projektu.  Nalézt kritickou cestu projektu. KLÍČOVÁ SLOVA KAPITOLY Projekt, činnost, kritická činnost, kritická cesta, síťový graf, CPM, PERT, GERT. 12.1Projekt Pojem projekt zde chápeme jako soubor činností prostorově a časově omezených, technologicky a organizačně souvisejících. Příkladů projektů můžete najít ve svém okolí celou řadu. Například rekonstrukce domu je složena z mnoha činností: výměny elektrické instalace, výměny rozvodů vody, tepla, opravy kanalizace, střechy, omítky apod. Z ekonomické praxe může být projektem například marketingová kampaň před zavedením nového výrobku na trh, která zahrnuje mnoho činností od marketingového výzkumu, též vytvoření reklamních materiálů, umístění reklamních materiálů v médiích, až po zaškolení produkto- Časová analýza projektů (CPM, PERT, GERT) 158 vých manažerů a prodavačů. Realizace projektu představuje realizaci všech činností tvořících projekt. Pro každou činnost musíme stanovit údaje, které ji charakterizují, například dobu trvání (danou nebo předpokládanou), požadavky na zajištění (finanční, materiálové nebo jiné), a její návaznost v rámci celého projektu. Poslední charakteristika znamená, že pořadí činností v projektu není náhodné. Například u rekonstrukce domu není asi rozumné nejprve obložit koupelnu novými kachličkami a až pak vysekávat staré vodovodní trubky (i když takové věci se bohužel někdy stávají). Složitější projekt musí být předem promyšleně naplánován. 12.2Konstrukce síťového grafu projektu Jednotlivé činnosti v projektu nelze provádět v libovolném pořadí, u činností se musí dbát na jejich věcnou a logickou (technologickou) návaznost na další činnosti v rámci celého projektu. Ukazuje se výhodné, aby matematickým modelem projektu byla síť – hranově ohodnocený orientovaný graf, kde jednotlivé hrany představují činnosti. Každá činnost je tedy vyjádřena orientovanou hranou mezi dvěma uzly, které představují začátek a konec dané činnosti. V závislosti na typu prováděné analýzy pak ohodnocení hran vyjadřuje dobu trvání činností, zdroje potřebné na realizaci činností, či náklady spojené s realizací činností. Se sítí – speciálním grafem – jste se setkali již v minulé kapitole. Připomeňme si definici sítě: Je to souvislý graf se vstupem a výstupem. Ve shodě s obvyklou terminologií z praxe síťové analýzy budeme pro speciální síť používat název síťový graf. Při konstrukci síťového grafu budeme požadovat tyto vlastnosti síťového grafu: 1. Síťový graf je acyklický: síťový graf neobsahuje žádný cyklus ani smyčku. 2. Síťový graf není multigrafem: souběžné činnosti je nutno znázornit pomocí tzv. fiktivních činností. Fiktivní činnost slouží k dodržení návaznosti mezi činnostmi, má vždy nulové ohodnocení (trvání fiktivní činnosti je 0) a nezasahuje tedy do výpočtu pro celkový projekt. 3. V síťovém grafu jediný uzel představuje okamžik zahájení projektu (žádné hrany do něj nevstupují, tj. žádné činnosti projektu mu nepředcházejí) a jediný uzel představuje událost ukončení projektu (žádné hrany z něj nevystupují, tj. žádné činnosti projektu po něm již nenásledují). 4. Index uzlu, ze kterého hrana vychází, je nižší než index uzlu, ve kterém hrana končí. Tato podmínka není nutná, ale ulehčí nám výpočty v síťovém grafu a současně zabezpečí, aby v síti nebyly žádné cykly. Příklad 1: Činnosti A a B jsou činnosti, které vycházejí ze vstupního uzlu projektu. Činnost C navazuje na činnost A i B. Na prvním obrázku vidíte nesprávné zobrazení této části projektu, neboť zde není splněna vlastnost 2. Druhý obrázek už znázorňuje správné vyjádření pomocí fiktivní činnosti X: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 159 ŘEŠENÁ ÚLOHA 12-1 Projekt uvedení na trh nového výrobku zahrnuje 12 činností označených A až L. Pro každou činnost jsou v následující tabulce uvedeny činnosti, které jí musí předcházet. Vaším úkolem bude sestrojit síťový graf tohoto projektu. Řešení: Podrobně popíšeme postup při konstrukci síťového grafu. V prvním kroku znázorněte všechny hrany, které nemají žádnou předchozí činnost. Z uzlu 1 vycházejí hrany A, B, C do uzlů s vyššími indexy: Ve druhém kroku zařaďte činnosti D, E, které následují po činnosti A, a činnosti F a G, které následují po činnosti C: Časová analýza projektů (CPM, PERT, GERT) 160 Jako další krok při konstrukci síťového grafu musíte vzít v úvahu fakt, že činnosti H a I následují po činnostech A, B a F. Bude tedy výhodné, když hrana F bude končit ve stejném uzlu jako hrana B. Od hrany A k hraně B musíte proto vést fiktivní hranu. Další změnu si žádá indexování uzlů, protože hrana F by měla vést od uzlu s nižším indexem do uzlu s vyšším indexem a uzel 7 by úplně zmizel, zatímco by zůstal uzel 8. Po přečíslovaní bude tedy hrana G končit v uzlu 7: Dalším krokem bude zakreslení činností H a I, které budou mít počátek v uzlu 4, protože jsou navazujícími činnostmi po činnostech A, B a F: Činnosti J a K následují po činnostech D a H. Bude tedy výhodné, aby činnosti D a H končily ve stejném uzlu: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 161 Teď už můžeme doplnit činnosti J a K, které začínají po činnostech D a H: V dalším kroku musíme vzít v úvahu, že poslední činnost, tj. L, začíná po činnostech G, I a J: V síťovém grafu máme nyní zakresleny všechny činnosti. Poslední podmínka, kterou by síťový graf měl ještě splňovat, je podmínka existence jediného vstupu a výstupu. Činnosti E, K a L musí tedy končit v jednom uzlu, který bude současně výstupem ze sítě. Pak provedeme odpovídající přečíslování uzlů: Tímto posledním krokem máme síťový graf hotov. Sami ještě jednou prověřte, že jsou všechny 4 požadované podmínky splněny. Časová analýza projektů (CPM, PERT, GERT) 162 12.3Metoda CPM Dvěma nejznámějšími metodami pro časovou analýzu projektu jsou Metoda kritické cesty – CPM (z anglického „Critical Path Method“) a metoda PERT (podle anglického „Program Evaluation and Review Technique“). Obě vznikly v 50. letech 20. století jako reakce na požadavky z praxe. Zatímco CPM předpokládá deterministicky určené délky trvání jednotlivých činností, PERT pracuje s pravděpodobnostním odhadem trvání činností. Algoritmus metody CPM se skládá ze čtyř fází výpočtů: I. fáze: Výpočet nejdříve možných začátků a konců činností. II. fáze: Výpočet nejpozději přípustných začátků a konců prováděných činností. III. fáze: Výpočet celkových časových rezerv. IV. fáze: Interpretace získaných výsledků. Pro algoritmus CPM budeme potřebovat označení činností, různých dob trvání, termínů a časových rezerv, konkrétně: (i,j) je činnost s počátkem v uzlu i a koncem v uzlu j, yij je ohodnocení - doba trvání činnosti (i,j), ti (0) je termín nejdříve možného zahájení činností vycházejících z uzlu i, ti (0) + yij je termín nejdříve možného ukončení činnosti (i,j), tj (1) je termín nejpozději přípustného ukončení činností končících v uzlu j, tj (1) - yij je termín nejpozději přípustného zahájení činnosti (i,j), Tp je plánovaná délka trvání celého projektu. V jednotlivých fázích výpočtu postupujeme takto: I. fáze: Postup “od začátku do konce”. Výpočet nejdříve možných termínů začátků a konců činností provádíme tak, že pro první uzel zadáme t1 (0) = 0 a pro další uzly hledáme  ijij ytt  )0()0( max , i = 1, 2, …, n. II. fáze: Postup “od konce k začátku”. Výpočet nejpozději přípustných začátků a konců prováděných činností provádíme tak, že pro poslední uzel zadáme tn (1) = Tp a pro další uzly hledáme  ijji ytt  )1()1( max , j = n, …, 2, 1. III. fáze: Celkové časové rezervy (CR) činností jsou časy, které je možno čerpat, aniž se prodlouží trvání celého projektu. Časové rezervy pro činnost (i,j) se dají vypočítat po- mocí: CRij = tj (1) – ti (0) – yij. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 163 Jestliže pro některou činnost k platí tk (1) = tk (0) , pak je pro tuto činnost časová rezerva nulová. Činnosti s nulovou celkovou rezervou se nazývají kritické činnosti a tvoří kritickou cestu mezi vstupem a výstupem sítě. Kritické činnosti rozhodují o délce trvání celého projektu. Pro zadanou plánovanou délku trvání celého projektu Tp platí, že když Tp ≥ tn (0) , pak na kritických hranách budou nezáporné rezervy, projekt je možno realizovat v plánovaném čase a projekt má časovou rezervu. Když Tp < tn (0) , pak projekt není možno realizovat v plánovaném čase bez zkrácení doby trvání některých činností. Výpočet termínů metodou CPM se provádí buď v tabulce, nebo v grafu. Pro výpočet v tabulce se do tabulky postupně vpisují položky: Pro výpočet v grafu se vepisují jednotlivé položky do značení uzlů (horní polovina, dolní levá a pravá čtvrtina) a pod a nad jednotlivé hrany grafu: Oba postupy budou demonstrovány na konkrétním příkladu. Nejprve samostatně sestavte síťový graf projektu a až potom se podívejte na výsledný graf projektu. Pokuste se pochopit každý krok algoritmu, v případě nejasnosti se vraťte, dokud vám postup nebude úplně jasný. ŘEŠENÁ ÚLOHA 12-2 Projekt zavedení nového druhu výrobku zahrnuje 12 činností (A až L). V následující tabulce jsou zadané předchozí činnosti a doba trvání ve dnech. Sestrojte síťový graf projektu a nalezněte kritickou cestu. Je možné ukončit projekt za jeden měsíc? Časová analýza projektů (CPM, PERT, GERT) 164 Řešení: Síťový graf, který jste sestavili podle pravidel minulého odstavce, by měl vypadat jako ten, který vidíte na obrázku: Nejprve si na tomto projektu vyzkoušíte výpočet prováděný v tabulce. Do tabulky zaznačíte všechno, co se dá vyčíst ze zadání a ze síťového grafu. Začnete vyplněním prvního sloupce: vepište tam všechny hrany (činnosti) ve tvaru (i,j), do druhého sloupce pak vyplňte všechna ohodnocení hran (délky činností) yij. Následující tabulka již je takto předvyplněna, ostatní volná políčka v tabulce již vyplníte samostatně podle následujícího postupu. Na konci řešení příkladu naleznete, jak má výsledná tabulka vypadat. V první fázi výpočtu „od začátku do konce“ položíme nejprve termín nejdříve možného zahájení ti (0) roven 0 pro činnosti, které vycházejí z uzlu 1, tedy pro činnosti (1,2), (1,3) a (1,4), protože těmto činnostem nepředchází žádná jiná činnost. Termín jejich nejdříve možného ukončení, který se zapisuje do sloupce ti (0) + yij, bude záviset pouze na délce těchto činností. Činnostem, které začínají v uzlu 2, předchází jen činnost (1,2), která končila v čase 5. Proto termínem nejdříve možného zahájení činností vycházejících z uzlu 2 je hodnota 5. Činnostem, které mají počátek v uzlu 3, předchází pouze činnost (1,3), která skončila v čase 6. To znamená, že pro činnosti s počátkem v uzlu 3 bude termínem nejdříve možného zahájení činností hodnota 6. Vyplňte odpovídající sloupec termínů nejdříve možného ukončení činností vycházejících z uzlu 2 a 3. Činnostem s počátkem v uzlu 4 předcházejí tři činnosti: činnost (1,4), která končí v čase 10, činnost (2,4), která končí v čase 6, a činnost (3,4), která končí v čase 8. Protože činnosti, které začínají v čase 4, mohou začít až po skončení všech předchozích činností, termínem nejdříve možného zahájení činností vycházejících z uzlu 4 bude ten poslední z nich, konkrétně je to čas 10. Činnostem s počátkem v bodě 5 předcházejí dvě činnosti: (2,5), která končí v čase 11, a (4,5), která končí v čase 18. Činnosti s počátkem v bodě 5 mohou proto začít až v čase 18. V posledním kroku první fáze algoritmu určíme termín nejdříve možného zahájení činnosti vycházející z uzlu 6 a termín jejího nejdříve možného ukončení. V uzlu 6 končí tři činnosti, Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 165 a to činnost (3,6) v čase 11, činnost (4,6) v čase 17 a (5,6) v čase 27. Maximum ze všech nejdříve možných ukončení činností končících v uzlu 6 je 27. Doplňte hodnoty do tabulky. Poslední vypočítané číslo, čas 39, je termín nejdříve možného ukončení celého projektu. Tím je ukončena první fáze výpočtu. Máme vyplněny první 4 sloupce tabulky: V tomto okamžiku také dokážete odpovědět na otázku ze zadání příkladu, zda je možné dokončit projekt za 1 měsíc. Odpověď zní NE – měsíc má maximálně 31 dní. Druhá fáze výpočtu metody CPM představuje „zpětný chod“ a vyplníte při ní další dva sloupce tabulky. Na rozdíl od první fáze budeme tabulku vyplňovat zdola nahoru, tedy „od konce k začátku“ projektu. Budeme předpokládat, že projekt má být dokončen v termínu nejdříve možného ukončení celého projektu, tj. v čase 39, který vyplníte do tabulky do řádků činností končících v uzlu 7 ve sloupci tj (1) - termín nejpozději přípustného ukončení činností končících v uzlu 7. Pak vypočítáte termín nejpozději přípustného zahájení činností končících v uzlu 7, tedy termíny, kdy nejpozději musí tyto činnosti začít, aby byl dodržen termín projektu. Termín nejpozději přípustného ukončení činností končících v uzlu 6 bude 27, protože žádná jiná činnost než činnost (6,7) v uzlu 6 nezačíná a její nejpozději přípustné zahájení je v čase 27. Termín nejpozději přípustného ukončení činností končících v uzlu 5 bude minimum z termínů nejpozději přípustného zahájení činností začínajících v uzlu 5. Činnosti začínající v uzlu 5 jsou dvě: činnost (5,7) musí začít nejpozději v čase 32 a činnost (5,6) musí začít nejpozději v čase 18. Minimem je čas 18. Doplňte příslušné hodnoty do tabulky. Termín nejpozději přípustného ukončení činností končících v uzlu 4 bude minimum z termínů nejpozději přípustného zahájení činností začínajících v uzlu 4. Činnosti začínající v uzlu 4 jsou opět dvě: (4,6) musí začít nejpozději v čase 20 a (4,5) nejpozději v čase 10. Minimem je čas 10. Analogicky vyplňte první dva řádky v tabulce: termín nejpozději přípustného ukončení činností končících v uzlu 3 bude minimum z termínů nejpozději přípustného zahájení činností začínajících v uzlu 3, tedy hodnota 8. Termín nejpozději přípustného ukončení činností končících v uzlu 2 bude minimum z termínů nejpozději přípustného zahájení činností začínajících v uzlu 2, tedy hodnota 9. Tím je ukončena druhá fáze výpočtů metodou CPM. Časová analýza projektů (CPM, PERT, GERT) 166 Ve třetí fázi se vypočítají časové rezervy pro jednotlivé činnosti a jako kritické činnosti se stanoví ty činnosti, které mají časovou rezervu nulovou. Časovou rezervu vypočítejte ze vztahu CRij = tj (1) – ti (0) – yij, který představuje rozdíl mezi nejpozději přípustným ukončením činnosti v uzlu j a nejdříve možným termínem ukončení činnosti (i,j). Výsledná tabulka by měla být identická s tou, kterou jste vyplňovali sami. Kritické činnosti jsou vyznačeny tučně. Kritickou cestu tvoří hrany s nulovou časovou rezervou, tedy kritickou cestu tvoří hrany (1,4), (4,5), (5,6) a (6,7). Kdyby se prodloužilo trvání kterékoliv z činností na kritické cestě, prodloužilo by se i trvání celého projektu. Druhý způsob použití metody CPM – s využitím síťového grafu – je názornější pro menší projekty, avšak pro velké projekty s několika stovkami činností je těžko realizovatelný. K jeho demonstraci použijeme stejný příklad projektu jako pro předchozí tabulkový způsob. V původním síťovém grafu, viz níže uvedený obrázek, vyplníte nejprve čísla uzlů (do horní poloviny uzlů), u jednotlivých hran (činností) uvedete jejich trvání. Začátek projektu v čase 0 vyplníte do levé dolní čtvrtiny uzlu 1. V celé první fázi výpočtů budete vyplňovat pouze levé dolní části jednotlivých uzlů. Vepisujte hodnoty podle návodu přímo do následujícího grafu. Do levé dolní čtvrtiny uzlů 2 a 3 vepište hodnoty termínů ukončení, protože do nich vstupují jenom hrany s počátkem v uzlu 1. Pro uzel 2 to bude termín nejdříve možného ukončení činnosti (1,2), který je roven součtu termínu nejdříve možného zahájení činnosti (1,2) a délky trvání činnosti (1,2): konkrétně je to 0 + 5 = 5. Pro uzel 3 to bude hodnota 6. Pokračujte vyplněním termínu nejdříve možného zahájení činností vycházejících z uzlu 4. Najdete jej jako maximum ze všech termínů nejdříve možných ukončení činností končících v uzlu 4, tedy jako maximum z termínů 6 pro hranu (2,4), 10 pro hranu (1,4) a 8 pro hranu (3,4). Do levé dolní čtvrtiny uzlu 4 doplníte tedy číslo 10. Analogicky postupujeme pro další uzly. Po ukončení první fáze algoritmu by měl být síťový graf projektu vyplněn následujícím způsobem: Ve druhé fázi budete vyplňovat pouze pravé dolní čtvrtiny uzlů. Tuto fázi začnete u posledního uzlu, kam dosadíte vypočítanou délku celého projektu, tedy hodnotu 39. Dále Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 167 vyplníte hodnotu nejpozději přípustného zahájení činnosti (6,7), která začíná v uzlu 6. Protože v uzlu 6 nezačíná již žádná jiná činnost, bude to 39 – 12 = 27. Analogicky postupujeme u všech dalších uzlů směrem k začátku. Po ukončení druhé fáze algoritmu by graf měl být vyplněn následujícím způsobem: V poslední fázi algoritmu vyplníme pod jednotlivé hrany jejich časové rezervy. V síťovém grafu tyto hodnoty obdržíte jako rozdíl hodnoty pravé dolní čtvrtiny u uzlu, do kterého hrana vstupuje a levé dolní čtvrtiny u uzlu, z něhož hrana vystupuje, mínus ohodnocení hrany. Hrany, jejichž časová rezerva je nulová, tvoří kritickou cestu. Kritická cesta je v grafu vyznačena tučně. Čtvrtá fáze metody CPM je z praktického hlediska ta nejdůležitější. Je jí interpretace získaných výsledků. Předchozí výpočty provede obvykle počítač, zatímco interpretovat výsledky musí člověk – uživatel. Úkolem je obvykle určit, které činnosti se mohou v čase částečně nebo úplně překrývat. Takové úvahy vyžadují v praxi kromě časového zhodnocení též analýzu zdrojů a nákladů. V dané situaci lze uvažovat časové rozvržení jednotlivých činností. K tomu nám poslouží následující tabulka, kde vymezení přípustné doby činnosti (mezi nejdříve možným začátkem a nejpozději přípustným koncem) je vyznačeno rámečkem a skutečná doba trvání projektu je vystínovaná. V první části tabulky jsou uvedeny kritické činnosti, tak, jak následují za sebou. S činnostmi, které nejsou kritické, lze „manipulovat“, tj. posouvat je v rámci uvedených časových mezí. Na jejich konkrétní časové zařazení bude mít vliv dostupnost zdrojů (lidských, finančních apod.), eventuálně náklady jejich realizace. V následujícím jednoduchém příkladu se pokuste vyřešit všechno samostatně a až pak se podívejte na postup. Pozor, tentokrát jsou činnosti definovány trochu jinak: pomocí činností následujících. Postup sestavení síťového grafu projektu je však stejný jako v případě zadání pomocí předcházejících činností. Časová analýza projektů (CPM, PERT, GERT) 168 ŘEŠENÁ ÚLOHA 12-3 Projekt uvedení nového výrobku na trh zahrnuje 4 činnosti (A - D). V následující tabulce jsou ke každé ze 4 činností uvedeny činnosti následující a doba trvání ve dnech. Sestrojte síťový graf projektu a nalezněte kritickou cestu. Je možné ukončit projekt za jeden týden? Řešení: Do následujícího rámečku sami načrtněte síťový graf projektu. Nápověda: síťový graf obsahuje jednu fiktivní hranu. Graf si zkontrolujte podle následující tabulky. Celou tabulku vyplňte a až ji budete mít kompletní, proveďte výpočet pomocí grafu: Pokud jste správně počítali, obsahuje vaše tabulka tyto hodnoty: Kritickou cestu tvoří činnosti A, X a C a projekt bude dokončen za 8 dní, což je doba delší než 1 týden. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 169 12.4Metoda PERT Metoda PERT je vlastně jen pravděpodobnostním rozšířením metody CPM. V praxi síťového plánování nejsme obvykle schopni stanovit délky trvání činností přesně, jak požaduje metoda CPM, ale jen přibližně. Je to způsobeno nedostatkem informací o prováděné činnosti a také působením mnoha nepředvídatelných vlivů na dobu jejich trvání. Pokud však pro každou činnost dokážeme určit, v jakých mezích, eventuálně s jakou pravděpodobností bude doba trvání činností, pak můžeme použít metodu PERT. Ta nám pak umožní stanovit termín ukončení projektu, resp. jeho další charakteristiky ovšem taktéž s určitou pravděpodobností, kterou však dokážeme vyčíslit. Ze základního kurzu statistiky víte, že doba trvání nějaké činnosti může být spojitá náhodná veličina, která je definována na číselném intervalu, který označíme . V metodě PERT se předpokládá, že doba trvání (každé) činnosti je náhodná veličina s tzv. β-rozdělením pravděpodobnosti na intervalu . Symbolem y označíme střední hodnotu a symbolem m označíme modus (tj. nejpravděpodobnější hodnotu). Graf funkce hustoty pravděpodobnosti β-rozdělení na intervalu je znázorněn na následujícím obrázku. Obrázek 12.1: Graf funkce hustoty β-rozdělení Levý krajní bod intervalu a nazveme optimistický odhad trvání činnosti (nejkratší doba trvání činnosti), pravý krajní bod intervalu b označíme jako pesimistický odhad trvání činnosti (nejdelší doba trvání činnosti), modus m budeme nazývat modální odhad trvání činnosti (nejpravděpodobnější doba trvání činnosti). Pro každou činnost pak můžeme vypočítat její střední hodnotu doby trvání y a směrodatnou odchylku s doby trvání, resp. rozptyl doby trvání s2 : Pro střední hodnotu ijy doby trvání činnosti (i,j), která má β-rozdělení na intervalu platí: 6 4 ijijij ij bma y   . Směrodatná odchylka sij doby trvání činnosti (i,j) je: Časová analýza projektů (CPM, PERT, GERT) 170 6 ijij ij ab s   . Rozptyl doby trvání činnosti (i,j) je potom: 2 2 6           ijij ij ab s . Při výpočtu kritické cesty metodou PERT namísto pevně zadaných hodnot délek (dob) trvání jednotlivých činností yij použijeme střední hodnoty dob trvání činností ijy a dále postupujeme stejně jako u metody CPM. Výsledkem výpočtů jsou jednotlivé hrany tvořící kritickou cestu. Namísto délky projektu vypočítáme pouze střední hodnotu doby trvání celého projektu, rozptyl doby trvání celého projektu, resp. směrodatnou odchylku doby trvání celého projektu: Střední hodnota trvání projektu se vypočítá jako součet středních hodnot dob trvání kritických činností, tj. činností na kritické cestě:  ..ckrit ijyT . Rozptyl doby trvání projektu se vypočítá jako součet rozptylů na kritických hranách:    .. 22 ckrit ijsTs . Směrodatná odchylka doby trvání projektu se vypočítá jako odmocnina ze součtu rozptylů na kritických hranách:    .. 2 ckrit ijsTs . Budete-li mít k dispozici všechny základní hodnoty, které vám metoda PERT poskytuje, budete schopni odpovědět na otázku, s jakou pravděpodobností bude projekt dokončen v plánovaném termínu. K tomu, abyste mohli určit požadovanou pravděpodobnost, potřebujete si připomenout některé pojmy ze statistiky. Dobu trvání projektu T lze přibližně odhadnout pomocí normálního rozdělení pravděpodobnosti se střední hodnotou T a směrodatnou odchylkou s(T). Tento odhad vyplývá z centrálního limitního teorému. Čím kritická cesta obsahuje více činností, tím je odhad přesnější. Můžeme proto napsat:   TsTNT , . Protože při ručním výpočtu můžeme využívat jen statistické tabulky, musíme všechny hodnoty tohoto normálního rozdělení převést na normované normální rozdělení, pro nějž jsou hodnoty distribuční funkce uvedeny v tabulkách nebo v Excelu. Jak známo, normované normální rozdělení má střední hodnotu 0 a směrodatnou odchylku 1, což zapisujeme N(0,1). Označme F(x) hodnotu distribuční funkce normovaného normálního rozdělení v bodě x. Potom pravděpodobnost toho, že projekt bude splněn v čase T, který nepřekročí čas plánovaný Tp, bude rovna: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 171               Ts TT FTTP p p . Celý výpočet pro analýzu PERT i s výpočtem pravděpodobnosti toho, že projekt bude ukončen včas a s hledáním v tabulkách si ukážeme na následujícím příkladu. ŘEŠENÁ ÚLOHA 12-4 Je dán projekt, který má následující síťový graf. Optimistické, pesimistické a modální odhady trvání činností jsou uvedeny v následující tabulce. Činnost E je fiktivní. Najděte kritickou cestu, vypočítejte střední hodnotu doby trvání projektu a směrodatnou odchylku doby trvání projektu. Určete pravděpodobnost toho, že celý projekt bude realizován v čase, který nepřekročí plánovaný termín ukončení projektu Tp = 42 dní. S jakou pravděpodobností bude projekt ukončen za 35 dní? Tabulka vstupních údajů: Řešení: Nejprve vypočtěte střední hodnoty dob trvání jednotlivých činností a rozptyl dob trvání jednotlivých činností s2 ij podle vztahů: Časová analýza projektů (CPM, PERT, GERT) 172 6 4 ijijij ij bma y   a 2 2 6           ijij ij ab s . Vypočítané údaje zapište do tabulky: Dalším krokem je výpočet kritické cesty metodou CPM, přičemž délky trvání činností jsou střední hodnoty dob trvání jednotlivých činností ijy . K výpočtu využijte prázdné sloupce tabulky. Znáte-li kritickou cestu, můžete vypočítat střední hodnotu doby trvání projektu, rozptyl a směrodatnou odchylku doby trvání projektu. Kritickou cestu pro zadaný projekt tvoří hrany (1,4), (4,5), (5,6) a (6,7), proto do výpočtu zahrnujeme jen hodnoty příslušné těmto hranám: Střední hodnota trvání projektu: 39129810 .   krit ijyT . Rozptyl doby trvání celého projektu:       . 22 36 148 36 4641664 krit ijsTs . Směrodatná odchylka doby trvání projektu:   03,2 36 148 . 2   krit ijsTs . Nakonec máme zjistit, s jakou pravděpodobností bude projekt ukončen za dobu kratší než 42 dnů a s jakou pravděpodobností za dobu kratší než 35 dnů. Po standardizaci, tj. transformaci na normované normální rozdělení, obdržíte hodnoty: Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 173      48,1 03,2 3942 42 FF Ts TT FTP p                   ,      97,1 03,2 3935 35                   FF Ts TT FTP p . V tabulce jsou uvedeny hodnoty F(z), které udávají pravděpodobnost toho, že náhodně vybrané číslo bude z intervalu <0, z>. Naším úkolem je najít pro hodnotu F(x) takovou pravděpodobnost, že náhodně vybrané číslo bude v intervalu (-∞, x). Pak hledanou hodnotu pravděpodobnosti dostaneme takto: pro kladné x:   )(5,0 xFTTP p  , pro záporné x:   )(5,0 xFTTP p  . Nejprve tedy naleznete v tabulce z Přílohy 1 (v závěru této kapitoly) hodnoty F(1,48) = 0,43056 a F(1,97) = 0,47558. V tabulce hledáme tak, že v levém sloupci najdeme číslo x zaokrouhlené na 1 desetinné místo, druhé desetinné místo najdeme podle příslušného sloupce tabulky. Hledané hodnoty pravděpodobnosti tedy jsou:   931,093056,043056,05,0)48,1(5,042  FTP ,   024,002442,047558,05,0)97,1(5,035  FTP . Projekt bude dokončen do doby 42 dnů s pravděpodobností 93,1% a do doby 35 dnů s pravděpodobností 2,4%. Hledané pravděpodobnosti můžeme obdržet také pomocí programu MS Excel. 12.5Metoda GERT V metodě GERT se pro každý uzel rozlišují tři typy vstupů a dva typy výstupů. Mezi vstupy patří: 1. konjunktivní vstup, při němž se uzel realizuje, tj. mohou se začít vykonávat z uzlu vystupující činnosti, až poté, co jsou ukončeny všechny do uzlu vstupující činnosti, 2. disjunktivní vstup, při němž se uzel realizuje, je-li ukončena právě jedna činnost do něj vstupující, 3. inkluzivní vstup, při němž se uzel realizuje, je-li ukončena alespoň jedna činnost do něj vstupující. Výstupy jsou následující: Časová analýza projektů (CPM, PERT, GERT) 174 1. deterministický výstup, kde se realizují všechny činnosti, které z uzlu vystupují, 2. stochastický výstup, kde se realizuje jen jedna z činností vystupující z uzlu s danou pravděpodobností. Kombinacemi 3 vstupů a 2 výstupů získáme 6 různých typů uzlů, graficky je označujeme podle následující tabulky. Přitom konjunktivně-deterministický typ uzlu je ten, který jsme doposud používali v metodě CPM a PERT, dalších 5 typů uzlů jsou nové typy, které rozšiřují možnosti síťové analýzy. Tabulka 12.1: Typy uzlů v síti GERT Příklad: Projekt je tvořen 6 činnostmi a 5 uzly, představuje systém kontroly kvality, viz Obr. 12.2. Při kontrole vyjádřené uzlem 1 vyhovující polotovary postupují na montážní linku (uzel 4). Opravitelné kusy jdou do opravny (uzel 2). Po opravě jde opět část opravených polotovarů na montážní linku, neopravitelné polotovary jdou do šrotu. Některé dobré výrobky se prodávají mimo podnik (uzel 3). Při dostatečně velkém počtu opakování tohoto procesu je možné vypočítat relativní četnost (tj. pravděpodobnost) polotovarů jdoucích do opravny, na montáž a do prodeje. Na síťovém grafu tyto pravděpodobnosti P1, P2 a P3 představují ohodnocení jednotlivých hran (1,2), (1,3) a (1,4). Analogicky pravděpodobnosti P4, P5 a P6 udávají relativní četnosti – pravděpodobnosti polotovarů, které jdou po opravě na prodej, na montážní linku, nebo do šrotu. Protože pro každý výrobek musí nastat právě jedna z uvedených situací po kontrole, resp. po opravě, platí P1+ P2 + P3 = 1 a P4+ P5 + P6 = 1. Obrázek 12.2: Síť GERT Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 175 Podrobněji se metodou GERT nebudeme v tomto textu zabývat, zájemce odkazujeme na odbornou literaturu. OTÁZKY  Může mít projekt více než jednu kritickou cestu?  K čemu se používá fiktivní hrana?  V čem se liší metoda PERT od metody CPM? SHRNUTÍ KAPITOLY Tato kapitola byla věnována řízení projektů – metodě kritické cesty CPM pro časovou analýzu projektů. Nejdříve byly upřesněny zásady konstrukce síťového grafu a použití fiktivní činnosti pro dodržení těchto zásad. Metoda CPM probíhá ve 4 fázích a lze ji realizovat dvěma postupy. V prvním z nich se výsledky propočtů zapisovaly do tabulky, ve druhém se k témuž využívalo grafického znázornění projektu pomocí speciálně upraveného síťového grafu. Oba postupy mají své přednosti i nedostatky. První postup je vhodnější pro rozsáhlejší projekty, je však méně názorný, druhý se naopak vyznačuje názorností, avšak pro rozsáhlé projekty je hůře realizovatelný. Poslední fáze metody CPM – interpretace výsledků je z praktického hlediska nejdůležitější. Výpočty provede zpravidla počítač, zatímco interpretovat výsledky musí sám uživatel. Úkolem je obvykle určit, které činnosti se mohou v čase částečně nebo úplně překrývat. Tato kapitola byla věnována řízení projektů, konkrétně metodám PERT a GERT. Větší pozornost byla věnována známější metodě PERT, která není nic jiného než stochastickou variantou metody CPM z předchozí kapitoly. Deterministické trvání činností z metody CPM je tu nahrazeno náhodnou veličinou s b-rozdělením pravděpodobnosti, která je plně určena třemi charakteristickými čísly: optimistickým, pesimistickým a modálním odhadem trvání činnosti. Z těchto hodnot se stanovily tyto charakteristiky: střední hodnota a rozptyl (směrodatná odchylka). Se středními hodnotami se zacházelo stejně jako v metodě CPM: stanovila se kritická cesta a střední hodnota trvání projektu, eventuálně charakteristiky variability (rozptyl, směrodatná odchylka). Dále se řešila úloha, s jakou pravděpodobností trvání projektu nepřekročí předem zadaný termín. Metodou GERT jsme v této kapitole zabývala pouze zevrubně, nejprve byly zavedeny základní pojmy: 6 typů uzlů podle toho, kdy mohou vystupující činnosti započít v návaznosti na ukončení vstupujících činností do uzlu. Bylo ukázáno, že jak metoda CPM tak PERT jsou pouze speciálními případy obecnější metody GERT. Na příkladu se demonstrovaly možnosti této metody a její odlišnosti od metod předchozích. Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 176 LITERATURA [1] CIPRA, T. Matematika cenných papírů. HZ Praha, 2000. ISBN 80-86009-35-1 [2] FIALA, P. Řízení projektů. Oeconomica, Praha 2002. ISBN 80-24-50448-0. [3] FIALA, P. Modely produkčních systémů. Oeconomica, Praha 2005. ISBN 80-24- 50985-7 . [4] FORRESTER, S. Operations research – e-book. World Technologies 2012, ISBN 97- 88-13232-561-1. [5] HUŠEK, R., MAŇAS, M. Matematické modely v ekonomii. Praha: SNTL, 1989. ISBN 80-03-00098-X. [6] JABLONSKÝ, J. Operační výzkum: Kvantitativní modely pro ekonomické rozhodování. Professional Publishing, Praha 2007. ISBN 80-86-94644-4. [7] JABLONSKÝ, J., DLOUHÝ, M. Modely hodnocení efektivnosti produkčních jednotek. Professional Publishing, Praha 2004. ISBN 80-86-41949-5. [8] KOLÁŘ, J., ŠTĚPÁNKOVÁ, O., CHYTIL, M. Logika, algebry a grafy. SNTL, Praha 1989. [9] KLEIN, M.W., Mathematical Methods for Economics (The Addison-Wesley Series in Economics). Addison-Wesley. Reading, Massachusetts, 1998. ISBN 0-201-85572-0. [10] RAMÍK, J., ČEMERKOVÁ, Š., MIELCOVÁ, E. Operační analýza pro ekonomy. Dist. studijní opora. Karviná, OPF SU, 2004, 80-7248-199-3. [11] ZMEŠKAL, Z. Finanční modely. Ekonomická fakulta VŠB-TU Ostrava, Ostrava 2002. ISBN 80-248-0182-5. http://www.economics.utoronto.ca/osborne/MathTutorial/index.html (klikni Contents... ) Jaroslav Ramík, Radomír Perzina - Ekonomicko-matematické metody 177 SHRNUTÍ STUDIJNÍ OPORY Tento text je určen studentům navazujícího magisterského stupně studia na Slezské univerzitě, Obchodně podnikatelské fakultě v Karviné. Jakožto studijní opora je určen především studentům kombinované formy studia, mohou jej však stejně dobře využíti studenti prezenční formy. Autor předpokládá, že čtenář – student má z předchozího studia znalosti ze základních kurzů matematiky a statistiky (kvantitativních metod) a též absolvoval základy z operačního výzkumu (operační analýzy). S těmito prerekvizitami je studium tohoto textu přirozeně jednodušší, neboť některá témata se částečně překrývají, avšak autor se snažil i o to, aby text byl samonosný, tedy aby mu bylo možno porozumět bez předchozího studia uvedených předmětů. K řešení příkladů uvnitř textu je systematicky využíván standardní program MS Excel. Mimo uvedenou teorii se proto čtenář naučil používat ExcelŘešitel k řešení konkrétních úloh. To mu umožnilo lépe pochopit podstatu matematického modelování a také ekonomickou interpretaci dosažených výsledků. 178 PŘEHLED DOSTUPNÝCH IKON Čas potřebný ke studiu Cíle kapitoly Klíčová slova Nezapomeňte na odpočinek Průvodce studiem Průvodce textem Rychlý náhled Shrnutí Tutoriály Definice K zapamatování Případová studie Řešená úloha Věta Kontrolní otázka Korespondenční úkol Odpovědi Otázky Samostatný úkol Další zdroje Pro zájemce Úkol k zamyšlení Pozn. Tuto část dokumentu nedoporučujeme upravovat, aby byla zachována správná funkčnost vložených maker. Tento poslední oddíl může být zamknut v MS Word 2010 prostřednictvím menu Revize/Omezit úpravy. Takto je rovněž omezena možnost měnit například styly v dokumentu. Pro jejich úpravu nebo přidávání či odebírání je opět nutné omezení úprav zrušit. Zámek není chráněn hes- lem. Název: Ekonomicko-matematické metody Autor: Prof. RNDr. Jaroslav Ramík, CSc., Ing. Radomír Perzina, Ph.D. Vydavatel: Slezská univerzita v Opavě Obchodně podnikatelská fakulta v Karviné Určeno: studentům SU OPF Karviná Počet stran: 179 Tato publikace neprošla jazykovou úpravou.